Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 64
Текст из файла (страница 64)
Купить 20 ъ 20 » 20 20 » 20 ъ 20 ъ 20 ъ 20 » 20 » 20 » 20 ъ 20 ъ 20 ъ 20 20 » 20 20 » 20 ъ 20 Сохранить Купить 20 » 20 ъ 20 20 ъ 20 ъ 20 20 » 20 ъ 20 ъ 20 » 20 ъ 20 ъ 20 ъ 20 ъ 20 » 20 ъ 20 » 20 » 20 1380,00 1260,00 1150,00 970,00 900,00 830,00 760,00 630,00 570,00 520,00 470,00 400,00 350,00 310,00 280,00 250,00 гЗО,ОО 210,00 190,00 280,00 213,02 145,00 130,00 120,00 110,00 100,00 90,00 80,00 70,00 65,00 60,00 55,00 50,00 40,00 35,00 30,00 25,00 15,00 7,00 0,00 Купить 19 ъ 19 Сохранить » Куцгтпь 19 19 19 ъ !9 » !9 ъ 19 » 19 » 19 » 19 19 » 19 » 19 » 19 » 19 19 19 617, 6 542,04 470,00 400,00 575,00 520,79 470,00 422,74 379,26 338,44 300,00 263,70 229,32 196,62 165,60 136,44 110,00 100,00 90,00 80,00 ?0,00 65,00 60,00 55,00 50,00 40,00 35,00 30,00 25,00 15,00 ?,00 0,00 201 407 злдлчл о злминв лвтомлшины Таблица 1!.7 Результаты по задаче о замене автомашины Игерецня 5 Итерация 4 Итеряцня а Сес шн- шш яы игры ш — 1Ы я 5 еынгр>нн — 157,07 еынгрыш — 15О,УУ ршненне ! зняченне решение ~ зняченне решение знзченне К>нить 12~ » 121 К>нить 12 » 12 12 12 12 12 12 > 12 > 12 > 12 12 Сохранить Купить 12 > 12 12 ь 12 !2 > 12 » 12 > 12 » 12 > 12 > 12 » 12 1') !'2~ > 12( ь 12, » 12 12 » 12~ 12 1 2 4 5 6 7 8 10 11 !'1 13 14 15 16 17 18 19 20 21 22 24 25 26 27 28 29 30 31 ;«о 36 37 38 39 40 1380,00 1260,00 1150,00 970,00 900,00 830,00 760,00 630,00 570,00 520,00 470,00 520,00 463,84 411,16 361,55 314,63 271,11 229,67 190,00 175,00 160,00 145,00 130,00 120,00 110,00 100,00 90,00 80,00 70,00 65,00 60,00 55,00 50,00 40,00 35,00 30,00 25,00 15,00 7,00 0,00 12 Сохранить Купить 12 Сохранить К>нить !2 12 !2»~ 12 12 » 12 ь 12, 121 12' > 121 > 12,' » 12! !о ь !2 1380,00 1260,0 1150,00 1002,62 917,24 836,21 760,00 760,54 694,9! 632,62 574,05 520,00 470,05 423,84 381,03 341,34 305,57 272,50 241,97 213,82 187,93 164,19 142,70 !23,?9 108,60 97,25 90,00 80,00 70,00 65,00 60,00 55,00 50,00 40,00 35,00 30,00 25,00 15,00 7,00 0,00 Купить 12 12 !2~ Сохранить! > Купить 12 12 !2 » 12 » 12 » 12 12 12 !2 12 12 > 12 12 12 » 12 > 12 1380,00 1260,00 1150,00 ! 072,26 987,22 906,67 831,16 760,30 694,73 632,50 573,99 520,00 470,12 423,97 381,23 341,61 305,92 272,95 242,51 214,46 188,68 165,07 143,73 124,99 110,00 100,00 90,00 80,00 70,00 65,00 60,00 55,00 50,00 40,00 35,00 30,00 25,00 15,00 7,00 0,00 [гл.
х! ИАРкОВские пропессы Решет!ий Таблица 11.8 по задаче о замене автомашины Результаты Итерации 7 Итерация З !значение! выигрыш г'ае =80 долларов — !00,00 Сосгоение решение вроданнан цена значение Купить 12 12 Сохранить 1380,00 1260,00 1160,66 1071,93 986,93 906,43 830,96 760,13 694,61 632,4! 573,95 520,00 470,16 424,05 381,36 341,80 306,! 6 273,24 242,87 214,89 189,19 165,67 144,42 125,80 110,95 100,00 12 !2 !2 12 12 12 !2 !2 12 12 12 12 12 12 90,00 80,00 70,00 65,00 50,00 40,00 35,00 30,00 25,00 15,00 7,00 0,00 1 2 3 4 5 6 7 8 9 1О 1! 12 13 14 !5 16 17 18 !9 20 2! 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 » ь ь ь » ь ь » ь ь ь » » » ь ь ь » » ь К?пить » ь ь » » ь » ь ь ь ь » ! 460,00 1340,00 1240,66 1151,94 1066,93 986,43 910,96 840, !3 ?74,6! 7!2,4! 653,95 600,00 550,16 504,05 461,36 421,80 386,16 353,24 322,87 294,89 269,19 245,67 224,42 205,80 190,95 180,00 ! 70,00 160,00 150,00 145,00 140,00 ! 35,00 130,00 120,00 ! 15,00 110,00 105,00 95,00 87,00 80,00 задача о злмвна Автомашины 409 201 значение состояния 40 положено равным 80 долларов, продажной цене машины такого возраста.
В этом случае каждое и, представляег собой значение машины возраста 1 для лица, которое следуег оптимальной политике. Чтобы огветигь на постанленный выше вопрос, мы должны сравнить значение ма~пины нозраста 1 год, па=1151,93 доллара, со значением чез ырехле ~ цей машины, вш — — 421,80 доллара. Если запрашиваемая приплата а меньше чем тц — вш 730 долларов, то ,уй7 йЫ л '- Л7 7ас7 7Ы й с7 7 а 7 4 а а 7 Ю Нсмер аагерааии Рис. 90. График зменьшении с номером итерации стон- мосги дзя задачи о замене автомашины. нам следовало бы согласигься на сделку, н противном случае — нет. Конечно, для ответа на поставленный вопрос нег необходимости дела~ь вш отличным от нуля; однако если взять т,„= 80 долларов, то переходные значения получаюг наряду с относигельной физической ингерпретацией также збсолютную. Если следовшь оптимальной политике, то годовая стоимость использования машины равна примерно 604 долларам (4 Х 150,95 доллара). Если бы мы следовали политике максимизации непосредственного дохода (показанной при итерации 1), то средняя годовая сгоимость была бы равна 1000 долларов.
Таким образом, следование политике максимизации будущего дохода, а не непосредственного имеет результатом ~гл. хг млгковскив пвоцессы Рвшвния экономию почти в 400 долларов за год. Уменьшение стоимости за период с номером итерации показано на рис. 90.
Выигрыш приближается к оптимальному значению, грубо говоря, экспоненциально. Заметим, что выигрыши на последних трех итерациях настолько близки, что с точки зрения практики соответствуюгцие политики можно рассказ ривать как эквивалентные. Тот факт, что трехлетняя мзшина является наилучшей при покупке, выявляешься уже на чегвертой итерации. Разрывы в функциях, имеюгцие место для трех лег, несомненно, объясняют этот выбор.
21. МЕТОД ИМИТИРОВАНИЯ Описанный выше метод включает решение системы ураннений. Если система плохо определена или если число урзвпений велико, то аналитически нельзя получить точных решений. Чтобы обойти эти трудности, был создан метод имитированин. 22.
СВЯЗЬ С ЛИНЕЙНЫМ ПРОГРАММИРОВАНИЕМ Наиболее сушественной чертой рассмотренных нами процессов является тот факт, что определение асимгпотического стационарного режима для них можно выполнить с помощью линейно~о программирования. Это важно потому, что в настоящее время в этой теории имеется много весьма эффективных алгоритмов, пригодных для решения задач большого размера. Так как для описания этих результатов потребовалось бы слишком много отступлений, мы отошлем чьпателя к некоторым оригинальным работам, перечисленным в конце главы. 23.
РЕЗЮМЕ В этой главе мы описали применение метода «приближения в пространстве политик», весьма удобного для исследования марковских процессов решения, где имеет смысл изучение асимптотического поведения. Во многих случаях можно показать, что режим устанавливается очень быстро. В других же случаях может оказаться, что только стационарный режим и представляет интерес. Следовательно, резулыаты, содержа- 411 комитптлиип и гпвлиогплвчщ шнеся н предшесгвующпх параграфах, можно применить целым рядом способов.
Наиболее трудной задачей в этой области в настоящее время является задача, относящаяся к развитию эффективных методов для рассмотрения переходных состояний. Здесь необходимы совсем другого рода приближения в пространстве политик. КОММЕНТАРИИ И БИБЛИОГРАФИЯ 4 2. Преносходное изложение основ теории марковских процессов можно найти в книгзх: '»М Г е!1е г, Ап 1п1гобосноп 1о РгоЬаЬгрду 'Птеогу апб 11з АРР1гса1гопз, лойп РЛ1еу апб Бонз, [Чсчг Тога, 1957[русский перевод; В. Ф е л л е р, Ваеление в теорию вероятностей, ИЛ, 1951; 2-с пзд, .Мир», 1964.[ Л О. К с пт е и у зпд 3. П 8 п е!1, Ргв!1е Магйот Спа!пз, П. Кап Комгапт1 Со., Рмпсе!оп, 1960.
9 3. Определение марковских процессов решения дано в книге К. В е1! ш а п, Пупаш!с Ргойгашш!пй, Рг!псе1оп Ппгкегюту Ргеаз., Рппсе1оп, 1»етч уегаеу, 1957, Сйартег Х! [Русский перевод; Р. Б е л л м а и, динамическое нрограмлгированис, ИЛ, 1960[. 9 7. доказательство можно пай~и в статье; К. В с!1ш а п, А Маг1»ошап бесьйоп ргосезз, 3. Мащ. апб Месй., т о1. 6, 1957, рр. 679 — 684. Многочисленные обобщения и применения к задаче оптимального управлении запасами можно найти в неопубликованной диссертации Д. Айгзхарта (матема и!ческий факультет Принстонского университета, 1960 г.) Я 9 — 14.
Эти результаты даны Р. Ховардом в его диссертации в Массачусетсколг Технологическом институте. Многие дальнейшие результаты приведены в его книге: К. А. Н о ж з г д, Пупаппс Ргойгашш!пя апб Магйот Ргосегжез, Тссппо)ояу Ргезз апб Зоип '»У!!еу агтб Бона, 74еж Тоги, 1960. [Русский перевод; Р, Х о в а р д, динамическое программирование и марковские процессы, М., «Сов.
радио», 1964[. 66 !6 — 20. Эти результаты впервые изложены в работе Б. О ге у1н з, А по1е оп ап )пбнз!г!а1 гер!асешепт ргосези Орегаиопа! Кезеагсй О., тоЬ 8, 1957, рр. 190 — !93. 9 21. О методе имитирования см, К. К о а си зт ! ей! апп А. Оно н 11а — Н о а г),Без сйо!х есопошн[аез, йесийопа лег[цент)е!)ез ет ашн1айоп, Пнподч РаПз, 1960. 4!2 МХРКОНПКИГ: ПРОЦНССЫ Птгглгтгглцн (г.т.
х! К. В е 11 п! а и, Г. К ! с с ! а г й и П. М а! с о1 пн С. С 1 а 1 'л апй С. С г а 11, Оп Тор-Мапацевсп! 5!во!а!гглп, Агпепсап 51аг!айевеп1 Аяосч Меж Тогй, 1957. 9 22. Значительная работа по численному решению уравнений для стационарного режима выполнена Бекманном, Манном и дру- гими авторами. Некоторые новые результаты, а также др)тие ссылки даны в статье: Г. О. Е р е п о и х, Бог пп ргоЫеве йе ргойцс!!оп ег йе з!осйаре йапа Га!саго!ге, Кетос Ггапеа!зе Кссйегспс Орега!1оппейе, по. 14, 1960, рр. 3 — 16.
Мы не касались связи между приведенными здесь результатачи и теорией послсцовательностных машин и, в частности, многих труд- ных и важных вопросов, возникающих в математических исследо- ваниях мсдицвнской диагностики. См, главу Н!!! книги; К. Ве11в а п, Айар!гас Соп1го1 Ргосеззез; А Солйей Тонг. Рппсе!оп Оп!тетю!у Ргезз., Рппсегоп, Меж дегасу, 1961, лде можно найти много ссылок, а танже статьи; К. Б. 1. ей!е у апй 1.. В. ! и атей, Кеалоп)пй 1оцпг)айопз о1 плей!са1 й!ацпоз!з, Бс!епсе, чо1. 130, 1959, рр. 9 — 21. В. В.
ТУ!о ! е г, Орин!а! гйайпоак ргосейогсз, 1КЕ Тгапл, оп Ке1!аЬ!Гиу апй ОцаТйу Соп!го1, то1. К!)С-9, 1960, рр. !3 — 19. 3. Е. О т е г а 11 апй С. М. В г!! !а в а, Мойе1а 1ог щей!па! гВайпоз!з, Вейан)ога! Боепсе, ъо!. 6, 1961, рр. !34 — 141.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
