Динамическое программирование: 3 модели управления запасами

1.Теория

Задачи управления запасами возникают, когда необходимо сделать запас материальных ресурсов или предметов потребления с целью удовлетворения спроса на заданном интервале времени. Любая модель должна ответить на 2 вопроса: 1) какое количество продукции заказывать (ответ на? обычно получается из задачи минимизации суммарных затрат в выбранную ед.времени); 2) когда заказывать (ответ на? зависит от типа контроля над уровнем запаса).

Контроль бывает периодическим: осущ-ние контроля в конце какого-то периода t(t запаса совпадает с одним из моментов контроля) и непрерывным( определяется точка заказа – объем товара на складе, при котором нужно сделать новый заказ).

Модели делятся:

1) Детерминированные (все параметры – неслучайные величины):

- статические: интенсивность потребления остается неизменной во времени

- динамические: спрос известен достоверно, но изменяется в зависимости от времени

2) Вероятностные (часть параметров – случайные величины):

- стационарные (функция плотности вероятности спроса неизменна во времени)

- не стационарные (функция плотности вероятности спроса изменяется во времени)

Затраты на приобретение(С) становятся важным фактором, когда цена единицы продукции зависит от размера заказа, что обычно выражается в виде оптовых скидок в тех случаях, когда цена единицы продукции убывает с возрастанием размера заказа.

Затраты на оформление заказа(К) представляют собой постоянные расходы, связанные с его размещением. При удовлетворении спроса в течение заданного периода времени путем размещения более мелких заказов (более часто) затраты возрастают по сравнению со случаем, когда спрос удовлетворяется посредством размещения более крупных заказов (и, следовательно реже).

Затраты на хранение запаса(Н), которые представляют собой расходы на содержание запаса на складе (затраты на переработку, амортизационные расходы, эксплуатационные расходы) обычно возрастают с увеличением уровня запаса.

Потери от дефицита представляют собой расходы, обусловленные отсутствием запаса необходимой продукции.

Оптимальный уровень запаса соответствует минимуму суммарных затрат.

 

- количество ед. товаров в ед. времени

y – объем заказа. Не допускается дефицит.

К – стоимость оформления заказа

h – стоимость хранения ед. товара в ед. времени

- цена, если объем закупаемого товара меньше q

- цена, если объем закупаемого товара .

q – размер заказа, при превышении которого предоставляется скидка.

-время выполнения заказа

 

2.Однопродуктовая статическая модель без дефицита

Эту модель можно интерпретировать как модель управления запасами в магазине. Руководство магазина закупает товар у оптовиков по цене c₁ за единицу товара, если объем закупаемой партии y < q. Если у>= q, делается скидка и цена единицы товара становится равной c₂ < c₁. Затраты при закупке товара состоят из двух величин: условно постоянной величины:стоимостью оформления заказа(K). Переменной величины ¾ стоимости закупаемой партии равной c(y)y. Здесь c(y) равно c₁,если y < q и равно c₂, если y ³ q. В рассматриваемой модели предполагается, что в магазине спрос на товар в единицу времени является величиной постоянной и принимает значение равное b.

Магазин также, несет расходы по хранению товара на собственном складе. В каждую единицу времени (час, день ит.д.) эти расходы составляют величину h за каждую единицу товара, находящуюся на складе в эту единицу времени.

После оформления заказа товар поступает на склад магазина через интервал времени длиной t^*.

Руководству нужно определить, какое количество y товара заказывать, и точку заказа R с тем, чтобы суммарные затраты в единицу времени на закупку продаваемого товара и хранение товара на складе было минимальным.

Затраты будут состоять из суммы трех величин: затрат на приобретение продаваемого товара, затрат на оформление заказа, затрат на хранение товара на собственном складе.

ри минимальных затратах новая партия поступает на склад магазина в момент, когда весь товар израсходован. Следовательно, максимальное количество товара на складе равно y в момент поставки. График зависимости количества товара на складе от времени показан на рисунке 2. Ось x ¾ ось времени, а ось y ¾ значение величины запаса на складе.

Вычислим средние затраты в единицу времени S(y). Отметим, что это можно сделать для одного периода [0; D1], так как на остальных периодах все вычисления будут полностью совпадать.

В момент t=0 на складе имеется максимальное количество запаса равное y. В единицу времени расходуется b единиц запаса, следовательно, весь запас будет израсходован за время

t = y/b

 

(1)

у

 

в

c

А F

R

0 E G D1 D2 D3

За рассматриваемое время заказ будет оформляться один раз, а расходы на оформление заказа в единицу времени составят K/ t = Kb/y. (2)

Так как величина запаса будет различной в каждую единицу времени, то и расходы по хранению будут различны. Проведем в D0В D1 среднюю линию AC и опустим перпендикуляр CE.В силу равенства треугольников DABC и DECD1, величина запаса в любой точке левее точки E больше величины 0A= y/2 настолько, насколько меньше этой величины в точке, симметричной относительно E. Поэтому на всем отрезке [0; D1] можно считать, что в среднем хранится величина y/2. Таким образом, для величины средних затрат в единицу времени получаем следующее выражение S₁(y)= c₁β + Kb/y + hy/2, (3)

если y<q и S₂(y)= c₂β + Kb/y + hy/2 (4) в противном случае. Здесь первое слагаемое выражает затраты на закупку товара продаваемого магазином в единицу времени. Второе ― затраты на оформление заказа отнесенные к единице времени. Третье ― средние затраты на хранение запаса в единицу времени. Так как первое слагаемое в зависимости от y меняется один раз на постоянную величину, то минимум у этих функций достигается в одной точке.

Найдем минимум этого выражения по величине заказа y. Для этого вычислим производную и приравняем ее нулю. - Kb/y² + h/2 = 0. i=1,2 (5)

Из равенства (5) получаем формулу экономичного размера заказа Уилсона y^*= . (6)

Если бы цена на товар была постоянной (не зависела от объема закупаемой партии), то величина y^* была бы оптимальной. Действительно, вторая производная функции S_i(y) больше нуля в области y> 0. Следовательно, функция S_i(y) выпуклая в этой области, а точка y^* доставляет минимум этой функции.

В случае разрыва цен величина оптимальной партии y_opt зависит от величины q.

S ₁(q)

Если y^* ³ q, тогда y_opt = y^*. Так как в этом случае при закупке партии в объеме y^* будет получена скидка и суммарные затраты в единицу времени составят наименьшую из всех величину S₂(y^*). Пусть y^* < q, тогда y_opt = q, если q £ y₁. Здесь y₁ ¾ больший корень уравнения S₁(y^*) = S₂(y). (7)

Если же q > y₁, то y_opt = y^*. Таким образом, если q £ y₁, то выгодно воспользоваться скидкой, в противном случае ¾ нет (смотри рис. 2).

Пусть оптимальный объем заказываемой партии определен и равен y_opt. Точку заказа R определяется из соотношений R = b´t^*, t^* < t; R = b´(t^*-m´t),

где m ¾ целая часть от деления t^* на t, а t = y_opt /b. Так на рис 1 величина t^* равна длине отрезка [ G; D ₃]. При этом m =2, а величина R показана на оси y.

 

3.Однопродуктовая статическая модель с дефицитом

В отличие от предыдущего пункта в данной модели предполагается, что цена на товар величина постоянная. Допускается дефицит. Как и ранее товар поставляется партиями через некоторые промежутки времени t. Интервал [0;C] длиной t делится на два (смотри рис.3). В течение первого интервала [0;A) длительностью t₁ непрерывный спрос интенсивностью b удовлетворяется из запаса, имеющегося на складе. В течение второго интервала [A;C] длительностью t₂ спрос не удовлетворяется. Накопленный неудовлетворенный спрос покрывается немедленно при поступлении следующей партии товара. За несвоевременную поставку товара взимается штраф.

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

 

y K - стоимость оформления заказа;

t*- время выполнения заказа;

B h - стоимость хранения единицы товара в единицу времени;

t - длина интервала [0, C] между поставками;

H-суммарные затраты на периоде между поставками ([0;C]);

А С t₁ - длина интервала [0, A];

t₂ - длина интервала [A, C].

 

 

D E

 

Обозначим: y - объем заказываемой партии (длина отрезка [D;B]); q - максимальное количество товара на складе (длина отрезка [0;B]). В рассматриваемой задаче нужно выбрать два параметра: y и q. Цель – минимизация суммарных затрат в единицу времени.

Можно найти суммарные затраты на периоде от момента поставки товара до следующего момента поставки. Затем разделить их на длину периода и получить суммарные затраты в единицу времени.

Выразим величины t₁ и t₂ через величину t. Из подобия треугольников DDBE, D0BC и DACE получаем: . Следовательно, ; (8)

На рассматриваемом интервале [0, C] только в течение интервала [0, A] на складе имеется запас товара и, следовательно, затраты по хранению товара. Аналогично, только на интервале [A, C] имеется дефицит и затраты связанные с ним. Как и в предыдущей задаче, средний уровень запаса на складе на интервале [0, A] равен q/2. Средний уровень дефицита в течение интервала [A, C] равен (y-q)/2. Тогда затраты на хранение и потери от дефицита на отрезке [0, C] будут, соответственно, следующие:

, .

Суммарные затраты на отрезке [0, C] будут состоять из этих затрат и затрат на оформление заказа. Заменяя t₁ и t₂ из соотношения (8), получим . (9)

Найдем суммарные затраты в единицу времени, разделив величину H на длину рассматриваемого интервала t (как и в предыдущей задаче t = y/b).

. (10)

Запишем необходимое условие минимума.

; .

Разрешая данные уравнения относительно y и q, получаем:

; . (11)

При этом длина периода и минимальные суммарные затраты будут задаваться соотношениями

; . (12)

Отметим, что при этом ,

т.е. отношение стоимостей хранения и стоимости дефицита единицы товара в единицу времени обратно пропорционально отношению максимального объема запаса и максимального объема дефицита.

Найдем теперь точку заказа R. В отличие от предыдущей модели в момент заказа на складе может либо быть некоторое количество товара, либо накоплен некоторый объем дефицита. Поэтому под точкой заказа будем понимать объем либо товара, либо дефицита при котором нужно делать новый заказ. Так же как и в модели без дефицита, нужно для оптимального объема заказа y^* определить величину t^* (смотри (12)). Затем найти число m равное целой части от деления t^* на t^*и число t_* = t^* - m´ t^*. Тогда точку заказа можно найти из соотношения

(13)

Первая строчка соответствует точке заказа равной объему товара, при котором нужно делать новый заказ, а вторая объему дефицита.

 

4.Многопродукт. статич. модель без дефицита (с ограничением на емкость складских помещений)

Эта модель предназначена для систем управления запасами, включающие n(>1) видов продукции, которая хранится на одном складе ограниченной площади. Данное условие определяет взаимосвязь между различными видами продукции может быть включено в модель как ограничение.

Пусть А – максимально допустимая площадь складского помещения для n видов продукции; предположим, что площадь, необходимая для хранения единицы продукции i -го вида, то ограничение на потребность в складском помещении принимают вид .

Допустим, что запас продукции каждого вида пополняется мгновенно и скидки цен отсутствуют. Предположим далее, что дефицит не допускается. Пусть b_i, K_i и h_i – интенсивность спроса, затраты на оформление заказа и затраты на хранение единицы продукции в единицу времени для i -го вида продукции соответственно. Общие затраты по продукции каждого вида, по существу, будут теми же, что и в случае эквивалентной однопродуктовой модели. Т.о., рассматриваемая задача имеет вид →MIN при для всех i.

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

Ограничение действует, если оно не выполняется для значений . В таком случае нужно найти новое оптимальное значение y_i, удовлетворяющее ограничению на площадь склада в виде равенства. Этот результат достигается построением функции Лагранжа вида , где l(<0) – множитель Лагранжа.

Оптимальные значения y_i и l можно найти, приравняв нулю соответствующие частные производные, что дает

, Из второго уравнения следует, что значение должно удовлетворять ограничению на площадь склада в виде равенства. Из первого уравнения следует, что .

Заметим, что зависит от оптимального значения l^* множителя l. Кроме того, при l^* =0 значение является решением задачи без ограничения.