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

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

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

 

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

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

 

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

 

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

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

 

 

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

 

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

на тему:

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

 

 

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

Выполнила: студентка 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… . Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

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