Экономико-математические модели управления производством (теоретические аспекты). Ломкова Е.Н - 49 стр.

необходимо знать, сколько средств осталось в наличии к этому году и ка-
кой доход получен в предыдущем (i-1)-м году. Таким образом, при выборе
шагового управления необходимо учитывать следующие требования:
     1) возможные исходы предыдущего шага Sk-1;
     2) влияние управления хk на все оставшиеся до конца процесса шаги
(n - k).
      В задачах динамического программирования первое требование учи-
тывают, делая на каждом шаге условные предположения о возможных
вариантах окончания предыдущего шага и проводя для каждого из вари-
антов условную оптимизацию. Выполнение второго требования обеспе-
чивается тем, что в этих задачах условная оптимизация проводится от
конца процесса к началу.
      Условная оптимизация. На первом этапе решения задачи, называе-
мом условной оптимизацией, определяются функция Беллмана и опти-
мальные управления для всех возможных состояний на каждом шаге, на-
чиная с последнего в соответствии с алгоритмом обратной прогонки. На
последнем, n-м шаге, оптимальное управление х*n определяется функци-
ей Беллмана: F(S) = max{Wn(S,xn)}, в соответствии с которой максимум
выбирается из всех возможных значений хn, причем хn∈Х.
      Дальнейшие вычисления производятся согласно рекуррентному со-
отношению, связывающему функцию Беллмана на каждом шаге с этой
же функцией, но вычисленной на предыдущем шаге. В общем виде это
уравнение имеет вид:
               Fn(S) = max{Wn(S, xn) + Fk+1(S1(S, xk))}, xk∈Х.
      Этот максимум (или минимум) определяется по всем возможным
для k и S значениям переменной управления X.
      Безусловная оптимизация. После того, как функция Беллмана и соот-
ветствующие оптимальные управления найдены для всех шагов с n-го по
первый, осуществляется второй этап решения задачи, называемый безус-
ловной оптимизацией. Пользуясь тем, что на первом шаге (k = 1) состояние
системы известно – это ее начальное состояние S0, можно найти оптималь-
ный результат за все n шагов и оптимальное управление на первом шаге x1,
которое этот результат доставляет. После применения этого управления
система перейдет в другое состояние S1(S,х*1), зная которое, можно, поль-
зуясь результатами условной оптимизации, найти оптимальное управление
на втором шаге х*1, и так далее до последнего n-го шага.
      Вычислительную схему динамического программирования можно
строить на сетевых моделях, а также по алгоритмам прямой прогонки (от
начала) и обратной прогонки (от конца к началу). Рассмотрим примеры
решения различных по своей природе задач, содержание которых требует
выбора переменных состояния и управления.

                                   49