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

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

В данном разделе рассматриваются две простейшие модели управления запасами [1, 29] с целью показать возможность применения метода динамического программирования с использованием множеств Парето и дополнительной отбраковки части бесперспективных паретовских точек по методу ветвей и границ с применением нового алгоритма спуска- подъёма..

Первая модель соответствует классической задаче управления запасами при производстве продукции. Именно для решения этой задачи был разработан метод динамического программирования. Задача ставится следующим образом [1].

Предприятие разрабатывает календарный план выпуска некоторых изделий на период, состоящий из N этапов (например лет, кварталов или месяцев).

Обозначения:

Xj- выпуск продукции в течение j-ro этапа; dj- заданный спрос на продукцию, постоянный в течение этапа, но изменяющийся от этапа к этапу, io- уровень запасов в начале планируемого периода, ij =ij-i+ Xj - dj - уровень запасов на конец j-ro периода (j=l,2,...,N). Cj(xj, ij-i) - суммарные затраты на производство и хранение запасов в j-ый период (этап). Количество изделий, выпускаемых в каждый из периодов ограничено возможностями предприятия, поэтому Xj=0,l,2,...,Xmax. Ограничены также и возможности хранения запасов, соответственно, ij=0,l,2,...,imax. Должно быть выполнено условие отсутствия дефицита ij-i+ Xj> dj для всех j.

Требуется так спланировать выпуск продукции, чтобы не допускать дефицита и обеспечить минимум суммарных затрат за все N этапов.

Неизвестными являются Xj, а целевая функция имеет вид

Предполагается, что производственные мощности достаточны для удовлетворения спроса и задача имеет решение.

Для решения этой задачи возможны различные варианты (схемы) реализации динамического программирования.

Под состоянием системы можно понимать суммарное количество произведённой продукции за все этапы, а можно понимать образовавшийся в конце этапа запас ij. В этом варианте все возможные состояния на всех этапах известны до расчёта, так как imax задан. Поэтому примем второй вариант.

В начальном состоянии запас io известен. После первого этапа для каждого из возможных ii определяем соответствующее ему xi=ii-io +di. Недопустимые xi и соответствующие им ii игнорируем. Для всех остальных xi и заданного io вычисляем и запоминаем затраты. На втором и последующих этапах выполняем эти действия поочерёдно для каждого из новых состояний ij, но при этом вместо одного io приходится рассматривать все состояния предыдущего этапа ij-i, то есть все переходы в состояние ij, и выбирать и запоминать тот переход, которому соответствует меньшее значение суммарных за все пройденные этапы затрат. Это обычная схема динамического программирования уже рассматривавшаяся ранее (разд. 3.2).

Возникает вопрос о возможности появления доминируемых состояний. Для ответа на этот вопрос нужно определиться какой двухкритериальной задачей заменяется исходная задача. С критерием затраты, всё ясно, нужен минимум. А с запасом? Больший запас означает увеличение затрат на его хранение по крайней мере на следующем этапе, но с другой стороны, он обеспечивает возможность уменьшить производство и сократить соответствующие затраты. Всё зависит от конкретных функций Cj(xj, ij-i). Например, имеем на некотором k-ом этапе два состояния А и В, запас ia> и целевая функция Са> Св. Пусть оптимальная траектория из состояния А до конца процесса начинается с перехода в некоторое состояние D, для чего требуется произвести ха единиц продукции. Соответственно затраты на этом этапе составят Ск(хдДд). Тогда для перехода в то же состояние D из состояния В требуется произвести хв=хд+(и- iB) единиц продукции с затратами СДхвДв). Затраты на все последующие шаги для обеих траекторий совпадают. Даже в случае Ск(хвдв)> Ск(хддд), но при Ск(хвДв) - Ск(хдДд)< Сд- Св состояние А и все его продолжения можно исключить. Поскольку оптимальная траектория из состояния А неизвестна, для отбраковки состояния А это неравенство должно выполняться для любого перехода из состояния А. При этом возможно, что переход в одно или несколько состояний возможен из состояния А, но невозможен из состояния В (например, переход в imax невозможен из-за ограничения по х„х). В таких случаях отбраковка состояния В недопустима.

Отметим, что здесь мы используем несколько иное очевидное правило отбраковки состояний, чем в разд. 5.2. Состояние с большим значением целевой функции можно обраковать, если в любое состояние следующего шага, достижимое из этого состояния, можно перейти из состояния с меньшим значением целевой функции, «не потеряв достигнутого преимущества». Такая ситуация возможна, если с течением времени затраты на производство единицы продукции уменьшаются, а затраты на её хранение растут, так что создание излишних запасов нерационально.

Фактически этот принцип отбраковки означает, что за один следующий шаг все пути из «худшего» состояния будут «обрезаны» и при обычной схеме динамического программирования. Ни о какой двухкритериальной задаче и паре- товских точках в этом случае речь не идёт.

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

Вторая модель соответствует задаче управления запасами, которая состоит в неоднократном получении и размещении заказов заданных объемов продукции (хранимых запасов) в определенные моменты времени. В рассмотрении данной задачи мы будем следовать [29], но интересовать нас будет возможность усовершенствования и постановки задачи и алгоритма её решения.

Стратегия управления запасами должна отвечать на 2 вопроса:

  • 1. Какое количество хранимого запаса следует заказать?
  • 2. Когда заказывать?

Ответ на первый вопрос определяет экономичный размер заказа путем минимизации следующей функции затрат:

Все эти величины должны быть выражены как функции искомого объема заказа и интервала времени между заказами.

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

Затраты на оформление заказа представляют собой постоянные расходы, связанные с его размещением (для изготовления продукции) на других производствах. Эти затраты не зависят от объема заказа.

Затраты на хранение запаса представляют собой затраты на содержание запаса на складе.

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

Ответ на второй вопрос (когда заказывать) зависит от типа системы управления запасами, с которой мы имеем дело. Если система предусматривает периодический контроль состояния запаса (неделя, месяц), момент поступления нового заказа совпадает с началом периода. Если же в системе предусмотрен непрерывный контроль состояния запаса, новые заказы размещаются тогда, когда уровень запаса опускается до заранее определенного значения, называемой точкой возобновления заказа. [29]

Простейшая модель управления запасами, которую мы будем рассматривать, характеризуются постоянным во времени спросом, мгновенным пополнением запаса и отсутствием дефицита. Сохраняем обозначения принятые в [29]:

у - объем заказа (количество единиц продукции);

D - интенсивность спроса (измеряется в единицах продукции на единицу времени);

to - продолжительность цикла заказа (измеряется во временных единицах).

Уровень запаса изменяется в соответствии с функцией, график которой показан на рис. 5.4, где использованы приведенные выше обозначения. Заказ объемом у единиц размещается и пополняется мгновенно, когда уровень запаса равен нулю. Затем запас расходуется равномерно с постоянной интенсивностью спроса D. Продолжительность цикла при этом:

единиц времени.

Средний уровень запаса определяется, как у/2 единиц.

Изменение запаса в классической модели

Рис. 5.4. Изменение запаса в классической модели

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

К - затраты на оформление, связанные с размещением заказа;

h - затраты на хранение (затраты на единицу складируемой продукции в единицу времени).

Суммарные затраты в единицу времени (обозначаются TCU1) можно представить как функцию от у в следующем виде: где

Z0 - затраты на оформление заказа в единицу времени;

Zx - затраты на хранение запаса в единицу времени.

так как средний запас равен у/2.

Используя равенство to=y/D,получаем

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

Это условие является также и достаточным, так как функция TCU(у) выпуклая.

Решение этого уравнения определяет объем заказа у*:

Оптимальная стратегия управления запасами для рассмотренной модели формируется следующим образом:

Заказывать у* единиц продукции через каждые to* единиц времени, где to* считается по формуле:

Аналогично в [29] рассматривается задача управления запасами п различных товаров, которые хранятся на складе ограниченной вместимости. Характер изменения запаса каждого товара в отдельности определяется функцией, показанной на рис.5.4. Предполагается, что дефицит отсутствует. Отличие от уже рас-

'TCU - сокращение от Total Const per Unit time, т.е. суммарные затраты в единицу времени.

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

Для i-ro товара (i = 1, 2, п) определяются следующие параметры:

Di - интенсивность спроса;

Ki - стоимость размещения заказа;

Ь - стоимость хранения единицы товара в единицу времени; yi - объем заказа;

ai - необходимое пространство для хранения единицы товара i-ro вида;

А - максимальное складское пространство.

При отсутствии дефицита математическая модель сформулированной задачи имеет следующий вид: Найти

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

Алгоритм решения этой задачи, приведенный в [29], состоит из трёх этапов: Этап 1. Вычисляются оптимальные объемы заказов без учета ограничения по вместимости склада:

Этап 2. Осуществляется проверка, удовлетворяют ли найденные значения у, * ограничению по вместимости склада. Если удовлетворяют, то вычисления заканчиваются, при этом значения у,* i = 1, 2, ..., п являются оптимальными. В противном случае следует перейти к этапу 3.

Этап 3. Ограничение по вместимости склада должно удовлетворяться в форме равенства. Используется метод множителей Лагранжа для определения оптимальных объемов заказа для задачи с ограничением.

Строится функция Лагранжа:

где Я<0 - множитель Лагранжа.

Поскольку функция Лагранжа является выпуклой, оптимальные значения у, и Я находятся из следующих уравнений, которые представляют собой необходимые условия экстремума функции Лагранжа:

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

Из первого уравнения следует, что

Полученная формула показывает, что у,* зависит от оптимального значения Я* множителя Лагранжа. Кроме того, при Я* = 0 значение у,* является решением задачи без ограничений.

Далее в [ 29 ] для определения Я* < 0 рекомендуется не вполне корректный приём, что по-видимому обусловлено погрешностью перевода: «последовательно уменьшаем Я на достаточно малую величину и используем ее в данной формуле для вычисления соответствующего значения у,*. Искомое значение Я* приводит к значениям у,* i = 1,2, ..., п, которые удовлетворяют ограничению по вместимости склада в форме равенства». Поскольку не приводятся правила выбора и изменения «достаточно малой» величины, то из этого предложения не следует как получить оптимальное решение с заданной точностью.

Фактически речь должна идти о решении одного уравнения с одним неизвестным X. Это уравнение получается, если в условие равенства нулю производной функции Лагранжа по X подставить все у*, выраженные через X. Полученное уравнение может быть решено с заданной точностью численным методом [8].

Предположение о непрерывности объёмов заказа товаров каждого вида (yi) не соответствует реальным условиям, так как товары поставляются партиями или штучно и трудно представить ответ к задаче например, в виде 5.75 автомобилей или 13.23 мебельных гарнитуров.

В этой связи рассмотрим как должна решаться задача в дискретной постановке.

Ограниченная вместимость склада А- это распределяемый ресурс, товары отдельных видов это потребители ресурса, ai- ресурс, потребляемый единицей товара i-ro вида, aiyi- ресурс, потребляемый при заказе yi. Объём заказа yi

принимает значения 1,2,___,[A/ai]. Здесь квадратные скобки означают целую

часть. Далее, TCU-аддитивная целевая функция yi (i=l,2,...,n). Задача может быть решена методом динамического программирования с использованием следующих понятий:

  • - очередной шаг (этап) переход к рассмотрению вариантов заказа товара i-ro вида;
  • - «состояние системы»- суммарный уже использованный ресурс;
  • - оценка состояния (значение целевой функции)- текущее значение TCU.

На первом шаге рассматриваются все возможные значения yi без превышения А и для каждого вычисляется TCU. Отбраковки нет.

На втором шаге рассматриваются все возможные варианты для заказов двух видов товаров и т.д. Если оказывается, что две комбинации требуют одно и то же количество ресурса, то остаётся та из них, для которой TCU минимальна. Задача аналогична задаче использования транспортных средств, но другая целевая функция и требуется найти минимум, а не максимум.

Оказывается, что для решения и этой задачи можно применить отбраковку непаретовских (доминируемых) состояний. Если одно состояние соответствует меньшему используемому ресурсу, чем другое, и равному или меньшему значению TCU, то оно является доминирующим, так как данную задачу можно рассматривать как задачу минимизации по двум критериям: TCU и используемый ресурс (требуемая вместимость склада). Характерно, что значения yi>yi где yi* вычисляются по формуле (5.6) можно не рассматривать вообще как доминируемые значением yi*, для которого меньше TCU и требуемый ресурс.

В результате решения задачи получаем паретовское множество точек, из которого нужно взять точку с меньшим значением TCU. Оптимальные значения неизвестных yi* определяются как обычно обратным разворотом по цепочке запоминаемых связей при переходе от этапа к этапу.

Нетрудно заметить, что задача в дискретной постановке с формальной точки зрения принципиально ничем не отличается от задачи распределения ресурса (5.1, 5.2), которую мы решили с помощью комбинированного метода (см. раздел 5.2) с использованием алгоритма спуска-подъёма для построения двусторонних оценок оптимума.

Она может решаться по той же компьютерной программе, если предварительно вычислить fi=aiyi и gi =KjDj/yi +hiyi/2 для всех дискретных значений каждого yi (i=l,2,...,n).

Решение задачи в дискретной постановке существенно отличается от решения, получаемого округлением значений переменных, полученных при решении непрерывной задачи по методу множителей Лагранжа. Эти отличия не носят фатального характера, как в примерах, приводимых при анализе особенностей дискретных задач (см. раздел 2.1), но отличия по целевой функции достигают 15% в зависимости от конкретных данных. Это является достаточным основанием для практического применения метода динамического программирования с использованием множеств Парето для решения рассмотренной и более сложных задач управления запасами. При большом количестве различных товаров и объёме склада для сокращения времени счёта можно рекомендовать комбинированный алгоритм.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >