XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 35
Текст из файла (страница 35)
( ) — элементы матриц переходных вероятностей и доходов на 1-м этапе, соответствующих оцениваемой стационарной стратегии, а о — годовой коэффициент дисконтирования. Пример 6.4. Найдя оптимальную стратегию поведения при трехлетнем горизонте планирования без дисконтирования 1см. пример 6.3), садовник решил оценить ожидаемый доход без дисконтирования для стационарной стратегии, реализация которой предполагает внесение удобрении тогда и только тогда, когда состояние почвы плохое. В этом случае 1см. пример 6.2) 0,2 0,5 О,З 7 6 3 Р= 0 0,5 0,5, Й= 0 5 1 0,05 0,4 0,55 6 3 — 2 и остается лишь воспользоваться рекуррентным уравнением динамического программировании: Уз(1) = 0,2 7+ 0,5 6+ 0,3 3 = 5,3, Хз(2) = 0'0+0,5 5+0,5 1= 3, Уз(3) = 0,05 6+0,4 3+0,55. ( — 2) = 0,4, Ь(1) = 5,3 + 0,2.
5,3+ 0,5 3+ 0,3 0,4 = 7,98, З'з12) = 3 + 0 5,3+ 0,5 3 + 0,5 0,4 = 4,7, Ь(З) = 0,4+ 0,05 5,3+0,4 3+0,55 0,4 = 2,09, Л(1) = 5,3+0,2 7,98+ 0,5 4,7+0,3 2,09 =9,87, )~12) = 3+ 0 7,98+ 0,5 4,7+0,5 2,09 = 6,39, ,11(3) = 0,4+0,05 ° 7,98+ 0,4 4,7+0,55 2,09 = 3,83.
Таким образом, при реализации рассматриваемой стационарной стратегии в зависимости от состояния почвы на начальном этапе садовнику следует ожидать суммарный доход в размере 9,87, 6,39 и 3,83 денежных единиц соответственно. б.З. Принятие решений при бесконечном гориэоите планировании 253 6,3.Принятие решений при бесконечном горизонте планирования На практике нередкими являются случаи, когда либо задача принятия решений охватывает весьма значительное число этапов, т.е. Х велико, либо горизонт планирования бесконечен 1Х = оо). В этих ситуациях процедуры нахождения оптимального решения обладают специфическими особенностями, в основе которых — свойства марковских процессов.
Поведение марковского процесса на долгосрочном горизонте планирования, когда 1ч' велико, характеризует его независимость от начального состояния системы. В этом случае будем говорить, что система достигла уетаховившегоел еоетполмиа. Нас будут интересовать решения, для которых соответствующие цепи Маркова допускают существование установившегося состояния изучаемой системы. При дальнейших рассуждениях совокупность этапов, предшествующих этапам функционирования системы в установившемся состоянии, будем называть переходным периодом. В этом параграфе рассмотрим проблему определения оптимальной долгосрочной стратегии марковской задачи принятия решений.
При оценке долгосрочной стратегии целесообразно базироваться на максимизации ожидаемого дохода или минимизации ожидаемых затрат за переходный период, так как при достижении изучаемой системой установившегося состояния эти показатели стабилизируются. Можно указать два основных метода решения задач принятия решений с бесконечным числом этапов. Реализация первого из них связана с перебором всех возможных стационарных стратегий принятия решений. В этом случае оптимальное решение может быть найдено путем оценивания эффективности каждой стационарной стратегии, а сам метод называют методом полмого перебора. Применение метода полного перебора оправдано лишь в тех случаях, когда число элементов множества сэ допустимых решений и, как следствие, число эле- 254 б. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ ментов множества Ь всех стационарных стратегий невелико в смысле вычислительных затрат.
При использовании второго метода, называемого методом игпераций по стратегиям (см. 6.2), трудности вычислительного характера не являются столь значимыми, как при применении метода полного перебора. Для упрощения дальнейших рассуждений мы будем предполагать, что марковский процесс изменения состояний изучаемой системы 5 однородный, т.е. однородна соответствующая цепь Маркова. Таким образом, мы фактически предполагаем независимость матрицы переходных вероятностей и матрицы доходов от номера этапа 1 = 1, оо.
Метод полного перебора. Предположим, что в рассматриваемой задаче принятия решений множество всех стационарных стратегий состоит из К элементов и Рь = (рз„(1с)) 6 М (И), В~ = (г „(й)) е М (Е) — матрицы одношаговых переходных вероятностей и доходов, соответствующие стационарной стратегии с номером й = 1, К, где т — число возможных состояний изучаемой системы 5. Метод полного перебора включает следующие этапы реализации. Этап 1, Вычисление ожидаемого дохода за один шаг при к-й стационарной стратегии для всех возможных состояний системы 5: ;(й) = ~~! р,„(й)г, (й), 3 =1» в=! Этап '2. Вычисление стационарных вероятностей П (й), у = 1, т, матрицы переходных вероятностей Рь, соответствующей стационарной стратегии с номером й = 1, К. Как известно из курса теории случайных процессов (ХЧП1), эти вероятности, если они существуют, являются решением следующей системы линейных алгебраических уравнений: П(й)(Рь — 7 ) =в~, ~> П-(й) =1, бяк , принятие решений при бесконечном горизонте планирования 255 где (~) = (П! (~) Пз(й) ...
П,„(й)) 6 М!,„(Ж), 7,„— единичнал матрица порядка т, а Й!,„— нулевая матрица типа 1 х т. Этап Определение ожидаемого дохода для всех стационарных стратегий: Эт ап 4 . Определение номера й* оптимальной стационарной стратегии из условия Е(к") = тах Е(й). !(ь(к Алгоритм реализации метода полного перебора не нуждается в обосновании нии, поэтому сразу переидем к рассмотрению примера. П име р мер 6.5. В задаче с садовником (см. примеры 6.1 — 6.4) имеется всего восемь стационарных стратегий: 1.
Вообще не применять удобрении. 2. Применять удобрения при любом состоянии пряны. 3. Применять удобрения лишь в том случае, когда почва находится в состоянии 5! (хорошем). 4. Применять удобрения лишь в том случае, когда почва находится в состоянии 5з (удовлетворительном). 5. Применять удобрения лишь в том случае, когда почва находится в состоянии 5з (плохом). 6.
Применять удобрения лишь в том случае, когда почва находится или в состоянии 5!, или в состоянии 5з. 7. Применять удобрения. лишь в том случае, когда почва находится или в состоянии 5„ или в состоянии 5з. 8. Применять удобрения лишь в том случае, когда почва находится или в состоянии 5з, или в состоянии 5з. Как было показано в примере 6.2, матрицы переходных вероятностей и матрицы доходов для стационарных стратегий 256 б. МКРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ с номерами от до мог 3 8 ут быть получены из соответствующих матриц для стационарных стратегий с номерами 1 и 2: й1 —— О 5 1 0,2 0,5 О,З Р1 — — 0 0,5 0,5 0 0 1 Таблица 6,6 На первом этапе вычисляют ожидаемые д д ( ) охо ы и (й) для всех стационарных стратегий (см.
пример 6.3). Результаты вычислений приведены в табл. 6.5. 0,3 0,6 0,1 Рг = 0 1 0 6 0,3 0,05 0,4 0,55 О,З 0,6 0,1 Рз = 0 0,5 0,5 0 0 1 0,2 0,5 0,3 Р4 = 0,1 0,6 013 О О 1 0,2 0,5 0,3 Рв = 0 0,5 0,5 0,05 0,4 0,55 0,3 0,6 0,1 Рв = 0,1 0,6 0,3 0 0 1 0,3 0,6 0,1 Рт — — 0 0,5 0,5 0,05 0,4 0,55 0,2 0,5 О,З Рв = 0,1 0,6 О,З 0,05 0,4 0,55 6 5 — 1 йз — — 7 4 0 6 3 — 2 йз= 0 5 1 й4= 7 4 0 7 6 3 й = 0 5 6 3 — 2 йв= 7 4 0 йт — — 0 5 1 йв= 7 4 0 б.з. Прииетие решений при бееконечнои гориаонте планироиании 257 Таблица 6.6 На втором этапе вычисляют стационарные вероятности П (й) матриц переходных вероятностей Рь для всех стационарных стратегий и всех возможных состояний изучаемой системы. Так, например, для второй стационарной стратегии стационарные вероятности П (2), у = 1, 2, 3, являются решением системы линейных алгебраических уравнений (О 3 1)П1(2) + 0 1Пз(2)+ О 05Пз(2) = 0 О 6П1(2)+ (О 6 — 1)Пз(2)+ 04Пз(2) = О, 0,1П1(2) + 0 ЗПг(2) + (0 55 — 1)Пз(2) = 0 П1(2)+ Пз(2) + Пз(2) = 1.
Результаты вычислений приведены в табл. 6.6. На третьем этапе вычисляют ожидаемый доход Е(й) для каждой стационарной стратегии с учетом результатов, полученных на первых двух этапах реализации алгоритма (см. табл. 6.5 и 6.6). Результаты вычислений приведены в табл. 6.7. На четвертом этапе находят (см. табл. 6.7) Е(й*) = п1ах Е(й) — Е(2) 2 26 258 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИИ Таблица б. У Таким образом, оптимальной является вторая стационарная стратегия, реализация которой предполагает применение удобрений при любом состоянии почвы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
