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

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

• Основные определения и история развития
• Уравнение Беллмана
• Математическая модель для  задачи динамического программирования
• Пример задачи динамического программирования

 

Динамическое программирование - это вычислительный метод для решения задач определенной структуры. Динамическое программирование возникло и сформировалось в 1950–1953 гг. благодаря работам Ричарда Беллмана и его сотрудников. Беллман (Bellman) Ричард Эрнест (1920-84)

– американский математик. Основные труды по вычислительной математике и теории оптимального управления. Разработал метод динамического программирования. Задачи управления запасами были первыми задачами,

которые решались этим методом.

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

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

программирования, написаны также программы полного перебора — для проверки основного алгоритма, и для более ясного понимания каждой из рассмотренных экономических задач.

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

 

 

 

Принцип оптимальности Беллмана (также известный как принцип динамического программирования), названный в честь Ричарда Эрнста Беллмана, описывает действие математического метода оптимизации, называемого динамическим программированием. Он заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции fk(хk, ξk), а выбирать оптимальное управление хk* в предположении об оптимальности всех последующих шагов.

 

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

Где, управляемый объект описывается  векторным дифференциальным уравнением  общего вида, а критерий оптимальности  также имеет общий вид

 

 

1) оптимальная стратегия замены оборудования;

 

2) оптимальное распределение ресурсов;

 

3) распределение инвестиций для эффективного использования потенциала предприятия;

 

4) минимизация затрат на строительство и эксплуатацию предприятий;

 

5) нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий.

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

 

Пусть дана операция О, состоящая из m шагов (этапов). Эффективность операции характеризуется показателем «выигрышем» – W. Выигрыш W за всю операцию складывается из выигрышей на отдельных шагах, где wi – выигрыш на i-м шаге.:

Если W обладает таким свойством, то его называют аддитивным критерием.

Совокупность всех шаговых управлений  представляет собой управление операцией в целом:

 

 – не числа, а может быть, векторы, функции и т. д.

Требуется найти такое управление  х, при котором выигрыш W обращается  в максимум:

 

Следует иметь в виду, что  в общем случае 

 

 

 То управление х*, при котором этот максимум достигается, называется оптимальным управлением. Оно состоит из совокупности оптимальных шаговых управлений , максимальный выигрыш, который достигается при этом управлении, обозначается W*:

 

 

Последняя формула читается  так: величина W* есть максимум из  всех W(x) при разных управлениях  х (максимум берется по всем  управлениям х, возможным в данных  условиях).

 

 

Прокладывается участок железнодорожного  пути между пунктами А и  В. Требуется так провести дорогу  из А в В, чтобы суммарные  затраты на сооружение участка  были минимальны. Для решения  задачи необходимо разделить  отрезок АВ на m частей, провести  через точки деления прямые, перпендикулярные  АВ, и считать за «шаг» переход  с одной такой прямой на  другую. На каждом шаге можем  двигаться либо строго на восток (по оси X), либо строго на север (по оси Y). Тогда путь от А  в В представляет ступенчатую  ломаную линию, отрезки которой  параллельны одной из координатных  осей. Затраты на сооружение каждого  из отрезков, млн. р., известны (рис. 1). Управление всей операцией состоит из совокупности шаговых управлений:

 

 

 требуется выбрать такое (оптимальное) управление х*, при котором суммарные затраты на сооружение всех участков минимальны:

 

 

Рис.1. Затраты на сооружение  каждого отрезка пути

 

 

Разделим расстояние от А  до В в восточном направлении  на 4 части, в северном – на 3 части. Путь можно рассматривать как  управляемую систему, перемещающуюся  под влиянием управления из  начального состояния А в конечное  В. Состояние этой системы перед  началом каждого шага будет  характеризоваться двумя целочисленными  координатами х и у. Для каждого  из состояний системы (узловой  точки) найдем условное оптимальное  управление.

 

 

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

Найдем условную оптимизацию  последнего шага (рис. 2, а).

 

Рис.2.а

 

Рис.2.б

 

 

 В точку В можно попасть точки из B1 или В2. В узлах записана стоимость пути. Стрелкой показан минимальный путь. Рассмотрим предпоследний шаг (рис.2, б).Для точки В3 условное управление – по оси X, а для точки B5 – по оси Y. Управление для точки В4 выбираем как , т. е. по оси Y.

 

 

 

 

Условная оптимизация для всех  остальных узловых точек показана  на рис. 3.

 

 

 

 

Получим , где с – север, в  – восток.

 

Минимальные затраты составляют 10 + 13 + 8 + 12 + 9 + 9 + 10 = = 71 млн. руб.

Если решать задачу исходя  из оптимальности на каждом  этапе, то решение будет следующим:

 

 

 

 

Затраты составят 10 + 12 + 11 + 10 + 9 + 13 + 10 = 75 > 71.

 

Ответ. Прокладывать путь целесообразно  по схеме: с, с, в, с, в, в, в, при этом  затраты будут минимальные и  составят 71 млн. руб.

 

 

• Гольдштейн А.Л. "Теория принятия решений" ПГТУ