Читать онлайн «Методы линейного программирования 3»

Р. Габасов § Φ. Μ. Кириллова Χ < CQ О CL· g МЕТОДЫ о ЛИНЕЙНОГО с ПРОГРАММИРОВАНИЯ О ι X < <[ О Η ЧАСТЬ Р. Габасов, Φ. Μ. Кириллова МЕТОДЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Часть 3 СПЕЦИАЛЬНЫЕ ЗАДАЧИ МИНСК ИЗДАТЕЛЬСТВО БГУ им. В. И. ЛЕНИНА 1980 ББК 22. 1 Г12 УДК 519. 852 Методы линейного программирования. Ч. 3. Специальные задачи. Габасов Р. , Кириллова Ф. М. — Минск, Изд-во БГУ им. В. И. Ленина, 1980, 368 с. Заключительная часть книги посвящена применению методой, изложенных в ч. 1 и ч. 2, решению разнообразных экстремальных задач, распространенных в приложениях. Рассматриваются большие задачи линейного программирования с обоснованием ряда новых методов их решения; задачи оптимального управления с доказательством усиленного принципа максимума; экстремальные задачи на сетях в усложненной постановке; обобщенные задачи линейного программирования в условиях неопределенности; задачи квадратичного программирования с исследованием невыпуклого случая; дискретные задачи; специальные задачи нелинейного программирования с доказательством теорем сходимости алгоритмов. Основной целью третьей части является демонстрация возможностей методов линейного программирования (в сочетании с другими идеями) при решении сложных задач оптимизации. Ил. 3, табл. 5, библ. 31. Г 30502-°44 45-80 М317—80 1502000000 ББК 22. 1 517. 8 © Издательство БГУ им. В. И. Ленина, 1980 ОГЛАВЛЕНИЕ Предисловие 5 ВВЕДЕНИЕ 7 § 1. Адаптивный метод 7 § 2. Метод решения задач с обобщенными прямыми ограничениями 28 § 3. К построению методов нулевого порядка . 40 Глава I. БОЛЬШИЕ ЗАДАЧИ 42 § 1. Задача с большим числом переменных ... 42 § 2. Задача с большим числом основных ограничений 54 § 3. Использование специальной структуры опоры . 61 § 4. Метод Данцига — Вулфа декомпозиции ограничений прямой задачи 70 § 5. Декомпозиция двойственных ограничений методом Данцига — Вулфа 79 § 6. Декомпозиция опоры 83 § 7. Метод возмущений 96 § 8. Метод распределения 104 § 9. Итеративные методы 111 Глава II. ДИНАМИЧЕСКИЕ ЗАДАЧИ 115 § 1. Задача терминального управления . . . . 115 § 2. Оптимальные процессы с фазовыми ограничениями 121 § 3. Оптимальное управление при смешанных ограничениях 133 Глава III. СЕТЕВЫЕ ЗАДАЧИ 138 § 1. Экстремальные пути 139 § 2. Потоки, оптимальные по времени . . . . 151 § 3. Условная оптимизация потока 158 § 4. Сетевая распределительная задача ... . 169 § 5. Оптимальный мультипоток на обобщенной сети 186 § 6. Производственно-транспортная задача . . . 198 § 7. Оптимальный поток на сети с делителем . 203 § 8. Задача сетевого планирования 207 3 Глава IV. ОБОБЩЕННЫЕ ЗАДАЧИ 228 § 1. Билинейные задачи 229 § 2. Стохастические задачи 240 § 3. Параметрические задачи 251 § 4. Многоцелевые задачи 258 § 5. Игровые задачи ... 280 Глава V. КВАДРАТИЧНЫЕ ЗАДАЧИ 287 § 1. Прямой опорный метод 287 § 2. Опорный метод с оптимальной заменой элементов опоры 305 § 3. Адаптивный метод 316 § 4. Многоцелевые задачи 258 Глава VI. ДИСКРЕТНЫЕ ЗАДАЧИ 330 § 1. Метод ветвей и границ 331 § 2. Метод отсечения 335 § 3.