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

Скачать

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

В1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S8

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

10

 

 

 

 

 

4

 

 

 

 

 

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

8

 

 

 

6

 

 

 

 

 

3

 

 

 

5

 

 

 

6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

 

 

 

11

 

 

 

 

 

4

 

 

 

 

 

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

5

 

 

 

7

 

 

 

 

 

7

 

 

 

9

 

 

 

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

4

 

 

 

 

 

10

 

 

 

 

 

9

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8

 

 

 

5

 

 

 

 

 

5

 

 

 

7

 

 

 

8

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

7

 

 

 

 

8

 

 

 

 

 

6

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

8

 

 

 

4

 

6

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

4

 

 

 

 

9

 

 

 

 

 

7

 

 

 

 

 

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

В2

 

1

 

2

 

 

 

 

3

 

 

4

 

 

5

 

Рис. 2.4

ла, равные времени улучшения показателя на одном шаге управления. Требуется так рассчитать траекторию управления состоянием оператора при переводе его из S0 в S8 , чтобы суммарное время нормализации его состояния было минимальным.

Из рисунка видно, что число шагов при переводе организма из состояния S0 в S8 всегда равно 8. Требуется выбрать такой путь из S0 в S8 , для которого сумма чисел, стоящих на отрезках, составляющих этот путь, минимальна. В соответствии с п. 4–6 вышеописанной процедуры решения задач динамического программирования и следуя ходу решения таких задач, изложенному в [6], произведем условную оптимизацию, начиная с последнего, 8-го шага.

S7′

8

8

S8

 

 

 

6

 

 

6 S7′′

Рис. 2.5

S7′

12

4

8

8

S6′

5

13

8

 

S6′′

Рассмотрим правый угол нашей сетки (рис. 2.5). После 7-го шага организм может находиться в состоянии либо S7′ , либо S7′′. Если он находится в S7′ , то управление однозначно (увеличить B2 на 1) и условный оптимум целевой функции равен времени перехода из

S'

в

S , т. е. W

(S′ )=8. Запишем это число в кружке у

7

 

 

 

 

8

8

7

 

 

точки S7′ , а оптимальное (и в данном случае единствен-

 

 

 

 

 

 

ное)

управление

изобразим стрелкой,

 

 

 

 

 

S

направленной из S7′

в S8 . Для состояния S7′′

 

 

 

 

 

8

управление также вынужденное (увеличить

 

 

 

 

 

 

 

 

 

 

 

 

B на 1), а W

(S′′)= 6 . Запишем и это число

 

 

6

 

 

 

 

 

 

 

 

1

8

7

 

 

 

 

 

 

S7′′

в кружке у точки S7′′, а оптимальное управ-

 

 

6

 

 

 

 

 

 

 

 

 

 

41

 

 

 

 

8

 

 

 

 

 

 

 

 

14

S6′′′

 

 

 

 

Рис. 2.6

ление в этом случае покажем стрелкой, направленной из S7′′ в S8 . Таким образом, условная оптимизация последнего шага сделана, условный оптимум целевой функции для каждого из состояний S7′ и S7′′ найден и записан в соответствующем кружке.

Теперь займемся оптимизацией предпоследнего, 7-го шага. Перед ним

(т. е. после

6-го шага) организм мог оказаться лишь в одном из трех состо я-

ний: S6′, S6′′

, S6′′′ (рис. 2.6). Найдем для каждого из них условное оптимальное

управление и условный оптимум целевой функции. Для S6′ управление вы-

нужденное:

переход

в S7′ ,

поэтому ставим стрелку из S6′

в S7′ . Временные затраты на этом пути

до S8

составляют 12 единиц (4 на данном шаге плюс 8, записанных в кружке

у S7′ ), которые мы также записываем в кружке у S6′. Аналогично для S6′′ управление также вынужденное (переход в S7′′, который мы обозначаем соответствующей стрелкой), а на весь этот путь до конца уйдет 14 единиц времени, что мы и отмечаем в кружке у S6′′′. Для S6′′ управление уже не вынужденное: мы можем двигаться как по вертикали, так и по горизонтали. В первом случае траектория из S6′′ до конца занимает 13единиц времени (5 на данном шаге, плюс 8, записанных в кружке у S7′ ), а во втором 14 (8 + 6). Значит, условное оптимальное управление в S6′′ – это перевод организма в состояние S7′ . Отмечаем это стрелкой, а число 13 записываем в кружке у S6′′.

Действуя аналогично и двигаясь от конца к началу, для каждого узла сетки найдем условное оптимальное управление, которое обозначим стрелкой, и условный оптимум целевой функции (время перевода в конечное состояние), который запишем в кружке. Вычисляется он так: время перевода на данном шаге складывается с уже оптимизированным расходом времени, записанным в кружке, куда ведет стрелка. Таким образом, на каждом шаге мы оптимизируем только этот шаг, а следующие за ним – уже оптимизированы. Конечный результат процедуры оптимизации показан на рис. 2.7. Теперь, находясь в любом узле сетки, мы знаем, какое управление применять (стрелка) и в какие временные затраты нам обойдется путь до конца (число в кружке). В кружке при S0 записаны оптимальные (минимальные) затраты на всю

процедуру нормализации состояния.

42

Теперь в соответствии с п. 7 приведенной ранее процедуры решения задачи динамического программирования построим безусловное оптимальное управление – траекторию, ведущую из S0 в S8 с минимальным временем нормализации состояния. Для ее построения нужно лишь выделить (из имеющихся) непрерывную цепочку стрелок, ведущую из S0 в S8 . Такая опти-

мальная траектория, для которой W =W1 (S0 )= 36 , выделена жирными

стрелками на рис. 2.7. Оптимальная траектория может оказаться не единственной, тогда задача имеет несколько эквивалентных решений.

 

27

5

22

10

12

4

8

8

S8

 

8

 

6

 

3

 

5

 

6

 

34

8

26

11

15

4

13

8

6

 

5

 

7

 

7

 

9

 

8

 

28

2

26

4

22

10

22

9

14

 

6

 

5

 

5

 

7

 

8

 

34

7

31

8

27

6

27

5

22

 

2

 

8

 

4

 

6

 

7

S0

36

4

39

9

31

7

33

4

29

Рис. 2.7

В рассмотренной задаче промежуточные состояния организма описывались с помощью прямоугольной сетки. В общем случае это не обязательно. Множество состояний и возможные переходы из состояния в состояние можно задать и в виде ориентированного графа. В этом случае задачи управляемого перевода организма из одного состояния в другое можно представить как поиск кратчайшего пути на ориентированной ациклической (т. е. без петель и контуров) сети [14]. Решаются такие задачи точно так же, как и на прямоугольной сетке. Заметим, что использованная нами для решения прямоугольная сетка также является ориентированной ациклической сетью, если на ее отрезках проставить стрелки всех возможных управлений. Ниже приведена задача, описываемая в виде сети.

Пример 2.2. Решается задача управляемого перевода организма G из исходного состояния S0 в конечное состояние S4 (лечение или нормализация

43

состояния оператора). При этом существует 8 промежуточных состояний, S1′, S1′′, S1′′′, S2′ , S2′′, S2′′′, S3′, S3′′, а возможные переходы из одного состояния в

другое изображены на рис. 2.8 в виде ориентированного графа.

На ребрах графа проставлено время, требующееся для перевода организма из одного состояния в другое. Предполагается, что выбор маршрута переходов полностью управляем. Требуется определить оптимальную траекторию перевода организма из S0 в S4 , при которой общее время этого пере-

вода будет минимально.

 

 

 

 

 

 

11

 

 

 

8

 

 

 

 

 

 

 

 

 

 

S1′

 

 

 

 

S2′

 

 

 

S3′

 

 

 

 

 

 

 

 

4

 

 

3

 

 

 

 

 

 

8

 

 

 

 

 

 

 

 

 

 

6

 

 

 

 

1

 

 

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6

 

 

 

8

 

 

 

 

 

 

S0

 

 

S1′′

 

 

 

S2′′

 

 

 

 

 

 

 

S4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

15

 

 

 

 

 

 

 

4

5

 

 

 

 

10

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S′′′

 

 

 

 

 

S2′′′

 

 

 

 

 

S′′

 

 

 

 

 

 

1

 

11

 

 

 

 

2

 

 

 

3

 

 

Рис. 2.8

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

xi ={Sk → S j } будет означать, что управление xi (на i-м шаге) переводит G

из Sk в S j :

 

 

 

 

 

 

 

 

 

(1)

′

→ S4};

(5)

′′′

′

(5)

′′

′′′

 

 

 

x4 ={S3

x3 ={S2

 

→ S3};

x2 ={S1

→ S2};

x4(2) ={S3′′ → S4};

x3(6) ={S2′′′→ S3′′};

x2(6) ={S1′′′→ S2′′};

(1)

′

′

(1)

′

 

′

(7)

′′′

′′′

 

 

 

 

x3 ={S2

→ S3};

x2 ={S1

→ S2};

x2 ={S1 → S2};

x3(2) ={S2′ → S3′′};

x2(2) ={S1′ → S2′′};

x1(1) ={S0 → S1′};

(3)

′′

′

(3)

′′

 

′

(2)

 

′′

 

 

 

 

 

x3 ={S2

→ S3};

x2 ={S1

→ S2};

x1 ={S0 → S1};

(4)

′′

′′

(4)

′′

′′

(3)

 

′′′

 

 

 

 

x3 ={S2

→ S3};

x2 ={S1

→ S2};

x1 ={S0 → S1}.

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

ствии с шаговыми управлениями, приведенными выше (w3(5) означает время перевода G из S'''2 в S3' , являющегося следствием управления x3(5)):

44

w4(1) = 6;

w3(5) = 7;

w2(5) =10 ;

w4(2) =5;

w3(6) = 2;

w2(6) =10 ;

w3(1) =8;

w2(1) =11;

w2(7) =11;

w3(2) = 4;

w2(2) = 4;

w1(1) =3;

w3(3) =3;

w2(3) =1;

w1(2) = 6;

w3(4) =5;

w2(4) =8;

w1(3) =15 .

Запишем основное рекуррентное уравнение динамического программирования, используемое для условной оптимизации. Согласно (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-й шаг. Для него

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 ,

45

Источник: https://studfile.net/preview/14965028/

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

Изложение содержания дела, по которому приняты судебные постановления
_-___-~1
_1-тема-СтрМетал
_10_Эмиль Золя для эл версии