Документ: Учебное пособие Немирко Манило, страницы 46-50

условное оптимальное управление в этом случае равно x3 (S2′ )= x3(2). Таким же способом можно вычислить, что W3 (S2′′)= 9 , x3 (S2′′)= x3(3) ; W3 (S2′′′)= 7, x3 (S2′′′)= x3(6) . Переходим к оптимизации 2-го шага. Для него

W2 (S1 )= min{w2 +W3 (S2 )}.

x2

Если перед 2-м шагом G находился в состоянии S1′, то x2 {x2(1), x2(2)}, поэтому

W2 (S1' )= min{ w2(1) +W3 (S2′ ) , w2(2) +W3 (S2′′) }= min{[11+9], [4 +9]}=13,

и условное оптимальное управление для состояния S1′ равно x2 (S1′)= x2(2).

Аналогично проводятся расчеты и для других предыдущих состояний этого шага, а затем рассчитывается 1-й шаг, перед которым G всегда находится в S0 . Все результаты условной оптимизации сведены в табл. 2.1.

На рис. 2.9 стрелками показаны все условные оптимальные управления, а в кружочках проставлены значения условного минимума для

									Таблица 2.1
Номер	Исходное	Условный минимум	Условное оптимальное						Состояние
Номер	состояние,	целевой функции,	Условное оптимальное							после
шага, i	состояние,	целевой функции,	управление, x			(S	i−1	)		после
	Si−1	Wi (Si−1)			i		i−1		управления, Si
	Si−1	Wi (Si−1)							управления, Si
	S3′	6		x(1)						S4
4				4
4	S3′′	5		x(2)						S4
	S3′′	5		x(2)						S4
				4
	S2′	9		x(2)						S3′′
				3
3	S2′′	9		x(	3)					S3′
				3
	S2′′′	7		x(6)						S3′′
				3
	S1′	13		x(2)						S2′′
				2
2	S1′′	10		x(	3)					S2′
				2
	S1′′′	18		x(7)						S2′′′
				2
1	S0	16	x(1)	или x(		2)			S1′	или S1′′
			1		1

46

	S1′	S2′	S3′
	13	9	6
S0			S4
16	10	9
	S1′′	S2′′
	18	7	5
	S1′′′	S2′′′	S3′′
		Рис. 2.9

всех состояний. Это то минимальное время, которое требуется для достижения S4 .

Из рисунка видно, что существует две различные оптимальные траектории, переводящие G из S0 в S4 . Они могут быть записаны в виде следу ю- щих двух цепочек:

S0 → S1′ → S2′′ → S3′ → S4; S0 → S1′′→ S2′ → S3′′ → S4 ,

и эквивалентны по временным затратам (16 единиц).

2.3.Управление переходом организма в нормальное состояние

вусловиях неопределенности

До сих пор мы рассматривали детерминированную модель динамического программирования. В реальной жизни как на состояние системы, так и на целевую функцию влияют случайные факторы, и поведение системы зависит не только от начального состояния S0 и выбранного управления x , но и от случайности. Рассмотрим стохастическую модель задачи о кратчайшем пути на ациклической сети [14]. Допустим существование в системе условных вероятностей P (Si Si−1 , xi ) того, что на i-м шаге управления система

перейдет в состояние Si при условии, что до этого она находилась в Si−1 и было применено управление xi . Это условие представляет собой допущение о марковском свойстве системы, согласно которому вероятность перехода системы в какое-либо состояние Si зависит только от состояния Si−1, из которого совершается переход, и от применяемого управления xi , но никак не зависит от предыстории системы, предшествующей ее переходу в Si−1.

Таким образом, теперь управляющее воздействие xi на 1-м шаге управления может лишь изменить вероятности перехода из данного состояния Si−1

47

в другие состояния Si . Теперь, находясь в каком-либо состоянии и применяя

некоторое управление, можно говорить только о средних затратах W времени достижения конечного состояния, которые вычисляются как взвешенные по соответствующим вероятностям затраты, рассмотренные по всем возможным из данного состояния траекториям. В этом случае, очевидно, задача заключается в нахождении такого множества оптимальных управлений (по одному для каждого состояния), которое дает минимальное среднее значение времени перехода из S0 в Sm .

Применение принципа оптималь-

Si(1)

ности

к

таким

задачам

приводит

к стохастической модели динамиче-

wi(1)

i+1 (Si(1))

W

Si( j)

ского программирования.

Пусть

p1

(2)

Si(2)

i+1 (Si(2))

обозначает конкретное состояние си-

(S

)

p2 wi

W

стемы, в которое она переходит на i-м

i

−1

p3

(n)

Si(n)

( j)

– временные

затраты на

xi

шаге, wik

wi

перевод организма в состояние

S( j)

i+1 (Si(n))

W

i

на i-м

шаге

из состояния

S(k ) .

Рис. 2.10

i−1

Допустим, что для части сети (рис.2.10)

известны условные минимальные средние временные затраты W i+1 (Si ) на достижение конечного состояния из Si (Si {Si(1), Si(2), , Si(n)}). На рис. 2.10

через

p1,

p2, , pn

обозначены

условные

вероятности

перехода

= P (S( j)

, x ), причем

n

p

j

| S

−

∑ p

j

=1. Если,

например, находясь в состоя-

i

1

i

j=1

нии Si−1, мы

xi ,

применяем управление

то средние затраты

времени

i (Si−1 | xi )

на достижение конечного состояния из Si−1 равны

W

)

n

i

(

i

) (

i

( j)

(

j)

( j)

W i (Si−1 | xi )= ∑

w

+W i+1 S

P S

| Si−1,

xi .

j=1

Так как вариантов управления наi-м шаге может быть несколько, т.е.

xi может

принимать разные значения x {x(1),

x(2)

, ,

x(p)}, выберем то из них, при

i (Si−1 | xi )

i

котором

становится

минимальным. При этом стохастическое

W

обобщение основного рекуррентного уравнения (2.2) имеет вид

i (S

)= min W

(S

| x )

,

W

i−1

x

{

i

}

i

48

или в развернутой форме

W i (Si−1)= minx ∑(wi( j) +Wi+1 (Si( j)))P(Si( j)

i j

Поскольку применяются условные вероятности, то

∑P(Si( j) | Si−1, xi )=1.

j

| Si−1, xi ) .

		Решение задач методом стохастического динамического программиро-
вания рассмотрим на конкретных примерах.
						5					Пример			2.3.	Решается задача
				S(1)		5	S(1)				управляемого перевода организма из
				S(1)			S(1)				управляемого перевода организма из
				1		6	2
		2				6	3				исходного		состояния S0 в конечное
		2				2	3				исходного		состояния S0 в конечное
			4			2					состояние		S3 (лечение, нормализация
S	0		4	S(2)					S	3	состояние		S3 (лечение, нормализация
	0			1		4				3	состояния оператора). При этом суще-
		3				4		8			состояния оператора). При этом суще-
		3				4		8			ствуют промежуточные состояния S1(1) ,
				S(3)		4	S(2)				ствуют промежуточные состояния S1(1) ,
				1			2
				1		5	2				S(2),	S(3), S(1),			S(2), а возможные
						5					S(2),	S(3), S(1),			S(2), а возможные
					Рис. 2.11						1	1		2	2
											переходы из состояния в состояние
изображены на рис. 2.11 в виде ориентированного ациклического графа.
		На ребрах графа проставлено время, требуемое для перевода организма
из одного состояния в другое. В каждом состоянии														Si−1	имеется несколько

управляющих воздействий xi , которым соответствуют определенные наборы вероятностей перехода P (Si | Si−1, xi ). Эти наборы приведены в табл. 2.2–2.5. В этих таблицах, как уже отмечалось, сумма чисел в каждой строке равна 1.

			Таблица 2.2

x1		P (S1 \| S0, x1)
x1	S(1)	S(2)	S(3)
	1	1	1

x(1)	0,6	0,4	0
1
x(2)	1	0	0
1
x(3)	0,3	0,3	0,4
1

Таблица 2.3

	P (S	2	\| S(1), x	)
x2		2	1	2
x2	S2(1)			S2(2)
	S2(1)			S2(2)
x(1)	0,2			0,8
2
x(2)	0,5			0,5
2
x(3)	0,6			0,4
2

49

Таблица 2.4

	P (S	2	\| S(2), x	)
x2		2	1	2
x2	S2(1)			S2(2)
	S2(1)			S2(2)
x(4)	0,5			0,5
2
x(5)	0,3			0,7
2

Таблица 2.5

	P (S	2	\| S(3), x	)
x2		2	1	2
x2	S2(1)			S2(2)
	S2(1)			S2(2)
x(6)	0,1			0,9
2
x(7)	0,6			0,4
2

	Кроме того, в состоянии S(1)				всегда применяется управление x(1)							и
			2								3
P (S	3	\| S(1), x(1) )=1, а в состоянии		S(2) –		x(2)	и	P (S	3	\| S(2), x(2) )=1. Каждо-
	3	2	3		2	3			3	2	3

му состоянию требуется сопоставить одно оптимальное управляющее воздействие, при котором общее среднее время перехода из S0 в S3 будет ми-

нимально, а также определить это время.

Согласно рис. 2.11 и принятым обозначениям времена перехода организма из состояния в состояние равны

w	=3;	w(1) = 2;		w(1) = 2;
31		23		1
w	=8;	w(2) = 4;		w(2) = 4;
32		21		1
w(1) =5;		w(2) = 4;		w(	3) =3;
21		22		1
	w(1) = 6;		w(2) =5.
	22		23

Условную оптимизацию, как и раньше, начинаем с последнего, 3-го шага управления. Из условия задачи видно, что на 3 -м шаге управление вынужденное, поэтому

W 3 (S2(1))= w31 = 3; W 3 (S2(2))= w32 =8.

Условную оптимизацию на 2-м шаге проводим с помощью рекуррентного уравнения, которое на этом шаге приобретает вид

			x					2		(		2	) (	2				)
									( j)			( j)		( j)
	W 2 (S1 )= min								( j)	+W 3	S	( j)		( j)	\| S1, x2
	W 2 (S1 )= min					∑ w				+W 3	S		P S		\| S1, x2				.
				2			j

Допустим, что S1 = S1(1), тогда x2 {x2(1), x2(2), x2(3)}и																			)
( 1				)			2	21		( 2			) (	2	1				)
		(1)					2		( j)			( j)		( j)		(1)
W 2 S			\| x2		= ∑ w					+W 3 S			P S		\| S		, x2 ;

j=1

W 2 (S1(1) | x2(1))= (5 +3) 0,2 +(4 +8) 0,8 =11,2 ;

50

Материал: Учебное пособие Немирко Манило

Смотрите также: