Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

поскольку

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


 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.