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

ПОНЯТИЕ И ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

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

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

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

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

 

ПРИНЦИП ОПТИМАЛЬНОСТИ

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ОСНОВНЫЕ ЭТАПЫ СОСТАВЛЕНИЯ  МАТЕМАТИЧЕСКОЙ

МОДЕЛИ ЗАДАЧИ ДИНАМИЧЕСКОГО  ПРОГРАММИРОВАНИЯ

 

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

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

         3. Определение  множества  шаговых управлений x_i, i=1..m и налагаемых на них ограничений, т.е. области допустимых управлений X.

    4. Определение выигрыша  φ(s, x_i),                                                          

который принесет на i-м шаге управление x_i, если система перед этим      находилась в состоянии s.

          5. Определение  состояния s’, в которое переходит система из состояния s под влиянием управления x_i s’=f_i(s, x_i,),                                                

где f_i—функция перехода на i-м шаге из состояния s в состояние s’.

        6. Составление  уравнения, определяющего условный оптимальный     выигрыш   на последнем шаге, для состояния s моделируемого процесса

 

                                                       W_m(S)=max{φ_m(s,x_m)}                         

                                                                  ^x_mЄ X

 

            7. Составление основного функционального уравнения динамического программирования, определяющего условный оптимальный выигрыш для   данного состояния s с i-го шага и до конца процесса через уже известный   оптимальный выигрыш с (i+1)-го шага и до конца:

 

W_i(S)=max{φ_i(s, x_i)+W_i=1(f_i(s, x_i))}

^x_mЄ X

 

 

           В уравнении в уже известную  функцию W_i+1(s), характеризующую условный оптимальный выигрыш с (i+1)-го шага до конца процесса, вместо состояния s подставлено новое состояние s’=f_i(s, x_i), в которое система переходит на i-м шаге под влиянием управления  x_i.

          В динамических  моделях, в отличие от линейных  моделей, отдельно вводятся переменные  управления x_i, и переменные, характеризующие изменение состояния s под влиянием управления. Таким образом, структура динамических моделей более сложная, что естественно, так как в этих моделях учитывается фактор времени.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАДАЧИ ДИНАМИЧЕСКОГО  ПРОГРАММИРОВАНИЯ

 

Задача планирования рабочей силы

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

Проект будет выполняться в течение n недель и минимальная потребность в рабочей силе на протяжении i-й недели составит b_i рабочих. При идеальных условиях хотелось бы на протяжении i-й недели иметь в точности b_i рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей.

Если x_i – количество работающих на протяжении i-й недели, то возможны затраты двух видов: 1) С₁(x_i- b_i)-затраты, связанные с необходимостью содержать избыток x_i - b_i рабочей силы и 2) С₂(x_i- x_i-1)-затраты, связанные с необходимостью дополнительного найма (x_i- x_i-1) рабочих.

Элементы модели динамического  программирования определяются следующим образом:

       1.Этап і представляется порядковым номером недели і,

         і=1,2,…n.

       2.Вариантами решения  на і-ом этапе являются значения x_i –

          количество  работающих на протяжении і-й недели.

       3.Состоянием на  і-м этапе является x_i-1 – количество

          работающих на протяжении (і-1) –й недели (этапа).

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

где

Вычисления начинаются с этапа  n при x_n=b_n и заканчиваются на этапе 1.

 

Задача замены оборудования

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

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

Обозначим через r(t) и c(t) прибыль от эксплуатации t-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) – стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна I.

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

Этап і представляется порядковым номером года і, і=1,2,...n.

Вариантами решения на і-м этапе (т.е. для і-ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і-ого года.

Состоянием на і-м этапе является срок эксплуатации t (возраст) механизма к началу і-ого года.

 Пусть f_i(t)-максимальная прибыль, получаемая за годы от і до n при условии, что в начале і-ого года имеется механизм t-летнего возраста.

Рекуррентное уравнение имеет  следующий вид:

(1)-если эксплуатировать механизм,

(2)-если заменить механизм.

 

Оптимальное распределение  инвестиций  как задача

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

 

          Инвестор  выделяет средства в размере  D условных единиц, которые должны быть распределены между m-предприятиями. Каждое i-е предприятие при инвестировании в него средств x приносит прибыль q_i(x) условных единиц, i=1..m. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

          Выигрышем  W в данной задаче является прибыль, приносимая  m-предприятиями.

1.  Определение числа шагов.  Число шагов m равно числу предприятий, в которые осуществляется инвестирование.

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

s≤D.

3   Выбор шаговых управлений. Управлением на i-м шаге x_i, x=1..m   является количество средств, инвестируемых в i-е предприятие.

4.  Функция выигрыша на  i-м шаге

q_i(x_i)

- это прибыль, которую приносит i-е предприятие при инвестировании в него средств

                                                                  _m   

                                                         W=∑q_ix_i,

                                                                  ⁱ⁼¹   

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

5.  Определение функции перехода  в новое состояние.

                                                         f_i(s,x)=s-x                                             

 

Таким образом, если на i-м шаге система находилась в состоянии s, а выбрано управление x, то на i+1-м шаге система будет находиться в состоянии s-x.  Другими словами, если в наличии имеются средства в размере s у.е., и в i-е предприятие инвестируется x у.е., то для дальнейшего инвестирования остается (s-x)  у.е.

6.  Составление функционального  уравнения для i=m.    

                             

                                                     W_m(s)=q_m(s)                                        

                                                      x_m(s)=s      

             

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

7.  Составление основного функционального  уравнения.

          Подставив  в формулу выражения и, получим следующее функциональное уравнение

                                             W_i(s)=max{q_i(x)+W_i+1(s-x)}                        

Пусть перед i-м шагом у инвестора остались средства в размере s  у.е. Тогда х у.е. он может вложить в i-е предприятие, при этом оно принесет доход q_i(x), а оставшиеся s-x  у.е.—в остальные предприятия с i+1-го до m-го. Условный оптимальный выигрыш от такого вложения  W_i+1(s-x). Оптимальным будет то условное управление x, при котором сумма q_i(x) и W_i+1(s-x) максимальна.