Исследование операций. Линейное, динамическое программирование



         

Исследование операций - часть 90


Определить, как изменяется состояние S

системы S под влиянием управления хi на i-м шаге: оно переходит в новое состояние

S ’=

 (S,xi).                (14.2)

«Функции изменения состояния» (14.2) тоже должны быть записаны1).

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W<(S) (начиная с i-го шага и до конца) через уже известную функцию Wi+1 (S):

. (14.3)

Этому выигрышу соответствует условное оптимальное управление на i-м шаге хi(S) (подчеркнем, что в уже известную функцию Wi+1(S) надо вместо S

подставить измененное состояние S ’ =

 (S, x).

7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле

(14.4)

и находя условное оптимальное управление xm(S), для которого этот максимум достигается.

8. Произвести условную оптимизацию (m - 1)-го, (m - 2)-го и т. д. шагов по формуле (14.3), полагая в ней i = (m - 1), (m - 2), ..., и для каждого из шагов указать условное оптимальное управление xi(S), при котором максимум* достигается.

Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно — прямо находим оптимальный выигрыш для данного начального состояния So. Это и есть оптимальный выигрыш за всю операцию

W* = Wi(So).

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге

; изменить состояние системы по формуле (14.2); для вновь найденного состояния найти оптимальное управление на втором шаге x.i и т. д. до конца.

* * *

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


Содержание  Назад  Вперед