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

Лекция № 7 09г.

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

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

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

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

Пусть Х(Х₁,Х₂,…,Х_n) – управление, переводящее систему S из состояния s₀ в состояние . Обозначим через s_k состояние системы после к -го шага управления. Получаем последовательность состояний s₀,s₁,….,s_k-1,s_k,......,s_n-1,s_n= , которую изобразим кружками.

Уравнение состояния

Целевая функция k-го шага управления

Функция эффективности

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

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

2. целевая функция равна сумме целевых функций каждого шага.

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

4. состояние после к шага управления зависит только от предшествующего состояния и управления (отсутствует последействие).

5. на каждом шаге управления зависит от конечного числа управляемых переменных, а состояние от конечного числа параметров.

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

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

Начальное состояние

Полученное состояние

условный максимум целевой функции на nшаге

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

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

можно найти из уравнения состояния при k=n-1

и подставить в целевую функцию .

В результате получим 2 функции и

Рассмотрим 3-х шаговую задачу.

Уравнение называется условно-оптимальным управлением на k шаге. Обозначим формулу для определения через . Уравнение называется уравнением Беллмана – это рекуррентные соотношения, позволяющие найти последующее значение функции, зная предыдущее. Если из уравнения найти , то при k=n-1 из (**) можно определить и соответствующие . Зная , находим уравнение состояния. Процесс решения уравнений (*) и (**) называется условной оптимизацией. В результате получается две последовательности:

, , …, , (1)

Это последовательность называется условные максимумы целевой функции.

Последовательность условно оптимальных управлений:

, ,…, , (2)

Используя эти последовательности, можно найти решение задач динамического программирования при заданных n и . - условный максимум целевой функции за n шагов при условии, что к началу первого шага система находится в состоянии , т.е. , при фиксированном значении получаем .

Далее находим и подставляем это выражение в последовательность (2) и т.д. по цепочке

Оптимальное решение задачи динамического программирования равно вектору .

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

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

X

Принято считать, что 1) прибыль (x) не зависит от вложения средств в другие предприятия.

2) прибыль от каждого предприятия выражается в одних у.е.

3) суммарная прибыль равная сумме прибылей, получаемых от каждого предприятия.

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

Решение:

Экономико-математическая модель

Условия: