Сущность динамического программирования
При решении задач линейного и нелинейного программирования, экономические процессы считаются статическими, т.е. не зависят от времени, в связи с чем оптимальное решение находилось на один этап. Такие задачи называются одноэтапными или одношаговыми.
Экономический процесс в задачах динамического программирования зависит от времени, т.е. от нескольких временных периодов, поэтому определяются оптимальные решения для каждого этапа, обеспечивающие оптимальное развитие целого процесса. Динамическое программирование является многоэтапным (многошаговым).
Динамическое программирование – это математический аппарат, который позволяет проводить оптимальное планирование многоэтапных управляемых процессов, а также процессов, которые зависят от времени. Управляемым экономический процесс становится тогда, когда можно воздействовать на его развитие. Управление – это совокупность решений, которые принимаются на каждой стадии влияния на процесс. Управление в экономических процессах состоит в распределении и перераспределении ресурсов на всех этапах.
К примеру, выпуск товаров предприятием – это управляемый процесс, поскольку он определен изменением количества оборудования, объемами финансирования, поставками сырья и т.д. Все решения, принимаемые в начале каждого периода по обеспечению организации ресурсами, сырьем, оборудованием, по размерам финансирования, а также по замене оборудования, являются управлением. На первый взгляд может показаться, что для получения максимальных объемов выпуска продукции, самым простым вариантом будет вложение максимально возможного количества средств и использование оборудования на полную мощность. Однако, это приведет к быстрому износу оборудования, а, следовательно, к снижению выпуска продукции. Таким образом, выпуск продукции необходимо спланировать так, чтобы оградиться от нежелательных эффектов. Стоит предусматривать мероприятия по пополнению оборудования по мере его изнашивания. Это хотя и снижает первоначальные объемы выпускаемой продукции, но в дальнейшем обеспечивает возможность наращивания производства. Так, экономический процесс состоит из нескольких этапов, действие каждого влияет на общее развитие. Управляемый процесс начинается, когда принимается какое-либо решение о замене оборудования, объемах капитальных вложений и т.д. Планирование многоэтапного процесса подразумевает учет интересов всего процесса, другими словами, при принятии любого решения всегда следует учитывать конечную цель.
С помощью динамического программирования можно упростить решение задач, а также решить такие, в которым нет возможности применить приемы и способы математического анализа. Упростить решение можно посредством уменьшения количества изучаемых вариантов, поскольку для решения сложной многовариантной задачи в методе поэтапного планирования предполагается многократное решение простых задач.
Между тем, в динамическом программировании есть и недостатки. Например, в линейном программировании является универсальным симплексный метод, а в динамическом такого метода нет. Также недостатком динамического программирования является трудоемкость решения многомерных задач.
Постановка задачи динамического программирования
Рассмотрим постановку задачи динамического программирования на примере инвестирования, которое связано с распределением ресурсов между предприятиями. При управлении инвестициями система постепенно переводится из состояния $S_0$ в состояние $S_n$. Предполагается, что управление можно разделить на шаги, а решение будет приниматься последовательно на каждом этапе. Управление будет представлять собой совокупность n управлений. Каждый шаг содержит две переменных: переменную управления $x_k$ и переменную состояния $S_k$. Переменная $S_k$ показывает, в каком состоянии может находиться система на $k$-м шаге. Состояние $S$ определяет управления, которые описываются переменной $x_k$ и удовлетворяют некоторым ограничениям.
Предположим, что $X=(x_1, x_2, …, x_k,… , x_n)$ – это управление, которое переводит систему из положения $S_0$ в $S_n$, а $S_k$ – это состояние системы на $k$ шаге. Последовательность состояний данной системы в таком случае можно изобразить в виде графа (Рисунок 1).
Рисунок 1. Состояния системы. Автор24 - интернет-биржа студенческих работ
Управляющее воздействие $x_k$ на любом шаге переводит систему в другое состояние, которое приносит результат. Для каждого состояния на всех шагах определяется оптимальное управление $x^*_k$, которое позволяет достичь оптимальный результат. Числовая характеристика такого результата носит название функция Беллмана $F(k)(S)$ и зависит от шага $k$, а также от состояния системы $S$.
Формулировка задачи динамического программирования такова: необходимо выявить такое управление $X^*$, которое переводит систему из состояния $S_0$ в $S_n$, а целевая функция при этом принимает наименьшее (наибольшее) значение $F(S_0, X^*)→extr$.
Характерные черты задачи динамического программирования состоят в следующем:
- Задача оптимизации является конечным многошаговым процессов управления;
- Выигрыш (целевая функция) имеет вид аддитивной и равняется сумме целевых функций на каждом шаге;
- Определение управления на каждом шаге находится в зависимости от состояния систем перед этим шагом и не воздействует на предшествующие шаги (обратной связи нет);
- Состояние системы $S_k$ зависит только от состояния $S_{k-1}$ и управляющего воздействия $x_k$;
- $X_k$ на любом шаге управления зависит от числа переменных управляющего типа, положение системы $S_k$ находится в зависимости от числа параметров;
- Оптимальным управлением является вектор $X^*$, который определяется последовательностью оптимальных управлений на каждом шаге: $X=(x^*_1, x^*_2, …, x^*_k, …, x^*_n)$, а количество управлений определяет число шагов в задаче.
