Общая постановка задачи

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

Каждому распределению ресурсов по периодам соответствует определенный доход w_t причем общий доход W за Т лет зависит от совокупности управлений на t-м шаге операции, т.е.

W = w(U₁,U₂,...,U_t,...,U_T) = w₁+w₂+...+w_t+...+w_T = Sw_t. (7.1).

При этом управление на шаге t – это функция нескольких переменных – параметров управления, т.е. U_t (x_t1,x_t2, …, x_ti, …, x_tn).

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

Управление на последнем шаге выбирают исходя из различных предположений об исходе предпоследнего этапа (о положении системы к началу последнего этапа). Для планирования следующего, предпоследнего (Т-1)-го этапа надо сделать различные предположения об исходе предпоследнего (Т-2)-го этапа и т.д. Оптимальное управление на этапах находится для каждого из возможных состояний системы на начало этапа. Такое управление называется условно-оптимальным; при достижении определенного предшествующего состояния оно становится оптимальным.

Таким образом, проходя последовательно от последнего этапа к первому, получаем совокупность условно-оптимальных управляющих воздействий:

(7.2)

Найденные условно-оптимальные управления позволяют определить для любых возможных состояний оптимальное продолжение процесса. Поэтому, начиная с начального состояния S₀, можно определить уже не условно-оптимальное, а просто оптимальное управление на каждом этапе. Для этого, используя условно-оптимальное управление, найденное для начального состояния S₀, находим состояние, в которое перейдет система S₁. Применяя условно-оптимальное управление для данного состояния, получаем новое состояние системы. Но так как известны условно-оптимальные управления для всех возможных состояний системы, постепенно находим совокупность оптимальных управлений на каждом шаге и, следовательно, оптимальное управление процессом в целом U=(U₁,U₂,...,U_t,...,U_T), дающее наибольший эффект W.

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

Символически метод динамического программирования можно записать следующим образом.

Обозначим через W_t(S) условно-оптимальный выигрыш (значение критерия) с t-го этапа до конца процесса, если система в начале находится в состоянии S; U_t(S) - условно-оптимальное управление на t-м шаге, которое совместно с оптимальными управлениями на последующих этапах дает нам условно-оптимальный выигрыш; w_t - выигрыш на одном t-м этапе, таким образом, что

(7.3)

Под влиянием управления U_t система на t-м шаге переходит из состояния S в состояние S'. По-другому, условно-оптимальный выигрыш выражается следующим образом

(7.4)

Первое слагаемое представляет значение критерия на данном этапе, а второе - от данного этапа до конца процесса.

В соответствии с принципом оптимальности на каждом шаге для достигнутого состояния S должны выбирать такое управление U_t, при котором критерий оптимальности (условно-оптимальный выигрыш) максимизируется.

Тогда основное функциональное уравнение динамического программирования, представляющее собой рекуррентное соотношение, имеет вид:

(7.5)

Рекуррентное соотношение позволяет определить функцию W_t(S), если известна следующая по порядку функция W_t+1(S’).

Первоначально находятся условно-оптимальный выигрыш W_t(S) на последнем шаге и соответствующее ему условно-оптимальное управление U_t=U_T.

(7.6).

Зная W_T(S) и U_T, и используя основное функциональное уравнение, находим W_T-1 и U_T-1. Подобная процедура повторяется вплоть до первого этапа.

Затем переходят ко второй стадии расчетов - нахождению оптимального управления U=(U₁,U₂,...,U_t,...,U_T). Начинают с первого шага. Для начального состояния S₀ определяют W_max=W₁(S₀) и управление U₁, переводящее систему в состояние S₁. Зная состояние S₁, находят оптимальное управление на втором шаге U₂ и затем S₂, и так последовательно получают шаговые оптимальные управления и поэтапные состояния системы.

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

Наиболее естественное разделение процессов по этапам - их рассмотрение во времени. Этот способ разбивки по шагам наиболее характерен для задач планирования и управления производством. Однако возможны и другие варианты деления процесса на этапы: изменение координат объекта, мощности, ресурсов.