Динамическая модель размера партии

Модель динамического размера партии в теории запасов представляет собой обобщение модели экономического количества заказа , которая учитывает, что спрос на продукт меняется со временем. Модель была представлена Харви М. Вагнером и Томсоном М. Уитином в 1958 году. ^[1]^[2]

Проблема с настройкой

У нас есть прогноз спроса на продукцию $d t$ на соответствующем временном горизонте t=1,2,...,N (например, мы можем знать, сколько виджетов потребуется каждую неделю в течение следующих 52 недель). t t $на единицу$ Для каждого заказа возникают затраты на настройку st t, а также стоимость хранения запасов также $может меняться$ со $временем,$ если $это товара за период (s t$ необходимо). Проблема заключается в том, сколько единиц $x t$ нужно заказать сейчас, чтобы минимизировать сумму затрат на установку и стоимость запасов. Обозначим инвентарь :

$I=I_{0}+\sum _{j=1}^{t-1}x_{j}-\sum _{j=1}^{t-1}d_{j}\geq 0$

Функциональное уравнение, представляющее политику минимальных затрат:

$f_{t}(I)={\underset {x_{t}\geq 0 \atop I+x_{t}\geq d_{t}}{\min }}\left[i_{t-1}I+H(x_{t})s_{t}+f_{t+1}\left(I+x_{t}-d_{t}\right)\right]$

Где H() — ступенчатая функция Хевисайда . Вагнер и Уитин ^[1] доказал следующие четыре теоремы:

Существует оптимальная программа такая, что I $x t$ =0; ∀т
Существует оптимальная программа такая, что ∀t: либо $x t$ =0, либо $x_{t}=\textstyle \sum _{j=t}^{k}d_{j}$ для некоторого k (t≤k≤N)
Существует оптимальная программа такая, что если $d t*$ удовлетворяется некоторыми $x t**$ , t**<t*, то $d t$ , t=t**+1,...,t*-1 также является удовлетворен $x t**$
Учитывая, что I = 0 для периода t, оптимально рассматривать периоды с 1 по t - 1 отдельно.

Теорема о горизонте планирования

Прецедентные теоремы используются при доказательстве теоремы о горизонте планирования. ^[1] Позволять

$F(t)=\min \left[{{\underset {1\leq j<t}{\min }}\left[s_{j}+\sum _{h=j}^{t-1}\sum _{k=h+1}^{t}i_{h}d_{k}+F(j-1)\right] \atop s_{t}+F(t-1)}\right]$

обозначим программу минимальных затрат для периодов от 1 до t. Если в периоде t* минимум F(t) возникает при j = t** ≤ t*, то в периодах t > t* достаточно рассматривать только t** ≤ j ≤ t. В частности, если t* = t**, то достаточно рассматривать программы такие, что $x t*$ > 0.

Алгоритм

Вагнер и Уитин дали алгоритм поиска оптимального решения методом динамического программирования . ^[1] Начните с t*=1:

Рассмотрим политику заказа в период t**, t** = 1, 2, ..., t* и удовлетворения потребностей $d t$ , t = t**, t** + 1, ... , t* , по этому заказу
Добавьте H( $x t**$ ) $s t**$ + $i t**$ $I t**$ к затратам на оптимальное действие для периодов от 1 до t**-1, определенным на предыдущей итерации алгоритма.
Из этих альтернатив t* выберите политику минимальных затрат для периодов с 1 по t*.
Перейдите к периоду t*+1 (или остановитесь, если t*=N)

Поскольку некоторые считали этот метод слишком сложным , ряд авторов также разработали приближенные эвристики (например, эвристику Серебряной муки). ^[3]) по поводу проблемы.

См. также

Бесконечная скорость заполнения производимой детали: экономичный объем заказа
Постоянная скорость заполнения производимой детали: экономичный объем производства.
Спрос случайен: классическая модель Newsvendor
Несколько продуктов, произведенных на одной машине: проблема экономичного планирования партий
Пункт повторного заказа
Базовая модель

Ссылки

^ Jump up to: ^а ^б ^с ^д Харви М. Вагнер и Томсон М. Уитин , «Динамическая версия экономической модели размера лота», Management Science, Vol. 5, стр. 89–96, 1958 г.
^ Вагельманс, Альберт , Стэн Ван Хозель и Антон Колен . « Определение экономического размера лота: алгоритм O (n log n), работающий за линейное время в случае Вагнера-Уитина ». Исследование операций 40.1-Дополнение - 1 (1992): S145-S156.
^ EA Silver, HC Meal, Эвристика для выбора размера партии для случая детерминированной, изменяющейся во времени скорости спроса и дискретных возможностей пополнения, Управление производством и запасами, 1973

Дальнейшее чтение

Ли, Чунг-Йи, Сила Четинкая и Альберт П.М. Вагельманс . « Динамическая модель определения размера партии с временными окнами спроса ». Наука управления 47.10 (2001): 1384–1395.
Федергрюэн, Ави и Михал Цур. «Простой прямой алгоритм для решения общих динамических моделей определения размера лота с n периодами за 0 (n log n) или 0 (n) времени». Наука управления 37.8 (1991): 909–925.
Янс, Раф и Зегер Дегрейв. «Метаэвристика для динамического определения размера партии: обзор и сравнение подходов к решению». Европейский журнал операционных исследований 177.3 (2007): 1855–1875.
Х. М. Вагнер и Т. Уитин, «Динамическая версия экономической модели размера партии», Management Science , Vol. 5, стр. 89–96, 1958 г.
Х. М. Вагнер : «Комментарии к динамической версии экономической модели размера партии», Management Science , Vol. 50 Приложение № 12, декабрь 2004 г.

Внешние ссылки

Решение проблемы определения размера партии с использованием алгоритма Вагнера-Уитина
Модель динамического размера лота
Python-реализация алгоритма Вагнера-Уитина.

[WW1958-1] Jump up to: ^а ^б ^с ^д Харви М. Вагнер и Томсон М. Уитин , «Динамическая версия экономической модели размера лота», Management Science, Vol. 5, стр. 89–96, 1958 г.

[2] Вагельманс, Альберт , Стэн Ван Хозель и Антон Колен . « Определение экономического размера лота: алгоритм O (n log n), работающий за линейное время в случае Вагнера-Уитина ». Исследование операций 40.1-Дополнение - 1 (1992): S145-S156.

[3] EA Silver, HC Meal, Эвристика для выбора размера партии для случая детерминированной, изменяющейся во времени скорости спроса и дискретных возможностей пополнения, Управление производством и запасами, 1973

[1]

[2]

[3]