4.2.3.3. Обобщенный алгоритм решения подзадачи А3 «Расчет опти-мальных значений»
Алгоритм решения подзадачи А3 Расчет оптимальных значений создан на основе динамического программирования.
Динамическое программирование (ДП) – метод оптимизации, приспособ-ленный к операциям, в которых процесс принятия решений может быть разбит на этапы.
Общая постановка задачи ДП:
Рассматривается управляемый процесс - Распределение денежных средств между различными средствами рекламы. В результате управления система S переводится из начального состояния s0 в состояние s. Предположим, что управление можно разбить на n шагов, т. е. решения принимаются последова-тельно на каждом шаге, а управление, переводящее систему S из начального состояние в конечное, представляет собой совокупность n пошаговых управ-лений.
Пусть Xk - управление на k – ом шаге
 X (X1, X2 , …, Xn) – управление, переводящее систему S из состояния s0 в состояние s. Обозначим через Sk состояние системы после k-го шага управле-ния. Получаем последовательность состояний s0, s1, …, sk-1,…,sn-1,sn = s
Показатель эффективности рассматриваемой управляемой операции – це-левая функция – зависит от начального состояния и управления:
Z = F(s0, X)
Необходимо определить такое допустимое управление X, которое переве-дет систему из состояния S0 – S с наибольшим или оптимальным значением целевой функции Z.
Уравнение Беллмана. Исходная задача динамического программирова-ния рассматривается как последовательность задач, при этом каждая задача представляет последовательный одношаговый, двухшаговый, …, n-процесс.
Рассмотрим n-шаг.
Имеем Sn-1 – состояние системы к началу n-го шага, sn – конечное состоя-ние, Xn – управление на n-м шаге, Zn (Sn-1) = fn(Sn-1, Xn) – целевая функция (вы-игрыш) n-го шага.
Согласно принципу оптимальности, Xn нужно выбирать так, чтобы для любых состояний Sn-1 получить максимум целевой функции на этом шаге.
Zn*(Sn-1) – показатель эффективности n-го шага, если Sn-1 – произвольная. Поэтому:
Zn*(Sn-1) = max {fn(Sn-1, Xn)}
если знаем Zn*, то находим
Xn*(Sn-1) – условный оптимальный выигрыш на n-ом шаге.
Рассмотрим: Zn-1 (Sn-2) = fn-1(Sn-2, Xn-1) + Zn*(Sn-1)
в результате получаем условия оптимальности решений на (n-1)шаге:
Zn-1*(Sn-1) = max {fn-1 (Sn-2, Xn-1) + Zn*(Sn-1)}
т. к. Sn-1 =  (Sn-2, Xn-1)     
Zn-1 = Zn-1(Xn-1)
 Получаем уравнение Беллмана:
Zk*(Sk-1) = max {fk (Sk-1, Xk) + Zk+1*(Sk)}
k = n-1, n-2, …, 1.
В результате решения уравнения Беллмана получим:
Z1* = Zmax , поэтому можно найти X1* = X1*(S0)  S1*= (S0,X1*)
X2* = X2*(S1*)…
В результате получим 2 последовательности:
Zn* … Z1*
Xn*… X1*
Оптимальное управление: X* = {X1*, X2*, …, Xn*}.
 Декомпозиция подзадачи на модули.
Данная подзадача может быть разбита на несколько основных этапов – модулей. Тогда обобщенный алгоритм решения подзадачи «Расчет оптималь-ных значений» можно представить как: