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

1  

  ТЕМА: ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 

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

  2.  Вычислительная схема метода  динамического программирования  (рекуррентные соотношения Беллмана)

  3.  Некоторые экономические задачи,  решаемые методом динамического  программирования

2  

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

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

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

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

3  

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

4  

  2.  Вычислительная схема  метода динамического  программирования  (ре-куррентные соотношения  Беллмана) 

  Пусть  имеется некоторая управляемая  система S, ее начальное состояние  известно s⁰. Допустимое множество состояний Sⁱ. Решение задачи заключается в том, что происходит последовательный переход системы из одного состояния в другое под воздействием управления u. Допустимое множество управлений Uⁱ.

5  

  Целевая  функция задается в виде суммы  оценочных функций r_ⁱ=(s_ⁱ; s_ⁱ⁺¹), значения которых получают на каждом шаге при переходе в решении задачи из состояния s_ⁱ в состояние s_ⁱ⁺¹ при выборе управления u_ⁱ. Необходимо найти такой сценарий развития ситуации u* = (u*_⁰; u*_¹;…; u*_^N-1), при котором достигается экстремум функции: 
 

6  

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

  Основное  функциональное уравнение динамического  программирования позволяет сформировать  стратегию решения задачи на  всех N этапах. Но это уравнение  не подходит для конкретных  вычислений, так как вид оценочной  функции r_ⁱ(s_ⁱ; u_ⁱ) не задан конкретно, и дает лишь общую схему вычислений.

7  

  Алгоритм  решения задачи при помощи  динамического программирования  можно представить в виде следующих  шагов:

  1)  выбрать группу параметров, которые  характеризуют состояние анализируемой  системы S в состоянии s_ⁱ;

  2)  разбить решаемую задачу на  этапы;

  3)  определить совокупность управлений  U_ⁱ для каждого этапа; 

8  

  4)  определить величину эффекта  оценочной функции r_ⁱ(s_ⁱ; u_ⁱ) на i-ом шаге, которое дает управление u_ⁱ при переходе системы из состояния s_ⁱ в s_ⁱ⁺¹ и определить как изменяется сама система при переходе в новое состояние, т. е. необходимо определить функцию изменения состояния s_ⁱ⁺¹ = φ_ⁱ(s_ⁱ; u_ⁱ);

  5)  далее нужно записать рекуррентное  уравнение динамического программирования,  которое определяет условный  оптимальный выигрыш                 , начиная с i-го шага и   до конца решения задачи:

9  
 
 
 
 

6)  затем следует провести условную  оптимизацию N-го шага, когда  из множества возможных состояний  Sⁱ, из которых за один шаг можно дойти до конца задачи, необходимо определить условный оптимальный выигрыш для каждого из них по формуле: 
 
 

и  среди полученных выигрышей выбрать  максимальный; 
 

10  

  7)  далее провести условную оптимизацию  N-1, N-2 и т. д. этапов решаемой  задачи по рекуррентному уравнению  и для каждого этапа выбрать  условное оптимальное управление  uⁱ, при котором получим максимальный выигрыш;

  8)  после того, как было выбрано  условное оптимальное управление  на каждом этапе решаемой задачи,  необходимо провести безусловную  оптимизацию этих управлений,  т. е. нужно взять оптимальное  управление на первом этапе  u*¹, изменить состояние системы по функции sⁱ⁺¹=φⁱ(sⁱ; uⁱ); далее уже для нового состояния системы найти оптимальное управление на втором этапе u*² и так до N-го этапа. 

11  

  3.  Некоторые экономические  задачи, решаемые  методом динамического  программирования

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

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

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

12  

  x_ⁱ - количество ресурсов, выделенных i-му предприятию (i=1,2…n);

  g_ⁱ (x_ⁱ) – функция полезности, в данном случае это величина дохода от использования ресурса x_ⁱ, полученного i - м предприятием;

  f_^k (x) - наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприятий. 

13  

  Сформулированную  задачу можно записать в математической  форме: 
 
 

  при  ограничениях: 

                        , х_ⁱ≥0, i=1,2…n 
 

14  

  Для  максимизации суммарного дохода  от k - го и первых (k–1) способов  необходимо выбрать х^k таким образом, чтобы выполнялись соотношения: 
 
 
 
 

15  

  Задача  о прокладке наивыгоднейшего  пути между двумя  пунктами

  Требуется  определить такой путь из пункта  А в пункт В, общая стоимость  которого является минимальной.

  Стоимость  переезда из пункта i в пункт j обозначим через c^ij.

  Используем  формулу рекуррентных соотношений  Беллмана 

16  
 

  где N— количество этапов в решении;

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

  Pⁿ(i)—решение, позволяющее достичь fⁿ(i). 
 
 
 

17  

  Задача  об определении  оптимальных сроков  замены оборудования

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

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

  r(t)—  стоимость продукции, производимой  за один год на единице оборудования  возраста t лет;

18  

  u(t)  — ежегодные затраты на обслуживание  оборудования возраста t лет;

  s(t)  — остаточная стоимость оборудования  возраста t лет;

  Р  — покупная цена оборудования.

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

  Пусть f^N(t)— максимальная прибыль, получаемая от оборудования возраста t лет за оставшиеся N лет цикла использования оборудования при условии оптимальной стратегии. 

19  

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

  Функциональные  уравнения, основанные на принципе  оптимальности, имеют вид:

20  

  Уравнение  состоит из двух частей: верхняя  строка определяет прибыль, получаемую  при сохранении оборудования; нижняя  – прибыль, получаемую при замене  оборудования и продолжении процесса  работы на новом оборудовании.

  Функция r(t)-u(t) показывает разность между  стоимостью произведенной продукции  и эксплуатационными издержками  на N-й стадии процесса.

  Функция                    характеризует суммарную 

  прибыль  от N-1 оставшихся стадий для оборудования, возраст которого в начале  осуществления этих стадий составляет t + 1 лет. 

21  

  Нижняя  строка характеризуется следующим  образом: функция s(t) – Р представляет  собой чистые издержки по замене  оборудования, возраст которого t лет.

  Функция r(0) – u(0) выражает прибыль, получаемую  от нового оборудования возраста  ноль лет. Предполагается, что переход  от работы на оборудовании  возраста t лет к работе на новом  оборудовании совершается мгновенно, т.е. период замены старого оборудования  и переход на работу на новом  оборудовании укладываются в  одну и ту же стадию. 
 

22  

Последняя  функция                    представляет

  собой доход от оставшихся N–1 стадий, до начала осуществления которых возраст оборудования составляет один год.

23  

 Пример

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

 Для  расширения производства совет  директоров инвестирует средства  в объеме 120 млн.р. с дискретностью 20 млн.р. Прирост выпуска продукции  зависит от выделенной суммы, его значения предоставлены предприятиям.

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