Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 62
Текст из файла (страница 62)
12. РЕШЕНИЕ ЗАДАЧИ О ТАКСИ Вернемся к задаче о такси из 9 4 и применим к ней данные выше правила. В качестве начзльного приближения выбираем вектор политики =П который означает, что мы курсируем во всех горо!дам. Эте '! р!К вЂ” ро1к! !чиргоч евши! гов1!ие. 1!!////л/. ред.) и/! З* 392 МАРКОВСКИЗ ПРОЦВССЫ РБШБННЯ 1гл. х! политика, максимизируюшая математическое ожидание непосредственного дохода. 71.ля нее имеем матрицу переходных вероятностей 1 1 4 4 1 2 1 2 1 о 2 [Рг!1 = 1 1 ! 4 4 2 и вектор непосредственного дохода [2 р ~=[161 Обозначим сумму ~ч~ р,г г!, через дп поскольку ожидаемый 7 ! доход зззисит только от !. Уравнения для определения значений оп если предположить о, равным нулю, запишутся в виде 1 ! у+о!=8+ — о, + — о„ 2 4 1 л+оа= !б+ 2 о! 1 ! 8=7+ 4 ~~+ 4" и имеют решение о, = 1,33, о,= 7,47, оз = 9 д= 9,2.
Используя политику «всегда курсировать», водитель в среднем будет иметь 9,2 единицы за поездку. Обрашаясь к Р!К, вычислим величины д;+Р,' р~р7 для ! всех 1 и 7г (см. таблицу 11.2). 898 121 вашинив задачи о тлкси Мы видим, но для ! = ! величина в правом столбце максииальна при 7г= 1. Лля 1 = 2 или 3 опа максимальна Таблица 11.2 !у Чу+ ~~~~~Р~ ~7 /1 !О,5О+ 8,43 5,51 16,67 21,75+ 9,20 9,66 + при 7с=2. Иными словами, наша новая политика будет определяться вектором 0=~2] Это значит, что если такси находится в городе 1, то оно должно курсировать; если в городе 2 или 3, то оно должно подъезжать к блнжайшеп стоянке.
Теперь имеем: 1 1 1 2 4 4 !Рй = !6 8 !6 ' ~ 4~' 1:1 1 8 4 8 Возвращаясь к ЧРО, решим уравнения 1 ! 1 К+ о, = 8+ —,, тб+ - ос+ — вь 4 ' ' 4 1 7, 1 а'+о' !5+ !6о'+ 8 ос+ !6оа' ! 3 1 4 + оа = 4 + — о, + -'- о + — о.. 13 Р. Бсллмся. С. дреафус 394 ~гл. !и МЛРКОВСКИЯ ПРОПЕССЫ РВШВИИВ Снова, полагая па=О, получим: и!= 388, па= 12,85, п,=О, е = 13,15.
Заметим, что и возросло от 9,2 до 13,15, чего мы и добивались, так что шофер зарабатывает в среднем за поездку 13,15 единицы, Используя Р!к для этих зиачеипп, получим: ! й 9,27 12,14 !- 4,91 14,06 26,00 + 9,26 12,02 + 2,3? Новая политика, .!аким образом, определяешься вектором' =Ц 3 3 4 16 1 16 7 1 3 16 ! !6 3 ! 4 3 4 Такси должно подъезжать к ближайшей стоянке независимо от города, в котором находится. При этой политике имеем: 12] яшньнив злдлчи о тлкси Используя 700, получим: 3 з и"+э,=2,75+ !6 о'+ 4 ~я+ ! !6 7 ! 8+ я + 16 а+ я+ 16 1 3 1 +.а — 4+-.,+-.,— —.. 8 4 ' ' 8 При оа — — О имеем: о, = — 1,18, о,= 12,66, па=О, д= 13,34 Т а б л и ц а 11.3 Л л л ча+ ла РО~) 7=! 10,57 12,16+ 5,53 ! 5,41 26,00+ 9,86 13,33+ 5,40 Вектором новой политики будет вектор =П который совпадает с вектором предыдущей политики, так что процесс сошелся и величина д достигла своего максимума, равного 13,34.
Водитель такси должен в любом городе подъезжать к ближайшей стоянке. Применение такой политики дает в среднем за поездку доход в 13,34 единицы, почти в полтора раза больший, чем при политике постоянного курсирования, найденной максимизацией непосредственного дохода. Выпишем результаты вычислений 1с точностью 13' Заметим, что произошло определенное возрастание, хотя и небольшое, значения д от 13,!б до 13,34.
Применяя Р!К, получим результаты, приведенные в таблице 11.3. МАРКОВСКИЕ ПРОЦЕССЫ РЕШЕНИЯ 1гл. Х1 до двух десятичных знаков) о, 0 1,33 — 3,88 — 1, 18 о, 0 7,47 12,85 !2,66 о, 0 0 0 0 е — 9,20 13,15 13,34 л ~ О, 1 ! 2 2 О, 1 2 2 2 О, 1 2 2 2 Р!к 'т'170 Р!к тгТ!О Р!К У00 Р1к СТОП Заметим, что оптимальная политика, предписывающая всегда подъезжать к стоянке, является наггхудшей политикой с точки зрения непосредственного дохода.
В последовательных процессах решения часто оказывается, что лучше журавль в небе, чем синица в руки. !3. БОЛЕЕ ОБЩАЯ ЗАДАЧА т10 сих пор мы требовали, чтобы существовал единственный выигрыш у, связанный с задачей. Это означает, что имеется только одна цепь и какую бы политику мы ни выбирали, из любого состояния можно перейти в любое другое. Гарангировать этот резулшаг можно, например, взяв все рг! положигельными, Хотелось бы, однако, чтобы наш метод был пригоден для более обще~о случая, когда имеется несколько цепей.
Вот, например, переходная матрица такой задачи: 1 ! — О 0 1 ! — — 0 2 2 0 0 1 ЖЛ= 3 4 1 7 0 0 8 8 Здесь, если мы выходим из состояния 1 или 2, то нет возможности перейти в 3-е или 4-е состояния, и наоборот. При соответствующей матрице дохода мы будем иметь один асимптотический средний выигрыш, связанный с выходом из 14] 397 овщее Рятценин !4. ОБЩЕЕ РЕШЕНИЕ политики, решим Используя Рц и д! для эаланной систсл!у уравнений л к ! = ~~~ Рйь ! у= ! л! и(+ь.! = 7!+ ~~Рону у=! лля всех о; и дь Решение будет содержать столько произвольных постоянных, сколько имеется независимых цепей МаРкова; эти постоянные можно положить равнымн нулю. Для каждого состояния ! находим зльтернатнву А, л которая максимизирует сумму ~'Р,.п!, и примем ее за нот=! Ф вое решение в г-м состоянии.
Если ~„р! л одинакова дэя а у=! всех алыернатив, то решение следует принять на основе переходных значений оя а не выи!рышей л!. Следовательно, если критерий выигрыша теряет силу, то находим аэыернативу й, максимизируюшую стмму Чт+ а л + л, рбол и примем ее за новое решение в Ли состоянии. а у=! Если старое решение в 1-и состоянии придает такое же ботьшое значение величине критерия, как любая лругая альтернатива, оставляем старое решение неизменныл!, независимо от того, основан ли тест улучшения политики на выигрышах д! или на значениях оо Это правило гарантирует сходимость в случае эквивалентных политик.
Когда эта процелура повторена для всех состояний, то определяется новая политика и получаются новые матрицы ]Р;] и [д!]. Если новая политика совпадает с предыдущей, то пройесс вычислений сошелся и наилучшая политика найдена. состояний 1 или 2, а другой — с выходом иэ состояний 3 и 4, Это приводит в общем к необходимости индексирования вынгрышз, причем а! будет означать выигрыш для цепи 1, пав для цепи 2 и т. д. Используя эти обозначения, перейдем к более общему алгоритму, который мы опишем схематически. 398 мликовскив пвоцвссы эвгпвния !гл, к! !6. ЗАДАЧИ О ЗАМЕНЕ ОБОРУДОВАНИЯ В ПЕРЕСМОТРЕННОЙ ПОСТАНОВКЕ В 9 12 главы !П мы довольно подробно рассмотрели задачу о замене оборудования.
Предложенный там метод заключался в решении некоторой задачи с конечным временем с помощью итерации рекуррентного соотношения. Это позволяет включить в рзссмотрение стоимостные изменения как функцию реального времени, так и функцию срока службы.
Если ищется решение с бесконечным временем, мы можем иаерировать уравнение, пока средний доход за шаг не будет равен постоянной с любой требуемой степенью точности, однако при использовании этого метода редко можно безусловно утверждать, что политика сходится, В качестве примера этого метода мы рассмочрим задачу о замене оборудования. Затем мы применим к аналогичной задаче метод пространства политик. !6. ЗАДАЧА О ПРОИЗВОДСТВЕ ШИН !!ри производстве резиновых шин используется машина с двумя устройствами, на которых одновременно изготовляется по одной шине. Если устройство отказывае~, то изготовляется дефектная шина, что приносит убыток гм В случае поломки устройства машина должна быть остановлена для его замены, в результате чего появляются издержки са, отражающие стоимость вложенного труда, и издержки см отражающие потерю производственного времени.
Новое устройство стоит си Когда машина остановлена, издержки по замене второго устройства равны стоимости такого устройства. При замене устройств до поломки можно избежать потери стоимости дефектной шины с, и производственных затрат см Однако такая политика с неизбежностью приведет к покупке большого числа новых устройств, а также потребует больше труда, чем политика замены после отказа в рабо~е.
Задача заключается в отыскании оптимальной политики замены. 17] еоемтливовкл задачи 17. ФОРМУЛИРОВКА В ТЕРМИНАХ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Начнем с определения функции 1,(1, 1) — суммарной ожидземой стоимости производства Аг дополнительных шин, если устройство ! уже произвело 1 шин, а устройство 2 произвело 1 шин, и при этом использовалась онтииальиал политика замены, Производить: ргруул (1+! 1- !)+ + (! — рг) (! — ру) [2с, + 2с, + сз + са -1- У~у (О, 0)] — 1- +(! — р)руги!и [с,+с,+с,+ -дол+у,,(0, /+1), 2с,+ сэ ' сз+са+эт, (О 0)]+ —, :р, (1 — р,) пп'п [с, + с, + с, + + с, +У,, (т + 1, 0), 2с, +. +сэ+сз+ел+1'ч~(00)] Заменить устройство 1: с,+са-[-У,(О, 1), Заменить устройство /: с, + с, + у (1, 0), Заменить обз устройства: 2с,+сз+~, (О, 0).
улг(1, /) — ш!п (11.18) Мы ищем у . (О, 0)1Аг — ожидаемые средние издержки на одну шипу при изготовлении уту шин, когда процесс начинался при новых устройствах и использовалась оптимальная политика. Еще больший интерес представляет соответствугощая политика замены. Определим ри 1=0, 1, 2, ..., как вероятности успешного изготовления шины устройством, которое уже произвело 1 шин, и допусгим, что зтп величины известны из опыта.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
