Постановка задачи динамического программирования

Краткие теоретические сведения

Постановка задачи динамического программирования

Принцип оптимальности и уравнения Беллмана

Постановка задачи динамического программирования

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

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

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

Приведем общую постановку задачи динамического программирования.

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

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

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

Пусть Х (X₁, Х₂,.,, Хп) - управление, переводящее систему S из состояния So в состояние S_i. Обозначим через S_k состояние сис­темы после k-ro.шага управления. Получаем последовательность состояний S₀, S₁,,.., S_k-1, S_k, …, S_n-1, S_n=Si. Изобразим каждое состояние окружностями(рис. 13.1).

Рисунок 13.1 – Процесс управляемого изменения состояний системы

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

Z = F (S₀, X). (13.1)

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

1. Состояние S_k системы в конце k-ro шага зависит только от предшествующего состояния Sk-1 и управления на k-м шаге X_k (и не зависит от предшествующих состояний и управлений). Это требование называется " отсутствием последействия": Сформулированное предположение записывается в виде уравнений

(13.2.)

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

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

. (13.3.)

Тогда

. (13.4)

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