Беллман Р. Прикладные задачи динамического программирования (2013)

Р. БЕЛЛМАН, С. ДРЕЙФУС ПРИКЛАДНЫЕ ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Перевод с английского Н, М. МИТРОФАНОВВЙ, А. А. ПЕРВОЗВАНСКОГО, А. П. ХУСУ, О, В. ШАЛАЕВСКОГО ПОД РЕДАКЦИЕЙ А. А. ПЕРВОЗВАНСКОГО ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО. МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ МОСКВА 1965 ОГЛАВЛЕНИЕ Предисловие редактора перевода. Предисловие автора Г ла ва !. Одномерные процессы распределения 1 Введение 2 Описание процесса распрелеления ресурсов .. 3 Построение математической модели.....

4 Обсуждение 5 Аппарат математического анализа 6. Трудности . 7 Заключение 8 Анализ чувствительности 9 Динамическое программирование ............. 10. функциональные уравнения ...... 11 Принцип оптииальности .... 12, Прямой вывод основного ф>нкционального уравнения 13. Обсуждение. 14. Вычислительная схема 15. Неединственность максимума................ 16. Эффективность динамического программирования по сравнению с прямым перебором ..............

17. Какие трулности мы преодолели? .... 18. Блок-схема вычислительного плана для общего процесса распрелеления 19. Численные результаты .. 20. Один полезный прием 21. Устойчивость 22. Процесс загрузки судна 23. Математическая постановка задачи ............ 24. Обсуждение 25. Рекуррентные соотношения ............., ...

26. Обсуждение вычислительной процедуры 27. Надежность многокомпонентных схем 28. Надежность на основе дублирования компонент.... 29. Математическая модель ...... 30. Параллельные операции . 31. Заключение Комментарии н библиография. 1' 12 17 23 23 24 25 26 27 28 33 34 34 35 36 37 38 41 42 44 46 49 51 52 52 53 53 54 55 57 59 60 61 62 63 огллвлгнив Глава 1 2 67 68 68 69 70 70 7! 71 3 4 5 6 7 8 9 10 71 73 74 76 78 80 80 82 8о 83 85 11 12 13 14 15 16 17 !8 19 20 21 22 о3 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4,! 45 П. Многомерные процессы распределения......

Введение. Процесс распределения при наличии двух типов ре- сурсов Рекуррентные соотношении, ................ Процесс распределения с двумя типами ограничений Рекуррентные соотношения ................. Вычислительные аспекты Обсуждение . Задачз о запасных частях.......,.....,.... Стохастические аспекты Подход с точни зрения динамического программиро- вания Вычислителы<ая процедура ................. Пример.

Множитель Лзгранжа Геометрическое происхождение Множитель Лагранжа в качестве цены.......... Применение множителя Лагранжа — 1.......... Применение множителя Лагранжа — П.......... Понижение размерности 'Зквивалентность вариационных задач Монотонность по Х Применение метода множителей Лагранжа — реклам- ная кампания . Метод множителей Лагранжа................

Результаты вычислений Вычисление множителей Лзгранжа . Зазача с многими уровнями Многомерное прострзнство политик Проблема надежности Введение множителя УШгранжа Численный пример. Блок-схема программы Обобщение Транспортная задача Хичкока — Купманса........ Математическая модель транспорпшго процесса Обсуждение .

Подход с точки зрения динамического программиро- вания . Обсуждение . Понйжение размерности Увеличение шага сетки .. Применение множителя 7!агрзвжз к задаче с тремя складами . Пример 1 — два склада, десять пунктов потреблении Блок-схема программы для случая двух скчадов ... Пример П вЂ” три склада, десять пунктов потребления Последовательные приближения — 1 Приближение в пространстве политик .......... Последовательные приближения — П 86 88 89 93 96 97 98 99 99 101 101 104 105 106 107 108 109 109 110 112 114 114 !16 117 119 огдапнпиив 121 124 125 126 !27 Г27 129 1ЗЗ 134 134 135 135 136 137 138 Хичкока— Глава ле 1. 2. 3.

4. 5. 6. 7. 8. 9, 1О. 11. 12, 13. 14. !5 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 46. Последовательные приближения — Ш .... 47. Козффнциенты связи 48. Грубая сетка 49. Последовательные приближения в задаче Купманса. 50. Сходилюсть . 51, Пример 1 — относите.льный минимум .... 52. Пример И вЂ” абсолютный минимум 53. Стохастнческая итерация ............ 54. Выводы . 55. Задачи о «трудной переправе»........ 56. Общая задача ..

57. Функциональные уравнения .......... 58. Обсуждение 59. Численное решение Комментарии и библиография........... Ш. Одномерные процессы сглаживания и со ния расписаний . Введение . Процессы сглаживания Пример процесса сглаживания Математическая постановка задачи........ Функциональные уравнения Обсуждение .

Вычислительные аспекты Результаты Блок-схема Несколько графических результатов .. Задачи о баижайшем соседе Замена обйр,'~повлияя. ° . став- про- про- Физический процесс Постановка задачи в терминах динамического граьглгирования . Аналитическое решение .. Технологические усовершенствования..... Формулировка задачи в терминах динамического граммирования . Пример . Другие постановки задачи Задача складирования Математическая модеаь Рекуррентные соотношения Обсуждение . Предварительные преобразовании .

Аналитическая структура ...... Доказательство теоремы Обе у ждение . Численный пример Выводы . Задача о поставщике 143 143 144 144 145 !46 146 146 148 149 149 149 !56 Г57 157 158 158 160 16! 166 169 169 !?О !71 171 173 173 !75 !75 !77 !77 оглдвлвппв 31. Подход с точки зрения динамического программирования 1.....................,, ....., 32. Подход с точки зрения динамического программирования П .................,, ...... 33.

Аналитическое решение для д = 1, р = 2. 34, Аналитическое решение дая д = й, р = Л + 1 ..... 35, Аналитическое решение для 9 = 1, р =3 (!) 36. Аналитическое решение для д = 1, р = 3 (П) 37. Аналитическое решение ..... - ... 38. Решение, основанное на здравом смысле ........ 39. Задача управления запасами ................ 40. Обсуждение....., .. 41.

Дальнейшие упрощенна....... 42. Планирование производственной линии.......... 43. Математическая постановка задачи ............ 44. Подход с точки зрения динамического программирования 45. Определение оптимальной перестановки ......... 46. Пример. 47. Заключение . Комментарии и библиография.... Гла за 1Н. Методы оптимального поиска............ 1. Введение . 2. Унимодальные функции 3. Одномерный оптииальный процесс нахождения точки максимума . 4. Числа Фибоначчн 5. Золотое сечение 6. Дискретный случай 7.

Нули функций 8. Функциональные уравнения ...... ° ° ° . ° ° ° 9. Частный случай и — 1 1О. Случай и=1, 3 — 0 11. Описание процесса вычислений.... 12. Численный пример — сравнение с вычислительным методом деления отрезка пополам .. 13. Обсуждение . 14. Задача о фальшивой монете .... !5. Задача с двумя лшнетами ........... ° ° ° 16. Аналитическая постановка задачи ........

!7. Значения функции р(г; з; т)....... ° 18. Основное функциональное уравнение 19. Вычислительные процедуры .. 20. Рассмотрение с помощью теории информации..... Комментарии и библиогрзфия..... Г л а в а Н. Динамическое программирование и вариацпом.

пое исчисление 1. Введение. 2. Функционалы . 178 178 180 181 181 183 184 184 186 188 189 190 191 192 193 194 195 196 202 202 203 203 205 206 206 207 208 2!2 2!3 215 216 218 219 220 221 223 223 225 230 232 234 234 235 ОГЛАВЛЕНИВ 236 240 240 241 241 244 245 247 Формальный аппарат вариационного исчисления Необходимые условия Естественные граничные условия Изопериметрические задачи .........., ... Недостатки вариационного исчисления....... Двухточечные краевые задачи ............ Ограничении Линейность 3 4 5 6 7 8 10 11 Формальный аппарат динамического программирования 247 12 13.

14. 15. 16. 17. 18. 19. 20. 2!. 22. 23. 24. 25. 26. 27. 28. 29. Ко Глава 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Решение с помощью динамического программирования — П. 286 Вычислительные результаты .......,........ 287 16 Основное нелинейное сравнение в частных произволных 248 Уравнение Эйлера . 249 Условие Лежандра.

250 Условие Вейерштрасса.....,.............. 250 Случай нескольких зависимых переменных....... 25! Изопериметрическая задача................. 252 Множитель Лагранжа . 253 Естественные граничные условия............. 254 Условие трансверсальности ................. 254 Угловые условия Эрдманна .................

255 Неявные вариационные задачи............... 255 Огрзничеиия в виде неравенств .............. 257 Уравнение Гамильтона †Якоби ............... 258 Дискретные приближения .................. 260 Обсужлеиие. . ......., ..., 262 Дв!хточечные краевые задачи ............... 262 Двойственность . 264 Закаючение . 264 мментарии и библиографии....., ........, ... 265 У!. Оптимальные траектории ............... 269 Введение . 269 Упрощенная задача о выборе траектории ........ 270 Двойственная задача 2?2 Задача о наборе высоты за минимальное время.... 272 Формулировка в терминах динзмического программирования. 273 Аналитическое решение ...................