XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 36
Текст из файла (страница 36)
В примере 6.5 следует обратить внимание на линейную зависимость трех первых уравнений системы линейных алгебраических уравнений для определения стационарных вероятностей П (2). Это обстоятельство не является случайным, так как в общем случае требуется найти нетривиальное решение квадратной однородной системы линейных алгебраических уравнений (Р« — 1 ) П (й) =0 значения неизвестных в которой неотрицательны, т.е.
П (и) > > О, у = 1, т, а их сумма равна единице. Таким образом, необходимым условием существования стационарных вероятностей для стационарной стратегии с номером й, и = 1, К, является условие ех(Р« — 1 ) =О. Чтобы оценить трудности, связанные с практическим использованием метода полного перебора, предположим, что (см. пример 6.1) у садовника множество 0 допустимых решений состоит не из двух, а иэ четырех элементов: Х1 — решение о невнесении удобрений; Хя — решение о внесении удобрений один раз в сезон; Хз — решение о внесении удобрений дважды в сезон; Хя — решение о внесении удобрений трижды в сезон. В этом случае общее число стационарных стратегий, имеющихся в распоряжении садовника, равно 64.
Сложно перечислить все стационарные стратегии в явном виде. Кроме того, велики вычислительные затраты, необходимые для практической реализации метода полного перебора. 6.3. Принятие решений ари 6еенонечном горизонте планировании 259 Метод итераций по стратегиям без дискоитироваиия. При анализе марковской задачи принятия решений с конечным горизонтом планирования Ф мы использовали понятие оптимального ожидаемого дохода Яд) за этапы с номерами ь', 1+ 1, ..., Ф, вычисляемого при условии, что после 1 этапов изучаемая система о находилась в состоянии о .
При бесконечном горизонте планирования удобнее использовать понятие ожидаемого дохода Р„(~) за этапы с номерами 1, 2, ..., и при условии, что к этапу с номером и+ 1 изучаемая система о будет находиться в состоянии 5. В этом случае, предполагая однородность соответствующей цепи Маркова, для любой конкретной стратегии с матрицей переходных вероятностей Р= (р «) 6 М (Е) и матрицей доходов Я=(г1«) 6 М (И) можно получить матричное рекуррентое уравнение Рч = и+ РР„,, (6.2) при записи которого использованы следующие обозначения: Р„(1) р1 и= Рч(ш) рт и = ~ р «г «, у=1,т. (6.3) Фактически уравнение (6.2) является матричным аналогом рекуррентного уравнения, лежащего в основе метода итераций по стратегиям при конечном горизонте планирования (см.
6.2). Но оно позволяет исследовать асиляпгаотаичесмое поведение изучаемого процесса при неограниченном возрастании числа этапов, т.е. при я — ь +со. Для удобства дальнейших рассуждений введем матрицу- столбец и вспомним, что сумма элементов любой строки матрицы переходных вероятностей Р равна единице, так же как и сумма 260 б. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ всех ее стационарных вероятностей, представленных матрицей- строкой П=(П, ...
П ) ЕМ, (К). Таким образом, Р1 = 1, П.7 = 1. (6.4) А так как матрица-строка П стационарных вероятностей ма- трицы переходных вероятностей Р удовлетворяет уравнению 6.3. Принятие решении при бесконечном горизонте планирования 261 система будет находиться в начале (т1+1)-го этапа.
Но в этом случае Рп(т') = т1Е+ РЯ, т' = 1, т, или Р„= т1ЕУ+ Р, где Р = (Р(1) Р(™)), и УРавнение (6.2) может быть представлено в следующем виде: или, что то же самое, ПР=П, то, умножив уравнение (6.2) слева на матрицу-строку П, при- ходим к равенству П(Є— Рп- ) = П" Таким образом, ожидаемый доход эа один этап при больших значениях номеров этапов безотносительно к состоянию, в котором система 5 окажется в начале следующего этапа, равен о1 Е = Пр = ~) П ру. т=т Если учесть, что при долгосрочном горизонте планирования поведение однородного марковского процесса характеризует его независимость от начального состояния системы то можно предположить, что при больших номерах т1 этапа значение ожидаемого дохода Рп(у) складывается из двух составляющих. Первой составляющей является величина «Е, зависящая лишь от числа рассмотренных этапов и ожидаемого дохода ачале за один этап безотносительно к состоянию системы в на следующего этапа.
Вторая составляющая, ру кото ю обозначим Р(~), полностью определяется лишь состоянием 5т, 5 в котором т1Е,У+ Р = р+ Р((п 1)Е у+ Р) А так как имеет место первое нз равенств (6.4), то мы прихо- дим к матричному уравнению относительно скаляра Е и вектора Р, т.е. имеем систему т линейных алгебраических уравнений тл Е+ Р(у) — ~ рбьР(й) = и,, у = 1, т, (6.5) Км! относительно т+1 неизвестных Е, Р(1), ..., Р(т).
Прн этом, как и в случае конечного горизонта планирования, конечной целью является определение стратегии, приводящей к максимальному значению Е. В связи с тем, что в нашем распоряжении имеется система (6.5), состоящая из т уравнений с т+ 1 неизвестными, оптимальное значение Е не может быть определено за один шаг. Поэтому используют итерационную процедуру, начиная с произвольной стратегии, а затем определяя новую стратегию, дающую лучшее значение Е. Процесс решения завершают, если две последовательно определенные стратегии совпадают.
Итерационный процесс состоит из двух основных этапов, называемых эт«а«ом отленивания «араметров и эт«а«ом Улучшения стратееии. шах(р1 (Х) + Я ~р~ь(Х)Р,Я). Х,еО Таблица 6.8 262 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ Этап оценивания параметров. Предположим, что С = (Х )Ми — множество допустимых решений. Выбираем произвольную стратегию т = (ХИ ХИ ... Х~ ), д =(Х Х ... Х ) гдеХ~ ЕС, у = 1, т.
Используя соответствующие стратегии т, матрицу переходных вероятностей Р(т) = (рря(т)) и матрицу доходов Н(т) = (г ь(з )) и полагая г',(гп) = О, решаем систему линейных алгебраических уравнений Е, + Р,(у) -'~ рз (т) Ре(й) = '~(т) относительно Е, Р,(1),, Е (ен — 1). Этап улучшения стратегии. Для каждогосостояния 5 у = 1, та, находим допустимое решение Х, 6 С, на 11 котором достигается Эти оптимальные решения образуют новую стратегию 1 = = (Х„| Х,з ... Х, ) . Если 1 = т, то стратегия т и является оптимальной. В противном случае нужно обозначить стратегию $ через т и вернуться к первому этапу — этапу оценивания параметров. Отметим, что, согласно (6.5), Е, = р (Х;)+~~~ рьь(Х;)Ре(й) — ~ О) еи1 т.е. задача максимизации на этапе улучшения стратегии эквивалентна задаче максимизации суммарного ожидаемого дохода за один этап по всему множеству допустимых решений С.
Пример 6.6. Вернемся к задаче с садовником цри бескопечном горизонте планирования, рассмотреннои в примере 6.5, и решим ее методом итераций по стратегиям. 6,3. Приинтие решений нри бесконечном горизонте планирования 263 В качестве произвольной стратегии т используем стратегию, исключающую использование удобрений (см. пример 6.5). В этом случае 0,2 0,5 0,3 7 6 3 Р(т) = 0 0,5 0,5, К(т) = 0 5 1 0 0 1 0 0 -1 На этапе оценивания параметров, учитывая, что Ре(3) = = О, получаем систему линейных алгебраических уравнений (см. табл. 6.5, столбец й= 1) ( о 2) Ре(1) — 0~5 Ее(2) = 5 3, + г (1) + (1 — 0,5) Ге(2) = 3, Е,+О Р„(Ц+О Ре(2)= 1, которая имеет единственное решение Е, = — 1, Р,(1) 12,54, Ре(2) = 8.
В рассматриваемой задаче множество С допустимых решений содержит всего лишь два элемента (см. пример 6.3). Результаты соответствующих вычислений на этапе улучшения стратегии приведены в табл. 6.8, где использованы уже найденные значения р,(Х,) (см. табл. 6.5, столбцы й = 1 и й = 2). 6 5 -1 Щт)= 7 4 0 6 3 -2 0,3 0,6 О,1 0,1 О,б 0,3 0,05 0,4 0,55 Еп р+орЕ 1 0(о(1 (6.6) „~+1Р +1Е а=о Таблица 6.9 Е = !1ш Е 4„— - р(1 — оР) 264 а мАРкОВские мОдели пРинятия Решении т Новая стратегия 1= (Хз Хз Хз) предусматривает применение удобрений при любом состоянии почвы. Оиа отличается т от стратегии т = (Х1 Х1 Х1), поэтому возвращаемся на этап т оценивания параметров, полагая т = (Хз Хз Хз) .
Новой стратегии т соответствуют матрицы (см. пример 6.5) которые при г,(3) = 0 определяют следующую систему линей- ных алгебраических уравнений (см. табл. 6.5, й = 2): Е 1. (1 03)Р',(1) — 0,6Р;(2) =4,7~ Š— 0,1 Е,(1) + (1 — 0,6) р; (2) = 3,1, Š— 0 Оба (1)'|РО 4Е (2) = 04 Эта система имеет единственное решение сер Е = 2,26, Г,(1) = 6,75, Г,(2) = 3,79. Результаты вычислений на этапе улучшения стратегии приве- дены в табл. 6.9. б.З.
Принятие решений прн оеенонечном горнэонте плпннрованнн 265 т Новая стратегия 1= (Хт Хз Хз), требующая применения удобрений независимо от состояния почвы, идентична предыдущей, т.е. она является оптимальной. Этот результат совпадает с результатом, полученным методом полного перебора (см. пример 6.5), как в смысле оптимальной стратегии, так и в смысле суммарного ожидаемого дохода за один этап, соответствующего этой стратегии. Отметим, что характерной особенностью метода итераций по стратегиям является его быстрая сходимость к оптимальной стратегии. Метод итерации по стратегиям с дисконтированием. Метод итераций по стратегиям может быть обобщен на случай дисноншированил. Действительно, если о — коэффициент дисконтирования, то рекуррентное уравнение (6.2) при конечном числе этапов в условиях дисконтирования принимает внд где и — число рассматриваемых этапов.
Непосредственно из (6.6) следует, что для любого п Е 1Ч Таким образом, существует предел где Е = (Е(1), ..., Г(т)) и Г(у) — приведенны4, к текущему моменту времени диспонтпироввнныб довод при условии, что система находится в состоянии 5 и функционирует в неограниченном временном интервале, Значит, при большйх значениях т1 значение Е„перестает зависеть от номера ц. В этом 266 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИИ и заключается принципиальное отличие рассматриваемого случал от случал без дисконтирования для ко1ч!рого имеет место равенство Такого результата и следовало ожидать, так как в случае с дисконтированием влияние будущих доходов асимптотически уменьшается до нуля, а приведенный доход и'„с ростом !1 стремится к Г. Исходя из вышеизложенных рассуждений, можно выделить следующие этапы реализации метода итераций по стратегиям с дисконтированием.
Этап оцен иван ия параметров. Для произвольно т выбранной стратегии т=(ХП Х!, ... Х! ), где Хб 60, у = = 1, т, с матрнцей переходных вероятностей Р(т) = (рть(т)) и матрицей доходов Й(т) = (т ь(т)) находим решение системы линейных алгебраических уравнений ~'(у) — Е ртз (т) Р. (й) = и, (т), Ии! Рб(т) = Е Рть(т) (т) Ьи! относительно Р,()с), Й = 1, пт. Этап улучшения стратегии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
