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

     Чтобы можно было использовать принцип  оптимальности практически, необходимо записать его математически. Обозначим  через z₁(x_n-1), z₂(x_n-2),…, z_n(x₀) условно-оптимальные значения приращений целевой функции на последнем шаге, двух последних,…, на всей последовательности шагов, соответственно.

     Тогда для последнего шага:

     z₁(x_n-1) = (min) {F_n(x_n-1, u_n)},  

     где u_n – множество допустимых (возможных) управлений на n-ом шаге, x_n-1 – возможные состояния системы перед n-ым шагом.

     Для двух последних шагов:

     z₂(x_n-2) = (min) {F_n-1(x_n-2, u_n-1) + z₁(x_n-1)}. 

     Для k последних шагов:

     z_k(x_n-k) = (min) {F_n-k+1(x_n-k, u_n-k+1) + z_k-1(x_n-k+1)}. 

     Для всех n шагов:

     z_n(x₀) = (min) {F₁(x₀, u₁) + z_n-1(x₁)}. 

     Полученные  рекуррентные соотношения называют функциональными уравнениями Беллмана.

     При этом согласно определению z_n(x₀) = F*. 
 
 
 
 
 

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

 

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

Планирование  рабочей силы:

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

    Задача:

    Предположим, что описанный выше проект будет  выполняться в течение 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 лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна l.

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

1. Этап і представляется порядковым номером года і, і=1,2,...n.
2. Вариантами решения на і-м этапе (т.е. для і-ого года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале і-ого года.
3. Состоянием на і-м этапе является срок эксплуатации t (возраст) механизма к началу і-ого года.

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

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

    

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

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

    Распределение инвестиций

    Динамическое  моделирование в инвестировании позволяет определить, как необходимо распределить капитальные вложения между объектами (предприятиями, проектами) таким образом, чтобы получить максимально  возможную суммарную прибыль.

    Задача:

    Предположим, что в начале каждого из следующих n лет необходимо сделать инвестиции P₁, P₂,…, P_n соответственно. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r₁, а второй - r₂. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы.

    Премиальные меняются от года к году, и для  і-ого года равны q_i1 и q_i2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.

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

1. Этап і представляется порядковым номером года і, і=1,2,...n
2. Вариантами решения на і-м этапе (для і-ого года) являются суммы l_i и инвестиций в первый и второй банк соответственно.
3. Состоянием x_i на і-м этапе является сумма денег на начало і-ого года, которые могут быть инветсированы.

    Заметим, что по определению  =x_i-l_i. Следовательно,

    где і=2,3,…n, x₁=P₁. Сумма денег x_i, которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за инвестиции, сделанные на протяжении (і-1)-го года.

    Пусть f_i(x_i)- оптимальная сумма инвестиций для интервала от і-го до n-го года при условии, что в начале і-го года имеется денежная сумма x_i. Далее обозначим через s_i накопленную сумму к концу n-го года при условии, что l_i и (x_i-l_i)-объемы инвестиций на протяжении і-го года в первый и второй банк соответственно. Обозначая , і=1,2, мы можем сформулировать задачу в следующем виде.

    Максимизировать z=s₁+s₂+…+s_n, где

    

    Так как премиальные за n-й год являются частью накопленной денежной суммы от инвестиций, в выражения для s_n добавлены q_n1 и q_n2.

    Итак, в данном случае рекуррентное уравнение  для обратной прогонки в алгоритме  динамического программирования имеет  вид 

    

    где x_i+1 выражается через x_i в соответствии с приведенной выше формулой, а f_n+1(x_n+1)=0.

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

     ЗАКЛЮЧЕНИЕ 

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

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

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

     СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 

1. Баканов  М.И., Шеремет А.Д. Теория экономического анализа: Учебник. – 4-е изд., доп. и перераб. – М.: Финансы и статистика, 1999

2. Браславец М.Е. Экономико-математические методы в организации и планировании сельскохозяйственного производства, 1974

3. Кравченко  Р.Г., Попов И.Г., Толпекин С.З. Экономико-математические методы в организации и планировании сельскохозяйственного производства, 1974

4. Кузнецов А.В., Холод Н.И. Математическое программирование: [ Учеб. Пособие для эконом. спец. вузов]. – Мн.: Выш. шк., 1984. – 221 с., ил.

5. Кузнецов  Ю. Н. и др. Математическое программирование. Учеб. пособие для вузов. М., «Высш. школа», 1976. – 352с. с ил.

6. Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988
7. Карманов В. Т. Математическое программирование. –М.:Наука,1986.
8. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
9. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
10. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,1965.
11. Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,1990.