8.3. Принцип оптимальности и математическое описание динамического процесса управления

 В основе метода ДП лежит принцип оптимальности, впервые сформулированный в 1953 г. американским математиком Р. Э. Беллманом: Каково бы ни было состояние системы в резуль­тате какого-либо числа шагов, на ближайшем шаге нужно выби­рать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптималь­ному выигрышу на всех оставшихся шагах, включая выигрыш на данном шаге. При решении задачи на каждом шаге выбирает­ся управление, которое должно привести к оптимальному выиг­рышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максималь­ный выигрыш именно на данном шаге. Однако, например, при покупке новой техники взамен устаревшей на ее приобретение затрачиваются определенные средства, поэтому доход от ее эксп­луатации в начале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохо­да в текущем году, то в дальнейшем это приведет к значительным убыткам. Этот пример демонстрирует следующий факт: в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс.

Кроме того, при выборе управления на данном шаге следует учитывать возможные варианты состояния предыдущего шага. Например, при определении количества средств, вкладываемых в предприятие в I-м году, необходимо знать, сколько средств ос­талось в наличии к этому году и какой доход получен в предыду­щем (I - 1)-м году. Таким образом, при выборе шагового управле­ния необходимо учитывать следующие требования:

  возможные исходы предыдущего шага Sk-1;

  влияние управления ХK на все оставшиеся до конца процесса шаги (N - K).

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

Условная оптимизация. На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные управления для всех возможных со­стояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, N-м шаге опти­мальное управление – Xn* определяется функцией Беллмана: , в соответствии с которой максимум вы­бирается из всех возможных значений ХN, причем .

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

Этот максимум (или минимум) определяется по всем возможным для K и S значениям переменной управления Х.

Безусловная оптимизация. После того, как функция Бел­лмана и соответствующие оптимальные управления найдены для всех шагов с N-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Пользуясь тем, что на первом шаге (K = 1) Состояние системы известно - это ее начальное состояние S0, можно найти опти­мальный результат за все N шагов и оптимальное управление на первом шаге Х1, которое этот результат доставляет. После при­менения этого управления система перейдет в другое состояние S1(S, X1*), зная которое, можно, пользуясь результатами услов­ной оптимизации, найти оптимальное управление на втором шаге Х2*, и так далее до последнего N-го шага.

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

< Предыдущая		Следующая >