Общая постановка задачи ДП

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

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

Задачи динамического программирования:

1. Задача распределения финансовых средств (капитальных вложений между направлениями их использования).

2. Замена технологического оборудования с учетом планирования текущих и капитальных затрат на его обслуживание.

3. Стратегическое планирование предприятия на несколько лет.

4. Разработка правил управления запасами, устанавливающими момент пополнения запасов и размер пополняющего заказа.

5. Календарное планирование производства и др.

Общая постановка задачи ДП

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

Управляемый процесс в качестве объекта имеет систему S, которая в процессе управления переводится из начального состояния s₀ в некоторое конечное состояние s_n, где n – число состояний системы или шагов.

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

Особенности модели ДП:

- задача оптимизации интерпретируется как n - шаговый процесс управления;

- целевая функция модели является аддитивной (суммарной) функцией показателей эффективности каждого шага;

- выбор управления на k -ом шаге зависит только от состояния системы на этом шаге;

- каждое состояние системы после k -го шага управления зависит только от предшествующего состояния и управления .

- на каждом шаге управление зависит от конечного числа управляющих переменных, а состояние - от конечного числа параметров.

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

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

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

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

Каждое состояние системы может быть выражено: