И. В. Коннов
Многошаговые процессы
принятия решений
Казань
2004
Печатается по решению
ыселамия кафедры прикладной математики
К л и нс ко го государственного университета
Протокол Ns 5 от 4.02 2004 г.
Автор
Профессор И.В.Коннов
Рецензент
Доцент кафедры прикладной математики
Р .Ф .Хабибуллин
Многошаговые процессы принятия решения:
1етодическая разработка / И.В.Коннов. — Казань
дзэнский государственный университет, 2004. — 42 с.
В методической разработке собран теоретический и
ллюстративный материал, входящий в состав нескольких
урсов, читаемых автором на факультете вычислительной
атематики и кибернетики КГУ. Этот материал освещает
‘матику, связанную с управлением многошаговыми
терминированными и стохастическими динамическими
кггемами на основе метода динамическогоо
ю грамм и рован ия. В работе описаны общие принципы
строения метода динамического программирования,
товия его применения, а также ряд наиболее важных
и клади ых задач.
Работа может быть рекомендована студентам старших
эсов факультета ВМК, а также аспирантам и научным
ютникам, заинтересованным в изучении подобных задач.
НАУЧНАЯ БИ5ЯИ0Т КА
занский государственный
иверситет, 2004
I.	Детерминированные процессы принятия решений
Вначале рассмотрим процессы управ; и? истемамя при отсутствии
неопределенных факторов Одним из наиболее общих подходов к решению
таких задач является иетсх) сгтш m ruwrwi vu прогр&ммироа&пш,
предложенный Р Веллманом
1.1.	Основы метода динамического программирования
Итак, рассматриваются системы, состояние которых меняется по
времени и для достижения поставленной пели управ. ения такими ~ем ам н
решения необходимо принимать последовательно, т.е -еод ира’чо
Типичными примерами являются управление движу тдичся объектам»*,
(автомобиль, самолет. пароход и т.п.), управление предприятвем, фермой и
т.д. Можно изучать процессы с непрерывным и дискретным временем
Выбор способа зависит от особенностей конкретной зада- - 'гричдипы
решения остаются неизменными. Для управления эк ено ми-ее «ими
объектами в большинстве случаев используется ~искре"гное время, поэтому
данный способ будет основным, а процессы с непрерыв ным врече -е м будут
использоваться для иллюстрации
Итак, в любой момент времени t состояние системы 'олностыо
определяется набором характеристик, называемых фазовыми координатами
и представляемых вектором х(7)из так называемого тазового п. остранства.
поэтому изменение состояния системы можно рассматривать как движение
точки в фазовом пространстве (см. рис.1). В случае обычного движения
объекта фазовыми координатами являются его координаты в некоторой
системе отсчета, значения скоростей и тд., в случае экономического объекта
- номенклатура выпускаемых изделий и используемых ресурсов, наличие и
состояние оборудования и т.п.
3
Рис Л. Движение в фазовом пространстве:
X) непрерывное время.
Б^ дискретное время
В случае непрерывного времени значения вектора—функции и (t/ описывают
некоторую кривую в фазовом пространстве, называем) ю фазовой
траекторией, в случае дискретного времени они образуют последователь-
ность (конечную или бесконечную), обычно для равных промежутков
времени, на которые делится рассматриваемый период.
Если система управляемая, то в каждый момент времени, помимо
фазовых координат х(г), существуют характеристики, значения которых,
задаваемые вектором u(t), влияют на траекторию движения: например,
положение рулей - при обычном движении объекта, режим работы,
стратегия закупок ресурсов и продажи товаров - для экономических
объектов. Рассмотрим случай полной управляемости. когда текущие
значения состояния х (f) н управления u(t’) полностью определяют
состояние системы в следующий момент времени. Таким образом, начальное
состояние х0 = х (t0) и вектор—функция u(t) , t > 0 полностью определяют
всю траекторию х (г), г к 0.
Движение системы обычно оценивается функцией /, задаваемой на
траекториях движения системы, в силу гипотезы полной управляемости ее
значение также однозначно определяется начальной точкой х^н
управлением и( • Л поэтому функция f называется критерием кичегж ~
4
\njh/мнения J 1»йм образом м >M' им гавить идя**» <xj < "гмм«аым«
уПрли ivHHH iHH-iMH'in t <ц < и< *гмой ижЯгм f>pr ьц>инсм н«чалм<«
С<К 1ОЯИИИ < ГЯ> 'Н brti fop «*. . о Лк • /, • O?'JpU обесЖГЧМЯМГ’ МВВКЯЗ-
маЛЬНОС «И «некие фу ни ИИ / ь ;• и -	-г -г^иорим
систомы но сравнению со всеми д; • ими трос»горнами
РлрабоТКа >ффса гивни •	м«--« .•••,	;с_. <rr*a :»«л*м_*иь)3	**,»чм
МНИСНЛ Г 1ДВИЫМ CXLp.iv М VI ДОГИ. -НИТСЯЫ1ЫА *о*ИЙ ЖТ>фЫМ
удовлетворяют функиии • I, • •	Про . <ма ДООМТ в том «гнобм
разработать метод, пригодный при минимальном	грсбованк*. Тл два
весьма общих классов м.1Л О <н .	' 
разработан Р.Веллманом. Этот метод, пгчмвпий мгмгЮпм А——
программирования^ дополнительно требует тнв ижптоста мевево*
функции /, та если траектория соедммяет точки А а В  яромягт черо
точку С, то значение функции / на криво* АВ рммо сумме «мяв*
функции / на ее частях АС м СВ	й	»<-
для многих важных в прикладном отношсии»- ..	«*	• • *
применимость метода без обычных усяпви* ж|| Г'ШВф5«иггш.
рассмотрим простой пример.
Пример 1.1. Предположим, что система в любо* ыоыежт вреяясш момг
находиться в одном из т состояний, переход кз согтолгаа . в ростоомс /
за один Л-н этап дает доход • ‘ . Зная на _ : •. с.<- ямже %  - -.ее
количество этапов V, требуется выбрать гас» -. г*-.- ддеяемая
обеспечивающую наибольший суммарным доход, Итак. ? _анг- м сл>ч*г
рассматривается система с дискретным временем	cdctwi в
непосредственном вы'оре следующего состоямжя. кроме тага, w£.*>tmb
функция, очевидно, аддитивна. Тем не менее, лростеАшмй «.t <х* вых* «
управления по принципу 'Текутжнй намлучкжй" может щ—l.iu с овмм^
плохому показателю в сумме. Напшер.
5
'(ГЬ/Ц'-тах/ХУ  3> /мм ж2’ ,o вибирипся HU первом лице переход
/
(2 >3), но если mm ffi'* min fl1/ ЮО, то по сумме уже двух линии
)	J
неэффективность такого управления очевидна Выбор максимальных
«качений на каждом этапе приводит обычно к несвязной (т.с. недопустимой)
траектории, а полный перебор требует рассмотрения mN вс тможных
траекторий, что вряд ли реализуемо при достаточно больших т и N.
Согласно методу динамическою программирования, данную задачу надо
решать с последнего этапа и определить для каждого состояния i в начале
А/-ого этапа состояние j в конце >того >гапа, дающее наибольший доход
На предпоследнем этапе также для любого состояния / находим
состояние j, такое что сумма F^N ° j (tJN 1>+F(jN) максимальна.
Аналогично рассматриваем (TV-27-й этан и определяем F/ 7 для любою i
и т.д. Таким образом, приходим к 1-му этапу, где требуется для данного /0
определить у, так чтобы сумма F(l) fM + pO) бь|ла f максИмаяы1а. В
результате таких попарных сравнений точное решение находится очень
быстро, при этом на свойства функции j никаких дополни зольных условий
не накладывается.
Обобщая этот алгоритм для исходной задачи оптимального
управления, прежде всего заметен, что он основан на двух принципах,
определяющих метод динамического программирования
/ Принцип погружения исходной задачи в семейство парамет-
рических задач.
Иначе говоря, вместо исходной задачи с фиксированными данными z0 и N
рассматривается семейство задач, к которому принадлежи! исходная задача.
В примере этот принцип реализован введением функции /• <к>.
2.	Принцип оптимальности.
)дна Из наиболее точных формулировок его следующая: "Оптимальное
правление обладает тем свойством, что оно остается оптимальным
пносительно Любой промежуточной точки траектории Иначе говоря,
ли оптимальная траектория, соединяющая точки А и 13, содержит
6
Рис 3
точку С, ю при решении задачи об оптимальной траектории, соединяющей
точки G и В, таковым будет участок СВ оптимальной траектории АВ.
Аналогичное свойство выполняется для задачи ит примера 1 1 Принцип
оптимальности предназначен для связывания задач из параметрического
семейства, определяемого принципом погружения, те ом позволяет
находи и. решение одной задачи по решению другой
В резулыаю метод динамического программирования строит
последовательность таких связанных задач из параметрического семейства,
начинающуюся с наиболее простой задачи и заканчивающуюся исходной
Задачей. Эта последовательность конечна, поэтому решение находится за
конечное число итераций.
1.	2. Мсюд динамического программирования для задач
распределения ресурсов
Вначале рассмотрим задачу управления экономической системой,
состоящей из двух предприятий (можно считать их также отраслями), в
условиях дискретного времени. Эти предприятия могут использовать
различные виды ресурсов для производства товаров (изделий), но будет
особо выделен один из них, который является возобновляемым Иначе
говоря, если в начале какою-либо этапа в системе имеется s единиц ресурса,
го первому предприятию передается д единиц, а второму - у единиц, так
чю a v + г. 13 конце этого »тапа первое предприятие приносит доход
J (\) п возвращает <р(х)<х единиц ресурса, а второе приносит доход go- и
возвращает ^0)* У единиц ресурса. На следующий этап остается
количество s' 9X') + V,Ot)» которое вновь перераспределяется между
7
upenupi’HiHWMH н i. i.
kUhCla CO*, loin u ЮМ, Ч1ООЫ liph 1.1 I.IIIIH'M ILl’I i'll-llOM k»»'Uri‘‘Ll l«‘
HO юбНОВ 1ЧСМОГС |’VC\|H fl Il 4VUUIIIUM КО llPICi inC Million Л’ v)lp еДСП1Ш
cipaieuno раенретсчецнм ptc\pcj меьТ\ преднртццнми 11.1 каждом чане,
1ЙК Ч1ОЙЫ UV bЧИН- Md-KCHMa ibHblll суммлрпый U'\O l.
СОСЮНПНС СНС1СМЫ I» noil I'UPIC 1ЛДС1 ПОЛНОСТЬЮ oripvjiriplll.ot
ho IH'lCCl Hi’M UO U’OHOHAMUMOro pCCypi I II । ' ari обо ПЛЧЛГЬ КОЛНЧС» Hill
ресурса в начале / ю чипа управленце на / м чине оцредепмск’Я юш-ко
величиной х копнчеепм ресурс», выделяемою первому прсдирпяппо,
поскольку количество ресурса, вы (еляемос в юром) предприятию онрсдс
iHcivH по формуле
г, 1;.
Hi.1к, получаем <адачу управления дпнимнчеккон hcicmoh дня io порок
выполнятся условия полной управляемое ।it и (1ддп i hbiioc i и ночому для
решения применим меюд динамически! о iipoi p.iMMiipoii.iiiini.
Прежде нсе1<| определим функцию/^ (л) H.iiiGoui.iiniii суммарный
доход О! работы системы ia чаны с А ю по /V и нключиюльпо при
начальном количсстс ресурса л па А м маис. 1см самым определено
пираме|рнческос ccmcIiciho »адач, к коь>рому принадлежи! исходная ыдача,
тачепие которой ес|ь /, fi(1) )ю шачнг. чю рсалп <онан принцип
погружения. Отмстим, что на последнем чане имеем
nia\ 1 .«(' 'a )}	(I)
почему необходимо ностронть цепочку ыдач, суя 'ынающпч /< N и 1\. Для
ною иснолыусм принцип он।нмл41.пос।и Рассмотрим Z н пап цуси н
начале шишпмеегся v единиц ресурса и первому нредпрня 11110 ныдсияс1ся
х4 единиц 1огда макенмальпып суммарный доход при чих двух условиях
онредслясц'я выражением
‘АГИ' Ч ) । G.i|X'a п Ч'^ b <|
Чтобы снят вюрои условие, возьмем максимум но и получим в iobhocih
течение Итак, получено рекуррентное cooiношение
/’*(•'> тих {/Y-Ч >1 ч J1/‘a.iI'/’C <* > । У’(' ч >1!
о Ч-. 5	*	( 2 )
к 1,2,. /V-I,
которое реализует пришит оптимальности и называется ткже
функциональным уравнгннсм Нсллмана Используя (I), (2), ncipymo
построй 11. грсбуемую цепочку задач, связывающих и /-| и в резулынтс
наЙги решение исходной шдачи.
К
Пример 1.2 II,. II 16 N I.
/( U ’ </»( tl <!/'•«,
'( »)	’ ч I U " ’
1’ICll lirplUH HpC IlipHJII II' >lf pii4l1IIO> I •V'Hl.HlC P' < ptl I ' И IlpMIll- Hi
Ml'lll-llllth Д4»Х<» I < ""IP lirn»l< ( I JlpH( <>p.-f I 11ИД
I'kI'I mm {./ 1 •’М ч, Л < /, .(j<i •	><>•/.,l.zt
II 1, s
I Io (»l IpVHC'li ll IIRI
/л(л) max <1*|(ч. /,1дгФ4г ,x) • •’ */»•ч‘
Поскольку фут инн ФДл, •; нылукдии i  • •• о им>м на /0, ./ до» ти
пи одном ИЧ кошцж <>1|к.*н । ИМ'-'-м
Ф,ЬЛ') <хг Ф,(.г, v)
iiKiiiш • «с iyci i( 0н/'ц(л2	’•!' при любом 0 . I 1Я н апои 1 и 4 им"’М
/ max ’,’ifv- '। ,дгф 6V« v ‘ f ‘ 4 '  ° ' ’ /
u \ . Л
Ah.ihoi II'IIIO функция ФД ,*) HJ.iiiyKl.1'1, 11' I >му И  " г • •
ФДл.О) 1 IBv’	125№ следует х. Uu/ (••) 21Хя; при любом
с о /(ля »1иион i и I имеем
/ max -(л ' 1	*1*• г*.	г * V»• «71 • 1 х[ 7 л "	./]
И 1, л
I ilK/KC II I ВЫ пук III К III Ф (л, ® ) И С(М»11 и мнений
<l’,(v,0) ZlVo.’.v' <!»,(.$,л) 2 2262'.г•' vi<* iyci |	। и / (») 22262^1 при
ilh'GoM V о Дп>* II.IIHIH I I имеем
шах <1’|(л- Ч 1 дс ‘i’/'. ха + 2^л-i 2 22б25[о 7$ । + о V»
о <1 л
Поскольку здесь ‘Р|(л,О)	* з 2 2?<>25(» 75л);. |<> . и
л I 2 2202^(0 75л) ( Иц им.ни.нос mi.i'ichmc нелепой функции / (16) •
5/(» 8 Илндсм oiiiiiM.i’ii.iiyio сipnici нк> распределения рссурсон, учиiмиля.
'о 16 i| з0. /	'| . Ч О. Ч О
f’C-’CypCl.!	16	12	0	О
11рг шрня।нс 1	к»	12	0	0
ЧрС’ДНрПЯ1ИГ 2	0	0	9	2.7
9
Получаем xf = 16. xj = 12. xj = 0. xj = 0.
Ji* = °- > 2 = °. Ъ = 9 J’4 = 27-
Рассмотрим иную задачу распределения ресурсов, в которой п
предприятий используют однородный ресурс для производства товаров,
причем для заданного планового периода известна величина запаса ресурса
Ь, а также доход /(хД приносимый z-м предприятием при использовании
количества ресурса х,. Требуется найти распределение ресурсов,
приносящее максимальный суммарный доход, или, в краткой записи,

тах->
xt =b xt e X, i = 1, n
где X обозначает множество допустимых значений ресурса Хотя в исходной
постановке эта задача является статической, для ее решения можно
применить метод динамического программирования. Заметим, что вместо
одного периода можно рассмотреть п этапов и одно предприятие, тогда
х, будет количеством ресурса, выделяемого предприятию на z-м этапе,
/(xj-доход от использования х,единиц ресурса на z-м этапе. Тогда
получаем динамическую систему с дискретным временем в условиях полной
управляемости и аддитивности. Определим функцию Fk(s) - наибольший
доход от работы предприятий с номерами с к-го по л-й включительно при
выделении для них s единиц ресурса, теперь исходная задача имеет
оптимальное значение F}(b) и принадлежит параметризованному семейству
задач. Очевидно, что
теперь для связи задач из семейства используем принцип оптимальности, из
которого следует
Fkty = max {fk(xk)+Fk+x(s-xk)} ,к=\,2,...,к-\.
(teXfc <s
Хкех
Данное функциональное уравнение позволяет построить связанную цепочку
задач от F„ к Ft и получить решение исходной задачи.
Пример 1.3. Пусть п - 4, b = 10, X = {0,2,4, 6, 8, J 0}, а функции / заданы
таблично.
10
	0	2	4	6	8	10
f\	0	8	10	1!	12	18
fl	0	6	9	И	13	15
fl	0	3	4	7	И	18
	0	4	6	8	13	16
Итак, переменные в этой задаче принимают дискретное множество значений.
По определению F4(s) - f4(s), т.е.
s	0	2	4	6	8	10	s	0	2	4	6	8	10 1
х4	0	2	4	6	8	10	*3	0	0	2	2	0	10 1
^4	0	4	6	8	13	16	Гз	0	4	7 9		13	18 |
На основе функционального уравнения находим F5, F2 hF , используя
таблицы значений.
5	0	2	4	6	8	10
Х3	0	0 2	0 2 4	0 2 4 6	0 2 4 6 8	0 2 4 6 8 10
Л+Л,	0	4 3	6 7 4	8 9 8 7	13 11 1011 11	16 161213 1518
11
5	0	2	4	6	8	10
*2	0	0 2	0 2 4	0 2 4 6	0 2 4 6 8	0 2 4 6 8 10
	0	4 6	7 10 9	9 13 13 11	13 15 16 15 13	18 19 18 18 17 19
5	0	2	4	6	8	10
	0	02	0 2 4	0 2 4 6	0 2 4 6 8	0 2 4 6 8 10
/1+^2	0	68	J0 14 10	13 18 16 11	1621 20 1712	19 24 23 21 18 18
5	0 2 4	6	8	10
х2 О 2	2	4	4	2
О 6 10 13 16	19
Получаем F/107 = 24, это максимальный доход. Определим оптимальные
значения ресурсов для предприятий. Из таблицы для F} имеем х, = 2 (при
5=10), тогда х2=4 (при 5 =8) из таблицы для F2, х3 —2 (при 5 =4) из таблицы
для F3 и х4=2(при 5 =2) из таблицы для F4.
Таким образом, метод динамического программирования может
12
применяться для ршличных дедлч с дмсхретиыми переменными, к их числу
относятся задачи << рюк - >хс гоммиьояжсра, р^ягр,я Ьо ъие> случаях метол
обеспечивает нахождение точною решения при сравнительно h<<*...iuwjh
количестве итераций
13. Экстремальные задачи иа графах
Теперь рассмотрим применение метода динамического проезжими
рования к задачам оптимизации, определенном на графовых структурах
Собственно, одна из таких задач уже рассматривалась в примере 1.1.
Напомним, что граф задается множеством вершим. которое будет считаться
конечным и его элементы обозначаются на у- рг. - на -г .тами миожеством
дуг и отображением, ставящим в соответствие варе вершив /и/ элемент
множества дуг. Если значение отображения для tn j непусто, то опрележм
дуга (i,j\ для которой вершина / является исходящей (качжжиой), а у-
входящей (конечной). Если значение отображения дни I  J пусто, то
вершины / и j не связаны дугой. Последэвательаость дут
с/|. d-^,d^,... dк.
где d{ = (ix,i2)’	= Ok- At+i? и любые две соседние дуги имеют смежную
вершину, называется цепью, соединяющей вершины ци если
/] g и /Л+1 е dk_x. Граф называется связным^ если любые две его вершимы
можно соединить цепью. Циклам называется замкнутая цепь, у которой
начальная и конечная вершины совпадают. Деревом называется сшпкы*
граф без циклов.
Для определения экстремальных задач на графах их элементам
приписывают значения, называемые весами. Такие задачи, помимо большого
числа самостоятельных решений, часто используются в качестве подзадач,
решения которых необходимо находить многократно, поэтому разработка
эффективных алгоритмов для них имеет очень бояыпую значимость.
Рассмотрим вначале простейшую задачу о нахождении кранячашшего
связывающего дерева графа. В этой задаче дан граф с весами (хтмммл)дут
Требуется найти связный подграф, содержащий все вершины графа и чисть
его дуг, так что он является деревом, причем дерево до.тжяо иметь
минимальный суммарный вес дут средн всех полученных нз графа даре п
Решение этой задачи находится с помощью очень простого алгоритма.
Алгоритм 1 (Прим - Краскал). Выбираем любую вершину
полагаем V* = {/0},£У = 0,s = 0.
13
На очередной итерации рассматриваем все дуги, у ко горы одна вершина
находится в И', и среди них выбираем дугу с наименьшим весом. Пусть это
дугаd = (ij), ieV'nj *V'. Тогда полагаем V = VU {j}
s = s+cv , где - вес дуги (ij). В случае, когда z е Р", )еГ, полагаем
K' = K'U^7,£>' = Z)'Ufd7»5 = 5 + c,-z. Построение дерева завершается, когда
И' = И, тогда его дуги находятся в D', а длина дана числом s.
Эта задача может иметь несколько решений, но тем не менее алгоритм
1 всегда находит одно из них. Действительно, пусть £>" определяет
множество дуг графа, задающих любое связывающее дерево. Пронумеруем
вершины графа в порядке их вхождения в V, тогда n(iQ) - 0, а также дуги
из D' по правилу n(d)~ max \n(i), n(j)}, где d = (ij). Предположим, что к-
наименьший номер дуги d такой, что d&D'nd^D". Тогда добавление
дуги d к дугам D” образует цикл. Пусть для определенности d = (ij) и
n(i) <п( j), тогда в цикле найдется дуга J, = (ixjx) е D", такая что n(ix)<n(j),
n(jx)>n(j\ а это значит, что >с^. Заменяя в £>"дугу dx на d, получаем
новое дерево, сумма весов дуг в котором не увеличилось, причем значение к
для нового дерева увеличится по крайней мере на 1, а если dx eD', то
n(dx)> n(d). Продолжая процесс замены дуг, в конечном счете придем к
дереву с дугами из D', поэтому оно является решением задачи.
Пример 1.4. Рассмотрим работу алгоритма 1 для следующего графа.
Этот граф удобно также задать в виде таблицы, отображающей матрицу
14
весов дуг (	(с, )tJ । „ В данном случае л »6
1		2	3	4	5	6
1	0	2	5	7	-	*
2	-	0	-	4	-	8
3	-	-	0	-	6	*
4	-	—	-	0	4	3
5	3	-		-	0	2
6	-	-	1	-	-	0
Если начать с вершины Zo = 6, то получим последовательность вершин И
{6,3,5,4,1,2} и кратчайшее дерево из дуг £>={(6,3) <5.6), (4.6), (5,1), (1,2)} с
суммарным весом 11.
Теперь рассмотрим задачу о кратчайшем связывающем пути в графе
Напомним, что путем называемся цепь, которую можно пройти от начальной
до конечной вершины в направлении дуг. Замкнутый луп», те цикл,
который можно пройти в направлении дуг, называется контуром Задача
будет состоять в том, чтобы для заданного графа и пары ею вершин /0 и JQ
найти путь с минимальным суммарным весом дуг из в jq. Если
отождествить вершины графа с состояниями некоторо динамической
системы, а дуги - с возможными одноэтапными переходами системы из
одного состояния в другое, то получаем задачу' оптимального управления
системой с дискретным временем, для которой можно применить метод
динамического программирования, поскольку и услог 4Й полн
управляемости, и условие аддитивности критерия выполняются. В этому
типу задач принадлежит и задача из примера .1, где вместо точного
указания конечной вершины jQ указано только множество, где она должна
находиться. Отметим также, что не для всех графов поставленная задача
может иметь решение, например, для графов, в которых есть контуры с
суммарным отрицательным весом дут. При отсутствии таких контуров
решение можно найти методом динамического программирования Реализуя
принцип погружения, определим функцию Fk(j) - величина кратчайшего
пути оз вершины Zo до вершины у0, содержащего не более к дуг. Если л—
количество вершин графа, то оптимальное значение в исходной задачи -
определяется как Fn^(j0).
Алгоритм 2 (Беллман-Форд). Полагаем FQuQ) =0, /^ =при
j* Zo. Затем последовательно пересчитываем значения по формуле
15
W-minИ'.	л»** -U. л-2,
•al
где /' - множество ПСрМиН грпфм
Очевидно, чп) рекурреншил формула (3) оиредепяст принцип
оптимальности для данной шдачи. Работа алгоритма 2 для i рифа и « примера
1.4 с /() I, j0"5 представлена в следующей шблицс
	1	2	3	4	5	6
	0					
	0	2	5	7	—	—
	0	2	5	6	и	10
	0	2	5	0	10	9
	0	2	5	6	10	9
1аким образом, длина кратчайше! о пути 10 и ин состои i и < ду| (1,2) (2,4),
(4,5). Заметим, что пег необходимости считан./', поскольку шачепия /-^
совпадают со значениями b's
Алгоритм 2 можно использовать для нахождения кратчайших путей
между всеми нарами вершин. Если для одной начальной вершины объем
вычислений О(п ), то для всех вершин он будет на порядок больше О(пА).
Однако для этой задачи сущсствуе! и более лрфективпый специальный
алгоритм.
Длноригм 3 (Флойд), Пусть квадратная матрица порядка п,
элементы которой с}*) определяют величины кратчайшею пути между
вершинами / и у, который может содержать в качестве промежуточных
только вершин из множества (1,2..Л}. Тогда Cf0J С ио определению, а
решение задачи дано матрицей Г’("\ Алгоритм состоит в последовательном
пересчете матриц но формуле
для а л 1	(4)
U	I ’/	t 	Л • • fi J I
Действигсльно, если известен кратчайший путь из / и у с промсжуц)’шыми
16
вершинными» fl. .,/•	i>> i»<< imoahm ди.» • лучам
j) Д*Илшлсиие boimoahoM П]юмгжуточной вершимы к f 1 иг мемкгг
величины Крн/ЧПЙШС! О нуги» /Of/Ы г^**^ ’
I)) Д<>ЬЛПЛС11И< вершины А >1 НО»ИОЛЯ‘1 (M'lfldUMII. Щл <айший путь и» / в
/, вида oil hy/ici < о< ion/ь и*. двух частей! or / до (4*1) и or (4*1) до / с
длинами и	Г' ГГИ’НИ' fl'o/GMy имггм '
В резулыатс получаем, Ч1<> сира/ едлим.) формула (4) Рябова алгоритма 3 ;yi«
грш|>н иг примера 1.4 показана в вил<  ледующсй последовательности таб-
лиц, где (,<ч>'	( ’ .
(.<»)
1 2 3 4 5 6
12 3 4 5 6
1 2 3 4 5 6
1	0	2	5	6	- 10
2		0		4	- 8
3		м»	0		6 —
4		—•	ч»	0	4 3
5	3	5	8	9	0 2
6	•ма	«*«	1	и»	- 0
I
2
3
4
5
6
0 2 5 7 - -
-0-4 -8
0-6
0 4	3
5-----0	2
1- -	О
и»
12 3 4 5 (
I
2
3
4
5
6
о 2 5 О 1V 9
О 4 8 7
V 6
О 4 3
3 5 8 9 0 2
I 7 О
С0>
	1 2 3 4 5 6
1	0 2 5 6 10 9
2	II 0 16 4 8 7
3	9 11 0 15 6 8
4	7 9 12 0 4 3
5	3 5 8 9 0 2
6	10 12 1 16 7 0
1 2 3 4 5 6
1	0 2	5	6 10	9
2	11 0	8	4 8	7
3	9 И	0	15 6	8
4	7 9	4	0 4	3
5	3 5	3	9 0	2
6	10 12	1	16 7	0
Аналогичным обрагом, для графов, удовлетворяющих реьтичиым
дополнительным условиям, можно построить более эффективные алгоритмы
нахождения кратчайшего пути между парой вершин по сравнению с
•ин ори । мом 2.
17
Рассмотрим. например, одни in нашчшее «ффеюипных luiiopniMon щм
графов с неотрицательным весом ду!
Алгоритм 4 (Денису па к Определяем Г * « Г \	, полагаем
F(/J е для J t 1 На каждой итерации выбираем индекс к из I
такой что F(k)» min F(j), полагаем I ' «I ’\{А} и определяем
F(/)« min{F(/). F(ty + c^j для у е И’
Алгоритм останавливается в случае, koi да к = у0. либо koi да I ' =0, в этом
случае определяются кратчайшие пути из i0 во все остальные вершины.
В этом алгоритме величина F(k) определяет кратчайший путь от i0 до
А. Это. очевидно, справедливо для первой итерации Для произвольной
итерации, если F(k) кратчайший путь от i0 до А. на всех предыдущих
итерациях, то обратное предположение для данной итерации приводит к
тому, что путь с меньшей длиной проходи! по вершинам из V'. т.е.
существует J <= V* для которого F( j) < F(k) , что невозможно.
Отметим, что алгоритм 4 имеет трудоемкость О(п2 ), или OfmCog^t).
где т - количество дуг графа, что значительно меньше, чем для алгоритма!.
Работа алгоритма 4 на графе из примера 1.4 представлена в следующей
таблице
	/	2	з	4	5	6	_ 1" ______	1				
F	0	2	5	7	-	*	2	3	4	5	6	к = 2
	0	2	1_5_	б	-	10	3	4	5	6	к = 3
	0	2	5 L	6	11	10		4	5	6	к = 4
	0	2	5	6	10	9			5	6	к = 6
	0	2	5	6	10	1_9				5		к = 5
Еще более простой алгоритм можно построить для графов, в которых
отсутствуют контуры, во веса дуг могут быть любыми. Для таких графов, не
ограничивая общности, можно считать, что если существует дуга (ij). го
всегда / < у, т.е. в таких графах всегда можно перенумеровать вершины,
чтобы это свойство выполнялось. Более того, всегда можно считать, что
18
находи к я крптчойший путь от верши ны I ;к> ыршишл п, г е I /», я Н
самом деле, если /ц I, ю можно ио лючить из рассмотрения все вершины |
номерами, меньшими чем /, и енмыннме ними дуги, а •• с. ••чае ,  »
ail.l'IOl ИЧ1Ю ИСКЛЮЧАЮТСЯ ВСрШИНЫ • И» '.'ej	♦ » льшими чем /е и
связанные с ними дуги, поскольку кратчайший путь и» «0 и /7 не будят
проходить чер- з ггу часть графа. Итак, ль в q зфе уги пр< обрв намия
выполнены
Алт ори !м 5. Полакаем ЛИ/ 0 и последовательно для каждого
j ‘2,3,..., и вычисляем
1'0) inin{F0/*-cJ
/
(5)
Этот .ип ори гм имеет трудоемкость O(mi Негру дн< нилеть что
алюрпгмы 3-5 основаны также на идеях метода динамического
программирования, только используют специфику задачи для построения
более эффективной схемы вычислений.
Алгоритм 5 может быть модифицирован для  »преледеним нс
кратчайшего, а длиннейшего пути от 1-й до п -Й вершины. Для :ноп
достаточно формулу (5) заменить на следующую
FO) max{Frr/ + cJ.
к! ’	*
Задача о длиннейшем пути является важнейшей составной частью юОичи
планирования сложного комплекса работ или, иначе. ъМачи p<j о яг..
сетевого графика. Предположим, что необходимо выполнить определенное
количество работ, каждая из них имеет заданную продолжительность, а
также связь с другими работами, т.е некоторые работы нельзя начинять до
завершения других. Например, при строительстве дома нельзя возводить
стены до завершения фундамента. При этом не связанные друг с другом
работы можно выполнять параллельно. Первый вопрос, который обычно
возникает, состоит в том, чтобы оценить общее время выполнения всего
комплекса работ. После »тою можно сзавитъ вопрос о наличии резервов
времени у тех или иных работ На «ти вопросы помогает ответить сетевой
график комплекса.
Алгоритм построения ceieBoiXk графика основан на представлении
исходной МкДйчи в виге графа, дугам которого соответствуют работы, л
вернишам события начдта иш <авершен» е одной или нескольких работ
Отметим, чю шкой граф не будет иметь контуров, поскольку каждая работа
19
№_ 1 2 3	№ uvCiie i.' нчич' 11.15 1.13 0,14	luniCJlbJIot 1 Ь 15 5 5
4	10	10
5	-	5
6	ЗЛ	10
7	8,2	10
8	11,15	20
9	5	10
10	-	20
11	5	10
12	1,13	20
13	9,14	10
14	10	10
15	9,14	5
Этому комплексу соответствует граф, где в скобках указаны веса дуг.
Длиннейший путь в этом графе, называемый также критическим
путем, определяет время выполнения всего комплекса работ. Работы,
чаходящнеся на критическом пути, не имеют резервов времени.
Задача расчета сетевого графика предусматривает вычисление двух
20
величин .ия ►ал-л'/й i й вершимы графа рамнего нимола воступавяаа
LOOMI ИЯ /, И Ш>»ДН4Ч</ МОЫГИТВ МЫДуПЛВММЯ С'«быТИЯ 7 ВсЯГШМ 1
равна длиннейшему itytn 1-Я дм* / в вершмам. вр*мйс гемо. 7, */,.»
величина / д;\п >• п • ч редка же и. Я <ю ц^цллуяиТ, * Т9 ! . iff *.
длиннейший пуп» от / й до и й вершимы K^imc того, дав макожаяши Г
может быть применен ашормтм ’ . жжмыуюсимй 4*,5**y*>
Т min / < для j л-М 2. ,1
Резульга! ы расчетов даны в следующей тЯбяммг
№ события	С	Т,
I	0	0
2	10	1$
3	20	20
4	30	35
5	35	35
6	40	40
7	50	50
8	50	65
9	70	
Критический путь здесь Ф-> I -> -> — -г . - < 4t _ > со^мтя* ю
критическом пути tt = Tt.
Кроме того, в задаче расчета сетевого графика пазят расчет резеряав
времени для работ, что позволяет мавеярвфоавтъ ресурсама в ацаг
выполнения комплекса. Определяй’?г« три ьмдв ре'«сра^в
а) £у = Т -I, -с, - полный резерв,
b) - tj -t, -су - свободный резерв,
с) =тах 0,Г — Т — с | — не шнейммм резерв
Полный резерв показывает, на сколько моаово мвержатъ зммтую ряботу 6п
ущерба для выполнения комплекса работ, свободный рс«ро — без савнг>
ранних моментов наступления последуххь.и\ р^бот, я незаамсашЫ1 ретар
показывает, на сколько можно ежвниуть данную работу бет утжцрбв ал
других работ.
21
Результаты расчета этих резервов для примера приведены
11 Tanjn1Ile
	1	№ работы	£		
	1	0	0	~0
	2	5	5	0
	3	5	5	0
	4	10	10	5
	5	15	15	0
	|	6	5	0	0
	7	5	0	0
	8	5	5	0
	9	15	0	0
	10	0	0	0
	11	20	5	5
	12	0	0	0
	13	10	10	10
	14	0	0	0
	15	1	0	0	0
22
II.	Марковские процессы принятия решений
Перейдем к рассмотрению процессов управления динамическими
системами при наличии неопределенных факторов В данном случае
исследуются системы, последующие состояния которых зазисят от
предыдущих состояний и управления случайным образом.
2.1.	Марковские процессы без управления
Рассматривается динамическая система, т.е. меняющая свое
состояние на некотором заданном отрезке времени, причем он может быть
как конечным, так и бесконечным. А именно, всего система имеет т
возможных состояний, весь период времени делится на этапы, причем
начало к-го этапа и конец (А:-1^-го не различается. Таким образом,
состояния системы могут последовательно меняться на каждом этапе,
определяя тем самым динамический процесс с дискретным временем.
Если для любого состояния i в начале к -го этапа известно состояние J в
конце этого этапа, то процесс является полностью детерминированным.
Рассмотрим более общий случай, когда вместо этого состояния J
известны лишь вероятности перехода в каждое из состояний системы из i-
го. Задавая векторы вероятности для каждого начального состояния,
получим так называемую матрицу переходных вероятностей Р с
элементами р„t такими что
0<р,у<1	i,j =
т
YPij=}	1 = \,...,т	(’)
7=1
Соотношения (1) показывают, что каждая строка матрицы Р задает
распределение вероятностей, причем второе из соотношений в (1)
определяет обязательность перехода системы в какое-лчбо состояние на
каждом этапе.
Отметим, что определение данной системы содержит два
дополнительных условия:
1)	переходные вероятности не зависят от предыстории процесса, т.е.
вероятность перехода р из i -го состояния в j -е на этапе не зависит от
того, в каких состояниях находилась система на предыдущих этапах;
2)	переходные вероятности не зависят от времени, т.е. от номера этапа.
Первое свойство, называемое марковским свойством, определяет
23
рассматриваемый процесс как марковский, тогда как оба свойства с
учетом конечности числа состояний т определяю! так называемую цепь
Маркова
Для иллюстрации подобных систем можно взять пример пруда, на
поверхности которого плавают листья кувшинок и лягушку,
перепрыгивающую с листа на лист (рис.5). Если всего т листьев, а
вероятность прыжка с i -го листа на j -й не зависит от количества
прыжков и от номеров всех предыдущих листьев, то получаем в точности
описанную систему. Можно взять и более приложимый пример об участке
земли, почва на котором может находиться в одном из т состояний,
причем вероятность перехода из одного состояния в другое за год зависит
лишь от текущего состояния.
Предположим, что нам известен вектор вероятностей состояний
системы а<*> =	в начале 1-го этапа. Тогда можно поставить
задачу о нахождении вектора а(п) вероятностей состояний в конце л-г о
этапа для произвольного п (Здесь и далее рассматриваются векторы-
строки). По определению,
= £ руа(1П~Х)	для i =1,...,т
или, в векторной записи,
а(п) = а(п-х)р	(2)
Поскольку формула (2) справедлива для любого п, то отсюда следует
а(п) ~а(0)Рп, л = 0,1,...	<3)
Пример 2.1. Для Р=(о4 ?б)пРи	=0,0) имеем
24
а<1' (0.5, 0.5),	(0.45,0 55), </''•(0.445,0.555), в при
a (0,1) имеем
a (0.4, 0 6),	(0 44,0,56), </*'• (0 446,0.556),
т.е. co временем вероятности //п/для разных стартовых состояний
стремятся к одному вектору
Теперь рассмотрим систему, движение которой сопряжено с
получением доходов А именно, если система переходит из i-ro в у-с
состояние, то получаем доход atJ. Таким образом, определяется матрица
доходов А и можно рассмотреть задачу об оценке дохода от работы
системы за фиксированное число этапов. Поскольку точную величину
дохода здесь невозможно оценить заранее, то используем среднее
значение. Пусть fn(i) - средней доход от работы системы за п этапов при
условии, что в начале первого из этих этапов система находятся в
состоянии i. Эту величину можно найти из рекуррентного соотношения
т
Ш (аи + Л-.<0) для i =
/=•	(4)
при л = 1,2,..., где/(0 = 0.
Обозначим
bt = ^Руау -среДний одноэтапный доход системы из i-ro состояния.
7=1 У
Тогда формулы (4) переписываются в более удобном для счета виде.
/»('> = *, + JjBflo t = 1........m
7=1
п = 2,3..., где f}(i) = bt для/ =
Пример 2.2. Пусть P = (о4	-7) Тогда
/=£ = (6,-3), /2 = (7.5,-2.4), /3 = (8.55,-1 44).
Таким образом, можно оценить доход от системы за любое число этапов.
2.2.	Марковские процессы с конечным числом этапов
Если на каждом этапе предоставляется возможность выбора
управляющего воздействия на описываемую систему, которое бу„ет в
данном случае состоять в выборе альтернативы к из множества К(у
альтернатив, где i - текущее состояние системы, а альтернатива к, в свою
25
очередь, будет опредезять матрицу переходных вероятностен Р* и
матрицу доходов fA, то можно ставить задачу об управлении системой,
обеспечивающем наибольший доход Псскольк управление не ткиволяет
точно предсказать траекторию движения системы и величину доходов, то
оценивается средний, или ожидаемый, доход. Вначале рассмотрим
подобную задачу управления системой за конечное число этапов /V. Для
е** решения можно также применить метод динамического програм-
мирования.
Прежде всего реализуем принцип погружения, для чего введем
функцию fn(i) - наибольший средний доход от работы системы за п
последовательных этапов, если в начале первого из этих этапов система
находиться в состоянии i. Если задано исходное состояние i* на первом
этапе, то оптимальное значение исходной задачи fN (i*;. Рассмотрим
первый из п этапов. Если система находится в состоянии i и выбрана
альтернатива к, то наибольший ожидаемый доход равен
Ру ау + fn-\(j), =
7=1	7=1
где 6* = 52 Ру ау ~ средний доход за один этап при условиях, что система
7=1
в начале этапа находилась в состоянии i и была выбрана альтернатива к
Поэтому получаем фу нкциональное уравнение
Л 0) = max # + S	для п = 1,2,...,А'';
*«*(•) (	У=1	(5)
f (Л = 0 для i =
Итак, принцип оптимальности также реализован. Отметим, что в исходной
постановке полной управляемости нет, но заменой целевой функции на
среднее значение мы добиваемся того, что новая целевая функция
однозначно определяется максимизацией по альтернативам с сохранением
свойства аддитивности, что и позволяет применить метод динамического
программирования. Соотношения ^5) позволяют найти решение
поставленной задачи с любым фиксированным числом этапов.
Пример 2.3 (Задача садовника;. Садовник обрабатывает участок
земли, почва которого может находиться в одном из трех состояний:
хорошем (1), удовлетворительном (2), плохом (3). Он может применять
26
две альтернаi ивм
О
О
0 5 0 5
О I
О
О
О

0.3 0 6 0 1
0.1 0.6 0 3
О
7
2
0.05 0.4 0.55
Необходимо найти решение задачи > каждого начального состояния за 3
этапа.
Вычислим величины среднего одиоэтжтюго дохода, тогда
1	Ь',	*,2
1	5.3	4.7
2	3	3.1
3	-1	0.4
i	1 //<>	*•	1
1	5.3	1
2	3.1	2
3	0.4	2
fx(ii) = тахф},bf}, согласно (5), к* обозначает оптимальную
альтернативу. Аналогично, используя 5), последовательно вычисляем
i	Ъ, + Е Pkgfx(j)		f'Ji)	*•
		*		
1	8.03	8.19	8.19	
2	4.75	5.61	5.61	n
3	-0.6	- ^2.13	2 13	7
2?
/	b^±P‘fM /-1		fy(i)	Л’
1	«10.38	«10.74	10.74	2
2	6.87	«7.92	7.92	2
3	1.13	«4.23	4.23	2
Итак, величины fa(i) показывают наибольший ожидаемый доход за 3
этапа для каждого начального состояния i на первом этапе. Оптимальное
управление определяется следующим образом: на первом и втором этапах
- вносить удобрения (2) независимо от состояния почвы, на третьем этапе
- вносить удобрения (2), если почва находится в удовлетворительном (2)
или плохом (3) состояниях. В дальнейшем для удобства альтернативы
будем также обозначать буквами:	а соответствует первой, Ъ
соответствует второй. Тогда оптимальная стратегия по этапам кратко
записывается в виде таблицы:
I	II	III
1—>b	1—>Ь	1 —>а
2—>Ь	2—>Ь	2->Ь
3->Ъ	3->Ь	3->Ь
2.3.	Модификации задачи управления на конечном числе этапов
Наряду с общей постановкой задачи управления из предыдущего
раздела существуют различные модификации и обобщения. Первая из них
связана с изучением решения для стационарных стратегий, каждая такая
стратегия определяется фиксацией альтернативы к для каждого
начального состояния i независимо от номера этапа, т.е. от времени.
Например, для задачи садовника оптимальная стратегия не является
стационарной, а стационарные стратегии гораздо удобнее реализовать,
особенно для достаточно большого числа этапов. Отметим, что выбрав
стационарную стратегию 5, мы тем самым однозначно определяем
матрицы Р } и A(s) по матрицам входящих в стратегию альтернатив и
можем решать задачи на основе подхода из раздела 2.1. Обозначим
-средний доход за и этапов от работы системы с 5-й
стационарной стратегией, если в начале первого из этих этапов система
находится в состоянии i, тогда имеем
28
/•I
/о' (0 sО для i
Здесь -^pyC/ty - средний одаоэталиый доход от f й
7-1
стационарной стратегии при начальном состоянии •. Заметим что
количество стационарных стратегий может быть очень большим, ь
частности, если множества альтернатив К.'i j содержат по / элементов, то
это количество равно Vя. Поэтому вместо решения задачи выбора
оптимальной стационарной стратегии можно оценивать эффективность
отдельных стратегий, сравнивая их величины доходов с максима, ъно-
Пример 2.4. Для задачи из примера 2.3 оценим эффективность
стационарной стратегии $=(]—>а, 2 —>а,3—>Ь), те косить удобрения
только при плохом состоянии почвы.
Имеем
( 0.2 0.5 0.3 А
($)
0 0.5 0.5
0.05 0.4 0.55,
отсюда, используя формулы (6), получаем
i	b(,s>	ft”	f(s) J2	f'*'
1	5.3	5.3	".98	*9.87
2	3	3	4.7	* 6.39
3	0.4	0.4	*2.09	* 3.83
Значения дохода близки к максимальным (10.74. 7.92, 4.23), т.е. данная
стратегия вполне приемлема.
Вернемся теперь к задаче оптимального управления из раздела 2.2
Используя метод динамического программирования, можно найти
решение более общей задачи в условиях, когда матрицы переходных
вероятностей и доходов на каждом этапе зависят не только от выбора
альтернативы к, но и от времени, например, от числа оставшихся этапов
п или от текущего номера этапа, т.е. необходимо использовать матрицы
Ркп и Акп для заданного общего числа этапов N. Обозначим
29
In *”
ZL Рц 11 иу'П ~ величину cool ВС !C Uiyioinri о ОДНО * I Illllloi о До» о ли
/"I
I <»гди НМССТО (5) ДОСТАТОЧНО исполь ЮПИ I Ь COOIношении
/•(О-max'Л''+£₽;/. Мь
*<К(О	7ч

/о(<)»0 Для i 
Аналогично, может швиссгь от времени и множество алыерни 1_ии, тогда и
формуле следует заменить Kf/Jna Кп(1).
Ьще ОДНО обобщение сиянию С Использованием Ко >ф<|>ИЦИСН|а
дискомтироваиия для более точной оценки величины будущих доходов
Действительно, если доход определи» в я и денежном выражении, то
получение суммы денет S' в текущей Момент времени боле» вытодно, чем
получение той же суммы на следующем пине (обычно 1 од равен папу),
поскольку сумма .S’, будучи положена в банк, прии»*» ст в следующем юду
S(\+t) единиц, где / — средний банковский процент
Обозначим у «—коэффициент дисконтирования тот ди \
единиц дохода в следующем году жвивалентны у S единицам дохода
текущего тода, причем y.S’<5. 1аким обраюм, коэффициент
дисконтирования помогает Приводить будущие доходы к доходам
текущего папа.
Если решать аналогичную «плачу управления в иостацоькс раздела
2.2, но с учетом коэффициента дисконтирования, то достаточно будет
соотношения (5; заменить на следующие.
//Oemax(b(‘ +?1Lp'i//n i(/)}» "
*«ЛН)	j-\

2.4.	Марковские Цепи ил бесконечном интервале времени
Для Того чтобы исследовать мнотошаювые процессы с бесконечным
числом этапов, требуется рассмотреть поведение и свойства систем,
описываемых марковскими цепями, в ном случае. Одним из основных
здесь является вопрос о существовании стациопари» о режима рибозы
системы, т.е. о существовании предела
К)
Um ",я>	(7>
n
Ич формулы ( 9 LJir/iy* I
<z* "'"’lim1"'	(«)
ft w
l/i<- /'♦ limJ ilp'Л' Л».и ;>»рИП. nt ; - /отны/ вероятностей (аким
ft **f
образом, вектор предельных вероятностей, • \\'ju шиллий стационарный
р<*/ким работы системы, иа/о/шии чо матрице Р Однако fljm ftoto
необходимо вычислит». предел степеней пой м грины Из (2)  л< л ует, что
ДЛЯ НИХоЖДСИИЯ <1* МОЖНО И< Tl'MLi f i, 'ю <• Пр*х ГОИ набор УСЛОВИЙ
f*
а* »а* Р.с," < (), ^at »1;
/ •!
или, и координатной форме,
a* Ч£РцаЧ •“Ч 0 Дли J 1- >т \"Ч
/-1	/-1
Все состояния марковской цепи по о г ношению к бесконечному
интервалу времени можно разбит». на шмкн)ты‘- глоссы и невозвратны*
состояния Невозвратными иатыиаюк.я состояния, попадание в которые
невозможно после достаточно большого числа шагов (этапов). Иначе
»<>воря, если i невозвратное состояние, то at «0. Замкнутый класс
содержит ПОДМНОЖЕСТВО состояний таких, что после попадания в одно из
лих состояний при достаточно большом числе шагов система будет
находиться только в состояниях этого подмножества
Пример 2.5. Гхли р (J75 °7]), TOP*	J), поэтому
состояние I невозврат нос, а состояние 1 образует замкнутый класс.
Вели, как в примере 2.5, замкнутый класс содержит лишь одно
состояние, то оно называется погюцаюи^им Далее приведем несколько
। иойств марковских пеней.
Свойство I. Конечная марковская цепь имеет х>>тя бы сх)ин
iOMKiiymidii / часе.
Это значит, что не существует цепей, содержащих только
HCBoHipanibie состояния. В свою очередь, замкнутые классы состоянии
мо»у/ бьль периодическими, т е. для всех состоянии этого класса
попадание в гакое с<м юяние возможно лишь через одно и то * 5 число
чипов (период), причем наименьшее значение этого числа С > I. Наличие
периодических классов указывает на во 1можность детерминированног о
поведения системы в стационарном режиме Кроме ггого, могут
существовать и апериодические замкнутые классы состояний, называемые
31
1/1 t’lHrtri l HMH I Hi'ИМ 'HipniOM, ll»l HoillHKHIH ‘	 O< Н»ЯИИ< Ollpi /II ЛИ' I
•pi ОЛЦЧ» < НИИ I* Hill I
< >•<•!!« run	/<	»<>Ч' Ч>пт мн/" <nh ют ift HH nt t ши I'm utijt ц
Hi / Nt'hitH i in >< bn i пи ( vui‘‘i пинт in >!/• 'H nt nt"	jim n/irih' и iiin
hl/HI’Iltf/l'f. in, II . . tHI/h •>, НЧ, Ц‘......HllltHIl, Hill I (Hl
•Il O', ll«1 fl I. I	•|>|ОДН*1' • kllMII '	lilt' I IMII и	| IV» IIlf l»1 1Ц1.1МИ Ч*	1ОНИИНМИ
Им»  I	( I IH|||oi|'1plV	11 К |||i« i|i|||(*llll<	»»• pOHIIIOl	|« if
< Il'JIlJIf.	I III \nlfHI'	I ) ‘I Iff! if.	II vf< I Щ Ц 1111)411111	mil lltlul!
t/i.'lllhiUtH кин I 1.1, .	...... Iit/ftn " " im/mtfi,' Г* • ч)/нн II < Hthl, HI (	</ *	//,•
Innin нт i>m rf,,>
/(rlh iниiciihiKi, ny< 11.
/’*
"1 ") n,n
Hj n)
ч /f I '' I •“ ft tn '
К ром* IIIHl IIMrrM
IKK KOJH.ny
' piunpt rri no	hr рои I HOI	I- ! I	lencpi	исп«>1||.|уя (К),	нолучисм
!•'	„	ч‘	m
*	\	* I hi 4 (hi	x.4	iiii	i
11 f	: .i>tit,i	2.’’ !,г(	,r/2-'z/	n i / l,	.in
i i	i-i	/-i
В них с ИИН1ЯХ вектор и * полное ii.pi опр-ук’ oh-k-h кнн.м>
нирингй /’* пт коньку и с нщиопарном рсжимг сиспсмя <>удс|
III ОДИ 11.1 Я ПОП.КО II <И1ОИН|1И III <*НИ11< Н1СЙ1ЮГО >Р1 ОДНЧСГКО! о I Л;|< гя.
I ИИ мир! ОН< Ю1И IICIII. ГО/|гр,|<|| I !»<-« Koill.|'(> >р1 ОД11ЧГ1 1 их 1 Н.П < oil, IO OI
II "|1|Ц1.1Г '| И р.1СИр<.'Л<*ЛСИИМ //” будг1 ННИК ГП. II НИКОИ ИМГННО KJIIICC
рои ' к । и» i< •' • и  гаиионирном режиме, ноному »/*Г»удг1 i.iniiicii.
Ы1 4 • и oi т п 1
( нои I по 4 /, lu l>. f>()ll'ii4 1<нн I, ц.н I yuiiii iH. 'Kim 1(11111 ti'ih f'ib Hill < '
II . . I. IHll 1ЦНН. ЩИ m'KIlin/i ll/H Ih 'tl'lll'l* Hf/JO IHIJIIH Illi II I' llityiitlUIIKH
>i)ln> Uhi'Utn III t i IIHIIIIIIIHHIIII thhlll llj KiHIHiimiX НШ11Н HICII IIII mlim >4llt,lM
< >*iciih IIJO, 4lo центр (/ * но опрг/и iiciiiiio y/ioiinciliopurI
> 01|||1оШ<*!1И!<> (4). 0(1 H VKH IIHHII.IX усноииях on MO/KCI lil.lll. 0/11101113’1111»
piiil/H n
I?
Пример I. h. а) П’/' I'
<>
0	1	0
r
i	о	0
0	0	I	J
fl [,И<>ДИЧ& КИЙ КЛ •, "J	4	%.' J. < j; 
b; flyCf b P
$;ШИ‘ иг m U
Состояние 3 является невозвратным состоян.>
0
О
7ОГД* I'*
имеются дня >ргодиче< ких класса
Гели a(i>) «fl,0,0у или а( J «fOJ.Oy, то и* or
а если а'0) (0,0,1), тоа*-
к <4 X*
т.е. а*здесь зависит ото/0>
2,5, Марковские процессы без дисконтирования ва бесконечном
интервале времени
Имк, рассматривается система, аналогичная описанной в разделе
2.3, т.е. система с дискретным временем, находящаяся в каждый момент
времени в одном из т состояний и допускающая для каждого состояния i
набор упровляющих альтернатив так что любая альтерната-
к> К(1) шдам матрицу переходных вероятностей Рк и матрицу доходов
Лк. Отличие состоит в том, что теперь изучается задача оптимального
управления такой системой при бесконечном числе этапов В этих
условиях отдельно рассматриваются задачи без учета дисконтирования и с
учетом дисконтирования Действительно, если определить функцию
ожидаемою дохода fn(i) в системе без учета дисконтирования, то тог.ха
4-но при МНОШХ стратегиях выбора альтернатив, т е задаче
максимн шпиц ожидаемою дохода вдоль всей траектории не имеет
зз
смысла. Поэтому в данном случае предлагается в качестве ошимальной
выбрать такую стационарную стратегию, которая дает наибольший
ожидаемый доход за один этап. Для решения >той задачи можно
использовать два метода.
Метод полного перебора. Пусть всего имеется d стационарных
стратегий, тогда для каждой стратегии s = 1,2.d вычисляем по матрицам
P(t) значение
одноэтапный доход из состояния i для .каждого i ~ 1........т; затем
вычисляем вектор предельных вероятностей а ♦, например, используя (9),
a'j = XPyS,ar aj дляу = 1,...,т;	=1.	(Ю)
•ы	>1
После этого вычисляем ожидаемый одношаговый доход для этой
стационарной стратегии
(11)
»=1
и переходим к следующей стратегии.
В результате перебора определяется оптимальная стационарная
стратегия 5*, такая что
f(s'f > f(s) Vs =	(12)
Пример 2.7. Рассмотрим систему из примера 2.3. Для нее имеется 8
стационарных стратегий:
1 (1->а, 2->а, 3->а), 2 (1->Ь, 2->Ь, 3->Ь), 3 (1->Ь, 2->а, 3->а),
4 (1 —»а, 2-»Ь, 3-»а), 5 (1->а, 2->а, 3-»Ь), 6 (1 —»Ь, 2->Ъ, 3—>а),
7 (1 -»Ь, 2-» а, 3->Ь), 8 (1 -»а, 2->Ь, 3—>Ь), напомним, что а означает “не
вносить удобрения”, Ь - “вносить удобрения”. Результаты даны в
следующей таблице.
34
Л	hi	ь.	ь,		> "1	• г/у	/**'
1	5.3	3	4	0	0	1	4
2	4 7	3.1	0 4	'./ /59	31/ /59	22/ /59	2.256
3	4 7	3	4	0	0	1	4
4	5.3	3.1	4	0	0	1	4
5	5.3	3	04	V /154	69/ 154	•0/ /154	1.^24
6	4.7	3.1	4	0	0	1	4
7	4.7	3	04	%37	62 /137	70/ /137	L734
8	5.3	3.1	0.4	69 /135	69/ 435	54 135	2216
Таким образом $ * =2 ( всегда вносить удобрения i
Заметим, что формулы (10) не всегда однозначно определяют а •, по
свойству 4, однозначность гарантируется. если Р ыхгпелствус!
марковской цепи с эргодическим классом, содержащим все состояния
Как уже отмечалось, число стационарных стратегий может быть
очень велико, что может вызвать затруднения при реализации метода
полного перебора. Тогда следует использовать иной подход
Метод преобразования к задаче линейного программирования.
Перепишем задачу (10) -(12) в следующем виде
max ->1Ё#'’ а>\ау ~Ё/£Ч =QA-°J=и,«;Ёо =1 -
j=i. .it »=1
(13)
Теперь введем вспомогательные переменные д* - вероятность вь ' г
альтернативы к при условии, что система находится в состоянии i. Если
/е(0,1} h^j<7*=1 для i=1,...,m, где K<i)= {1, то каждый набор
*=i
значений этих переменных будет определять одну из стационарных
стратегий, причем
/М	у/**
35
Генери лиДича (13) можс! бы и. (вменена »квивалснтной задачей
<>п । имитации
•и / t	\
max	.	(И;
1-1 \А I	J
при oi рапичениях
f Г	\
\ч'ь> в0
। \» ।	7
«	Z
/I	A I
a,£OJ = l,. ,/н; q е{0,1[ / = A = l,...,€.
(15)
Задача (14), (15) имев! mнепрерывных переменных а и Im булевых
переменных g*. Введем теперь новые переменные a>tk - а//* -совместная
вероятность юго, что система находится в состоянии /и выбирается
альтернатива к.
Г
1огда а, = и Ч, =	• Используя новые переменные,
*"	X®,
J I
преобразуем задачу (14), (15) к эквивалентному виду:
(16)
(-1 А-1
при ограничениях
Г	т С
=0	/и;
Й»1	I I Л«1
т
Е2а=1> <4*^° i = к
i~l A-I
(17)
t
По определению, равенства ^<у* =1 для i = l,...,m выполняются
к ।
автоматически, однако задача (16), (17) позволяет получить точное
решение задачи (14), (15) только в том случае, когда для каждого индекса
/в точности одно значение <м,*при всех к — 1, ,€ ненулевое.
Действительно тогда переменные г;*будут принимать значения {0,1}.
Если для любой альтернативы к матрица Распределяет марковскую цепь
с эргодическим классом, содержащим все тсостояний, то но свойству 4
имеется т независимых ограничений -равенств в (17), т.е. при решении
36
задачи линейною npoi раммирования (16;, (17; каждый базис содержит
ровно m элементов. I 1оэтому если выбрать начальный базис так чтобы для
каждого 7 только одному индексу А € Л"соответствовала ненулевая
переменная 69 А, го это свойство сохраняется и для решения
w’ / =	/я, к = 1,.../.
Тогда пары t-> к(i) при условии d)’it *0 / = гп будут определять
оптимальную стационарную стратегию,
а' = 22^ для 7 »
/ «I
а значение целевой функции в (16) будет давать наибольший ожидаемый
одноэтапный доход.
Пример 2.8. Для системы из примера 2.3 задача (16), (17)
приобретет вид:
1ПЗХ —»5.3<z>u +4.7<z>12 + ЗбУ21 + 3.1бУ22 -6У31 +0.4й>32при ограничениях
бУц + 6z>12 -(0.2гдн + 0.3б9,2 + 0.1<у22 + 0.05бУ32) = 0
бУ2| + 6У22 - (О.5бУ, , + О.6бУ12 + 0.5гу2| + 0.6бУ22 + 0.4бУ32) ~ 0
бэ31 +<д32 -(0.3б9,, +0.1б912 +0.5<у21 + 0.3бэ22 +693, +0.55<у32) = 0
69,, + 69,2 + 6Э2| + 6922 + 6У3, + 6У32 — 1
а)л > 0 для i = 1,2,3,к = 1,2.
Применяя симплекс — метод, получаем решение
, Г = 2.256,5* = (I -+ Ь, 2 -> Ь,3 -> Ь),
т.е. аналогично результату метода полного
перебора из примера 2.7.
2.6. Марковские процессы с дисконтированием на бесконечном
ишервале времени
При учете коэффициента дисконтирования суммарный ожидаемый
доход при бесконечном увеличении числа этапов не стремится к
37
бесконечности» а достигает некоторое» предельно! о конечною «качения,
полому можно определят!, оптимальную епщнонарную CipaielHIO,
дающую наибольший суммарный ожидаемый доход. )(дя конечною числа
напои имеем функциональное уравнение
/„<»>= max	+ Г Е Ру fn-\( J А п =  1 е 1 
k*K(i) (	/< 1	J
для стационарной стратегии имеем
т
= 1,2./ = 1.т	(18)
>1
Если f(ns)(l) -> при п -> 00, то, обозначив v„ = .получим систему
уравнений
v„ ^>+y±p^vJS i =
7=1
Теперь с помощью конечного метода можно найти оптимальную
стационарную стратегию управления системой.
Метод итераций по стратегиям. Выбираем произвольно стацио-
нарную стратегию 5, затем находим значения гидля/ = 1....т.решая
систему (18). После этого для каждого состояния i находим альтернативу
к( i) из условия
лт	fn
+	= maxW +	-
7=1	киК(<)	у-1
таким образом определяя стационарную стратегию s'. Если s' = s, то
оптимальная стратегия получена, иначе полагаем 5 = s' и переходим к
следующей итерации.
Пример 2.9. Рассматривается система из примера 2.3 с
коэффициентом дисконтирования / = 0.6.
Первая итерация. Выбираем s = (1 —> а,2 —> а,3 —> а).
Система (18) приобретает вид (s = 1)
v„ - 0.6(0.2v„ + 0.5v„ + 0.3v3,) = 5.3
Ъ,-0.6( +O.5vb + O.5vJ1) = 3
v»‘-°-6(	v„) = -l
и дает решение v, = (6.6Д.21-2.5). Получаем
за
/	b't	6?
1	53	47
2	3	3.1
3	-1	04
I	V я		k(i)
I	6.6	6 89	2
2	3.21	4JZ	2
3	-2.5	0.54	2
отсюда ж’ = (1 —► ЬД —► 63 —* 6) • я Гкмагасы > « ж'.
Вторая итерания Решаем сактему (i « 2)
vb — О 6(0 3vu + О 6» ъ * 0.1»->г I « 4 “
’ v2, -0 6(0 l»u т06^ *0 3»;, «31
v3> -06fo05vu -04^-05^«О*
получаем vf = (8 88.6.62.3 37 > Гккжолгу
i	V s		bi/	
1	888	8.95	1	—I
2	6.62	5.99	7	1
3	3.3“	02	2	
Треялл мямрацил Решаем ежтемгу U «t)
v -0.O(0.2i *0.5v -й 'м = 53
vb -O.b(O.lv,f +0.6v^ ♦ 03*v * =3.1
1^-0.6^0.051 ~0.4v.,*0'S «3=0 4
получаем ve «=(8.^K 6oX 338V Гкктвшг>
i	V 5	V (МЫИ	k(i)
1	8.98	8.91	1
2	6.63	6.00	2
3	3.38	1.02	2
то s* = (I ->а,2 ->b,3-+b) - оптимальная стационарная стратегия
40
( писак литературы
I.	Ьеллмаи Р Динамич»< жн программирование М ИЛ. I960
2	Беллман Р, Дрейфус С Прикладные задачи динамического
мироваиия М/Наука, J 965, 460 с.
3,	Кемени Дж,, ( иелл Дж Конечные пели Маркова М Наука.
272 с.
4.	Майн X., Осаки С. Марковские процессы принятия решений
Наука, 1977. 176 с.
5	Морозов В.В., Сухарев АГ, Федоров В В. Исследование one
задачах и упражнениях. — М.: Высшая школа, 1986. 287 с.
6.	Оре О. Теория графов. - М.: Наука. 1980 - 336 с.
7.	Романовский ИВ. Алгоритмы решения экстремальных задач. -1
Наука, 1977.-352 с.
8.	Сухарев А.Г., Тимохов А.В., Федоров В.В Курс методов оптим
М.: Наука, 1986.-328 с.
9.	Таха X. Введение в исследование операций. - М.: Мир; Кн. 1, 1
479 с.; Кн.2, 1985.-496 с.
10.	Ховард Р.А. Динамическое программирование и марковские про
— М.: Советское радио, 1964. - 190 с.