XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 37
Текст из файла (страница 37)
Для каждого состояния 5 изучаемой системы о', у =1,то, находим допустимое Решение Хеб 6 С, на котоРом достигаетсЯ шах(и (Х;)+се,~ Рть(Х!) Р ((с)) х!ес т Эти решения образуют новую стратегию 1= (Хл, Х., Х,„) . Если 1 = т, то вычисления завершены и т — оптимальная стратегия. В противном случае обозначаем стратегию 1 через т и возвращаемся к первому этапу. Пример 6.7, Решим задачу с садовником при бесконечном горизонте планирования (см. примеры 6.5, 6.6) с учетом 6.3. Принлтие решений при бесконечном гориаонте планирования 267 дисконтирования, полагал, что коэффициент дисконтирования ст = 0,6. ч' В качестве начальной выбираем стратегию т = (Х! Х! Х!) ! исключающую использование удобрений. Матрицы Р(т) и К(т) (они приведены в примере 6.6) определяют систему линейных алгебраических уравнений (1 — О 6.02) Р(1) — Об 05Г,(2) — 06 ОЗР',(3) = 53, -О,б О Р,(Ц+(1-0,6.0,5)Р,(2)-0,6 0,5Р,(3)=3, -0,6 .
0 Р,(1) — 0,6 0 ~;(2) + (1 — 0,6 1) Р,(3) = — 1, решение которой не вызывает затруднений: Р,(1) б,б, Р',(2) 3,2, Р,(3) ж -2,5. Результаты вычислений на этапе улучшения стратегии отражены в табл. 6.10, в которой использованы уже найденные значения и (Х;) (см. табл. 6.5, столбцы й = 1 и й = 2) и переходные вероятности р ь(Х,), являющиеся элементами матриц Р; = Р(Х;) (см. пример 6.5). Таблица 6.10 Таблица 6.11 Таблица 6.19 268 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИИ т Новая стратегия 1 = (Хг Хз Хз), тРебУющал пРименениЯ удобрений при любом''состоянйй поончвь~, отличается от предыдущей. Поэтому полагаем т =1 и возвращаемся на этап оценивания параметров, записав систему линейных алгебраических уравнений на основе матриц Рг и Вз (см. пример б 5): (1 — 06 03)Р,(1) — 06.06й;(2) — 06 01Г„(3)=4,Т, -О,б .
0,1г;(1) + (1 — 0,6 . 0,6) Г,(2) — 0,6 0,3 Р,(3) = 3,1, — О,б 0,05 Р,(1) — 0,6 0,4 Г,(2) + (1 — 0,6 0,55) Р„(3) = 0,4. Таким образом, в рассматриваемом случае г',(1) 8,9, г',(2) ж 6,6, Р,(3) 3,4. Результаты вычислений на этапе улучшения стратегии отра- жены в табл. 6.11. т Новел стратегия 1= (Х~ Хз Хз), требующая применения удобрений лишь при удовлетворительном и плохом состояниях 6.3, Принатие решений при оеекоиечнои горизонте нланиронания 269 почвы, отличается от предыдущей. Поэтому полагаем т =1 и возвращаемся на этап оценивания параметров, записав систему линейных алгебраических уравнений на основе матриц 1за и Ва (см. пример 6.5): (1 — 06 02) г',(1) — 06 Офг,(2) — 06.03Р;(3) = 53, -0,6 0,1г',(1) + (1 — 0,6 0,6) Г,(2) — 0,6 . 0,3 г',(3) = 3,1, — О 6 О 05 Р,(1) — 0 б .
О 4г',(2) + (1 — О 6 - О 55) Р;(3) = О 4. Таким образом, в рассматриваемом случае Ге(1) 9,0, Р'т(2) 6>6, 1ге(3) 3,4. Результаты вычислений на этапе улучшения стратегии отра- жены в табл. 6.12. Так как 1= (Х~ Хт Хз) = т, то оптимальнзл стратегия найдена, и исходнзл задача решена полностью. ф 271 Пу(т)=1, т~Т. 1=1 П, (т) ) О, 7' = 1,,п. Таким образом если Е(т) = П(т)и(т), (Х1)-',» р,«(Х1,), (Х,). «=1 т=(Х1, Х1, ... Х1 ) бТ е = '~,П, Д-,;;) 1=1 гм1 при ограничениях Р(т) = (р «(т)) б М,„(К), П,=~ П,„...
«м1 Тй М ,' П,=1; 3=1,т; 3=1,т; П(т)(Р(т) — 7 ) =91 П,~0, 91 ~30, 1=1,т, 1=1,М 270 а мАРкОВские МОдели пРинятия Решений Сопоставляя результаты теоретических рассуждений и вычислительных экспериментов (см. примеры 6.6, 6.7), приходим к выводу о том, что дисконтирование может влиять на оптимальную стратегию. 6.4, Марковская задача принятия решений и метод линейного программирования Вернемся к марковской задаче принятия решений при бесконечном числе этапов без дисконтирования.
Предположим, что С = (Х;ф — множество допустимых решений и Р(Х1) = = (р «(Х,)), В(Х;) = (т «(Х;)) 6 М К вЂ” матрицы переходных вероятностей и доходов, соответствующие допустимому решению Х; б с *, а т — число возможных состояний изучаемой системы 5, представленных множеством (5 ),. Тогда величина ожидаемого дохода при принятии допустимого решения Х1, для состояния Е определяется равенством Пусть теперь Т = С" — множество стационарных стратегий, причем стационарной стратегии соответствует матрица переходных вероятностей для которой матрицу-строку стационарных вероятностей П(т) = (П1(т) Пз(т) ...
П (т)) можно определить как решение однородного матричного уравнения а . етая яннемного программирования удовлетворяющее очевидным условиям и(т) = (и1(Х1,) из(Х1,) ... и (Х, ))т то ожидаемый дохоД за один этап безотносительно к состоя нию, в котором система 5 окажется на следующем этапе п и Р реализации стратегии т 6 Т равен и в соответствии с методом полного перебора оптимальная стратегия т* Е Т определяется из условия Е(т') = шахЕ(т).
тЕТ Для преобразования рассмотренной задачи к задаче линейного программирования воспользуемся следующими соображениями. ! Пусть д. — условнэл вероятность того, что будет принято допустимое решение Х; е С, если изучаемая система 5 находится в состоянии 5 . Обратимся к задаче минимизации скалярной функции 273 п1 М е = ~> ~> и~~!о.!, 1=1 !=! /с=! ~=! !оу! = П!!1!, ео; > О, у = 1, и!, ' = 1, М. Таким образом, !о!1 % М и ограничение Ч'=, б(0, 1), !о; ~ П,=1 ри! Что и требовалось доказать. эквивалентно ограничению п1 М ЕЕ" =' ри! !=! 272 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ где М вЂ” ' число элементов множества допустимых решений; я!, к, ' = 1,, — функции выбранной стратегии и, как следствие, конкретн ых допустимых решений из множества С = = 1 ъ!е! !', и.
= и. = (Х ~м и1 = и (Х;). Отметим, что эта задача эквивалентна исходной лишь при условии, что д — д ф р ' = 1 ля фиксированного !, при каждом у = 1, тп, так как в этом случае значение совпадает со значением и ', где Х„ Е с' — оптпим ние для состояния Я, изучаемой системы о'. Для любых 3 = 1,т и ! = 1,М полагаем где !о; — вероятность пребывания системы 5 в состоянии 5 при принятии решения Х; б С. При этом для любого у =1, т М ~- „.
= ~ П1~,* = И, ~ Ц,' = И,. ои! 1=! бдк Метод лииейиого програииироааииа Скалярная функция е может быть представлена в виде а исходная задача может быть сформулирована в виде задачи линейного программирования с переменными ео;: п1 М ~> ~ и (Х!)!от, -+ тах; т=! з=! М п1 М ~!о„— ~ ~~ рь (Х )!оы = О, ! = 1, т, Для завершения наших рассуждений осталось показать, что оптимальное решение гарантирует выполнение равенства е* = 1 для фиксированного ! при любом у = 1, тп. Система ограничений задачи линейного программирования содержит вт + 1 ограничений типа равенства, одно из которых является избыточным (см.
6.3). Следовательно, в задаче должно быть ги базисных вере,венных, н можно показать, что вероятность ватт должна быть строго положительной по меньшей мере при одном ! для каждого у', т.е. ПримеР 6.8. Сформулируем задачу с садовником в виде Ьадачи линейного программирования, для чего воспользуемся целевой функцией Е6 Р.(7), 1=1 7' = 1,2,3, 1= 1,2. ~я > о Т, ~м,,=1, 1=1 1=! 7=1,т, 1=1,М, ш М 7=1,т, й=1 1=! мгг>0, 7'=1,1п,1=1 ц 274 б. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ (Х ) входящими в матрицы переходрыми вероятностями ртй(,), Р, = Р(Х;) (см. пример . ), а а 6.5) также вычисленными значениями ожидаемых доходов (см. табл..
): . 6.5): 53ь!11+ 47!о!2+ Зь!21 + 3,1о!22 — ~21 + (1 О 2) ш1, + (1 — О,З) 1о12 — 0,1ыгг — 0,05~22 = 1о =0 \ 15 0 6 +(1 — 0,5)ь!21+(1 — 0,6)ь!22 — О '1шзг = 0 -О 3!о11 — 0,1 !о!2 — 0,5ь!21- О,Зь!22+ (1 — 1) 1оз1+ (~,ф) зг ее -0,3!о!!в Для этой задачи оптимальным является решение: о!11 = Т =( 2 2 2) * = (Х Х Х ), что совпадает с результатом, полученным методом полного перебора (см. пример 6.5) 4й В О.З мы показали, что марковская задача принятия решений с дисконтированиеле фактически связана с рекуррентными уравнениями и Р;Ц) = шах(р (Х;)+оч! р,й(Х1) Р;(6)), у = 1, т, й=1 которые могут ыть з б аменены эквивалентной системой нера- венств Р,(1) > ~~ р, (Х )РгЯ+р!(Х') ,' = 1, И, (6.7) при услов вии что функция стратегии (7) д Р (') остигает своего а- наименьшего значения,.
(1) Р ° ( !) на множестве стационарныхстртегий Т при л ом 7' = юб ' = 1 т. При этом, если воспользоваться б.4. Метод линейного программировании где произвольные постоянные 6-, 7' = 1, т, положительны, то становится понятным, что ее минимизация с учетом ограниче- ний (6.7) типа неравенства обеспечивает также и минимальное значение функции Р,(7) при 7 = 1, т. Но при этом задача ти 6; Р,(7') -+ ппп; 1=1 РгО) — о'Яр„(Х1) Р,(й) >;(Х!), йм1 в общем случае не является стандартной задачей линейного программирования, так как функции Р,(7) не ограничены в знаке.
Но двойственная к ней задача относительно перемен- ных и!!ч р! (Х;)ь!!ч — ~ !пах; 1=1 ем1 М и М ;):!ч-о,~,',у р,й(Х!)мй,=6„ является стандартной задачей линейного программирования. При этом ее целевая функция имеет тот же вид, что и в аналогичной задаче линейного программирования без дисконтирования. А зто обстоятельство позволяет сохранить содержательнУю интеРпРетаЦию пеРеменных ь2!ч. Пример О.Э. Рассмотрим задачу с садовником, в которой коэффициент дисконтирования равен о = 0,6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
