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

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

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

Осуществив таким образом путь «из конца в начало», можно найти на каждом шаге так называемое условное оптимальное частное решение (если система находится в данном состоянии S', то лучшим будет только решение и-). Если определено исходное состояние S¹, соответствующая совокупность частных решений (uj, U-2,..., Щу) даст искомое решение задачи, двигаясь уже «из начала в конец».

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

Этот принцип позволяет сформировать следующие рекуррентные уравнения динамического программирования, называемые также уравнениями Веллмана. На каждом к-м этапе, находясь в состоянии S_k, частное управление и_к необходимо выбирать по правилу

где к = 1, ..., N — номер этапа; j — номер состояния, в которое попадает система после принятия управления и_к, если перед этим она находилась в состоянии номер i.

Для последнего шага (к = N) это правило приобретает вид

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

• 1. Весь процесс разбивается на N этапов (шагов). Фиксируются исходное состояние системы и функция перехода/, определяющая новое состояние системы, в которое она может перейти под воздействием некоторого управляющего частного решения. Для каждого состояния на всех этапах должен быть определен эффект w_k(S^lk,u_k), который получится, если принять управление и_к, когда система была в состоянии S^lk.
• 2. Для каждого из возможных состояний системы на последнем этапе (к - N) решается уравнение (18.2).
• 3. Последовательно для каждого этапа к - N - 1, N - 2,..., 3, 2, 1 для каждого из возможных на данном этапе состояний S_k решается уравнение (18.1), из которого на соответствующих этапах определяются условные оптимальные управления {и‘}_к, т.е. «если будем находиться в состоянии S^lk, то надо принимать управление и[».
• 4. Для заданного исходного состояния системы выписывается последовательность промежуточных состояний и приводящих к ним уже безусловных оптимальных частных управлений

Решение задачи есть вектор оптимального управления [Г = = (u[,u₂,...,u_N) (оптимальный план), переводящий систему из исходного состояния в конечное с максимальным эффектом W₁.

Примечание 18.1. При решении задачи, когда эффект заключается в минимизации целевой функции, в уравнениях (18.1) и (18.2) вместо операции определения max требуется выполнять операцию определения min.

К достоинствам метода динамического программирования следует отнести его возможность решать оптимизационные задачи, которые другими методами не могут быть решены (например, экстремальные задачи на дискретных множествах, оптимизационные задачи с неаналитическими функциями и т.п.).

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