XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 34
Текст из файла (страница 34)
Если же садовник принял пр нял решение о применении удобрений,то переходные вероятности задаются матрицей нагляд о иллюстРиРУющей улучшение состояния почвы в следующие годы, В рассматриваемом примере множество допустимых решений 0=1Х 1' 1 г,, где 1 решение о невнесении удобрении, а Хр — решение о внесении удобрении.
Таким образом, для й= 1, Ф матрица переходных вероятностей равна С переходом системы 5 из одного состояния в другое связана мотприца дохода В(1(ХО,) = (гул(1(ХН,)) е М (Е), в которой элемент г л(1(ХН,) есть доход (положительное значение) или убыток (отрицательное значение) эа 1-й этап. Прн этом доход или убыток за 1-й этап связан лишь с переходом системы иэ состояния 51, в котором она находилась после (й-1)-го этапа, в состояние 5ь при принятии решения Х, Е С. ц Величина ш ),~,рул И(Х~ ) гхл(ь ~ Хг ) (6 1) ь=1 пределяет озмидаемьлц довод за 1-й этап, если по е ( — 1)- этапа система находилась в состоянии о б и ыло принято К, Е 6'. Заметим, что ожидаемый доход связан решение Х 244 В.
МЛРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ Пример 6.2. Продолжим анализ задачи с садовником 1см. пример 6.1) и для наглядности будем считать, что матрицы доходов 1в условных денежных единицах), соответствующие матрицам переходных вероятностей Р, и Рз, имеют следующий вид: И1 — 0 5 1 Нз 7 4 0 где в матрице доходов Йз учтены затраты, связанные с внесе- нием удобрений, и КЯХО,) = ' (л„ 21 х,,=х,; ХО, = Хз.
лишь с переходами системы иэ одного возможного состояния в другое при фиксированном допустимом решении. Далее в качестве принципа оптимальности, совпадающего в рассматриваемом случае с критерием оптимальности, использована максимизация ожидаемого дохода за Х этапов. При этом специфика решения задачи прежде всего связана с тем, будет ли число этапов Х конечным или нет. В соответствии с этим рассматривают задачи принятия решений с конечныль горизонпьоль планирования, когда Ж < 1ю, или с бесмонечныль горизонпьоль планирования, когда Д1 = оо. Необходимо отметить, что „лицо, принимающее решения", может интересовать величина ожидаемого дохода при заранее определенной стратегии поведения в случае того или иного состояния системы.
Так, например, „лицо, принимающее решения", может считать, что если после 11 — 1)-го этапа система находится в состоянии 5,, то безотносительно к конкретному значению 1 всегда необходимо принимать решение Х' Е С. В этом случае говорят, что процесс принятия решений описывается спьационарнььми спьрапзегияльи. При этом каждой стационарной стратегии будут соответствовать свои матрицы переходных вероятностей и доходов.
В З ПРннятне ешенвм Р аРи конечном гьрмзокгь аланцр~вани~ 245 арактер задачи принятия решений, стоящей перед садовником, прежде всего связан с тем б удет ли его деятельность продолжаться конечное число лет 11ч' < оо или он и его наследники будут заниматься садом всю свою жизнь 1% = оо . Но в любом случае садовнику необходимо выбирать наилучшую ст атегию по е р в дения ~вносить или не вносить удобрения) чвы, харакпри известных результатах химического,анализапочв теризующих ее состояние с целью максими с мизации ожидаемого дохода за Ж лет. частности, садовник может решить вносить удобрения тогда и только тог а д, когда состояние почвы плохое.
Этой 1одной из возможных) стационарной стратегии соответствуют свои матрицы переходных вероятностей Р и доходов Н: Р = 0 0,5 0,5 , В = 0 5 1 Они отличаются от матриц Р и Н 1 лишь третьими строками, заимствованными из матриц Р В з н з соответственно. 62.П ин р ятие решении при конечном горизонте планирования При конечном горизонте планирования (1У < оо) на невскую задач и и я у р н тия решений с принципом оптимальности, который состоит в максимизации ожидаемого дохода за 1ч' этапов, можно п е ст р д авить как задачу динамического и аг а мирования. го програму г,(у) — оппьилваяьный ожидаемый Действительно и сть доход 1т.е.
а д 1 н илучший в смысле используемо го принципа оптимальности) заэтапы с номерами 1,1+1, ... 1У п и после ~1 — 1'-го этапа ми 1, 1, ..., при условии, что после 11 — )-го этапа изучаемая система э находится тся в состоя, где у' 1,, ..., т). Так как горизонт планирования конечен, то для оптимальны ных ожидаемых доходов должны быть Лс!+!О) Б О, у = 1, т.
шах ~ р «(1+ 1(Х! ) г,+, (ь) " "«=1 1=О,Д(-1, 2=1,т, А+!(1) Ае ! ((е1 !!+!(пс1 1( (Х, 1ээ, Х, =Х, Этап !+1 Этап с Рнс. 6.1 246 к мйРкОВСКИе МОДелИ пРИНЯТИя РЕШЕНИЙ выполнены естественные условия: Оптимальный ожидаемый доход Д(у') на этапах с номерами 1, 1+ 1, ..., Ж складывается из двух составляющих. Первая составляющая — оптимальный ожидаемый доход на (!+1)-м этапе, обусловленный одним лишь переходом системы 5 из состовниЯ Еэ, в котоРом она нахоДилась на 1-м этапе, в любое допустимое состояние 5«, и = 1, т, на (1+1)-м этапе (рис. 6.1). Эта составляющая равна (см. (6.1) ) со шах 1,(Х1,), Р,(Х!.) = ~! рэ«(1+ 1(Х1,) гэ«(1+ 1) Х!1), Хс.нС «=1 где рэ«(1+ 1)Х1,) — условная вероятность того, что после (1+1)-го этапа система 5 будет находиться в состоянии Е«, если после 1 этапов она находилась в состоянии 5 и было принято допустимое решение Х1,, г,«(1+ 1)Х1,) — доход или убыток, связанный лишь с переходом системы из состояния 5„ в котором она находилась после 1 этапов, в состояние 5« на (1+1)-м этапе в результате принятия решения Х1, из множества допустимых решений 6.
Вторая составляющая оптимального ожидаемого дохода 1!(~) определяется совокупностью оптимальных ожидаемых до- Е 2 П и!!итие Р Ре'пений пРи конечном г риз нте планирования 24Т ходов у1, й '+ ' с с учетом переходных вероятностей Р, (1+ЦХ!), й=1 В результате проведенных рассуждений мы приходим к рекуррентному уравнению динамического программирования (см. 2) с конечным числом этапов, связывающему оптимальные ожидаемые доходы Яу), у = 1, т, и 1!+! (к), к = 1 т: с Л(У) = шах (и,(Х1,) + ~) р «(1+ 1(Х1,) 1!+1(к)(, «=1 При этом напомним, что д,„+!(ь) = О й — 1 (Х1,) =,'! рх«('+1(Х,,) х«((+1(Х,), 1 «=1 П име 63 Ве е р ..
рн мся к задаче с садовником, которую мы начали рассматривать в прймерах 6.1, 6.2, н предположим, что он планирует прекратить занятие садоиодством через три года и за этот период хочет получить максимальный доход. Для этого ему необходимо выработать апти,мальную страп1егию поведения (в смысле максимума суммарного дохода). Напомним, что изучаемая система (сад) имеет три возможных состояния, определяемые состоянием почвы: 5 1 хорошее, Ез — удовлетворительное, лз — плохое.
Множество опустимых решений садовника: С = (Х Х, Х з, где , — решение о невнесении удобрений, а Хз — решение о внесении удобрений. Матрица переходных вероятностей имеет вид Таблица 6.2 где а зиагприца дохода имеет вид Х,, =Х„. Х,,=Х, Таблица 6.3 где Йг= 7 4 0 В! — — О 5 1 Таблица 6.4 из (Хя ) + ~.,' р, ! (! + 1 ) Хя ) Уг (1) Оптимальное решение !гц 5 3+02 819+ +05 561+ + 0,3 2,125 = 10,38 3+ 0 8,19+ + 0,5 5,61+ + 0,5 2,125 = 6,87 — 1+ О 8,19+ +О 561+ + 1 2,125 = 1,13 4,7+ О,З 8,19+ + 0,6. ог,61+ +0,1 2,125=10,74 3,1+ 0,1 8,19+ +06 561+ +0,3 2,125 — 7,92 0,4+ 0,05 . 8,19+ + 0,4 5,61+ + 0,55 2,125 = 4,23 10,74 Хг 4,23 Хг 248 6.
МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИЙ 0,2 0,5 0,3 0,3 0,6 0,1 Р! — — 0 0,5 0,5 , Рг = 0,1 0,6 0,3 0 0 1 0,05 0,4 0,55 В ассматриваемом случае горизонт планирования !ч' = 3, а эле- Р менты матриц доходов и переходных вероятностей не зависят от номера этапа. Воспользовавшись матрицами Р!, Рг, Н!, ггг и их незави- симостью от номера этапа, вычислим ожидаемые доходы (6,1), обусловленные одним лишь переходом изучаемой системы 5 иэ одного возможного состояния в другое, при различных вариан- тах допустимых решений из множества С: р! (Хг) = 0,2 ° 7+ 0,5 ° 6+ 0,3 ° 3 = 5,3, рг(Х!) = 0 О+0,5 5+0,5 1 = 3, рз(Х!) =0 О+О О+1. ( — 1) = — 1, Рг(Хг) =О,З 6+0,6.5+0,1. ( — 1) =4,7, рг(Хг) = 0,1. 7+ 0,6. 4+ 0,3 0 = 3,1, рэ(Хг) =005.6+04 3+055 ( — 2) = 04.
Для наглядности воспользуемся табличным алгоритмом реше- ния рассматриваемой задачи (табл. 6.2 — этап 3, соответ- ствУющий 7з(7), табл. 6.3 — этап 2, соответствУющии Ь(7), табл. 6А — этап 1, соответствующий 7г(3) ), при этом нумера- ция этапов „с конца" обусловлена определением оптимального ожидаемого дохода Щ). б.2. Принятие решений при конечном горизонте пяанироиания 249 где !!ч+! (!т) е— г О, й = 1, т, и 1 а= 1+ зе т=1,!т', 1=1,т, где ))я+!(й) = — О, й = 1, т, 1» Р1(!) = ~~ Рхь(!)г Я(!), ь=! 1=1,т, 1=1,т, 250 6. МАРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИИ Из отинимального Решения следует, что первые два года садовник должен применять удобрения при любом состоянии системы, т.е. вне зависимости от результатов химического анализа почвы (первые два года оптимальным является допустимое решение Хя для всех возможных состояний), но на последнем этапе (третий год) ему следует применять удобрения лишь при удовлетворительном (зз) и плохом (зз) состояниях почвы.
В этом случае суммарный ожидаемый доход составит 10,74 при хорошем состоянии почвы в начале первого года, 7,92 — при удовлетворительном и 4,23 — при плохом состоянии почвы в начале первого года. Заметим, что при нахождении оптимальной стратегии поведения садовника в примере 6.3 мы воспользовались тем, что по самой природе рекуррентного уравнения для определения оптимальных ожидаемых доходов Ц(у)) их значения вычисляются итеративно.
Именно поэтому рассмотренный метод решения задач дискретного динамического программирования называют методом итераиит2 ио стратегиям. В марковских моделях принятия решений матрицы поощрений (тя(! ~ Х!,,)), которые в соответствии со сложившейся терминологией мы назвали матрицами доходов, в общем случае не обязательно отражают доходы в прямом смысле этого слова. Но если матрицы (Н(т~Х!,,)) действительно являются матрицами доходов, а длительность каждого этапа — год, то при нахождении оптимального решения необходимо учитывать дисконтирование путем введения годового коэффициента дисконтпиров ани.в где зт — годовая норма процента и 0 < ст < 1. Годовой коэффициент дисконтирования указывает на то, что Р денежных единиц будущего года равны стР денежным единицам настоящего года.
Поэтому в рассматриваемом случае при построении 6.2. Принятие решений при конечном горизонте нланироввння 251 марковской модели принятия решений необходимо использовать коэффициент дисконтирования ожидаемых оптимальных доходов для последовательных этапов, вследствие чего значения (1!(з)) — приведенные величины ожидаемых оптимальных доходов по всем этапам. При введении коэффициента дисконтирования исходное рекуррентное уравнение динамического программирования с конечным числом этапов, связывающее оптимальные ожидаемые доходы 1!(1), ! = 1, т, и !т+! (1), у = 1, т, имеет вид 1в 1!(~) = шах (ру(Х!,)+а ~! р я(т+1~Х!,,)Ль!(к)), ь=! з=1,1з!, у=1,т, р,(Ху,) =~У рть(т+1~Х!)грь(т+1~Х!), з'=1,т. ь=! Решение задачи принятия оптимального решения с учетом дисконтирования ничем не отличается от решения аналогичной задачи, но без учета дисконтирования, т.е.
при а= 1. Естественно, что в общем случае оптимальные решения, полученные с учетом и без учета дисконтирования, могут различаться. Следует также отметить, что рекуррентные уравнения динамического программирования могут быть использованы для оценки любой сптационарной стратегии. В этом случае с учетом дисконтирования имеем 1)(У') = и,(!)+а~ Р Ь,(!) 1г ь!(Iс), я=! 252 б. МЛРКОВСКИЕ МОДЕЛИ ПРИНЯТИЯ РЕШЕНИИ а р.ьЯ и гбь(1)— .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
