Читайте также:
|
В данной модели предполагается, что уровень запаса контролируется периодически, а запаздывание с поставкой товара либо равно нулю, либо кратно периоду контроля. Поэтому будем считать, что пополнение запаса происходит мгновенно в начале этапа. Спрос также удовлетворяется мгновенно в начале этапа. Дефицит не допускается. Рассматривается конечный горизонт (n этапов) планирования. Отметим, что параметры этой модели меняются от этапа к этапу, то есть зависят от времени. Время меняется дискретно на величину этапа.
Обозначим:
y i - количество заказываемой продукции на i – ом этапе;
b i- спрос на продукцию на i – ом этапе;
x i- запас продукции на начало i – го этапа;
h i- затраты на хранение единицы продукции, переходящей с этапа i на этап i +1;
K i- затраты на оформление заказа на i – ом этапе;
c i(y) - затраты на закупку продукции на i – ом этапе при условии, что объем закупаемой партии равен y.
Требуется найти значения 
на всех этапах i= 1,…, n, минимизирующие суммарные затраты по всем этапам.
Обозначим Ci(y) все затраты на закупку продукции объемом y на этапе i, тогда
.
Для дальнейшего рассмотрения удобно представлять процесс поступления на склад и расходования со склада продукции в виде схемы
Для решения задачи будет применяться метод динамического программирования. Этот метод позволяет разбить исходную задачу поиска оптимума на всем горизонте планирования на n подзадач поиска экстремума на каждом этапе. Пусть состоянием системы на i – ом этапе будет объем запаса x i+1. Так как планируется минимизация затрат только на этапах от 1 до n, то величина x n+1 должна быть равна нулю. В этом случае объем запаса x i не должен превышать величину суммарного спроса на этапах i,…, n,
(31)
Пусть fi(xi+1) - минимальные суммарные затраты на этапах 1,…, i при заданной величине запаса xi+1 на конец этапа i. Тогда рекуррентное уравнение будет иметь вид
;
Таким образом, на первом этапе по заданному запасу x 2 величина y 1 определяется однозначно. На последующих этапах величина y i определяется из условия минимума суммарных затрат на этапе i (первые два слагаемых) и на всех предыдущих этапах 1,…, i- 1 (третье слагаемое). Аргумент функции fi-1(xi) вычислен из соотношения
. (32)
Следуя методу динамического программирования последовательно находятся значения функций f 1, f 2,, f n. Это прямая прогонка. Затем, начиная с номера n и до номера 1, вычисляются оптимальные значения 
- обратная прогонка.
Пример. Рассмотрим 3 – этапную систему управления запасами. Пусть начальный запас равен 1 единице продукции. Стоимость закупки единицы продукции составляет 10 денежных единиц за каждую из первых трех единиц продукции и 20 - за каждую единицу продукции сверх 3. Остальные данные представлены в таблице
| i | b I | K i | h i |
В рассматриваемой задаче затраты на закупку можно записать следующим образом
Вычисление функций 
, i = 1,…, n производится по этапам.
Этап 1. Вычисление значений функции 
сведем в таблицу
| x 2 | h 1 x 2 | y 1 | C 1(y 1) |
|
Здесь интервал изменения x 2 вычислен по формуле (31)
0 £ x 2 £ b 2 + b 3 =2 + 4 = 6,
а величина y 1 для каждого x 2 находится из соотношения (32)
y 1 = x 2 - x 1 + b 1.
Этап 2. Интервал изменения x 3 будет от 0 до 4. Вычисление значений функции f 2(x 3) приведено в следующей таблице
| x 3 | h 2 x 3 | y 2=0 | f 2(x 3) | 
| ||||||
| C 2=0 | ||||||||||
| - | - | - | - | |||||||
| - | - | - | ||||||||
| - | - | |||||||||
| - | ||||||||||
Для каждого значения x 3 (соответствующая строка) и каждого значения y 2 (соответствующий столбец) в ячейке таблицы находится значение выражения
, (33)
где в силу (32) x 2 = x 3 - y 2 + b 2.Величина y 2 изменяется в интервале
0£ y 2 £ x 3 - x 2 + b 2.
При этом максимальное значение y 2 будет достигаться при максимальном значении x 3 и минимальном значении x 2. Следовательно,
0£ y 2 £6.
Отметим, что этот интервал совпадает с интервалом изменения x 2. Покажем нахождение этих значений для двух случаев x 3 =0 и x 3 =1. Для x 3 =0 получаем
=0+0+55,
=17+0+34=51,
=27+0+23=50.
Вычисление 
для y 2 >2 невозможно, так как значение аргумента функции f 1 будет отрицательным, что недопустимо по условиям задачи. Поэтому в соответствующих ячейках стоит прочерк. Минимальное значение по строке 50 равно значению функции f 2(0) и расположено в столбце f 2(x 3) таблицы. В столбце этой таблицы расположено значение y 2, при котором достигается это минимальное значение (в рассматриваемом случае это y 2 =2). Для x 3 = 1 будем иметь
0+3+76=79;
17+3+55=75;
27+3+34=64;
37+3+23=63.
Вычисление 
для y 2 >3 невозможно по причине аналогичной предыдущей. Минимальное значение по строке 63 равно значению функции f 2(1) и расположено в столбце f 2(x 3) таблицы. В столбце этой таблицы расположено значение y 2, при котором достигается это минимальное значение (в рассматриваемом случае это y 2 =3).
Этап 3. Переменная x 4 может принимать единственное значение равное нулю, y 3 изменяется в пределах от 0 до 4. Соответствующие значения 
и f 3(0) приведены в следующей таблице
| x 4 | h 3 x 4 | y 3=0 | y 3=1 | y 3=2 | y 3=3 | y 3=4 | f 3(x 3) | 
|
| C 3=0 | C 3=16 | C 3=26 | C 3=36 | C 3=56 | ||||
В соответствии с полученным результатом минимальные суммарные затраты равны 99. Теперь нужно найти величины 
. Будем находить их, двигаясь по таблицам в обратном направлении. Величину = 3, получим из последней таблицы. Найдем 
из соотношения (32)
= x 4 - + b 3=0 - 3 + 4=1.
Теперь из предпоследней таблицы в строке = 1 находим 
= 3. Соответственно.
= - + b 2=1 - 3 + 2 = 0.
Из первой таблицы в строке = 0 находим 
= 2.
Ответ. Для минимизации суммарных затрат необходимо на первом этапе заказать 2 единицы продукции, на втором - 3 единицы, а на третьем также 3 единицы. При этом суммарные затраты составят 99 денежных единиц.
Дата добавления: 2015-10-23; просмотров: 135 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Nbsp; d | | | Частный случай постоянных или убывающих предельных затрат |