Предлагаемая вниманию читателя книга Дж. Хедли «Нелинейное и динамическое программирование» имеет целью познакомить неискушенного в математике читателя с задачами, решение которых сводится к отысканию наибольшего или наименьшего значения некоторой функции, зависящей, как правило, от большого числа переменных. Такие задачи возникают в самых разнообразных областях человеческой деятельности Я в первую очередь — это и обусловило повышенный интерес к ним — в практике планирования и организации производства.
• Имея в виду указанный выше круг читателей, автор не стремится углубляться в дебри теоретических исследований. Его интересует, во-первых, математическое описание различных ситуаций, типичных для оптимального планирования, и, во-вторых, численное решение возникающих при этом математических задач. Надо сказать, что эти стороны вопроса совершенно недо-.статочно освещены в советской литературе. Поэтому столь подробное их изложение, которое мы находим в книге Дж. Хедли, •Следует расценивать как явление весьма положительное. , ; Все это дает основания надеяться, что книга окажется полезной для обширного круга специалистов, так или иначе связанных с оптимальным планированием: от сотрудников научных учреждений до практических работников предприятий и плано-*вых органов, занимающихся организацией и планированием .Производства.
Книга не обращена непосредственно к математикам, но те *э них, кто работает по реализации на ЭВМ задач математиче-йкой экономики или им подобных, также прочтут ее с пользой яля себя.
При переводе мы сочли нужным сделать некоторые, впрочем совсем небольшие, сокращения. В ряде случаев оказались необходимыми и другие отступления от текста, главным образом уточнения отдельных формулировок. Указанные изменения в оригинале ввиду их незначительности, как правило, не оговариваются.
Список литературы дополнен важнейшими советскими изданиями, имеющими прямое отношение к затронутым в книге вопросам.
Главы 1, 10, 11 переведены А. Б. Горстко, главы 2, 8 — Ю. И. Волковым, главы 3, 4, 6. 7 — А. А. Капланом, главы 5, 9 — Э.О.Рапопортом.
Г. П. Акилов
ПРЕДИСЛОВИЕ
Эта книга задумана как продолжение книги автора «Линей-Гное программирование» и посвящена изучению теоретических и вычислительных аспектов нелинейного программирования.
Первая глава посвящена обсуждению тех трудностей, ко-'\ торые возникают при переходе от линейных задач к нелинейным. Во второй главе делается попытка дать необходимые для ^дальнейшего чтения сведения по математике, а также вводятся 'принятые обозначения. Благодаря включению этой главы на-•стоящую книгу можно читать независимо от книг автора «Ли-йейное программирование» и «Линейная алгебра».
Глава 3 содержит описание классических методов оптимиза-"ции, основанных на использовании дифференциального исчисле-щ- ния. Особенно подробно обсуждается метод множителей Ла-гранжа. Здесь же определяются основные свойства выпуклых и вогнутых функций, которые используются в дальнейшем. В этой -.главе не делается попытки изучить вариационное исчисление, taK как для этого понадобилось бы слишком много места. О нем «Лишь коротко упоминается в главах, посвященных динамиче-екому программированию.
В гл. 4 изучаются приближенные методы для отыскания ло-альных или глобальных экстремумов в задачах нелинейного программирования.
Пятая глава посвящена задачам стохастического программирования, а шестая — теории Куна—Таккера.
Задачи квадратичного и целочисленного программирования ^обсуждаются соответственно в седьмой и восьмой главах.
Глава 9 посвящена градиентным методам решения нелиней-?,,аых задач, а две последние главы — динамическому программи-" рованию.
Проблемы нелинейного программирования гораздо шире и .•разнообразнее, чем проблемы линейного программирования. Отчасти это и послужило причиной того, что отдельные главы ногда содержат описания никак не связанных между собой :етодов решения специальных типов задач. Другая причина (Стоит в том, что в настоящее время не существует теории,
объединяющей все относящееся к нелинейному программированию, да и вычислительные алгоритмы разработаны лишь для очень специальных классов задач. Схемы этих алгоритмов весьма существенно зависят от особенностей решаемых задач.
Для решения рассматриваемых в книге задач было предложено множество вычислительных методов. Так как не представлялось возможным изложить все методы, автор был вынужден отобрать лишь наиболее интересные. Конечно, в ряде случаев этот выбор был довольно субъективным, так как не имелось данных, позволяющих сравнить эффективность различных вычислительных схем. Некоторые интересные методы могли оказаться неупомянутыми просто потому, что автор не знал об их существовании.
Нелинейное программирование в настоящее время бурно развивается. При выборе материала для этой книги автор старался включать то, что более или менее уже выдержало испытание временем. Однако -вполне возможно, что в недалеком будущем м-ногие из обсуждаемых алгоритмов будут вытеснены новыми, которые окажутся лучше существующих.
Математическая подготовка, необходимая для изучения этой книги, неодинакова для разных глав. В большинстве случаев необходимы первоначальные сведения из линейной алгебры и линейного программирования (например, в пределах первых восьми-девяти глав книги автора «Линейное программирование»). Большая часть материала, относящегося к динамическому программированию, может быть изучена и без этих сведений. При чтении третьей и шестой глав необходимо знание, хотя и не слишком основательное, дифференциального исчисления.
Как уже говорилось, в гл. 2 сделана попытка собрать все необходимые для дальнейшего изложения сведения из математики. Исключение составила лишь элементарная теория вероятностей, даже не упоминающаяся в этой главе, но используемая далее в гл. 3, 5, 10 и И.
Автор очень обязан Д. Е. Моррису, который подобрал великолепные эпиграфы к каждой главе.
Рецензенты Р. Дорфман и С. Дрейфус внесли много полезных предложений, за которые автор им очень благодарен. Помощь при перепечатывании рукописи и издании книги была любезно оказана аспирантурой Школы бизнеса Чикагского университета.
Дж. Хедли
Богота, Колумбия июнь 1964 г.
ОГЛАВЛЕНИЕ
От редактора перевода ................... 5
Предисловие.......................7
Глава I. Введение.......................... 9
1.1. Задачи математического программирования........ 9
.2. Типы задач................... И'
.3. Вычислительные методы . . ! '. •............ 15
.4. Трудности, порождаемые нелинейностями......... 16
.5. Краткий исторический обзор ............... 23
.6. Обзор дальнейшего содержания.............. 25
Литература ' ... ; . . . : . . ..........• • 26
Упражнения...................... 27
Глава 2. Необходимый математический аппарат........... 29
2. 1. Матрицы и векторы................ 29
2. 2. Системы линейных уравнений .............. 38
• 2. 3. Линейное программирование i .............. 40
2. 4. Модифицированный симплекс-метод.......... . 44
• 2.-5. Двойственность ...................... 48
2. -6. Выпуклые множества................ 49
2. 7. Характеристические числа и квадратичные формы .... 52
2. 8. Функция п переменных.................. 55
• -2.-9. Частные 'производные •. .................. 56
2.10. Теорема Тейлора . . - ;................ '. 59
2.11. Теорема о неявных функциях .• . . ,.......... 60
Литература ...................... 63
Упражнения...................... 63
Глава 3. Классические методы оптимизации и свойства выпуклых
функций ......................... 65
3. I. Введение....................... 65
. 3. 2. Максимум и минимум при отсутствии ограничений .... 65
3. 3. Пример........................70
3. 4. Условный максимум и минимум. Множители Лагранжа 73
3. 5. Общий случай..................79
3. 6. Случай неотрицательных переменных и ограничений в
форме неравенств...............,......82
3. 7. Интерпретация множителей Лагранжа........85
3. 8. Интерпретация функции Лагранжа; двойственность .... 86 3. 9. Примеры ........................88
3.10. Выпуклые и вогнутые функции.............97
3.11. Примеры .........................102
3.12. Максимум и минимум выпуклых и вогнутых функций . . . 105
Литература........................... . 109
Упражнения ...........................109
Глава 4. Приближенные методы решения задач с сепарабельными
функциями.......................116
4. I. Введение .......................116
4. 2. Построение приближенной задачи и определение локального максимума.....................116
4. 3. Пример.........................123
4. 4. Другая формулировка..................129
4. 5. Замена переменных для получения сепарабельности .... 132 4. 6. Случаи, когда лекальный экстремум одновременно является глобальным.................... . 136
4. 7. Использование принципа декомпозиции при наличии ограничений сверху..................... 140
4. 8. Пример........................143
4. 9. Метод Хартли для максимизации функции на выпуклом
множестве при сепарабельных ограничениях......148
4.10. Задача с фиксированными затратами . . ........151
4.11. Пример задачи с фиксированными затратами......156
4.12. Транспортные задачи с выпуклыми сепарабельными целевыми функциями................159
Литература............................163
Упражнения . . . • •......................164
Глава 5. Стохастическое программирование.............170
5.1. Введение........................170
5.2. Одношаговые стохастические задачи со случайностями, появляющимися только в спросе ..............172
5.3. Одношаговые стохастические задачи со случайными величинами в технологических коэффициентах.........180
5.4. Многошаговые стохастические задачи ..........184
5.5. Средняя стоимость из-за неопределенности........ 191
5.6. Замена случайных параметров их средними значениями . . 192
Литература ............................192
Упражнения ...........................193
Глава 6. Теория Куна—Таккера...................195
6.1. Введение ........................195
6.2. Необходимые и достаточные условия для седловой точки 195
6.3. Теорема Куна—Таккера..................200
6.4. Установление необходимых условий методом Куна—Таккера 204
6.5. Один частный случай и пример..............212
Литература............................ 215
Упражнения ...........................216
Г л а в а 7. Квадратичное программирование..............220
I 7.1. Введение........................220
| 7.2. Решение задачи квадратичного программирования с отрицательно определенной формой x'Dx..........222
7.3. Окончание процесса в случае отрицательной определенности формы x'Dx.................226
7.4. Способ Чарнса для случая неположительности квадратичной формы........................229
7.5. Способ Вольфа, использующий параметризацию целевой
функции...................230
7.6. Пример .........................234
7.7. Другие методы решения задач квадратичного программирования ..................... . . 241
7.8. Двойственность в квадратичном программировании .... 246
Литература ............................249
Упражнения ...........................249
Глава 8. Целочисленное линейное программирование.........254
8. 1. Введение . . '.'.'..'..................254
8. 2. Задача с фиксированными затратами ..........255
8. 3. Определение глобального экстремума для приближенной
задачи в б-форме................256
8. 4. Определение глобального экстремума для приближенной
задачи в Х-форме....................258
8. 5. Представление некоторых поверхностей........260
8. 6. Конечные альтернативы .........i ...... 260
8. 7. Задачи с условиями очередности ............266
8. 8. Реализация проектов и календарное планирование .... 266
8. 9; Задача о бродячем торговце...............271
• 8.10. Капитальные вложения фирмы..............273
8Л1. Решение целочисленных задач линейного программирования ,....-..-..............275
• 8.12. Алгоритм Гомори для решения полностью целочислен-
ной задачи ........................ 276
•8.13. Доказательство конечности ..............281
8.14-. Алгоритм для-решения частично целочисленных задач . . . 287
8.15. Доказательство конечности для случая частично целочисленной задачи . . . .....................291
8.16. Пример ........................291
Литература ..............................295
Упражнения .•.-.••••.•..........................296
Глава 9. Градиентные методы....................302
'9. 1. Введение • •........................302
9. 2. Случай линейных ограничений..............303
9. 3. Сходимость итерационного процесса ...........309
9. 4. Геометрическая интерпретация .............312
9. 5. Численное определение г..............315
9. 6. Градиентный проективный метод............322
9. 7. Геометрические иллюстрации ..............329
9. 8. Сравнение методов определения г..........332
9. 9. Решение задач линейного программирования с использованием градиентных методов.............. 333
9.10. Задачи с нелинейными ограничениями......... . 337
9.11. Градиентный метод для задач с сепарабельными ограничениями........................ 340
9.12. Определение допустимого решения............347
9.13. Пример .......•....'.....•.........348
9.14. Некоторые дополнительные замечания' о сходимости . . . 352
9.15. Градиентный метод Эрроу—Гурвица для вогнутого программирования .....................353
Литература '............................355
Упражнения .........................• • 355
Глава 10. Динамическое программирование I............. 359
. 10. 1. Введение.......................359
10. 2. Сущность вычислительного метода.........359
10. 3. Эффективность метода .................367
10. 4. Основные свойства динамического программирования. .369
, . 10. 5. Численный пример ...................372
10. 6. Несколько других практических примеров........ 375
. 10. 7. Случай непрерывности переменных.........378
. 10. 8. Случай выпуклости или вогнутости функций fj(Xj) . . . 383 . . 10. 9. Детерминированные задачи последовательного принятия
«. решений ........................387
10.10. Простая задача об использовании рабочей силы ..... 387
. 10.1-1. Детерминированные задачи создания запасов......391
10.1-2. Случай, когда fj(Xj, i/j) —-вогнутые .функции......394
10.13. Пример ..........- .•............399
. 10.14. Функциональные уравнения для систем с бесконечным
числом шагов......................401
10.15. Явное решение функционального уравнения.......405
10.16. Задачи о замене оборудования.............409
10.17. Стохастические задачи последовательного принятия решений.........................414
10.18. Стохастическая динамическая модель в теории создания запасов ........................ 414
10.19. Динамическое программирование и вариационное исчисление .................'........422
10.20. Программы для решения задач методом динамического программирования на вычислительных машинах .... 426
Литература ............................427
Упражнения ...........................428
Глава 11. Динамическое программирование II............436
11. 1. Введение.......................436
11. 2. Задача распределения с двумя ограничениями.....436
11, 3. Задача с двумя переменными управления .......439
11. 4. Случай непрерывности переменных...........441
И. 5. Сравнение линейного и динамического программирования 445 11. 6. Использование динамического программирования в транспортных задачах с двумя пунктами производства .... 447 11. 7. Использование множителей Лагранжа для уменьшения
размерности......................449
11.8. Замена оборудования..................454
11. 9. Некоторые задачи вариационного исчисления ...... 456
11.10. Планирование выпуска продукции и задачи теории создания запасов......................460
11.11. Случай квадратичных затрат..............462
11.12. Доказательство эквивалентности стохастической и детерминированной задач в случае квадратичных затрат . . . 467
11.13. Стохастические задачи последовательного принятия решений с бесконечным планируемым промежутком и марковские процессы......................469
11.14. Пример ........................476
11.15. Оптимальность чистых стратегий ............478
11.16. Сведение к задаче линейного программирования .... 480
11.17. Двойственная задача линейного программирования . . .483
11.18. Дополнительные обсуждения ..............487
11.19. Заключительные замечания о проблеме размерности. . .490
Литература............................491
Упражнения...........................492
Именной указатель............. . ......496
Предметный указатель * ,.................497
Цена: 600руб.
