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

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

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

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

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

Обозначим через Хk управление на k-м шаге (k=1, 2, ..., п). Переменные Хk удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Хk может быть числом, точкой в п-мерном пространстве, качественным признаком).

Пусть Х (Х1, Х1, ..., Хn) – управление, переводящее систему S из состояния s0 в состояние sn Обозначим через sk состояние системы после k-го шага управления. Получаем последовательность состояний s0, s1,..., sk-1, sk,..., sn-1, sn=, которую изобразим кружками (рис. 1).

Показатель эффективности рассматриваемой управляемой операции – целевая функция – зависит от начального состояния и управления:

Z=F(s0,Х).                           (1)

Сделаем несколько предположений.

1. Состояние sk системы в конце k-го шага зависит только предшествующего состояния sk-1 и управления на k-м шаге Хk. (и не зависит от предшествующих состояний и управлений). Это требование называется «отсутствием последействия». Сформулированное положение записывается в виде уравнений

sk=?k(sk-1,Хk), k=1,2,…,n,     (2)

которые называются уравнениями состояний.

2. Целевая функция (1) является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффективности k-го шага через

Zk=fk(sk-1,Хk) , k=1,2,…,n,     (3)

Тогда

Z=fk(sk-1,Хk).                  (4)

Задача пошаговой оптимизации (задача ДП) формулируется так: определить такое допустимое управление Х, переводящее систему S из состояния s0 в состояние , при котором целевая функция (4) принимает наибольшее (наименьшее) значение.

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

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

2. Целевая функция равна сумме целевых функций каждого шага.

З. Выбор управления на k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).

4. Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Хk (отсутствие последействия).

5. На каждом шаге управление Хk зависит от конечного числа управляющих переменных, а состояние sk – от конечного числа параметров.

Смысл замечаний станет ясным из рассмотренных ниже примеров.

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