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

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ЭКОНОМИКИ И  ПРЕДПРИНИМАТЕЛЬСТВА

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА ПО  
дисциплине «Методы и модели в экономике»

на тему:

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

 

 

                                                             Работу выполнил: студент гр. ЭиП-213

                                                                                                                                          Работу проверил:

 

 

 

 

 

 

 

 

Челябинск

2011

Содержание.

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

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

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

Заключение…………………………………………………………………….…..11

Список литературы………………………………………………………………..12

 

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

 

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

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

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

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

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

Вот некоторые типичные области применения моделей динамического программирования при принятии решений:

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

 

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

 

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

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

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

Таким образом, на каждом шаге в соответствии с принципом оптимальности ищется решение, обеспечивающее оптимальное продолжение процесса относительно состояния, достигнутого в данный момент. Если при движении от конца к началу оптимизируемого процесса определены условно – оптимальные решения для каждого шага и вычислен соответствующий эффект (эту стадию рассуждений называют иногда условной оптимизацией), то остается «пройти» весь процесс в прямом направлении (стадия безусловной оптимизации) и «прочитать» оптимальную стратегию, которая нас интересует.

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

 

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

 

Задача о  выборе наиболее экономного маршрута доставки груза.

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

 

рис. 1

 

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

                   f_n(s)=min_"(s,j)( с_sj + f_n-1(j)), где

    f_n(s) – стоимость, отвечающая стратегии минимальных затрат для пути от состояния s до конечного состояния, если до него остается n шагов;

    х_n(s) – решение, позволяющее достичь f_n(s).

Т.е. х_n(s) соответствует пути минимальной длины от состояния s до конечного состояния, которое достигается за n шагов.

Таблица 1

I	II	III	IV	V
1	2 3 4	5 6 7	8   9	10

 

К группе I отнесем пункт 1, к группе II – пункты, в которые можно попасть из пункта 1 (таковыми будут 2; 3; 4), к группе III отнесем пункты, в которые можно попасть непосредственно из любого пункта группы II (таковыми будут 5; 6; 7), и т.д. в результате движение транспорта с грузом из пункта 1 в пункт 10 примет поэтапный характер: на первом этапе транспорт перемещается из пункта 1 в какой-то пункт группы II, на втором этапе – из пункта группы II в пункт группы III и т.д. Вместе с этим и процесс нахождения наиболее экономного маршрута из пункта 1 в пункт 10 распадается на шаги. На каждом шаге надо так выбрать маршрут следования груза в пункт соседней группы, чтобы доставка груза по всему маршруту была сопряжена с минимальными затратами. Избранный нами подход к решению задачи учитывает особенности сети, изображенной на рис. 1: после разбиения на группы пункты, оказавшиеся в одной и той же группе, дорогами не соединены.

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

В данном случае процесс  состоит из четырех шагов (рис. 2). Будем оптимизировать каждый шаг, начиная  с последнего – четвертого. На этом шаге в пункт 10 можно попасть из пункта 8 или 9, причем из каждого пункта только одним способом. Если предпоследний, третий, шаг привел груз в пункт 8, то дальше следует двигаться по маршруту 8 – 10, и затраты на перевозку единицы груза будут равны единице; если же в пункт 9 – то следует двигаться по маршруту 9 – 10, на котором затраты составят 4 единицы. Условное оптимальное решение помечаем на сети стрелкой, выходящей из соответствующего кружка, а величину затрат записываем в нижней половинке кружка.

1 шаг 2 шаг 3 шаг 4 шаг

рис.2

 

Переходим к оптимизации  предпоследнего, третьего, шага. Для  этого рассмотрим все возможные  исходы предшествующего, второго, шага. После этого шага груз может оказаться  только в одном из пунктов – 5,6,7. Для каждого пункта выбираем условное оптимальное решение – оптимальный маршрут в пункт 10 и соответствующие минимальные затраты. Так, если груз оказался в пункте, 5, то далее можно следовать либо через пункт 8, либо через пункт 9. В первом случаи затраты равны 7+1=8 единицам, во втором – 5+4=9 единицам. Значит, условный оптимальный маршрут из пункта 5 в пункт 10 проходит через пункт 8, а условные минимальные затраты составляют 8 единиц. На ребре 5 – 8 сети ставим стрелку, а в кружке 5 записываем минимальные затраты: 8=7+1. ребро 5 – 9 остается без стрелки. Аналогично для пункта 6 находим условно-оптимальный маршрут 6 – 8 – 10 с затратами в 4 единицы; для пункта 7 – условно-оптимальный маршрут 7 – 9 – 10 с затратами в 5 единиц.

Далее оптимизируем путь доставки груза на втором шаге процесса. Для этого рассматриваем все возможные исходы первого шага. После первого шага груз мог оказаться только в одном из пунктов: 2, 3 или 4. При нахождении условного оптимального решения в каждом из этих пунктов надо просмотреть все возможные маршруту их этого пункта и для каждого из них найти сумму затрат на этом шаге и условных минимальных затрат на оптимальном продолжении маршрута, уже построенном для следующего пункта. Этого требует принцип оптимальности. Из всех возможных маршрутов выбирается тот, для которого эта сумма меньше (если суммы равны, выбирается любой маршрут). Для пункта 2 оптимальным будет маршрут 2 – 6 – 8 – 10 с затратами 12+4=16 единиц; для пункта 3 – маршрут 3 – 7 – 9 – 10 с затратами 7+5=12 единиц; для пункта 4 – маршрут 4 – 7 – 9 – 10 с затратами 13+5=18 единиц.

Оптимизируем, наконец, первый шаг. Для выбора условного оптимального решения рассматриваем три возможных  маршрута: через пункты 2, 3 или 4. Устанавливаем, что наивыгоднейшим будет маршрут 1 – 3 с затратами в 17 единиц. Итак, этап условной оптимизации закончен, и остается пройти процесс в направлении от пункта 1 к пункту 10 и прочитать оптимальный маршрут: 1 – 3 – 7 – 9 – 10.