Волгоградский государственный технический университет;pdf

ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Глава 1
Декомпозиция Данцига — Вулфа . . . . . . . . . . . . . . . . . . . . . . . . .
§ 1. Метод декомпозиции Данцига — Вулфа . . . . . . . . . . . . . . . . .
§ 2. Двойственный подход в блочном программировании . . . . .
§ 3. Решение транспортной задачи методом разложения . . . . . .
§ 4. Декомпозиции для задачи с блочно"лестничной
структурой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 5. Решение задачи интервального программирования . . . . . . .
§ 6. Распространение принципа декомпозиции
Данцига — Вулфа на задачи
нелинейного программирования . . . . . . . . . . . . . . . . . . . . . .
Глава 2
Параметрическая декомпозиция . . . . . . . . . . . . . . . . . . . . . . . . .
§ 7. Метод Корнаи — Липтака . . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 8. Метод решения блочно"сепарабельных
нелинейных задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 9. О параметрической декомпозиции
задачи распределения ресурсов . . . . . . . . . . . . . . . . . . . . . . .
§ 10. Один метод параметрической декомпозиции
для задач линейного и сепарабельного
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 3
Декомпозиция на основе разделения переменных . . . . . . . . . .
§ 11. Метод релаксации ограничений
для задачи выпуклого программирования . . . . . . . . . . . . .
§ 12. Метод Риттера для блочной задачи со связывающими
переменными и связывающими ограничениями . . . . . . . .
§ 13. Метод расчленения Розена
для задач линейного программирования . . . . . . . . . . . . . . .
§ 14. Метод расчленения Розена
для нелинейного программирования . . . . . . . . . . . . . . . . . .
§ 15. Метод Бендерса для специальной задачи
математического программирования . . . . . . . . . . . . . . . .
7
7
16
23
28
33
41
49
49
53
64
70
74
74
77
83
90
100
ОГЛАВЛЕНИЕ
Глава 4
Декомпозиция на основе методов оптимизации . . . . . . . . . . . .
§ 16. Использование метода покомпонентного спуска
для решения задач математического
программирования и оптимального управления . . . . . . .
§ 17. Методы условного градиента и декомпозиция задач
математического программирования
и оптимального управления . . . . . . . . . . . . . . . . . . . . . . . .
§ 18. Использование штрафной константы в декомпозиции
задач математического программирования . . . . . . . . . . .
§ 19. Декомпозиция на основе модификаций
симплекс"метода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 5
Декомпозиция и агрегирование . . . . . . . . . . . . . . . . . . . . . . . . .
§ 20. Метод агрегирования для решения
системы линейных уравнений . . . . . . . . . . . . . . . . . . . . . .
§ 21. Метод агрегирования для блочной задачи
линейного программирования . . . . . . . . . . . . . . . . . . . . . .
§ 22. Декомпозиция и агрегирование на основе метода
возмущений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 23. Метод декомпозиции на основе агрегирования
переменных из разных блоков . . . . . . . . . . . . . . . . . . . . . .
Глава 6
Оптимизация бесконечномерных задач . . . . . . . . . . . . . . . . . .
§ 24. Основные понятия и утверждения . . . . . . . . . . . . . . . . . . .
§ 25. Обоснование численных методов решения
бесконечномерных задач программирования . . . . . . . . . .
§ 26. Численные методы решений . . . . . . . . . . . . . . . . . . . . . . .
§ 27. Сепарабельные бесконечномерные задачи
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 7
Дискретное математическое программирование . . . . . . . . . . .
§ 28. Геометрическая интерпретация методов
целочисленного линейного программирования . . . . . . . .
§ 29. Эквивалентные формы и теоретико"групповая
интерпретация задач дискретного
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 30. Алгоритм решения задачи целочисленного
линейного программирования . . . . . . . . . . . . . . . . . . . . . .
§ 31. Условие оптимальности и метод поиска
для дискретных задач оптимизации . . . . . . . . . . . . . . . . .
§ 32. Алгоритм для решения смешанно"целочисленных
задач линейного программирования . . . . . . . . . . . . . . . . .
§ 33. Решение большой задачи целочисленного линейного
программирования методом динамического
программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
377
114
114
118
122
127
141
141
147
156
173
185
185
199
205
222
233
236
243
249
257
265
275
378
В. В. КОЛБИН. СПЕЦИАЛЬНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Глава 8
Методы и модели программирования
в условиях неполной информации . . . . . . . . . . . . . . . . . . . . . .
§ 34. Модель Катаока и методы ее решения . . . . . . . . . . . . . . . .
§ 35. Метод решения Элмаграби . . . . . . . . . . . . . . . . . . . . . . . . .
§ 36. Квазиградиентные методы . . . . . . . . . . . . . . . . . . . . . . . . .
§ 37. Двухэтапная задача Данцига — Маданского . . . . . . . . . .
Глава 9
Задачи оптимизации на полных векторных решетках . . . . . .
§ 38. Бинарные отношения на векторных решетках . . . . . . . . .
§ 39. Семейство функций Ф(Л) . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 40. Бинарные отношения на ПВР и ОФПI . . . . . . . . . . . . . . . .
§ 41. Задачи ОМП и МППШ в условиях ПВР . . . . . . . . . . . . . .
§ 42. Свойства задач ОМП и МППШ на ВПР . . . . . . . . . . . . . . .
§ 43. Задачи бинарной оптимизации на ПВР . . . . . . . . . . . . . . .
§ 44. Задача математического программирования
на ПВР (МППВР) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
§ 45. Свойства задач МППВР и задач ПП . . . . . . . . . . . . . . . . .
§ 46. Виды задач на ПВР . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Приложения
Приложение 1
Определения и свойства бинарных отношений . . . . . . . . . . . . .
Приложение 2
Основные определения из теории векторных решеток . . . . . . .
Приложение 3
Задачи программирования на ПВР . . . . . . . . . . . . . . . . . . . . . .
Приложение 4
Виды и свойства бинарных отношений . . . . . . . . . . . . . . . . . . .
281
281
287
297
303
313
316
319
327
332
337
341
345
350
353
357
360
364
365
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
ПРЕДИСЛОВИЕ
Практические задачи прикладной математики облада
ют рядом особенностей, среди которых — большая раз
мерность (бесконечномерность), дискретность, стохастич
ность условий и др.
В работе представлены методы декомпозиции Данци
га — Вулфа, методы параметрической декомпозиции и
методы декомпозиции на основе разделения переменных.
Работа содержит обоснование и подробное описание мето
да Корнаи — Липтака, метода решения блочносепара
бельных нелинейных задач, методы параметрической де
композиции задач распределения ресурсов и методов па
раметрической декомпозиции линейного и сепарабельного
программирования.
В работе рассматривается метод релаксации ограниче
ний для задач выпуклого программирования, метод Рит
тера для блочной задачи со связывающими переменными
и связывающими ограничениями, метод расчленения Ро
зена для задач линейного и нелинейного программирова
ния, метод Бендерса для специальной задачи математиче
ского программирования. Работа включает обоснование
и описание декомпозиции на основе методов оптимизации
и методов декомпозиции и агрегирования.
Показано использование метода покомпонентного спус
ка для решения задач математического программирова
ния и оптимального управления, показано использование
штрафной константы в декомпозиции задач математиче
ского программирования, приведена декомпозиция на
6
В. В. КОЛБИН. СПЕЦИАЛЬНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
основе модификации симплекс#метода. Рассмотрены ме#
тоды декомпозиции и агрегирования на основе метода воз#
мущений и метод декомпозиции на основе агрегирования
переменных из разных блоков.
Бесконечномерное программирование рассматривает#
ся как раздел, обобщающий теорию детерминированного
программирования и теорию выпуклой двойственности.
Значительное внимание уделено описанию численных
методов решения бесконечномерных задач программиро#
вания, в том числе и сепарабельных.
Приведены различные подходы к решению задач дис#
кретного программирования. Наряду с теорией линейно#
го программирования для решения целочисленных задач
применяется динамическое программирование, комбина#
торные методы и результаты теории графов, развиваются
методы решения, которые опираются на теоретико#груп#
повую структуру целочисленных задач. Даются описания
и операционные блок#схемы алгоритмов решения дискрет#
ных и смешанно#целочисленных задач линейного програм#
мирования, в том числе и задач большой размерности.
Описаны методы оптимизации задач стохастического
программирования. Приводится модель Катока и методы
ее решения, метод решения Элмаграби, квазиградиентные
методы оптимизации двухэтапной задачи Данцига — Ма#
данского.
Оптимизация на полных векторных решетках рассмат#
ривается как раздел, обобщающий теорию и методы опти#
мизации задач большой размерности и бесконечномерных
задач программирования.
В учебном пособии представлены приложения, позво#
ляющие осваивать материал, а список рекомендованной
литературы в достаточной степени отражает рассматри#
ваемую проблематику и доступен обучающимся.
Учебное пособие предназначено для обучения бакалав#
ров, студентов#специалистов, магистров и аспирантов в об#
ластях экономической кибернетики, прикладной матема#
тики и информатики.
ГЛАВА 1
ДЕКОМПОЗИЦИЯ
ДАНЦИГА — ВУЛФА
§ 1.
МЕТОД ДЕКОМПОЗИЦИИ
ДАНЦИГА — ВУЛФА
Пункт 1.1. Рассмотрим задачу линейного программи
рования (ЛП), матрица ограничений которой имеет блоч
нодиагональную структуру со связующими строками вида:
1 A1
3B
3 1
A 5 3 111
3 111
3
63 111
A2
111
B2
111
111
111 A 1 2
111 111 4
4
111 111 4 2
111 111 4
4
111 B 1 74
где p ³ 1.
Матрица любой задачи ЛП может быть приведена к
такому виду, при p = 1, в результате соответствующего
разбиения ограничений на два подмножества.
Запишем задачу ЛП в виде:
минимизировать L = cx
(1.1)
A1x = b1 (m1 ограничений);
(1.2)
A2x = b2 (m2 ограничений),
(1.3)
при условиях
где c = (c1, c2, ..., cn) — nмерный вектор; b1 — m1 мерный
вектор; b2 — m2мерный вектор; A1 — (m1´n)мерная мат
рица; A2 — (m2´n)мерная матрица; x — nмерный вектор.
Предположим, что множество, определяемое условия
ми (1.2)–(1.3), ограничено (ниже будет показано, что это
предположение не является обязательным).
8
В. В. КОЛБИН. СПЕЦИАЛЬНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Обозначим
S = {x|A2x = b2, x ³ 0}.
Приведем теоремы, на которых, вместе с методом ге'
нерации столбцов, основан принцип разложения Данци'
га — Вулфа.
Теорема 1.1 [10]. Пусть X = {x|Ax = b, x ³ 0} — непустое
ограниченное множество и 21 11 1 12 3 3 — его граничные точ'
ки. Тогда любой элемент x Î X может быть представлен в
виде:
1
3 1 3 42 32 1
42 2 01 2 1 11 11
2 11
1
3 42 1 12
2 11
Теорема 1.2 [10]. Пусть X = {x|Ax = b, x ³ 0} — непустое
множество. Точка x Î X тогда и только тогда, когда она
может быть представлена как сумма выпуклой комбина'
ции граничных точек и линейной комбинации с неотри'
цательными коэффициентами крайних лучей однородных
решений множества X, т. е.
2 1 4 31 21 1
1
где
2 1 4 31 21 1 11
1
31 3 01
111 21 —граничная точка X;
21 3 4
1
501 2 —луч множества X.
Пусть x1, x2, ..., xN — крайние точки множества S.
Тогда по теореме 1.1 любой элемент S может быть пред'
ставлен в виде:
1
3 1 2 42 32 1
(1.4)
где
2 11
1
3 32 1 11
2 11
32 2 01 2 1 11 42
Подставив (1.4) в (1.1), (1.2) получим
1
3 1 2 1452 262 3
2 11
1
2 1A152 262 1 714
2 11
ГЛАВА 1. ДЕКОМПОЗИЦИЯ ДАНЦИГА
— ВУЛФА
9
Обозначим
pi = A1xi;
(1.5)
i
fi = cx .
(1.6)
Исходную задачу ЛП перепишем в виде:
1
минимизировать 3 1 2 42 52 1
(1.7)
2 11
при условиях
1
2 32 42 1 511
(1.8)
2 11
1
2 32 1 11
(1.9)
21 1 01 1 2 11 32
(1.10)
2 11
Задача (1.7)–(1.10) называется координирующей. Она
имеет (m1 + 1) строк по сравнению с (m1 + m2) строками
исходной задачи и большое число столбцов. Чтобы не хра?
нить в памяти машины все эти столбцы, их получают по
мере необходимости, используя для этих целей метод ге?
нерации столбцов. Для краткости назовем задачу (1.7)–
(1.10) — z?задачей, а исходную — X?задачей.
Пункт 1.2. Рассмотрим схему решения z?задачи.
Предположим известными векторы базиса некоторо?
го опорного плана z?задачи. Для каждого i вычислим ха?
рактеристические разности
12 2
31 4 31 5 6 7 1 8 1
91
где L — вектор двойственных переменных.
Представим L в виде L = (L1, L0), где L1 соответствует
ограничениям (1.8), а L0 — ограничению (1.9).
Используя формулы (1.5), (1.6) запишем
Di = (c – L1A1)xi – L0.
(1.11)
В соответствии с процедурой симплекс?метода для оп?
ределения переменной, например, zS, вводимой в базис,
надо найти
123 11 2 1 S 2 42 3 41A1 56
(1.12)
1
10
В. В. КОЛБИН. СПЕЦИАЛЬНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
Так как оптимальное решение задачи ЛП, множество
ограничений которой является ограниченным, достигается в крайней точке этого множества, выполнение операции (1.12) эквивалентно решению задачи вида:
минимизировать LL(x) = (c – L1A1)x
(1.13)
при ограничениях
A2x = b2, x ³ 0.
(1.14)
Назовем задачу (1.13)–(1.14) XL-задачей.
Вычисление решения xS этой задачи позволяет найти
столбец, который следует ввести в базис z-задачи:
1A 1S 2
2S 3 4 1 5 1
6 1 7
(1.15)
Соответствующий коэффициент в целевой функции
равен
fS = cxS.
(1.16)
Такой подход особенно эффективен, если число независимых диагональных блоков больше единицы, т. е. если
исходная задача может быть представлена в виде:
минимизировать L = c1x1 + c2x2 + ... + cpxp (1.17)
при ограничениях
A121
B121
1 A 2 22
1 111 1 A 1 2 1
B2 22
2 30
2 31
2 32 2
(1.18)
111
B 1 21
21 1 01 1 2 11 32
2
31
(1.19)
Обозначим St = {x|Btx = bt, x ³ 0}, 1 1 11 22 По теореме 1.1
п. 1.1 любой элемент St может быть представлен в виде
21
4 112 1 2 53112 43112 3
3 11
(1.20)
ГЛАВА 1. ДЕКОМПОЗИЦИЯ ДАНЦИГА
— ВУЛФА
11
21
2 43112 1 13
(1.21)
3 11
где Nt — число крайних точек множества St.
Используя (1.20), (1.21) и рассуждения п. 1.1, запи/
шем z/задачу к задаче (1.17)–(1.19):
2 31
33 5411264112 2 345
(1.22)
111 4 11
при условиях
2 31
22 2411254112 1 60 3
(1.23)
1 11 4 11
21
2 43112 1 13
1 1 13 54
(1.24)
3 11
32112 1 03 2 2 13 43 1 2 13 53
(1.25)
32112 1 41 52112 3
(1.26)
32112 1 A 142112 3
(1.27)
где
Если числа 321112 являются решением z/задачи, то век/
торы
21
431112 2 3 5311243112
3 21
составляют оптимальный план
x*(t) = (x*(1), x*(2), ..., x*(p))
исходной задачи.
XL/задачи, связанные с каждым шагом решения z/за/
дачи распадаются на 1 12 1 12 13 X11 /задач, которые имеют
вид
(1.28)
21112 2 131 3 11A 1 24 112 4 345
при ограничениях
Btx(t) = bt, x(t) ³ 0.
(1.29)