Математические методы в экономике
Главная | Динамическое программирование | Регистрация | Вход
 
Пятница, 24.11.2017, 23:04
Приветствую Вас Гость
Главное меню
Статистика
Форма входа

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

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

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

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

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

Постановка задачи

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между несколькими предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния S0 в конечное Sn. Предположим, что управление можно разбить на n шагов и решение принимается последоватльно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных - переменную состояния системы Sk и переменную управления xk. Переменная Sk определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояни S1 на этм шаге можно применить некоторые управления, которые характеризуются переменной xk, удовлетворяющей определенным ограничениям, и называются допустимыми.

Применение управляющего воздействия xk на каждом шаге переводит систему в новое состояние Sk и приноит некоторый результат φ(Sk-1xk). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление xk* - такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(Sk) и зависит от номера шага k и состояния системы Sk-1.

Задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция принимает наибольшее (наименьшее) значение F(S0,X*) → extr.

Решение задач ДП

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

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

Среди всех шагов есть один, последний, который может планироваться, без оглядки на будущее, чтобы он принес наибольшую выгоду. Поэтому процесс динамического программирования обычно разворачивается от конца к началу: прежде всего планируется последний, n-й шаг Метод решения был предложен в 50-х годах 20 века Р.Беллманом.

Согласно принципу Беллмана, решение начинается с последнего n-го шага. Для этого делаются предположения, в каких состояниях могла быть система перед этим шагом и для каждого находится оптимальное управление. Затем, на n-1–м шаге управление выбирается так, чтобы выигрыш двух последних шагов был максимальным. Затем рассматриваются 3 последних шага и т.д.

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

Математическая формулировка принципа Беллмана

Обозначим:

Fn(S0) – выигрыш, который получается при переходе системы из начального состояния S0 в конечное состояние Sn за n шагов S0 → Sn.

Fn-k(Sk) – выигрыш, полученный при переходе системы из состояния Sk в конечное состояние Sn за n-k шагов.

Тогда будет верным соотношение Fn(S0) = max [W1(S0,U1)+W2(S1,U2) + ..... + Wn(Sn-1,Un)]. Общий выигрыш есть сумма выигрышей на каждом шаге. Выигрыш на k-м шаге – это сумма выигрышей на этом шаге плюс выигрыш на всех последующих шагах. Fn-k(Sk) = max [Wk+1(Sk,Uk+1) + Fn-k-1(Sk+1)] - это математическая формулировка принципа Беллмана.

Пример


Copyright MyCorp © 2017Бесплатный конструктор сайтов - uCoz