8.4. Общая схема применения метода динамического программирования

 Приведем общую схему применения метода ДП.

Предположим, что все требования, предъявляемые к задаче динамического программирования, выполнены. Построение метода ДП для решения сводится к следующим моментам:

1) Выбирается способ деления процесса управления на шаги.

2) Определяются параметры состояния Sk и переменные управления Xk на каждом шаге.

3) Записываются уравнения состояний.

4) Вводятся целевые функции K-го шага и суммарная целевая функция.

5) Вводятся в рассмотрение условные максимумы (минимумы) Z*K(Sk-1) и условное оптимальное управление на K-м шаге: X*K(Sk-1), K =N, N-1, …, 2, 1.

6) Записываются основные для вычислительной схемы ДП Беллмана для Z*N(Sn-1) и Z*K(Sk-1), K=N-1, …, 1.

7) Решаются последовательно уравнения Беллмана (условная оптимизация), и получаются две последовательности функций: {Z*K(Sk-1)}, {X*K(Sk-1)}.

8) После выполнения условной оптимизации определяется оптимальное решение для конкретного начального состояния S0:

А) Zmax = Z*1(s0) (здесь Zmax = max Z)

Б) по цепочке

,

Оптимальное управление: Х* =(Х1*, Х2*, …, ХN*).

Яндекс.Метрика