§2. Постановка и общая схема решения задачи динамического программирования

Рассмотренные выше примеры позволяют выделить следующие характерные черты задач динамического программирования.

1. Рассматривается система, которая под воздействием управлений, т.е. некоторых мероприятий, переходит за n шагов из начального состояния S₀ в конечное состояние S_n. Управление на k-м шаге (k = ) обозначим u_k. В результате этого управления система переходит из состояния S_k-1 в состояние S_k. Состояние S_k системы после k-го шага характеризуется некоторым параметром x_k, который может быть числом или вектором. Параметр начального состояния обозначим x₀. Величины x_k называют параметрами состояния системы.

2. Предполагается, что изменение состояния системы на каждом шаге зависит только от предшествующего состояния и управления на этом шаге. Это условие называется «отсутствием последействия». Эта зависимость задается в виде соотношений, которые называют уравнениями состояний:

x_k = F_k (x_k-1, u_k), k = .

Здесь x_k и x_k-1 — параметры состояний S_k и S_k-1.

3. Как правило, на управления u_k на каждом шаге накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям, называют допустимыми. Будем обозначать множества допустимых управлений на k-м шаге через D_k.

4. Управление на каждом шаге связано с определенным выигрышем , характеризующим его эффективность. Величина этого выигрыша зависит только от предшествующего состояния и решения, принятого на этом шаге.

5. Общий показатель эффективности Z (целевая функция) всего процесса управления представляет собой сумму показателей эффективности на каждом шаге, т.е.

.

Общая задача динамического программирования формулируется так.

Найти управление U=(u₁, u₂, ,..., u_n), переводящее систему из начального состояния S₀ в конечное состояние S_n, и удовлетворяющее ограничениям

x_k = F_k (x_k-1, u_k), k = , (1.1)

u_k  D_k, k = , (1.2)

которое доставляет максимальное значение целевой функции

(1.3)

Управление , удовлетворяющее условиям (1.1) – (1.2) и доставляющее максимальное значение целевой функции (1.3), называется оптимальным управлением.

Суть предложенного Беллманом метода решения задач динамического программирования заключается в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управление только этого шага. Однако на любом шаге управление следует выбирать с учетом последствий этого выбора на последующих шагах. В этом и заключается сформулированный Беллманом принцип оптимальности.

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

Этот принцип лежит в основе процедуры нахождения оптимального управления в задаче динамического программирования (1.1) – (1.3). Сама процедура состоит из двух этапов: условной и безусловной оптимизации.

1. Этап условной оптимизации. На каждом шаге k этого этапа для любого возможного состояния системы S_k-1, описываемого параметром x_k-1, находятся так называемые условные максимумы и условные оптимальные управления.

Условным максимумом, обозначающимся , называется величина

= , (2.1)

которая представляет собой максимальный выигрыш на всех оставшихся шагах, начиная с k-го шага. Слово «условный» употребляется потому, что значение зависит от параметра x_k–1, характеризующего текущее состояние системы.

Условным оптимальным управлением, обозначающимся , называется такое управление на k-м шаге, которое обеспечивает достижение максимального значения в (2.1) при условии, что на всех последующих шагах k+1, …, n также выбраны оптимальные управления.

Чтобы найти условные максимумы и условные оптимальные управления, нужно решить функциональные уравнения Беллмана, которые являются математической формой записи принципа оптимальности. Эти уравнения имеют следующий вид:

= . (2.2)

= , k = , (2.3)

Уравнения Беллмана (2.3) представляют собой рекуррентные соотношения, позволяющие вычислить предыдущее значение функции через последующие. Проще всего найти решение уравнения Беллмана для последнего шага (k = n), так как в этом случае оптимальное управление выбирается без учета будущего. Для всех возможных значений параметра x_n-1 находят и запоминают решения задачи (2.2) — условные максимумы и условные оптимальные управления . Затем, поскольку значения известны, решается уравнение Беллмана для предпоследнего шага

=

при всех возможных значений x_n-2. Полученные результаты и также запоминают и переходят к следующему (n – 2)-му шагу, потом к (n – 3)-му шагу и т.д. В результате будут найдены условные максимумы и условные оптимальные управления:

, , ......., , .

для всех возможных значений x_n-1, ..., x₀. На этом этап условной оптимизации заканчивается.

Замечание. Отметим, что решаемые на каждом шаге задачи оптимизации имеют намного меньшую размерность, чем исходная задача (1.1) – (1.3), поскольку в них ищется максимум функции, зависящей лишь от управления данного шага u_k, а не от всей совокупности управлений (u₁, u₂, ,..., u_n). Поэтому решать эти задачи существенно проще, чем исходную задачу. Однако обычно этот этап является весьма трудоемким, так как хотя каждая из задач решается достаточно просто, их количество, а следовательно и общий объем вычислений, может быть большим.

2. Этап безусловной оптимизации. Этап безусловной оптимизации также как и первый этап производится по шагам, но в их естественном порядке: от первого шага к последнему. На каждом шаге этого этапа находятся параметры оптимальных состояний и оптимальные управления . Делается это следующим образом.

Пусть x₀ = фиксировано. Тогда на первом шаге этого этапа находится максимальное значение целевой функции Z_max = и соответствующее оптимальное управление , так как по определению условного максимума = .

Зная и , на втором шаге по уравнению состояния можно найти оптимальное состояние . Так как известно множество условных оптимальных управлений для всех возможных значений x₁, то по значению на втором шаге находим оптимальное управление и параметры оптимального состояния .

Продолжая процесс нахождения оптимальных управлений на всех последующих шагах, получим на последнем шаге:

, , .

Таким образом, после завершения этого этапа задача динамического программирования (1.1) – (1.3) решена. Найдены:

• максимальное значение Z_max целевой функции;

• оптимальные управления , , ..., на всех шагах;

• соответствующие оптимальным управлениям параметры оптимальных состояний системы , , ..., на всех шагах.

Замечание. Если начальное условие задано в виде x₀X₀, то на первом шаге этапа безусловной оптимизации максимальное значение Z_max целевой функции находится в результате решения задачи:

= .