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

Динамическое программирование (ДП) — метод оптимизации, приспособленный к операциям, в которых процесс принятия ре­шения может быть разбит на этапы (шаги). Такие операции назы­ваются многошаговыми. Начало развития ДП относится к 50-м годам XX в. Оно связано с именем Р.Беллмана¹.

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

В реально функционирующих больших экономических систе­мах еженедельно требуется принимать микроэкономические ре-

Беллман Р.Э. (р. 1920 г.) — американский математик.

Глава 12

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

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

Обозначим через Х_к управление на k-м шаге (к=\, 2, ..., л). Пе­ременные Х_к удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Х_к может быть числом, точкой в «-мерном пространстве, качественным признаком).

Пусть Х(Х\, Xj, ..., Х„) — управление, переводящее систему S из состояния s₀ в состояние s. Обозначим через s^ состояние сис­темы после к-ro шага управления. Получаем последовательность состояний s₀, Si, ..., s/c-i, %..., s_n-\, s„=s, которую изобразим кружками (рис. 12.1).

0i0£- ■ ■ ^©^(Э^ • ■ ^0^0

Рис. 12.1

Показатель эффективности рассматриваемой управляемой опе­рации — целевая функция — зависит от начального состояния и управления:

Z=F(s₀,X). (12.1)

Сделаем несколько предположений.

1. Состояние Sk системы в конце А:-го шага зависит только от предшествующего состояния s_k-\ и управления на к-м шаге Х_к

Модели динамического программирования 247

(и Не зависит от предшествующих состояний и управлений) Это требование называется "отсутствием последействия". Сформули­рованное положение записывается в виде уравнений

*к ⁼ Ф*С**-ь Хк), к= \,2, ..., п, (12.2)

которые называются уравнениями состояний.

2. Целевая функция (12.1) является аддитивной от Показателя эффективности каждого шага [3]. Обозначим показатель эффек­тивности к-то шага через

Zk ~fk(sk-\, X_k), k=\, 2, ..., п, (12.3)

тогда

п

Z = Yjfk(^sk-\,X_k). (12.4)

*=i

Задача пошаговой оптимизации (задача ДП) формулируется ^так: определить такое допустимое управление X, переводящее сис­тему s из состояния s₀ в состояние s , при котором целевая функция (12-4) принимает наибольшее (наименьшее) значение.

Выделим особенности модели ДП:

1- Задача оптимизации интерпретируется как п-шаговый процесс
управления.

2- Целевая функция равна сумме целевых функции каждого шага.
3. Выбор управления на k-м шаге зависит только от состояния

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

4- Состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k~\ и управления Х_к (отсутствие по­следействия).

5- На каждом шаге управление Х_к зависит от конечного числа управляющих переменных, а состояние s_k — от конечного числа па­раметров (смысл замечания 5 станет ясным из рассмотренных ниже примеров).

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

Глава 12

Модели динамического программирования

12.2. Принцип оптимальности и уравнения Беллмана

Принцип оптимальностивпервые был сформулирован Р. Белл-маном в 1953 г. Каково бы ни было состояние s системы в резуль­тате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управле­нием на всех последующих шагах приводило к оптимальному выигры­шу на всех оставшихся шагах, включая данный^]. Беллманом четко были сформулированы и условия, при которых принцип верен. Основное требование — процесс управления должен быть без обратной связи, т.е. управление на данном шаге не должно ока­зывать влияния на предшествующие шаги.

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

Уравнения Беллмана.Вместо исходной задачи ДП (см. разд. 12.1) с фиксированным числом шагов п и начальным состоянием 5Ь рассмотрим последовательность задач, полагая последовательно л=1, 2, ... при различных s — одношаговую, двухшаговую и т.д., — используя принцип оптимальности.

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

На каждом шаге любого состояния системы s^-i решение Х# нужно выбирать "с оглядкой", так как этот выбор влияет на по­следующее состояние Sk и дальнейший процесс управления, зави­сящий от St. Это следует из принципа оптимальности.

Но есть один шаг, последний, который можно для любого со­стояния s„-i планировать локально-оптимально, исходя только из соображений этого шага.

Рассмотрим л-й шаг: s„-\ — состояние системы к началу я-го шага, s_n=s— конечное состояние, Х„ — управление на «-м шаге af„(s„-i, X„) — целевая функция (выигрыш) «-го шага.

Согласно принципу оптимальности, Х_п нужно выбирать так чтобы для любых состояний s_n-\ получить максимум¹ целевой функции на этом шаге.

Обозначим через Z*„(s_n-\) максимум целевой функции — показателя эффективности «-го шага при условии, что к на­чалу последнего шага система S была в произвольном состоя­нии s„~\, а на последнем шаге управление было оптималь­ным.

Z„(s„-\) называется условным максимумом целевой функции на п-м шаге. Очевидно, что

К^п-\) = max f„ Су„__ь Х„).

Максимизация ведется по всем допустимым управлениям Х„.

Решение Х„, при котором достигается Z*„ Cv-r), также зависит от s„_i и называется условным оптимальным управлением на п-м шаге. Оно обозначается через Х*_п {s_n-\).

Условно оптимальный выигрыш на п-м шаге

¹ Формулировка принадлежит Е.С.Вентцель [3] и немного отличается от предложенной Беллманом.

Ограничимся здесь задачей максимизации целевой функии.-,.

Глава 12

Модели динамического программирования

Решив одномерную задачу локальной оптимизации по уравне­нию (12.5), найдем для всех возможных состояний s_n-\ две функ­ции: Z'„{s„-x) и Х'„ (s„-x).

Рассмотрим теперь двухшаговую задачу: присоединим к я-му шагу («-1)-й (рис. 12.2).

Для любых состояний s„-2, произвольных управлений Х_п-\ и оптимальном управлении на п-и шаге значение целевой функции на двух последних шагах равно:

fn-i(s_n-b Х_п-_Х)+Z'„{s_n-_X). (12.6)

Согласно принципу оптимальности для любых s_n-i решение нужно выбирать так, чтобы оно вместе с оптимальным управле­нием на последнем (п-и) шаге приводило бы к максимуму целе­вой функции на двух последних шагах. Следовательно, нужно найти максимум выражения (12.6) по всем допустимым управле­ниям Х„-\. Максимум этой суммы зависит от s„-i, обозначается через Z„_| (s_n-2) и называется условным максимумом целевой функ­ции при оптимальном управлении на двух последних шагах. Соответ­ствующее управление Х_п-\ на (п~1)-и шаге обозначается через

X*„.i(s_n-2) и называется условным оптимальным управлением на (п— 1)-м шаге.

2*_п-\ fe-2)= maxJ/„_i(V2.*_fl-i) + ^zl (-Vi)) ■ (12.7)

Следует обратить внимание на то, что выражение, стоящее в фигурных скобках (12.7), зависит только от s„-2 и Х_п-\, так как s„-\ можно найти из уравнения состояний (12.2) при к=п—\.

^-1=9/7-1(^-2 ,Х_п-\) и подставить вместо s_n-\ в функцию Z* (s_n-\).

В результате максимизации только по одной переменной Х„-х согласно уравнению (12.7) вновь получаются две функции:

К-1 (^sn-2) И Х*_п__х (s„-₂).

Далее рассматривается трехшаговая задача: к двум последним шагам присоединяется (л-2)-й и т. д.

Обозначим через Z*_k (s_k-\) условный максимум целевой функции, полученный при оптимальном управлении на п—к+1 шагах, начиная с

к-го до конца, при условии, что к началу k-го шага система находи­лась в состоянии s_k-_h Фактически эта функция равна

^*(**-i)= max tfi(Si-i>Xi)-Z'_k+l(s_k) = max £fi{si-_UXi)-

{(** + ! .-.*«)} i = k + \

J к № h Л_к)