![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Динамическое программирование. Задача об управлении запасами.
Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами: 0. Задача 1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: 2. Вывод уравнения Беллмана. 3. Решение семейства задач. 3.1. Находим более простые задачи и решаем их. 3.2 Находим значение функции Беллмана B(t) и Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи. Задача об управлении запасами: Пусть имеется некоторая система снабжения (склад, оптовая база и т. п.), планирующая свою работу на n периодов. Введем обозначения: yk — остаток запаса после (k -1)-го периода; dk — заранее известный суммарный спрос в k -м периоде; хk — заказ (поставка от производителя) в k -м периоде; сk (хk) —затраты на выполнение заказа объема xk в k -м периоде; sk (ξ k) — затраты на хранение запаса объема ξ 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 (ξ) и условных оптимальных управлений
|