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

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

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом (1920-1984) для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953г. он уточнил это определение. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE[1]. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования.

Модели ДП применяются:

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

– при распределении дефицитных капитальных вложений между возможными направлениями их использования,

– при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию,

– при составлении календарных планов ремонта оборудования и его замены и т.п.

Сформулируем общую постановку задачи ДП.

Рассматривается управляемый процесс, в результате которого система S переводится из начального состояния s₀ в конечное состояние s_n. Предполагается, что управление X можно разбить на n шагов и принимать решение на каждом шаге. Следовательно, управление представляет собой совокупность n пошаговых управлений: X=(X₁, X₂,…X_n). Последовательность состояний системы s₀, s₁, …, s_k-1, s_k, s_k+1,… s_n можно изобразить в виде схемы:

Целевая функция (показатель эффективности системы) зависит как от начального состояния системы s₀, так и от управления X:

(4.1)

Необходимо определить такое допустимое управление X, переводящее систему S переводится из состояния s₀ в состояние s_n, при котором целевая функция (4.1) принимает максимальное (минимальное) значение.

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

(4.2)

Уравнения (4.2) называют уравнениями состояний. Они выражают «отсутствие последействия», т.е. независимость состояния системы в конце каждого шага от состояний и управлений на всех предыдущих шагах.

Целевую функцию считают аддитивной функцией от показателя эффективности каждого шага:

(4.3)

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

(4.4)

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

Дата добавления: 2014-01-06