Применение моделей динамического программирования для решения управленческих задач

Федеральное государственное бюджетное  образовательное учреждение

высшего профессионального образования

РОССИЙСКАЯ АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА И ГОСУДАРСТВЕННОЙ  СЛУЖБЫ

ПРИ ПРЕЗИДЕНТЕ РОССИЙСКОЙ ФЕДЕРАЦИИ

НИЖЕГОРОДСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ

Факультет заочного обучения

Кафедра математики и системного анализа

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ «Разработка  управленческого решения»

на тему:

«Применение моделей динамического  программирования для решения управленческих задач»

Специальность: ГМУ

Выполнила: студентка 4 курса, группы  ГК-641  

Кожевникова В.В.

Научный руководитель:

Старший преподаватель:

Макаров Сергей Александрович

Нижний Новгород

2012г. 

Содержание

Введение.

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

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

- определить предмет и особенности  динамического программирования;

- разъяснить принцип Беллмана, лежащий в основе метода;

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

- выявить преимущества и недостатки  данного метода.

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

1. Динамическое программирование.

1. Предмет и особенности динамического программирования.

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

Методология решения задач с применением динамического программирования состоит в разбиении процесса на достаточно мелкие интервалы и отыскании на каждом из них, начиная с последнего, условного оптимального управления (при всех возможных предположения о результатах предыдущего шага). Когда процесс доведен до исходного состояния, то снова повторится вся последовательность шагов от исходного состояния до конечного. При этом из множества условно-оптимальных управлений выбирается одно – оптимальное. Таким образом, здесь решение одной сложной задачи заменяется решением множества простых.

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

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

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

1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
2. Критерий должен обладать свойством аддитивности, т.е. его величина есть сумма частных величин, достигаемых на отдельных этапах. Целевая функция равна сумме целевых функций каждого шага.
3. Рассматриваемый процесс должен быть марковским, т.е. в нем предыстория не должна иметь значения для определения будущих действий. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).
4. Состояние Sk после k-го шага управления зависит только от предшествующего состояния Sk-1 и управления Xk (отсутствие последействия).
5. На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние Sk — от конечного числа параметров.

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

Принцип оптимальности впервые  был сформулирован Р. Беллманом  в 1953 г. «Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения»¹.

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

На  первом  этапе  решения  задачи,  называемом  условной  оптимизацией,  определяются  функция  Беллмана  и  оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге, оптимальное управление х^*_n определяется функцией Беллмана: V(S)=max{f_n(S,x_n)}, в соответствии с которой максимум выбирается из всех возможных значений х_n, причем х_n∈Х.

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

V_n^*=max{f_n(S_n-1,x_n)},

{x_n}

V^*_n-1=max{f_n-1(S_n-2,x_n-1)+V^*_n},

  {x_n-1}

V^*_n-2=max{f_n-2(S_n-3,x_n-2)+V^*_n,n-1},

  {x_n-2}

…………………………………..

V₁^*=max{f₁(S₀,x₁)+V^*_n,n-1…2}.

{x₁}

V_n^* - условный максимум целевой функции показателя эффективности n-го шага при условии, что к началу последнего шага система S была в произвольном состоянии S_n-1, а на последнем шаге управление было оптимальным.

S_n-1 — состояние системы к началу n-го шага,

Х_n — управление на n-м шаге,

f_n(S_n-1,x_n)— целевая функция (выигрыш) n-го шага.

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

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

2. Задачи динамического программирования.

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

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

Будем считать, что состояние S_k рассматриваемой системы S на k-м шаге (k = 1, 2, ..., n) определяется совокупностью чисел S_k= (S_1, S₂ … S_m), которые получены в результате реализации управления X_k, обеспечивающего переход системы S из состояния S_k-1 в состояние S_k.

Пусть также выполняются два условия:

1. Условие  отсутствия последействия. Состояние S_k, в которое перешла система S, зависит от исходного состояния S_k-1 и выбранного управления X_k и не зависит от того, каким образом система S перешла в состояние S_k-1.

2. Условие  аддитивности. Если в результате  реализации k-го шага обеспечен  определенный выигрыш, также зависящий от исходного состояния системы и выбранного управления, то общий выигрыш f_k(S_k-1,x_k)за k шагов составит

F(x)= f_k(S_k-1,x_k), где x=(x₁, x₂…x_n)

Задача  состоит в нахождении оптимальной  стратегии управления, т. е. такой  совокупности управлений x=(x₁, x₂…x_n), в результате реализации которых система S за k шагов переходит из начального состояния в конечное,  и при этом функция дохода F(x) принимает наибольшее значение.

Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление x_n⁰, обеспечивающее максимальное значение функции дохода f_n(S_n-1,x_n).  Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага.

Чтобы решить задачу необходимо воспользоваться  основным функциональным уравнением Беллмана.

Полагая k = n - 1 в уравнении Беллмана, получаем следующее функциональное уравнение:

V_n-1=max{f_n-1(S_n-2, x_n-1)+V_n}

         {x_n-1}

 Используя теперь это уравнение и рассматривая всевозможные допустимые состояния системы S на (n - 1)-м шаге находим условные оптимальные решения и соответствующие значения функции.

Таким образом, на n-м шаге находим условно оптимальное управление при любом допустимом состоянии системы после (n - 1)-го шага, т. е. в каком бы состоянии система не оказалась после (n - 1)-го шага, нам уже известно, какое следует принять решение на n-м шаге.

Перейдем теперь к рассмотрению функционального уравнения при

k = n - 2:

V_n-2=max{f_n-2(S_n-3, x_n-2)+V_n-1}

         {x_n-1}

Решая это функциональное уравнение при различных состояниях на (n - 2)-м шаге, получим условно оптимальные управления x⁰_n-2(S_i^(n-2)), i=1,2… . Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

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

Чтобы найти оптимальную стратегию  управления, т. е. определить искомое  решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. На первом шаге в качестве оптимального управления x^*₁возьмем найденное условно оптимальное управление x⁰_1.На втором шаге найдем состояние S^*₁, в которое переводит систему управление x^*_1. Это состояние определяет найденное условно оптимальное управление x^*₂=x⁰₂, которое теперь будем считать оптимальным. Найти S^*₂ можно, учитывая x^*₂, а это, в свою очередь, позволяет определить  x^*₃ и т.д. В итоге представляется возможным нахождение решения задачи, сущность которой — определение наибольшего дохода и оптимальной стратегии управления на конкретных этапах.

2. Содержательные постановки задач динамического программирования.

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

Задача 1². Планируется деятельность группы филиалов F₁, F₂ …F_k на период хозяйственной деятельности из m лет. В начале периода на развитие всех филиалов выделены средства S, которые должны быть распределены между филиалами. В процессе работы вложенные средства частично расходуются, частично возвращаются в виде дохода и могут быть перераспределены.

Доход каждого филиала зависит от того, сколько средств в него вложено, средства перераспределяются в начале каждого года в периоде из m лет. Какое количество средств в начале года нужно вложить в каждый филиал, чтобы суммарный доход по k филиалам за m лет стремился к максимуму?

Задача 2³. Пусть владелец автомобиля эксплуатирует его в течение m лет. В начале каждого года он может выполнить одно из указанных воздействий:

1. эксплуатация машины без ремонта;
2. ремонт и дальнейшая эксплуатация;
3. продажа автомобиля или замена его новым автомобилем.

Нужно выбрать одно из решений на каждом из m годов (шагов).

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

Задача 3. Планируется распределение начальной суммы X₀ млн. р. Между четырьмя предприятиями некоторого объединения. Средства выделяются только в размерах кратных  a=80 млн. р. Функции прироста продукции от вложенных средств на каждом предприятии заданы таблично. Требуется так распределить вложения между предприятиями, чтобы общий прирост продукции (в млн. р.) был максимальным. Решить задачу на основе функционального уравнения Беллмана.

Задача 4. К началу текущей пятилетки на предприятии установлено новое оборудование. Зависимость производительности этого оборудования от времени его использования предприятием, а также зависимость затрат на содержание и ремонт оборудования при различном времени его использования приведены в таблице:

Зная, что затраты, связанные с  приобретением и установкой нового оборудования, идентичного с установленным, составляют 40 тыс.руб., а заменяемое оборудование списывается, составить такой план замены оборудования в течение пятилетки, при котором общая прибыль за данный период времени максимальна⁴. 

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

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

Постановка задачи.

Найти оптимальное распределение  средств между 5 отраслями на один год. Пусть общее количество средств, которые необходимо наилучшим образом распределить между рассматриваемыми производственными отраслями, равно 500 условным единицам. Шаг дискретизации для простоты ведения расчетов выбран равным 100ед.

Решение.

Введём обозначения:

 количество средств, выделяемых  -му предприятию ( =1, 2, 3, 4, 5). .

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения  средств  = 5 рассматриваем как 5-шаговый, номера шагов совпадают с номерами предприятий, выбор , , , , - управления на 1, 2, 3,4,5 шагах. Конечное состояние равно нулю, так как все средства должны быть распределены.

Уравнения состояний в данной задаче имеют вид:

,

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

Введем  условную оптимальную прибыль, полученную от -го, +1-го, …,5-го предприятий, если между ними распределялись оптимальным образом средства . Допустимые управления удовлетворяют условию . Т.е. либо -му предприятию ничего не идет, либо не более того, что остается к -му шагу.

Уравнение Беллмана и  уравнение для максимума целевой  функции на последнем шаге примут вид:

Шаг 1. Предположим, что задача полностью  решена и осталось распределить оставшийся ресурс Х₁₂ между 1 и 2-й отраслями. Необходимо рассмотреть все возможные варианты и найти оптимальные сочетания между 1 и 2 отраслями.

Шаг 2.

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

Шаг 3.

Теперь необходимо рассмотреть как единый комплекс отрасли 1,2 и 3 и провести аналогичную процедуру распределения ресурсов между этим комплексом и отраслью 4.