Общая схема решения задачи ДП
Билет №9
Динамическое программирование. Решение задач методами динамического программирования.
Динамическое программирование– метод нахождения оптимальных решений многошаговых (многоэтапных) задач.
ДП дает возможность принять ряд последовательных решений, обеспечивающих оптимальность развития процесса в целом.
В задачах динамического программирования экономический процесс зависит от времени (от нескольких периодов (этапов) времени), поэтому находится ряд оптимальных решений (последовательно для каждого этапа), обеспечивающих оптимальное развитие всего процесса в целом. Задачи динамического программирования называются многоэтапными или многошаговыми. Динамическое программирование представляет собой математический аппарат, позволяющий осуществлять оптимальное планирование многошаговых управляемых процессов и процессов, зависящих от времени. Экономический процесс называется управляемым, если можно влиять на ход его развития. Управлением называется совокупность решений, принимаемых на каждом этапе для влияния на ход процесса. В экономических процессах управление заключается в распределении и перераспределении средств на каждом этапе. Началом этапа (шага) управляемого процесса считается момент принятия решения (о величине капитальных вложений, о замене оборудования определенного вида и т.д.). Под этапом обычно понимают хозяйственный год.
|
|
|
Динамическое программирование, используя поэтапное планирование, позволяет не только упростить решение задачи, но и решить те из них, к которым нельзя применить методы математического анализа. Упрощение решения достигается за счет значительного уменьшения количества исследуемых вариантов, так как вместо того, чтобы один раз решать сложную многовариантную задачу, метод поэтапного планирования предполагает многократное решение относительно простых задач.
Планируя поэтапный процесс, исходят из интересов всего процесса в целом, т.е. при принятии решения на отдельном этапе всегда необходимо иметь в виду конечную цель.
Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. При очень большом числе переменных решение задачи даже на современных ЭВМ ограничивается памятью и быстродействием машины. Например, если для исследования каждой переменной одномерной задачи требуется10 шагов, то в двумерной задаче их количество увеличивается до 100, в трехмерной - до 1000 и т.д.
|
|
|
ДП применяется только для решения определенного класса задач, удовлетворяющим следующим требованиям:
1. Задача оптимизации интерпретируется как n-шаговый
процесс управления.
2. Целевая функция равна сумме ЦФ каждого шага.
3. Выбор управления на k-м шаге зависит только от
состояния системы к этому шагу, не влияет на
предшествующие шаги (нет обратной связи).
4. Состояние sk после k-го шага управления зависит только
от предшествующего состояния sk-1 и управления xk
(отсутствие последействия).
5. На каждом шаге управление Xk зависит от конечного
числа управляющих переменных, а состояние sk- от
конечного числа параметров.
Наиболее широко применяемыми практическими
приложениями ДП являются:
• капитальное бюджетирование инвестиций (формирование портфеля реальных инвестиций);
• формирование оптимального портфеля рисковых финансовых инвестиций;
• управление активами и пассивами финансовых организаций (банки, инвестиционные фонды, страховые компании);
• планирование производственной мощности предприятий;
|
|
|
• управление запасами;
• оптимизация в сельском хозяйстве;
• составление оптимальных маршрутов, расписаний и др.
Общая схема решения задачи ДП
1. Определить все состояния системы при переходе из начального
состояния S0 в конечное состояние Sn,
вид ЦФ на каждом шаге Fk (Sk-1,xk) (k=1,2,....n),
функции перехода Sk(Sk-1,xk) из состояния Sk–1 в состояние Sk.
Записать уравнения Беллмана.
2. Из уравнения Беллмана для Z1(S0) по S0 найти
оптимальное управление (ОУ) на 1-м шаге x1*.
3. По S0 и x1*определить состояние системы после 1-го шага:
S1=S1(S0,x1).
4. Из уравнения Беллмана для Z2(S1) по S1 найти
ОУ на 2-м шаге x2*.
5. По S1 и x2* определить состояние системы после 2-го шага:
S2=S2(S1,x2) .
6. Из уравнения Беллмана для Z3(S2) по S2 найти ОУ на 3-м шаге x3* .
7. И т. д.
S0 → x1* → S1 → x2* →S2 → x3* → ... → Sn-1 → xn*
Дата добавления: 2018-04-15; просмотров: 608; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!