4.2.5. Динамические задачи управления запасами

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

Если рассматривается функционирование системы за n периодов, причем спрос нестационарный, то имеем динамические модели задач управления запасами. Такие задачи, как правило, не допускают аналитического решения, однако оптимальную стратегию управления можно найти, применив метод динамического программирования.

1. Пусть рассматривается задача управления запасами на n периодов, когда спрос за -й период детерминированный и определяется величиной,.

Введем такие обозначения: - остаток запаса от ()-го периода;- спрос в-м периоде ();- запас, создаваемый в-м периоде (или заказ на поставку).

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

Тогда суммарные расходы системы по производству и хранению избыточных запасов за периодов составляют

(7.4.1)

при ограничениях

, .

Требуется найти такие , для которых (7.4.1) обращается в минимум. Чтобы минимизировать, воспользуемся метдом динамического программирования. Последовательно будем минимизировать затраты на 1, 2, .,периодов при условии, что на начало ()-го периода есть избыточный запас. Определим последовательность функций состояния

(7.4.2)

при ограничении

.                             (7.4.3)

Тогда основное рекуррентное соотношение ДП запишется так:

(7.4.4)

где

.

На первом шаге (при ) получим:

при ограничении

.

Вычислив последовательно ,, .,, на последнем шаге, приняв, найдеми. Оптимальные значениянаходим дальше последовательно по формуле

.                          (7.4.5)

2. Рассмотрим частный случай, значительно упрощающий вычислительную схему ДП. Предположим, что:

все функции вогнуты по переменным;

функции затрат на хранение запасов линейны, то есть

.

Тогда общее выражение для функции затрат будет иметь вид

(7.4.6)

при ограничении

, .                          (7.4.7)

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

Рассмотрим процедуру решения. Поскольку нужно найти минимум суммы вогнутых функций на выпуклом множестве, то оптимальным решением будет одна из крайних точек допустимого множества решений, определяемого ограничением (7.4.7).

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

.                              (7.4.8)

Условие (7.4.8) эквивалентно следующей паре условий:

(7.4.9)

Поясним смысл условий (7.4.8), (7.4.9). Заказ на изготовление (поставку) новой партии не поступает, если в начале периодаимелся ненулевой запас (), и наоборот, если в начале периодазапас, то делается заказ на поставку. Отсюда следует, что= 0, или=, или=и т.д., то естьоптимальный размер заказа равен спросу за целое число периодов.

Предположим, что . Тогда решаем задачу (7.4.6) в прямом направлении. Пусть- минимальные затраты запериодов, если запас на начало ()-го периода равен. Основное рекурентне соотношение ДП для этой задачи имеет вид

(7.4.10)

при ограничении

, .

В рассматриваемом случае, поскольку , то минимум в (7.4.10) в силу вогнутости функциидостигается в одной из крайних точекили.

Поэтому

(7.4.11)

Аналогично

(7.4.12)

Выписав выражения, аналогичные (7.4.12), для ,, .,и подставив их в (7.4.12), (7.4.11), получим в результате

.                              (7.4.13)

Здесь

(7.4.14)

где - затраты запериодов при условии, что последний заказ сделан в начале периода.

3. Рассмотрим частный случай функции производственных затрат на выполнение заказа . Пусть

(7.4.15)

где - фиксированные затраты на заказ;

(7.4.16)

Тогда

В этом случае задача упрощается и сводится к задаче ЛП:

минимизировать           (7.4.17)

при ограничениях

.              (7.4.18)

Используя выражения (7.4.15) - (7.4.17) и подставляя их в (7.4.14), получаем, с учетом , соотношение

(7.4.19)

.                           (7.4.20)

Дальнейшее упрощение в вычислительной схеме можно получить, если учесть следующее обстоятельство. Если при вычислении оказалось, что заказ, с помощью которого удовлетворялся спрос ()-го периода, должен поступить в начале периода, то и заказ, удовлетворяющий спрос-го периода в оптимальном решении, должен поступить также не ранее периода. Следовательно, при вычислениидостаточно рассматривать

.                          (7.4.21)

Пример 7.3. Предприятие планирует поставку своей продукции на 7 месяцев в таких объемах: = 90 шт.,= 125 шт.,= 140,= 100,= 45,= 60,= 130. Затраты на хранение единицы продукции в течение месяца составляют= 2 грн.мес.;. Затраты на наладку оборудования (станков) для производства партии составляют= 300 грн.;. Причем наладка делается лишь в те месяцы, когда выпускается партия. Временем на выполнение заказа пренебрегаем. Требуется определить месяцы, когда производятся заказы, а также оптимальные размеры партий,.

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

Требуется

минимизировать    ,

где =1, еслии=0, если,

при ограничениях

= 90,

, .

Используя соотношения (7.4.19), (7.4.21), имеем:

                          k = 1      ;

k = 2     ;.

Таким образом, только при двух периодах выгоднее выполнять лишь один заказ в первом периоде:

k = 3

; i = 3.

Результаты остальных вычислений приведены в табл. 7.10.

Таблица 7.10

Период k			1	2		3		4	5		6		7
Спрос dk			90	125		140		100	45		60		130
	i = 1	300		550*	1100
	2			600	880
gk(i)	3				850*		1050*		1230*	1590
	4						1150		1240	1480
	5								1350	1470*		1990
	6									1530		1790
	7											1770*
Λk(0)			300	550		850		1050	1230		1470		1770
			1	1		1		1	1		1		1
V						3		3	3		3		3
											5		5
													7

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

Покажем, как последовательно с табл. 7.10 определить периоды выполнения заказов при . Минимум в столбцедостигается при(= 1770).

Поэтому переходим к задаче при . Минимум в шестом столбце достигается при. Следовательно, последний заказ выполнялся в пятом месяце. Тогда переходим ки находим, что минимум придостигается при. Тогда переходим ки сразу находим, что минимум в столбцедостигается при. Таким образом, номера месяцев, когда заказ выполняются, следующие:1, 3, 5, 7.

Оптимальное решение в соответствии с табл. 7.10 таково:

;

;

.