11

Раздел 3

ЭЛЕМЕНТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

1. Особенности метода

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

1.1. Основные понятия

Динамическое программирование (иначе – динамическое планирование) – это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой. Многие экономические процессы расчленяются на шаги естественным образом. Это все процессы планирования и управления, развивающиеся во времени. Естественным шагом в них может быть год, квартал, месяц, декада, неделя, день и т.д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких задачах вводятся искусственно. Поэтому «динамика» задач динамического программирования заключается в методе решения.

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

В общей постановке задача динамического программирования формулируется следующим образом. Имеется некоторая управляемая физическая система , характеризующаяся определенным набором параметров. В этой системе происходят какие-то процессы (экономические, производственные, технологические и т.п.), которые можно представить как многошаговые. На каждом шаге процессам в системе соответствуют определенные значения параметров, описывающих состояние системы. Заданы условия, позволяющие определять или начальное, или конечное состояние системы, или оба этих состояния. Иногда задаются области начальных и конечных состояний. Поскольку управление системой осуществляется для достижения конкретной цели, то указан показатель эффективности управления, называемый целевой функцией, численно выражающий эффект («выигрыш»), получаемый при том или ином управлении на множестве допустимых управлений. В экономических системах целевая функция может определять прибыль, затраты, рентабельность, объем производства и т.д. Задача динамического программирования состоит в выборе из множества допустимых управлений такого, которое переводит систему из начального состояния в конечное, обеспечивая при этом целевой экстремум (минимум или максимум в зависимости от ее экономической сути). Упомянутое управление называют оптимальным.

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

2. Особенности задач динамического программирования

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

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

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

.

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

4. На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решения .

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

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