§2.2 Динамическое программирование. Принцип оптимальности Беллмана.

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

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

Рассмотрим управляемы процесс, в результате управления система которого S переводится из начального состояния в состояние . Предполагается что управление можно разбить на n шагов, т.е. решение принимается последовательно на каждом шаге.

Пусть управление на k-ом шаге (k=1,2,…n). Переменные удовлетворяют некоторым ограничениям и называются допустимыми.

Пусть - управление, переводящее систему S из состояния в состояние . Обозначим через состояние системы после k-го шага управления. Тогда - последовательность состояний, изображаемая кружками.

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

Состояние системы в конце k-го шага зависит только от предшествующего состояния и управления на k-ом шаге . Это утверждение можно записать в виде уравнений состояний

, (k=1,2,…n).

Целевая функция является аддитивной от показателя эффективности каждого шага. Если обозначить показатель эффективности k-го шага через , где (k=1,2,…n), то .

Общая формулировка задачи динамического программирования.

Определить такое допустимое управление Х, переводящее систему S из состояния в состояние , при котором целевая функция принимает оптимальное значение.

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

Каково бы ни было состояние s системы в результате какого-либо p числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлении на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

Уравнения Беллмана.

Рассмотрим последовательность задач, полагая последовательно n=1,2,… при различных s – одношаговую, двухшаговую и т.д. – используя принцип оптимальности.

Принцип оптимальности можно представить в виде уравнений Беллмана

,                 (4)

k=n-1,n-2,…,2,1.

где n – общее количество шагов (расчет ведется, начиная с последнего шага); – состояние системы соответственно в конце (k-1)-го и k-го шагов. - условный максимум целевой функции, т.е. максимум выражения (4) при условии оптимального управления на n-k+1 шагах, начиная с k-го шага до конца, если к концу k-го шага система находилась в состоянии . - произвольное управление на k-ом шаге и оптимальном управлении на последующих n-k шагах. - показатель эффективности k-го шага.

Уравнения Беллмана (4) представляют рекуррентные соотношения, позволяющие найти предыдущее значение функции через последующие.

Пример.

Задача о распределении инвестиций между предприятиями.

Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства усл. ед. Размеры вложения в каждое предприятие кратны 1 усл.ед. Средства х, выделенные k-му предприятию (k=1,2,3,4) , приносят в конце года прибыль . Функции заданы таблично.

Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.

Решение.

Пусть: - количество средств, выделенных k-му предприятию.

и переменные х удовлетворяют ограничениям

, . Требуется найти переменные , удовлетворяющие последнему равенству и обращающие в максимум функцию Z.

Процесс распределения средств можно разбить на четыре шага, причем номер шага совпадает с номером предприятия. Выбор переменных  - управление соответственно на I, II, III, IV шагах. -конечное состояние процесса распределения, оно должно быть равно нулю. Т.к. все средства должны быть вложены в производство.

Уравнения состояний , k=1,2,3,4 где – параметр состояния – количество средств, оставшихся после k-го шага, т.е. средства, которые остается распределить между оставшимися 4-k предприятиями.

Введем функцию - условную оптимальную прибыль, полученную от k-го, (k+1)-го,…, 4-го предприятий, если между ними распределялись оптимальным образом средства ().

Уравнения Беллмана имею вид:

k=4, , ,

Далее последовательно решаем записанные уравнения, проводя условную оптимизацию каждого шага.

Шаг IV. В таблице исходных данных прибыли четвертого предприятия монотонно возрастают, поэтому все средства, оставшиеся к IV шагу, следует вложить в 4-е предприятие. При этом получим, для возможных значениях , и .

Шаг III. Делаем все предложения относительно остатка средств к III (т.е. после выбора ); может принимать значения 0,1,2,3,4,5 (например, , если все средства отданы 1-му и 2-му предприятиям, , если 1-е и 2-е предприятия ничего не получили  и т.д.).

Шаг II. Условная оптимизация приведена в таблице при k=2. Для всех возможных значений значения находятся в столбцах 8 и 9, первые слагаемые в столбце 7 – значения - взяты из таблицы в условии задачи, а вторые слагаемые из 5-го столбца таблицы, рассмотренной ниже при .

Шаг I.

При k=1 для . Условная оптимизация приведена в таблице.

Если , то одначает прибыль полученную от четырех предприятий при условии, что ед. средств между оставшимися тремя предприятиями будет распределена оптимально и равна.

Если , то , то.

Если , то , то.

Если , то , то.

Если , то , то.

Если , то , то.

Сравнивая полученные результаты получим

при .

Используя равенство получаем

, а ,

, а ,

, а , т.е. .

Максимум суммарной прибыли равен 24 усл. Ед. средств при условии, что первому предприятию выделена 1 усл.ед.; 2-му – 2 усл. ед.; 3-му – 1 усл. ед.; четвертому – 1 усл. ед.