Файл: Методичка.pdf

27

Для каждого шага запишем временные затраты wi в функции от состояния на предыдущем шаге и шагового управления. Обозначим их в соответствии с

Запишем основное рекуррентное уравнение динамического программирования, используемое для условной оптимизации. Согласно (2.2), оно имеет вид

Wi (Si−1 )= min{wi +Wi+1 (Si )}

xi

Проведем условную оптимизацию, начиная с последнего, 4-го шага. Согласно

(2.3)

W4 (S3 )= min{w4 }

x4

Перед 4-м шагом состояние G может быть либо S3' , либо S3'' . В обоих случаях оптимальное шаговое управление – это перевод G в S4 . Значения условного оптимума целевой функции равны, соответственно

W4 (S3' )= w4(1) = 6,

W4 (S3'' )= w4(2) = 5.

Далее оптимизируем предпоследний, 3-й шаг. Для него

28

W3 (S2 )= min{w3 +W4 (S3 )}

x3

Если перед этим шагом G находился в состоянии S2' , имеем две возможности перевода G в S4 : либо через S3' (это займет 8 + 6 = 14 единиц времени), либо через S3'' . В последнем случае временные затраты равны 4 + 5 = 9,

поэтому этот вариант следует предпочесть и считать, что минимальное время достижения конечного состояния из S2' равно 11 единицам. Формально в случае,

если S2 = S2' , то имеется два управления x3(1) и x3(2) и условный оптимум целевой

функции

W3 (S2' )= min{[w3(1) +W4 (S3' )], [w3(2) +W4 (S3'' )]}= min{[8 + 6], [4 +5]}= 9,

Если перед 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).

Аналогично проводятся расчеты и для других предыдущих состояний этого шага, а

29

На рис.2.9 стрелками показаны все условные оптимальные управления, а в кружочках проставлены значения условного минимума для всех состояний. Это то минимальное время, которое требуется для достижения S4 . Из рис.2.9 видно, что существует две различные оптимальные траектории, переводящие G из S0 в S4 .

Они могут быть записаны в виде следующих двух цепочек

S0 → S1' → S2'' → S31 → S4 ; S0 → S1'' → S2' → S3'' → S4

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

Рис.2.9

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

До сих пор мы рассматривали детерминированную модель динамического программирования. В реальной жизни как на состояние системы, так и на целевую функцию влияют случайные факторы. В этом случае поведение системы зависит не только от начального состояния S0 и выбранного управления x , но и от случайности. Рассмотрим стохастическую модель задачи о кратчайшем пути на ациклической сети [12]. Допустим существование в системе условных вероятностей

Ρ(Si / Si−1 , xi ) того, что на i-м шаге управления система перейдет в состояние Si при

30

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

Si−1 .

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

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

Применение принципа оптимальности к таким задачам приводит к стохастической модели динамического программирования. Пусть Si(j ) обозначает конкретное состояние системы, в которое она переходит на i-м шаге, wik(j ) -

временные затраты на перевод организма в состояние Si(j ) на i-м шаге из состояния

Si(−k1) . Допустим, что для части сети (рис.2.10) известны условные минимальные