Динамическое программирование. Задача об управлении запасами.

Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами:

0. Задача состоит в оптимизации функции f на множество M.

1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: , каждая из которых состоит в поиске оптимального элемента с учетом ограничений:

2. Вывод уравнения Беллмана. – решение задачи оптимизации , т.е. то значение x, при котором целевая функция принимает значение – функция Беллмана. А уравнением Беллмана называется уравнение, в которое входит функция Беллмана и значение – оптимальное значение.

3. Решение семейства задач.

3.1. Находим более простые задачи и решаем их.

3.2 Находим значение функции Беллмана B(t) и , найденные на предыдущем этапе и подставляем в уравнение Беллмана. Получаем новое решение.

Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи.

Задача об управлении запасами:

Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на n периодов. Введем обозначения: y_k — остаток запаса после (k -1)-го периода; d_k — заранее известный суммарный спрос в k -м периоде; х_k — заказ (поставка от производителя) в k -м периоде; с_k (х_k) —затраты на выполнение заказа объема x_k в k -м периоде; s_k (ξ _k) — затраты на хранение запаса объема ξ _k в k -м периоде.

После получения поставки и удовлетворения спроса объем товара, подлежащего хранению в период k, составит ξ _k = y_k + х_k - d_k. Учитывая смысл параметра y_k, можно записать соотношение:

Расходы на получение и хранение товара в период k описываются функцией

Планом задачи можно считать вектор х = (х ₁, х ₂,..., х_n), компонентами которого являются последовательные заказы в течение рассматриваемого промежутка времени. Соотношение между запасами (5.24) в сочетании с некоторым начальным условием связывает состояния системы с выбранным планом и позволяет выразить суммарные расходы за все п периодов функционирования управляемой системы снабжения в форме аддитивной целевой функции:

В качестве начального условия используем требование о сохранении после завершения управления заданного количества товара y_{n +1}, а именно

При решении поставленной задачи методом динамического программирования в качестве функции состояния управляемой системы Λ _k (ξ) логично взять минимальный объем затрат, возникающих за первые k периодов при условии, что в k -й период имеется запас ξ. Тогда можно записать основное рекуррентное соотношение

поскольку

Система рекуррентных соотношений (5.27)-(5.28) позволяет найти последовательность функций состояния Λ ₁(ξ), Λ ₂(ξ), …, Λ _n (ξ) и условных оптимальных управлений ₁(ξ), ₂(ξ), …, _n (ξ). На n -м шаге с помощью начального условия (5.26) можно определить х*_n = _n (y_{n +1}). Остальные значения оптимальных управлений x*_k определяются по формуле: