Советский читатель уже знает автора по его монографии „Теория устойчивости решений дифференциальных уравнений", вышедшей в Издательстве иностранной литературы в 1954 г.
Теория динамического программирования родилась из ряда технико-экономических задач, таких, как задача о наиболее эффективном использовании оборудования или задача о наиболее выгодной политике закупок. По этой новой области математики литература на русском языке отсутствует, если не считать небольшой обзорной статьи автора, опубликованной в сборнике „Современная математика для инженеров" под редакцией Э. Ф. Беккенбаха, Издательство иностранной литературы, 1958 г. Автор является одним из создателей теории динамического программирования, подробному изложению которой и посвящена его монография.
Книга интересна для широкого круга математиков, занимающихся приложениями, специалистов по регулированию, инженеров, экономистов и др.
Книга доступна студентам старших курсов и аспирантам указанных специальностей.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
В самых разнообразных областях теоретической и практической деятельности часто оказывается целесообразным принимать решения не сразу, а постепенно, шаг за шагом. Принятие решения, таким образом, рассматривается не как единичный акт, а как процесс, состоящий из нескольких этапов.
Такой подход использовался уже довольно давно при исследовании некоторых частных вопросов. Наиболее полно эта идея была воплощена А. Вальдом в его теории секвенциального статистического анализа. Систематизация примеров подобного рода исследований показывает, что многие из них с успехом могут быть обслужены некоторым единообразным математическим аппаратом. Таким аппаратом оказывается созданная в значительной мере трудами Р. Беллмана и его учеников теория динамического программирования.
Предметом динамического программирования является изучение многошаговых решений, в том или ином смысле оптимальных. Классические методы нахождения экстремумов функций многих переменных здесь часто оказываются неприменимыми ввиду большого числа параметров, от которых зависит решение. Лежащий же в основе динамического программирования принцип оптимальности часто может быть реализован в виде такого функционального уравнения, решение которого более доступно методам современной математики (в том числе вычислительной математики), чем решение соответствующих уравнений в условиях классической постановки задачи. На таком пути обнаруживается и новый подход к решению обычных задач вариационного исчисления.
Оптимизационные задачи встречаются почти во всех отраслях науки, техники и хозяйства. С ними приходится иметь дело в промышленной технологии, в организации производства, в экономическом планировании, в различных вопросах физики, биологии и военного дела. Поэтому круг приложений динамического программирования исключительно широк.
Возможности применения методов динамического программирования для решения задач, возникающих в физике, экономике, биологин и т. д., отнюдь не означают, что динамическое программирование является частью одной из этих дисциплин. ^Теория динамического программирования, подобно, например, математической физике, есть часть математики, и в этом отношении она принципиально не отличается от Других математических теорий. При этом, разумеется, не следует
ОГЛАВЛЕНИЕ
Предисловие редактора перевода .................. 5
Предисловие автора ..... .................... 7
Глава Г. Многошаговый процгсс распределения.......... 21
§ 1. Введение.......................... 21
§ 2. Многошаговый процесс распределения ресурсов....... 22
§ 3. Обсуждение........................ 23
§ 4. Метод функциональных уравнгний.............. 26
§ 5. Обсуждение ........................ 28
§ 6. Многомерная задача о максимизации............ 28
§ 7. Задача о „сглаживании" .................. 29
§ 8. Бесконечношаговая аппроксимация............. 30
§ 9. Теоремы существования и единственности .......... 3')
§ 10. Последовательные приближения............... 35
§ 11. Приближение в пространстве поведений........... 35
§ 12. Свойства решения. I. Выпуклость . . :.......... . 38
§ 13. Свойства решения. II. Вогнутость............. . 39
§ 14. Свойства решения. III. Вогнутость.............. 41
§ 15. Причудливый пример.................... 44
§ 16. Обычный пример. I..................... 45
§ 17. Обычный пример. II.................... 47
§ 18. Приближение и устойчивость................ 48
§ 19. Процессы, зависящие от времени.............. 50
§ 20. Процессы с несколькими видами ресурсов.......... 51
§ 21. Теоремы о структуре решения для многомерных задач ... 53
§ 22. Разыскание единственного максимума вогнутой функции ... 54
§ 23. Непрерывность и память.................. 57
§ 24. Стохастические процессы распределения ресурсов...... 58
§ 25. Функциональные уравнения................. 59
§ 26. Интегралы Стильтьеса................... 60
Упражнения и проблемные задачи к главе I........... 61
Библиография и комментарии к главе I.............. 81
Глава II. Стохастический многошаговый процесс решения .... 83
§ 1. Введение.......................... 83
§ 2. Стохастический процесс золотодобычи............ 84
§ 3. Метод перечисления .................... 84
§ 4. Метод функциональных уравнений.............. 85
§ 5. Аппроксимация бесконечношаговым процессом ....... 86
§ 6. Существование и единственность.............. 86
§' 7. Приближение в пространстве поведений и монотонная сходимость ............................ 88
§ 8. Решение.......................... 88
§ 9. Обсуждение......................... 92
§ 10. Некоторые обобщения ................... 92
§ 11. Вид функции f(x, у).................... 93
§ 12. Задача для процесса с конечным числом шагов....... 95
§ 13. Трихотомическая задача................... 93
§ 14. Теорема устойчивости.................... 99
Упражнения и проблемные задачи к главе II........... 100
Библиография и комментарии к главе II............. 13-
Глава ///..Структура процессов динамического программирования 103
§ 1. Введение .......................... 103
§ 2. Обсуждение двух процессов, рассмотренных ранее...... 103
§ 3. Принцип оптимальности.............•..... 105
§ 4. Постановка задачи. 1. Дискретный детерминированный процесс 105
§ 5. Постановка задачи. П. Дискретный стохастический процесс . . 108 § 6. Постановка задачи. Ill, Непрерывный детерминированный
процесс........................... 10Э
§ 7. Непрерывные стохастические процессы........... НО
§ 8. Обобщения......................... 110-
§ 9. Причинность и оптимальность................ 111
§ 10. Приближение в пространстве поведений........... 111
Упражнения и проблемные задачи к главе III........... 113
Библиография и комментарии к главз III.............. 141
Глава IV. Теоремы существования и единственности...... . 142
§ 1. Введение.......................... 142
§ 2. Основное неравенство.................... 143
§ 3. Уравнения первого типа .................. 145
§ 4. Уравнения второго типа.................. 147
§ 5. Монотонная сходимость ................... 148
§ 6. Теоремы устойчивости............•....... 150
§ 7. Некоторые направления обобщений............. 151
§ 8. Пример уравнения третьего типа.............. 152
§ 9. Уравнение оптимального управления запасами........ 157
Упражнения и проблемные задачи к главе IV........... 160
Библиография и комментарии к главе IV............. 180
Глава V. Уравнение оптимального управления запасами...... 182
§ 1. Введение.......................... 182
§ 2. Постановка общей задачи.................. 183
A. Конечный период времени ................ 184
Б. Бесконечный промежуток времени, скидка с издержек . . 186
B. Бесконечный промежуток времени, частичный возврат предметов .......................... 187
Г. Бесконечный промежуток времени, задержка поставки на
один период....................... 187
Д. Бесконечный промежуток времени, задержка поставки
на два периода ..................... 187
•§ 3. Одно простое замечание .................. 188
§ 4. Постоянный уровень запасов, предварительное обсуждение . . 189
§ 5. Пропорциональные издержки, одномерный случай...... 190
§ 6. Пропорциональные издержки, многомерный случай...... 196
§ 7. Конечный промежуток времени............... 198
§ 8. Конечный промежуток времени, многомерный случай .... 202 § 9. Непропорциональные „дополнительные расходы"—административные расходы ...................... 202
§ 10. Частные случаи....................... 205
§ 11. Вид общего решения.................... 205
§ 12. Постоянные расходы.................... 206
§ 13. Предварительные замечания к обсуждению более сложных
поведений......................... 207
§ 14. Неограниченно продолжающийся процесс, запаздывание на один
период........................... 207
§ 15. Выпуклая функция издержек, неограниченно продолжающийся
процесс .......................... 210
Добавление к главе V. Уравнение восстановления......... 212
Упражнения и проблемные задачи к главе V.......... . 214
Библиография и комментарии к главе V............. 217
Глава VI. Задачи „на узкие места" в многошаговых процессах
производства....................... 219
§ 1. Введение.......................... 219
§ 2. Общий класс задач, возникающих при изучении многошагового процесса производства................. 220
§ 3. Обсуждение рассмотренной выше модели.......... 224
§ 4. Функциональные уравнения................. 225
§ 5. Непрерывный вариант.................... 226
§ 6. Система обозначений.................... 227
§ 7. Постановка задачи с точки зрения динамического программирования .......................... 228
§ 8. Основное функциональное уравнение............ 229
§ 9. Нелинейное дифференциальное уравнение в частных производных............................ 229
§ 10. Приложение дифференциального уравнения в частных производных ........................... 230
§ 11. Частный пример...................... 231
§ 12. Двойственная задача.................... 234
§ 13. Проверка решения, построенного в§11........... 237
§ 14. Численное решение..................... 240
§ 15. Нелинейные задачи..................... 241
Упражнения и проблемные задачи к главе VI........... 241
Библиография и комментарии к главе VI............. 243
Глава VII. Задачи „на узкие места". Примеры........... 245
§ 1. Введение.......................... 245
§ 2. Предварительные замечания . .......>........ 247
§ 3. Дельта-функции....................... 249
§ 4. Решение.......................... 250
§ 5. Модифицированное до-решение............... 253
§ 6. Равновесное решение.................... 254
§ 7. и>-решение для процесса малой продолжительности..... 256
§ 8. Описание решения и доказательство............. 257
§ 9. Перечень случаев расхода начального запаса стали..... 260
Библиография и комментарии к главе VII............. 261
Глава VIII. Непрерывный стохастический процесс решения .... 262
§ 1. Введение.......................... 262
§ 2. Непрерывный случай. I. Дифференциальный подход..... 263
§ 3. Непрерывный случай. II. Интегральный подход....... 264
§ 4. Предварительное обсуждение................ ;j°j?
§ 5. Смешивание в точке.................... ^°°
§ 6. Новая формулировка процесса золотодобычи........ «?/
§ 7. Вывод дифференциальных уравнений............ ;*°
§ 8. Вариационный метод.................... ^Й?
§ 9. Поведение функций Ki................... ?1?
§ Ю. Решение для случая Т = оо................. ~?А
§ 11. Решение для конечного полного времени....... . . • tit
§ 12. Задача о трихотомическом выборе............. ?l_
§ 13. Некоторые леммы и предварительные результаты...... ?ij?
§ 14. Смешанные выборы..................... ^?а
§ 16. Случай D < 0....................... 282
§ 17. Случай гъ = г±....................... %*>
§ 18. Нелинейная функция выгоды — задача о дихотомическом выборе 284
Библиография и комментарии к главе VIII............ 28&
Глава IX. Новая формализация вариационного исчисления .... 287
§ 1. Введение.......................... 287
§ 2. Новый подход....................... *0®
со
§ 3. Максимизация функционала I F(x, у) dt .......... 291
о
§ 4. Обсуждение........................ 293
§ 5. Двумерный случай.................: . . . /94
Т
§ 6. Максимизация функционала I F(x, y)dt........... 295
296
§ 7. Максимизация функционала I F(x, у) dt при условии 0<; у
о
§ 8. Численное решение..................... 297
§ 9. Обсуждение ........................ 298
§ 10. Пример........................... 299
§ 11. Дискретная модель..................... 302
§ 12. Доказательство сходимости................. 304
т
§ 13. Максимизация функционала I F(x, у, t)dt......... 307
О
§ 14. Обобщение и обсуждение................... 30$
§ 15. Интегральные ограничения................. 309
§ 16. Дальнейшие замечания относительно численного решения . . 310
§ 17. Задача о собственных значениях.............. 311
§ 18. Первая формулировка.................... 313
§ 19. Приближенное решение................... 314
§ 20. Вторая формулировка.................... 315
§ 21. Дискретные аппроксимации................. 315
§ 22. Последовательные приближения............... 316
§ 23. Монотонная аппроксимация................. 318
§ 24. Единственность решения.................. 318
§ 25. Минимум максимального отклонения............ 319
Упражнения и проблемные задачи к главе IX........... 320
Библиография и комментарии к главе IX............. 3'19
Глава X. Многошаговые игры.................... 331
§ 1. Введение......................... 331
§ 2. Одношаговая дискретная игра................ 332
§ 3. Теорема о минимаксе.................... 334
§ 4. Непрерывные игры..................... 335
§ 5. Ограниченные ресурсы................... 335
§ 6. Игры на выживание..................... 337
§ 7. Игры погони........................ 337
§ 8. Общая формулировка.................... 338
§ 9. Принцип оптимальности и функциональные уравнения .... 340
§ iu. оолее оощии процесс.................... 342
§ 11. Основная лемма...................... 343
§ 12. Существование и единственность.............. 345
§ 13. Доказательство результатов................. 347
§ 14. Другое доказательство существования............ 349
§ 15. Последовательные приближения в общем случае....... 350
§ 16. Эффективность решения................... 350
§ 17. Дальнейшие результаты................... 352
§ 18. Односторонний минимакс.................. 353
§ 19. Существование и единственность для игр на выживание . . . 353
§ 20. Приближение........................ 357
§ 21. Ненулевые игры на выживание............... 358
§ 22. Приближенное решение................... 359
§ 23. Доказательство обобщенной теоремы о минимаксе...... 359
§ 24. Истолкование игр с ненулевой суммой........... 361
Упражнения и проблемные задачи к главе X........... 362
Библиография и комментарии к главе X............. 368
Глава XI. Марковские процессы решения............. 370
§ 1. Введение.......................... 370
§ 2. Марковские процессы решения............... 370
§ 3. Обозначения........................ 372
§ 4. Лемма........................... 373
§ 5. Существэвание и единственность. 1............. 374
§ 6. Существование и единственность. И............. 378
§ 7. Существование и единственность. III............ 379
§ 8. Уравнение Риккати..................... 380
§ 9. Приближение в пространстве поведений........... 381
§ 10. Дискретные варианты.................... 383
§ 11. Рекуррентное соотношение................. 385
§ 12. Минимакс.......................... 387
§ 13. Обобщение результата Неймана.............. 388
Упражнения и проблемные задачи к главе XI........... 389
Библиография и комментарии к главе XI............. 391
Указатель приложений....................... 393
Именной и предметный указатель................. 395
Цена: 150руб.
