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

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

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

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

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

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

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

динамические задачи управления запасами - student2.ru (7.4.1)

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

динамические задачи управления запасами - student2.ru , динамические задачи управления запасами - student2.ru .

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

динамические задачи управления запасами - student2.ru (7.4.2)

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

динамические задачи управления запасами - student2.ru . (7.4.3)

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

динамические задачи управления запасами - student2.ru (7.4.4)

где

динамические задачи управления запасами - student2.ru .

На первом шаге (при динамические задачи управления запасами - student2.ru ) получим:

динамические задачи управления запасами - student2.ru

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

динамические задачи управления запасами - student2.ru .

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

динамические задачи управления запасами - student2.ru . (7.4.5)

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

все функции динамические задачи управления запасами - student2.ru вогнуты по переменным динамические задачи управления запасами - student2.ru ;

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

динамические задачи управления запасами - student2.ru .

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

динамические задачи управления запасами - student2.ru (7.4.6)

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

динамические задачи управления запасами - student2.ru , динамические задачи управления запасами - student2.ru . (7.4.7)

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

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

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

динамические задачи управления запасами - student2.ru . (7.4.8)

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

динамические задачи управления запасами - student2.ru (7.4.9)

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

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

динамические задачи управления запасами - student2.ru (7.4.10)

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

динамические задачи управления запасами - student2.ru , динамические задачи управления запасами - student2.ru .

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

Поэтому

динамические задачи управления запасами - student2.ru (7.4.11)

Аналогично

динамические задачи управления запасами - student2.ru (7.4.12)

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

динамические задачи управления запасами - student2.ru . (7.4.13)

Здесь

динамические задачи управления запасами - student2.ru (7.4.14)

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

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

динамические задачи управления запасами - student2.ru (7.4.15)

где динамические задачи управления запасами - student2.ru - фиксированные затраты на заказ;

динамические задачи управления запасами - student2.ru (7.4.16)

Тогда

динамические задачи управления запасами - student2.ru

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

минимизировать динамические задачи управления запасами - student2.ru (7.4.17)

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

динамические задачи управления запасами - student2.ru . (7.4.18)

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

динамические задачи управления запасами - student2.ru (7.4.19)

динамические задачи управления запасами - student2.ru . (7.4.20)

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

динамические задачи управления запасами - student2.ru . (7.4.21)

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

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

Требуется

минимизировать динамические задачи управления запасами - student2.ru ,

где динамические задачи управления запасами - student2.ru =1, если динамические задачи управления запасами - student2.ru и динамические задачи управления запасами - student2.ru =0, если динамические задачи управления запасами - student2.ru ,

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

динамические задачи управления запасами - student2.ru = 90,

динамические задачи управления запасами - student2.ru , динамические задачи управления запасами - student2.ru .

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

k = 1 динамические задачи управления запасами - student2.ru ;

k = 2 динамические задачи управления запасами - student2.ru ; динамические задачи управления запасами - student2.ru .

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

k = 3

динамические задачи управления запасами - student2.ru ; i = 3.

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

Таблица 7.10

Период k
Спрос dk
  i = 1 550*        
           
gk(i)     850* 1050* 1230*  
         
          1470*
           
              1770*
Λk(0)
 
V    
           
             

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

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

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

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

динамические задачи управления запасами - student2.ru ;

динамические задачи управления запасами - student2.ru ;

динамические задачи управления запасами - student2.ru .


Наши рекомендации