Output Summary 3 страница

S		v;
/= 1	/= 2	/= 3
	5,3	3,0	-1,0
	4,7	3,1	0,4
	4,7	3,0	-1,0
	5,3	3,1	-1,0
	5,3	3,0	0,4
	4,7	3,1	-1,0
	4,7	3,0	0,4
	5,3	3,1	0,4

Стационарные вероятности находятся из уравнений

я*Р*=я\

л, + л₂+...+ л„, =1.

Для иллюстрации применения этих уравнений рассмотрим стратегию s = 2. Соот­ветствующие уравнения имеют следующий вид.

0,3л, + 0,1л₂ + 0,05л₃ =тс,, 0,6л, + 0,6л₂ + 0,4л₃ = л₂, 0,1л, + 0,3л₂ +0,55л₃ = л₃, л, + л₂ + л₃ = 1.

(Отметим, что одно из первых трех уравнений избыточно.) Решением системы будет

₂__6_ ₂_31_ ₂_22 ~ 59' "² ~59' *' ~ 59'

Глава 19. Марковские процессы принятия решений

В данном случае ожидаемый годовой доход равен

Е¹ = ]Гя? v,² = — (6 х 4,7 + 31 х 0,31 + 22 х 0,4) = 2,256.

;=| 59

Результаты вычислений и для всех стационарных стратегий приведены в сле­дующей таблице. (Отметим, что хотя каждая из стратегий 1, 3, 4 и 6 имеет погло­щающее состояние (состояние 3), это никоим образом не влияет на результаты вы­числений. По этой причине л_х = л_г = 0тл л_ъ = 1 для всех этих стратегий.)

S	К	А	<
				-1,0
	6/59	31/59	22/59	2,256
				0,4
				-1,0
	5/154	69/154	80/154	1,724
				-1,0
	5/137	62/137	70/137	1,734
	12/135	69/135	54/135	2,216

Из этой таблицы видно, что стратегия 2 дает наибольший ожидаемый годовой до­ход. Следовательно, оптимальная долгосрочная стратегия требует применения удобрений независимо от состояния системы.

УПРАЖНЕНИЯ 19.3.1

1. Решите задачу из упражнения 19.2.1 методом полного перебора при беско­нечном числе этапов.

2. Решите задачу из упражнения 19.2.2 при бесконечном горизонте планирова­ния методом полного перебора.

3. Решите задачу из упражнения 19.2.3 методом полного перебора, предпола­гая, что горизонт планирования бесконечен.

19.3.2. Метод итераций по стратегиям без дисконтирования

Чтобы оценить трудности, связанные с применением метода полного перебора, предположим, что у садовника вместо двух имеется четыре стратегии поведения (альтернативы): не удобрять, удобрять один раз в сезон, удобрять дважды и удоб­рять трижды в сезон. В этом случае общее число стратегий, имеющихся в распоря­жении садовника, составляет 4* = 256 стационарных стратегий. Таким образом, при увеличении числа альтернатив с 2 до 4 число стационарных стратегий возрас­тает по экспоненте с 8 до 256. Трудно не только перечислить в явном виде все эти стратегии, но и может оказаться также недопустимо большим объем вычислений, требуемых для оценки всего множества стратегий.

19.3. Модель с бесконечным числом этапов

Метод итераций по стратегиям основывается на следующем. Как показано в разделе 19.2, для любой конкретной стратегии ожидаемый суммарный доход за л-й этап определяется рекуррентным уравнением

т

/.(0 = ^v<+Z/V/:*. (Л ' = 1.2,..., т.

Это уравнение и служит основой метода итераций по стратегиям. Однако, чтобы сделать возможным изучение асимптотического поведения процесса, вид уравне­ния нужно немного изменить. В отличие от величины п, которая фигурирует в уравнении и соответствует ге-му этапу, обозначим через rj число оставшихся для анализа этапов. Тогда рекуррентное уравнение записывается в виде

т

/,(0 = v₍ + I^/,-,(у). ' = 1.2,..., т.

Здесь — суммарный ожидаемый доход при условии, что остались не рассмотрен­ными п этапов. При таком определении п можно изучить асимптотическое поведе­ние процесса, полагая при этом, что л -» оо.

Обозначим через я = (я,,п₂,...,п_и) вектор установившихся вероятностей состоя­ний с матрицей переходных вероятностей Р=|ру| и пусть £ = n,v, + t₂v₂+... + 7c_mv„ —

ожидаемый доход за этап, вычисленный по схеме раздела 19.3.1, тогда можно по­казать, что при достаточно большом п

/„(') = л*+ /(').

где f(i) — постоянный член, описывающий асимптотическое поведение функции f,j(i) при заданном состоянии i.

Так как /%(/) представляет суммарный оптимальный доход за п этапов при за­данном состоянии i, а Е — ожидаемый доход за один этап, то интуитивно понят­но, почему величина f_n(i) равна сумме цЕ и поправочного числа f(i), учитываю­щего определенное состояние i. При этом, конечно, предполагается, что число п достаточно велико.

Теперь рекуррентное уравнение можно записать в следующем виде

п£ + / (,') = v, + {(Ti -1) £ + f(j)}, i = 1, 2,т.

Упростив это уравнение, получаем

E+f(0-£Pi,fU) = ^vi> ' = 1.2.....m,

т.е. имеем т уравнений с т + 1 неизвестными /(1), /(2),f(m)nE.

Здесь, как и в разделе 19.3.1, конечной целью является определение оптималь­ной стратегии, приводящей к максимальному значению Е. Так как имеется т уравнений ст + 1 неизвестными, оптимальное значение Е нельзя определить за один шаг. В связи с этим используется итеративная процедура, начинающаяся с произвольной стратегии, а затем определяется новая стратегия, дающая лучшее значение Е. Итеративный процесс заканчивается, если две последовательно полу­чаемые стратегии совпадают.

Глава 19. Марковские процессы принятия решений

Итеративный процесс состоит из двух основных шагов.

1. Шаг оценки параметров. Выбираем произвольную стратегию s. Используя соответствующие ей матрицы Р* и R* и полагая (произвольно) f(m) — О, реша­ем уравнения

т

^Л"-/'(')-Z Л'/'(У)-v;. i = I, 2,..., и

относительно неизвестных Ё, f(l),f(m - 1). Переходим к следующему шагу.

2. Шаг улучшения стратегии. Для каждого состояния i определяем альтерна­тиву k, обеспечивающую

maxjvf+f>J/^s(/)J,/=1,2,...,т.

(Здесь используются значения f(j), j=l, 2, т, определенные на шаге оценки параметров.) Результирующие оптимальные решения для состояний 1, 2, т формируют новую стратегию t. Если s и t идентичны, то алгоритм заканчивается; в этом случае t — оптимальная стратегия. В противном слу­чае полагаем s = t и возвращаемся к шагу оценки параметров.

Оптимизационная задача на шаге улучшения стратегии нуждается в пояс­нении. Целью этого шага является получение максимального значения Е. Как показано выше,

Поскольку /(г) не зависит от альтернатив k, задача максимизации на шаге улучше­ния стратегии эквивалентна максимизации Е по альтернативам k.

Пример 19.3.2

Решим задачу садовника методом итераций по стратегиям.

Начнем с произвольной стратегии, исключающей применение удобрений. Имеем соответствующие матрицы

	'0,2	0,5	0,3'		'7 6 3N
р =		0,5	0,5	, R =	0 5 1
	. о		1,		0 0 -1,

Уравнения шага оценки параметров принимают вид

£ + /(1) -0,2/(1)- 0,5/(2) - 0,3/(3) = 5,3,

£ + /(2) -0,5/(2)-0,5/(3) = 3,

£ + /(3) -/(3) = -1.

ПолагаяД3) = 0, получаем решение этих уравнений

£ = -1, /(1) = 12,88, /(2) = 8, /(3) = 0.

Перейдем к шагу улучшения стратегии. Результаты соответствующих вычислений приведены в следующей таблице.

19.3. Модель с бесконечным числом этапов

	vf+ />*/(!)+Л*/(2)+ /^/(3)				Оптимальное решение
/'	/с= 1	к = 2			f(i) к
	5,3 + 0,2 х 12,88 + 0,5 х 8 + 0,3 х 0 = 11,875	4,7+ 0,3x12,88 +0,6 х	8 + 0,1 х0 =	13,36	13,36 2
	3 + 0 х 12,88 + 0,5 х 8 + 0,5 х 0 = 7	3,1 +0,1 х 12,88 +0,6 х	8 + 0,3x0 =	9,19	9,19 2
	-1 + 0x12,88 + 0x8 + 1 х0 = -1	0,4+ 0,05x12,88 +0,4 х	8 + 0,55 х 0	= 4,24	4,24 2

Новая стратегия предусматривает применение удобрений независимо от состояния почвы. Так как новая стратегия отличается от предыдущей, повторяется шаг оцен­ки параметров. Новой стратегии соответствуют матрицы

	Г 0,3	0,6	0,Г		'6	5 -Г
р =	0,1	0,6	0,3	, R =		4 0
	0,05	0,4	0,55 j		,6	3 -2,

Эти матрицы определяют следующие уравнения:

£ + /(1)-0,3/(1)-0,6/(2)-0,1/(3) = 4,7,

£ + Д2)-0,1/(1)-0,6/(2)-0,3/(3) = 3,1,

Е + /(3)-0,05/(1)-0,4/(2)-0,55/(3) = 0,4.

Снова полагаяДЗ) = 0, получаем решение

£ = 2,26, /(1) = 6,75, /(2) = 3,80, /(3) = 0.

Результаты вычислений на шаге улучшения стратегии приведены в следующей таблице.

	vf + A'/(0 + A<2/(2) + ^3/(3)			Оптимальное решение
/	к= 1	к = 2		т к
	5,3 + 0,2 х 6,75 + 0,5 х 3,80 + 0,3 х 0 = 8,55	4,7 + 0,3 х 6,75 + 0,6 х 3,80 + 0,1 х 0	= 9,01	9,01 2
	3 + 0 х 6,75 + 0,5 х 3,80 + 0,5 х 0 = 4,90	3,1 + 0,1 х 6,75 + 0,6 х 3,80 + 0,3 х 0	= 6,06	6,06 2
	-1 + 0 х 6,75 + 0 х 3,80 + 1 х 0 = -1	0,4 + 0,05 х 6,75 + 0,4 х 3,80 + 0,55 х 0	= 2,26	2,26 2

Новая стратегия, требующая применения удобрений независимо от состояния сис­темы, идентична предыдущей, поэтому последняя стратегия оптимальна и итера­тивный процесс заканчивается. Естественно, что этот результат совпадает с резуль­татом, полученным методом полного перебора (подраздел 19.3.1). Однако следует отметить, что метод итераций по стратегиям достаточно быстро сходится к опти­мальному решению, что является его характерной особенностью.

Глава 19. Марковские процессы принятия решений

УПРАЖНЕНИЯ 19.3.2

1. Пусть в задаче упражнения 19.2.1 горизонт планирования бесконечен. Ре­шите эту задачу методом итераций по стратегиям.

2. Решите задачу упражнения 19.2.2 методом итераций по стратегиям, предпо­лагая, что горизонт планирования бесконечен.

3. Решите задачу упражнения 19.2.3 методом итераций по стратегиям, предпо­лагая, что горизонт планирования бесконечен.

19.3.3. Метод итераций по стратегиям с дисконтированием

Описанный метод итераций по стратегиям можно обобщить на случай дискон­тирования. Если обозначить через а (< 1) коэффициент дисконтирования (переоценки), то рекуррентное уравнение при конечном числе этапов можно запи­сать в следующем виде (см. раздел 19.2)

(Отметим, что п равно числу этапов, которые необходимо рассмотреть.) Можно по­казать, что при п -» оо (модель с бесконечным числом этапов) f^i) = f(i), где f(i) — приведенный к текущему моменту времени дисконтированный доход при условии, что система находится в состоянии i и функционирует на бесконечном интервале времени. Таким образом, долгосрочное поведение f^i) при п -> оо не зависит от зна­чения п. В этом состоит отличие от случая без дисконтирования, когда fiJLi)" пЕ + f(i). Этого следовало ожидать, так как в случае с дисконтированием влияние будущих доходов асимптотически уменьшается до нуля. Действительно приведенный доход f(i) должен стремиться к постоянной величине при 77 -»<».

С учетом вышеизложенного в данном случае при использовании метода итера­ций по стратегиям выполняются следующие действия.

1. Шаг оценки параметров. Для произвольной стратегии s с матрицами Р* и R' решаем систему из т уравнений

относительно т неизвестных f(l), f(2),f(m).

2. Шаг улучшения стратегии. Для каждого состояния i определяем альтерна­тиву k, обеспечивающую

где f(j) имеют значения, определенные на шаге оценки параметров. Если по­лученная стратегия t совпадает со стратегией s, то алгоритм закончен; в этом случае стратегия t оптимальна. В противном случае полагаем s = t и повторя­ем шаг оценки параметров.

Пример 19.3.3

Решим задачу из примера 19.3.2 с учетом коэффициента дисконтирования а= 0,6.

19.3. Модель с бесконечным числом этапов

Выберем произвольную стратегию, например s= {1,1, 1}. Матрицы Р и R (Р¹ и R¹ в примере 19.3.1) определяют уравнения

/(1) - 0,б[0,2/(1) + 0,5/(2) + 0,3/(3)] = 5,3,

/(2)-0,б[ 0,5/(2) + 0,5/(3)] = 3,

/(з)-о,б[ +/(з)] = -1.

Решение этих уравнений дает

/₁ = 6,61,/₂ = 3,21,/₃ = -2,5.

Результаты вычислений итерации по улучшению стратегии приведены в следую­щей таблице.

vf + ОЛРп/0) + Р*№ + /4/(3)] Оптимальное

	к=1	к = 2		т	к
	5,3 + 0,6[0,2 х 6,61 + 0,5 х 3,21 + 0,3 х х (-2,5)] = 6,61	4,7 + 0,6[0,3 х 6,61 + 0,6 х х (-2,5)] = 6,90	3,21 + 0,1 х	6,90
	3 + 0,6[0 х 6,61 + 0,5 х 3,21 + 0,5 х х (-2,5)] = 3,21	3,1 +0,6[0,1 х6,61 +0,6х х (-2,5)] = 4,2	3,21 + 0,3 х	4,2
	-1 + 0,6[0 х 6,61 + 0 х 3,21 + 1 х х (-2,5)] = -2,5	0,4 + 0,6[0,05 х 6,61 + 0,4 х (-2,5)] = 0,54	х 3,21 + 0,55 х	0,54

Шаг оценки параметров, выполненный на основе матриц Р² и R² (пример 19.3.1), приводит к следующим уравнениям.

/(1) - 0,б[0,3/(1) + 0,6/(2) + 0,1/(3)] = 4,7, /(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. Решением этих уравнений будет

у; = 8,89,/₂ = 6,62,/₃ = 3,37.

Результаты, полученные на шаге улучшения стратегии, приведены в следующей таблице.

	vf +0,6[Л*/(1)+ />*Д2) + />*ДЗ)]				Оптимальное решение
/	к = 1	к = 2			t\l) к
	5,3 + 0,6[0,2 х 8,89 + 0,5 х 6,62 + 0,3 х х 3,37] = 8,96	4,7 + 0,6[0,3 х х 3,37] = 8,89	8,89 + 0,6 х	6,62 + 0,1 х	8,96 1
	3 + 0,6[0 х 8,89 + 0,5 х 6,62 + 0,5 х х 3,37] = 6,00	3,1 + 0,6[0,1 х х 3,37] = 6,62	8,89 + 0,6 х	6,62 + 0,3 х	6,62 2
	-1 + 0,6[0 х 8,89 + 0 х 6,62 + 1 х 3,37] = = 1,02	0,4 + 0,6[0,05 х 3,37] = 3,37	х 8,89 + 0,4	х 6,62 + 0,55 х	3,37 2

Так как новая стратегия {1,2, 2} отличается от предыдущей, повторяем шаг оценки параметров с использованием матриц Р⁸ и R⁸ (пример 19.3.1). Получаем следующие уравнения.

752 Глава 19. Марковские процессы принятия решений

/(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.

Решением этих уравнений будет

/₁ = 8,97,/₂ = 6,63,/₃ = 3,38.

Результаты, полученные на шаге улучшения стратегии, приведены в следующей таблице.

vf + 0,6[ _А< Д1) + _Л'₂/(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[0х 8,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).

УПРАЖНЕНИЕ 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, со­ответствующей

max |\*v; | я'Р'= я\ < + я₂+... + < =1, <>0, i = 1, 2,..., А,

19.4. Применение методов линейного программирования

где S — множество всех возможных стратегий. Здесь я',» = 1,2,...,т, представляют

установившиеся вероятности марковской цепи р*. Подобная задача была решена в подразделе 19.3.1 полным перебором всех стратегий s.

Приведенная задача служит основой для формулировки марковской задачи принятия решений в виде задачи линейного программирования. Однако необходи­мо преобразовать переменные задачи таким образом, чтобы оптимальное решение автоматически определяло оптимальное действие (альтернативу) k, когда система находится в состоянии i. Совокупность всех оптимальных действий определяет оп­тимальную стратегию s*.

Это реализуется следующим образом. Введем обозначение: q) — условная веро­ятность выбора альтернативы k, когда система находится в состоянии i. Тогда зада­чу можно представить в следующем виде.¹

Заметим, что вероятности p_tj являются функциями выбранной стратегии и, следо­вательно, конкретных альтернатив k этой стратегии.

Ниже будет показано, что эту задачу можно преобразовать в задачу линейного программирования путем соответствующих подстановок, включающих q\. Но сле­дует отметить, что приведенная выше формулировка эквивалентна исходной фор­мулировке задачи из раздела 19.3.1 только при условии, что q\ = 1 для одного k при

каждом £, так как только при этом сумма Z*-i^*^v* будет сведена к v*, где k' — вы­бранная оптимальная альтернатива. Предлагаемая здесь линейная задача учиты­вает это условие автоматически.

Обозначим w_ik = Для ^всех ' ^и По определению величина w_it представляет со­бой совместную вероятность пребывания в состоянии i и принятия решения к. Из теории вероятностей известно, что

при ограничениях

т

^%j = Е^Я<Л/' У = 1. 2,т,

71, + 71₂ +...+ К_т = 1,

q]+q²_t +... + q? = \, / = 1,2,...,/и, я, > 0, q. > 0 для всех /' и к.

к

Следовательно,

Ч, =

Поэтому очевидно, что ограничение ^ я, = 1 можно записать в виде

т К

¹ Здесь и далее К — количество возможных альтернатив. — Прим. ред.

Глава 19. Марковские процессы принятия решений

Ограничение ⁼' ^также автоматически вытекает из способа определения q)

через Wj_t. (Проверьте!) Таким образом, задачу можно записать в следующем виде.

Т К

Максимизировать Е = ^^vf w_a

при ограничениях

= 1 *=1

т К

11", =1,

-1 *=i

w_lt>0, i = l,2,...,m; к = 1,2,-,К.

Сформулированная задача представляет собой задачу линейного программирования с переменными w,_t. Покажем, что ее оптимальное решение автоматически гарантиру­ет, что q\ = 1 для одного k при любом i. Заметим, что в задаче линейного программиро­вания имеется т независимых уравнений (одно уравнение, соответствующее я = яР, избыточно). Следовательно, задача должна включать т базисных переменных. Однако можно показать, что w_lt должно быть строго положительным по меньшей мере при

одном k для каждого /. Из этих двух утверждений можно заключить, что величина

может принимать только два значения (0 или 1), что и требовалось доказать. (Фактически полученный выше результат показывает также, что я, = X*-i^vt'<* ^=VV > где k - альтернатива, соответствующая w_jt > 0.)

Пример 19.4.1

Ниже приведена формулировка задачи садовника без дисконтирования в виде за­дачи линейного программирования.

Максимизировать £ = 5,3w,, + 4,7w_]2 + 3w_2l + 3,lw₂₂ - w₃₁ +0,4w₃₂ при ограничениях

w_M + w₁₂-(0,2w_M + 0,3w_l2 +0,lw₂₂ + 0,05w₃₂) = 0,

w_2l + w₂₂ -(0,5w_u +0,6w_]2 + 0,5w_2] + 0,6w₂₂ + 0,4w₃₂) = 0, w₃₁ + w₃₂ -(0,3w_n + 0,lw_l2 + 0,5w_2l + 0,3w₂₂ + w_3l + 0,55w₃₂) = 0, w„ + w_l2 + w_2l + w₂₂ + w_3l + w_i2 = 1, w_lt It 0 при любых i и к.

Оптимальным решением является w_n= w_2l= w_3l = 0, w₁₂ = 0,1017, w₂₂ = 0,5254 nw₃₂ = 0,3729. Это означает, что q] =q\=q\ = \. Таким образом, оптимальная стратегия требует выбора альтернативы 2 (к = 2) при /'= 1, 2 и 3. Оптимальное значение Е равно 4,7x0,1017 + 3,1x0,5254 + 0,4x0,3729 = 2,256. Интересно отметить, что положитель­

19.4. Применение методов линейного программирования

ные значения w_lk в точности равны значениям я,, соответствующим оптимальной стратегии, определенной с помощью метода полного перебора в примере 19.3.1, что доказывает непосредственную взаимосвязь между двумя методами решения.

Рассмотрим теперь марковскую задачу принятия решений с дисконтированием. В подразделе 19.3.2 эта задача описывается рекуррентным уравнением

/(/) = maxU + a£pj/(y), / = l,2,...,m.

у»'

Это уравнение эквивалентно следующему:

т

/(/) > cC£,P-,f{j) + v., для всех ink,

при условии, что при любом i функция f(i) достигает минимального значения. Рас­смотрим теперь целевую функцию

In

минимизировать Z^./(')'

где b_t (> 0 при всех i) — произвольные константы. Можно показать, что оптимиза­ция этой функции (при ограничениях в виде приведенных выше неравенств) дает, что и требуется, минимальное значение f(i). Таким образом, задачу можно записать следующим образом.

m

Минимизировать ZV(')

при ограничениях

/(О ^_aZPijfU) - ^v'> ^пр^{и любых}'^и *.

/(/') не ограничены по знаку, / = 1,2,...,т. Двойственной к приведенной выше задаче является задача

т К

максимизировать ZZ^V*^W>*

при ограничениях

К т К

*=1 1=1 *=1

и^>0при / = l,2,...,m; к = \,2,...,К.

Пример 19.4.2

Рассмотрим задачу садовника с коэффициентом дисконтирования а = 0,6. Если по­ложить Ъ_х = Ъ_г = b₃ = 1, то двойственную задачу линейного программирования можно записать в следующем виде.

Максимизировать 5,3w_M + 4,7w₁₂ + 3w₂₁ + 3,lw₂₂ - w,, + 0,4w,₂

756 Глава 19. Марковские процессы принятия решений при ограничениях

w„ + w,₂-0,6[0,2w_n + 0,3w_l2 + 0,lw₂₂ + 0,05w₃₂] = l,

w₂₁ + w₂₂ -0,6[0,5w_n +0,6w_l2 + 0,5w₂, + 0,6w₂₂ + 0,4w₃₂] = l, w,, + w₃₂ -0,6[0,3w_n + 0,lw_l2 + 0,5w₂₁ + 0,3w₂₂ + w_3P + 0,55w₃₂] = 1, w_lk > 0 при любых / и к.

Оптимальным решением будет w₁₂ = w_2] = w_3] = 0, w_n= 1,5678, w₂₂ = 3,3528 и w₃₂ = 2,8145. Из этого решения следует, что оптимальной стратегией является {1,2,2}.

УПРАЖНЕНИЯ 19.4

1. Сформулируйте указанные ниже задачи в виде задач линейного программи­рования.

a) Задача упражнения 19.3.2.1.

b) Задача упражнения 19.3.2.2.

c) Задача упражнения 19.3.2.3.

19.5. ПРИЛОЖЕНИЕ: ОБЗОР ТЕОРИИ ЦЕПЕЙ МАРКОВА

Рассмотрим дискретные моменты времени {t_k}, k = l, 2.....и пусть Е, — слу­чайная величина, характеризующая состояние системы в момент t_k. Семейство случайных величин } образует стохастический процесс. Состояния в момент

времени t_k, в которых может находиться в этот момент система, формируют пол­ную и взаимно исключающую группу событий. Число состояний системы может быть конечным или бесконечным. Так, например, распределение Пуассона

P„(t) =-Ц и = 0,1,2,...

я!

представляет стохастический процесс с бесконечным числом состояний. Здесь слу­чайная величина п соответствует числу наблюдаемых событий в интервале от 0 до t (начальным моментом считается 0). Таким образом, состояния системы в любой момент t задаются случайной величиной п = 0, 1, 2,...

Еще одним примером может служить игра с k подбрасываниями монеты. Каждое испытание (подбрасывание монеты) можно рассматривать как некоторый момент времени. Полученная последовательность испытаний образует случайный процесс. Состоянием системы при любом испытании является либо "герб", либо "решка".

В данном разделе приводятся сведения о таких случайных процессах, как марковские процессы и марковские цепи. Цепь Маркова является частным случаем марковских процессов. Цепи Маркова используются при изучении крат­косрочного и долгосрочного поведения стохастических систем с дискретным множеством состояний.

19.5.1. Марковские процессы

Марковский процесс описывает поведение стохастической системы, в которой наступление очередного состояния зависит только от непосредственно предшест­