УПРАЖНЕНИЕ 19.3.3
1. Решите указанные ниже задачи, приняв коэффициент дисконтирования равным а =0,9.
a) Задача упражнения 19.3.2.1.
b) Задача упражнения 19.3.2.2.
c) Задача упражнения 19.3.2.3.
19.4. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Марковскую задачу принятия решений при бесконечном числе этапов как с дисконтированием, так и без него можно сформулировать и решить как задачу линейного программирования. Рассмотрим сначала случай без дисконтирования.
В подразделе 19.3.1 было показано, что марковская задача без дисконтирования при бесконечном числе этапов сводится к поиску оптимальной стратегии s , соответствующей
maxJJ£n>f яР* =я\ я[+ я2+... + <= 1, <>0, i = 1, 2,..., А,
/(1) - 0,б[0,2/(1) + 0,5/(2) + 0,3/(3)] = 5,3, /(2) -0,б[0,1/(1) + 0,6/(2) + 0,3/(3)] = 3,1, /(3) - 0,б[0,05/(1) + 0,4/(2) + 0,55/(3)] = 0,4.
Решением этих уравнений будет
/1 = 8,97,/2 = 6,63,/3 = 3,38.
Результаты, полученные на шаге улучшения стратегии, приведены в следующей таблице.
vf + 0,6[ А< Д1) + Л2Д2) + р\,/(3)] Оптимальное
решение
/ к= 1 к =2 fji) к
1 5,3 + 0,6[0,2 х 8,97 + 0,5 х 6,63 + 0,3 х 4,7 + 0,6[0,3 х 8,97 + 0,6 х 6,63 + 0,1 х 8,97 1 х 3,38] = 8,97 х 3,38] = 8,90
2 3 + 0,6[0 х 8,97 + 0,5 х 6,63 + 0,5 х 3,1 + 0,6[0,1 х 8,97 + 0,6 х 6,63 + 0,3 х 6,63 2 х 3,38] = 6,00 х 3,38] = 6,63
3 -1 +0,6(0x8,97 + 0x6,63 + 1 хЗ,38] = 1,03 0,4 + 0,6[0,05 х 8,97 + 0,4 х 6,63 + 0,55 х 3,37 2
х 3,38] = 3,37
Так как новая стратегия {1, 2, 2} идентична предыдущей, то она оптимальна. Заметим, что при дисконтировании оптимальная стратегия исключает применение удобрений при хорошем состоянии системы (состояние 1).
где S - множество всех возможных стратегий. Здесь я, »= 1,2,...,т, представляют
установившиеся вероятности марковской цепи Р*. Подобная задача была решена в подразделе 19.3.1 полным перебором всех стратегий s.
Приведенная задача служит основой для формулировки марковской задачи принятия решений в виде задачи линейного программирования. Однако необходимо преобразовать переменные задачи таким образом, чтобы оптимальное решение автоматически определяло оптимальное действие (альтернативу) k, когда система находится в состоянии i. Совокупность всех оптимальных действий определяет оптимальную стратегию s*.
Это реализуется следующим образом. Введем обозначение: q) - условная вероятность выбора альтернативы k, когда система находится в состоянии i. Тогда задачу можно представить в следующем виде.1
Заметим, что вероятности ptj являются функциями выбранной стратегии и, следовательно, конкретных альтернатив k этой стратегии.
Ниже будет показано, что эту задачу можно преобразовать в задачу линейного программирования путем соответствующих подстановок, включающих q\. Но следует отметить, что приведенная выше формулировка эквивалентна исходной формулировке задачи из раздела 19.3.1 только при условии, что q\ = 1 для одного k при
каждом £, так как только при этом сумма X*-i*v* будет сведена к v* , где k - выбранная оптимальная альтернатива. Предлагаемая здесь линейная задача учитывает это условие автоматически.
Обозначим wlt = я.<7* для всех < и к. По определению величина wit представляет собой совместную вероятность пребывания в состоянии i и принятия решения к. Из теории вероятностей известно, что
при ограничениях
%j = ЕЯ<Л/ У = 1. 2,т,
л, + я2 + ... + Кт = 1, ql+ql+.-. + q* =\, / = 1, 2, я, > 0, q. > 0 для всех / и к.
Следовательно,
4i =
Поэтому очевидно, что ограничение
щ = 1 можно записать в виде
т К
1=1 *=1
1=1 *=1
1 Здесь и далее К - количество возможных альтернатив. - Прим. ред.
Ограничение =1 также автоматически вытекает из способа определения q)
через Wjt. (Проверьте!) Таким образом, задачу можно записать в следующем виде.
т К
Максимизировать Е = vf wa
при ограничениях
= 1 *=1
т К
11", =1,
-1 *=i
wlt>0, i = l,2,...,m; к = 1,2,-,К.
Сформулированная задача представляет собой задачу линейного программирования с переменными w,t. Покажем, что ее оптимальное решение автоматически гарантирует, что q\ = 1 для одного k при любом i. Заметим, что в задаче линейного программирования имеется т независимых уравнений (одно уравнение, соответствующее я = яР, избыточно). Следовательно, задача должна включать т базисных переменных. Однако можно показать, что wlt должно быть строго положительным по меньшей мере при
одном k для каждого /. Из этих двух утверждений можно заключить, что величина
может принимать только два значения (0 или 1), что и требовалось доказать. (Фактически полученный выше результат показывает также, что я, = X*-ivt<* =VV > где k - альтернатива, соответствующая wjt > 0 .)
Пример 19.4.1
Ниже приведена формулировка задачи садовника без дисконтирования в виде задачи линейного программирования.
Максимизировать £ = 5,3w,, + 4,7wl2 + 3w2l + 3,lw22 - w31 + 0,4w32 при ограничениях
vvM + w12-(0,2wM + 0,3wl2 +0,lw22 + 0,05w32) = 0,
w2l + w22 -(0,5wu +0,6w]2 + 0,5w2] + 0,6w22 + 0,4w32) = 0, w31 + w32 -(0,3wn + 0,lwl2 + 0,5w2l + 0,3w22 + w3, + 0,55w32) = 0, w„ + w,2 + w2l + w22 + w3l + wi2 = 1, wlt 2. 0 при любых i и к.
Оптимальным решением является wn= w2l= w3l = 0, w12= 0,1017, w22 = 0,5254 nw32 = 0,3729. Это означает, что q] =q\=q] = \. Таким образом, оптимальная стратегия требует выбора альтернативы 2 (к = 2) при /= 1, 2 и 3. Оптимальное значение Е равно 4,7x0,1017 + 3,1x0,5254 + 0,4x0,3729 = 2,256. Интересно отметить, что положитель-