| Number of periods N= | Current period^ | ||||||||||||||
| Period | |||||||||||||||
| c(1to4)- | Optimum Solution | ||||||||||||||
| K(1 to 4) - | Summary | ||||||||||||||
| h{1to4)- | X | f | z | X | f | z | |||||||||
| D(1 to 4) - | Current | period 1 | |||||||||||||
| Are xl values co<'r ^' | " ^ | I ИИ | | optimum | 220, 61 | |||||||||||
| 1 Period 0 | z1- | Period 1 | ^298~ 87" | ||||||||||||
| 1f0 | C1(z1)= | f1 I z1 | 116" | ||||||||||||
| x2= | 22(Г" | 183u | |||||||||||||
| x2= | M11111 | 298 Г 87 | |||||||||||||
| x2= | " 116 | 111111' | (111111 | 568 i 177 | |||||||||||
| x2= | " 183 | 1111111_, | 769 1 244 | - | — |
Рис. 11.11. Вычисления в Excel первого периода для задачи из примера 11.3.3
УПРАЖНЕНИЯ 11.3.4
1. С помощью шаблона chllWagnerWhitin.xls решите задачу из примера 11.3.3, предполагая, что начальный запас — 80 единиц.
2. Решите следующую 10-этапную детерминированную задачу управления запасами, предполагая, что исходный запас — 50 единиц.
Глава 11. Детерминированные модели управления запасами
| Этап / | Спрос, D, | Стоимость единицы | Затраты на хранение | Затраты на оформление |
| (единицы) | продукции (долл.) | единицы продукции (долл.) | заказа (долл.) | |
3. Определите оптимальную стратегию управления запасами в следующей 5-этапной задаче. Стоимость единицы продукции равна 10 долл. для любого периода. Стоимость хранения единицы продукции на протяжении периода равна 1 долл.
| Этап /' | Спрос, D, (единицы) | Затраты на оформление заказа, К, (долл.) | |
| Определите оптимальную стратегию управления запасами в следующей 6-этап- | |||
| ной задаче. Стоимость единицы продукции равна 2 долл. для любого периода. | |||
| Этап /' | О, (единицы) | К, (долл.) | hi (долл.) |
Эвристический подход Сильвера-Мила. Данный подход применим к решению только тех задач управления запасами, в которых затраты на закупку единицы продукции постоянны и одинаковы для всех этапов. Поэтому эвристический подход стремится сбалансировать лишь стоимости размещения заказа и затраты на хранение.
Эвристический метод определяет последующие этапы, потребности которых можно удовлетворить за счет размещения заказа на протяжении текущего периода. Задача планирования заключается в минимизации затрат, которые связаны с размещением заказа и хранением продукции и отнесены к одному периоду.
Предположим, на этапе / размещается заказ для периодов i, i + t (i<t).
Пусть TC(i, t) — соответствующая стоимость размещения заказов и хранения
11.3. Динамические задачи экономичного размера заказа
продукции для этих же этапов. С использованием обозначений, принятых для моделей динамического программирования, математически это можно выразить следующим образом.
{К,, t = i.
rC(''f) к, + h,DM +(/*,. + hM)DM +... + (/*,. + Лм1 +... + V,) Д, г > /. Обозначим далее через TCU(i, t) соответствующие затраты за период, т.е.
тс (и)
TCU{i,t) =
/-/4-1
Таким образом, для заданного текущего этапа / эвристический метод определяет t, которое минимизирует функцию TCU(i, t).
Функция TC(i, t) определяется с помощью рекуррентных соотношений.
TC(i, i) = К,,
TC(i, t) = TC{i, * - 1) + (Л, + Vi + ••• + *,-i)A. t=i + l,i + 2, n. Алгоритм эвристического метода состоит из следующих шагов.
Шаг О. Пусть i = l.
Шаг 1. Определяем локальный минимум t функции TCU(i, t), который должен удовлетворять неравенствам
TCU(i,t'-l)>TCU(i,t
TCU{i,t+l)>TCU(i,t').
Тогда в соответствии с эвристическим подходом на этапе i размещается заказ объемом (Д 4- Дм + ... + Д.) для этапов /4-1, t .
Шаг 2. Пусть i = t+ l. Если I > п, вычисления заканчиваются; рассмотрен весь плановый период. Иначе следует перейти к шагу 1.
Пример 11.3.4
Найдем оптимальную стратегию управления запасами в следующей 6-этапной задаче. Стоимость единицы продукции равна 2 долл. для любого периода.
| Этап i | D, (единицы) | К, (долл.) | h, (долл.) |
Итерация 1 (i — 1, Jf, = 20 долл.). Функция ТС(1, t) определяется рекуррентно по t. Например, при заданном значении 742(1, 1) = 20 долл., 742(1, 2) = 742(1, 1) 4- h,D2 = = 20 4- 1 х 15 = 35 долл.
Глава 11. Детерминированные модели управления запасами
| Этап f | D, | ТСЦ1, f) | |
| 20/1 = 20,00 | |||
| 20 + 1 х 15 = 35 | 35/2 = 17,50 | ||
| 35+ (1 +1)х7 = 49 | 49/3 = 16,33 | ||
| 49+ (1 +1 +1)х20 = 109 | 109/4 = 27,25 |
Локальный минимум достигается при t* = 3, что означает необходимость размещения на первом этапе заказа объемом 10 + 15 + 7 = 32 единицы для этапов 1, 2, 3. Полагаем i = t +1 = 3 + 1=4.
| Итерация 2 (< | = 4, Kt = 18 долл.) | ||
| Этап t | D, | Щ4, 0 | TCU(4, f) |
| 18/1 = 18,00 | |||
| 18 + 3x13 = 57 | 52/2 = 28,50 |
Значение £* = 4 означает, что на четвертом этапе необходимо разместить заказ объемом 20 единиц для этапа 4. Полагаем i = 4 + 1 = 5.
Итерация 3 (i = 5, Кь = 5 долл.)
| Этап f | D, | Щ5, 0 | TCU(5, 0 |
| 5/1 =5 | |||
| 5 + 1 х 25 = 30 | 30/2 = 15 |
Так как t = 5, на пятом этапе заказывается 13 единиц для этапа 5. Полагаем далее г = 5 + 1 = 6. Так как i = 6, то это последний этап планирования. Мы должны заказать на шестом этапе 25 единиц для этого же этапа.
В следующей таблице сравниваются решения, полученные эвристическим методом и точным методом динамического программирования. Мы исключили из части таблицы, содержащей результаты динамического программирования, стоимость закупки единицы продукции, так как этот параметр в вычислениях с помощью эвристического метода не учитывается.
| Этап | Эвристический метод | Метод динамического программирования | ||
| Закуплено единиц | Стоимость (долл.) | Закуплено единиц | Стоимость (долл.) | |
| Всего |
Стоимость производственного плана, предложенного эвристическим методом, примерно на 32 % превышает стоимость аналогичного плана, полученного методами динамического программирования (122 долл. против 90). "Неадекватность" результата эвристического метода может быть обусловлена данными, которые ис
11.3. Динамические задачи экономичного размера заказа
пользовались в задаче. В частности, причиной этого может быть чрезвычайная неравномерность стоимостей размещения заказов для этапов 5 и 6. Тем не менее этот пример показывает, что эвристический метод не обладает способностью "смотреть вперед" в поисках лучшего производственного плана. Например, размещение на пятом этапе заказов для этапов 5 и 6 (вместо размещения их в отдельности) может сэкономить 25 долл., что уменьшит суммарные затраты производственного плана, предложенного эвристическим методом, до 97 долл.
Реализация в Excel эвристического подхода Сильвера-Мила. Шаблон Excel chllSilverMealHeuristic.xls разработан для получения решения на основе эвристического подхода Сильвера-Мила. Процесс решения задачи начинается со ввода всех необходимых данных, включая значения величин К, й и D для каждого периода и значение N — количество периодов. (Ячейки рабочего листа для входных данных выделены цветом.) Затем пользователь должен инициировать вычисления для каждой итерации вручную.
На рис. 11.12 показано применение этого шаблона для решения задачи из примера 11.3.4. Первая итерация инициируется путем введения значения 1 в ячейку F11, это означает что на первой итерации выполняются вычисления для первого периода. Excel выведет столько строк расчетных значений, сколько указано в ячейке G3 как общее число периодов (в данном примере это число равно 6). Номера периодов выводятся в диапазоне G11:G16. Далее проверяем вычисленные значения TCU в столбце L (этот столбец выделен зеленым цветом) и находим минимальное значение. В данном случае локальному минимуму соответствует t = 3 (третий период) со значением TCU = 16,33. Отсюда следует, что следующая итерация должна начаться
О Р О R ^