Динамическая задача управления производственными запасами
Условие задачи:Рассматривается трехэтапная система управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Заявки потребителей на продукцию составляют на этапе j равен dj единиц (j = 1, 2, 3).К началу первого этапа на складе имеется только y1 единицы продукции. Затраты на хранение единицы продукции на этапе j равны hj.
Затраты на производство xj единиц продукции на j-м этапе определяются
Функцией ϕ=хj2+хj+5, j=1,2,3.
Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.
Для этого необходимо составить математическую модель динамической задачи управления производством и запасами и решить ее методом динамического программирования, обосновывая каждый шаг вычислительного процесса. Исходные данные приведены в табл.
№ вар. | Исходные данные | |||||||||
d1 | d2 | d3 | a | b | c | h1 | h2 | h3 | y1 | |
Решение:
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F1(y2 ), F2 (y3 ), F3 (y4 ) и соответственно находим x1* (y2 ) , x2*(y3 ) , x3* (y4 ) .
1. Положим k=1, тогда согласно формуле:
F1(y2 )=min(ax12+bx1+c+h1*y2) (3.1)
имеем F1(y2 )=( x12+x1+5+ y2).
Учтем, что согласно условия: 0 ≤y2≤d2+d3+…+dn (3.2)
Параметр состояния у=у2 может принимать целые значения на отрезке
0≤y2≤ d2+d3, 0≤y2≤ 2+2=4, т.е. y2=0,1,2,3,4.
При этом каждому значению параметра состояния должна отвечать определенная область изменения управления х1, характеризуемая условием:
0 ≤х1≤d1+y2,
0≤х1≤2+ y2.
Однако объем производства на первом этапе х1 не может быть меньше 0, т.к. спрос d1=2, а исходный запас y1=2.
Кроме того, из балансового уравнения:
y1+x1-d1=y2 (3.3)
непосредственно следует, что объем производства связан со значением параметра состояния y=y2 соотношением:
х1=y2+d1-y1= y2+2-2= y2.
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению y2 отвечает единственное значение х1 и поэтому:
F1(y2 )=W(y2,х1)
Придавая х2 различные целые значения от 0 до 4 и учитывая х1= y2 находим:
y2=0 х1=0 W(0;0)=02+0+5+0=5.
y2=1 х1=1 W(1;1)=12+1+5+1=8
y2=2 х1=2 W(2;2)=22+2+5+2=13
y2=3 х1=3 W(3;3)=32+3+5+3=20
y2=4 х1=4 W(4;4)=42+4+5+4=29
Значения функции состояния F1(y2 ) представим в таблице 1.
Таблица1.
y =y2 | |||||
F1(y2 ) | |||||
x1* (y2 ) |
2. Положим k=2 и табулируем функцию F2(y3 ) с помощью соотношения:
Fk(y=yk+1)=min Wk(yk+1,хk),
F2(y3 )= min(ax22+bx2+c+h2y3+ F1(y2 ))=min (x22+x2+5+2y3+ F1(y2 )),
Здесь минимум берется по единственной переменной х2, которая может изменяться, согласно: 0≤хk≤dk+yk+1, 0≤х2≤d2+y3 или 0≤х2≤2+y3,
Где верхняя граница зависит от параметра состояния y=y3, который принимает значения на отрезке: 0≤y3≤d3, т.е. 0≤y3≤2,
А аргумент y2 в соотношении F2(y3 )= min (x22+x2+5+2y3+ F1(y2 )), связан с y3 и x2 балансовым уравнением: y2+х2-d2= y3, откуда y2= y3+ d2-х2= y3+ 2-х2.
Придавая параметру состояния y=y3 различные состояния от 0 до 2, будем последовательно вычислять W2(y.x2), а затем определять F2(y3 ) и х2*(y).
Положим что y= y3=2, тогда 0≤х2≤2+2=4,
Т.е. х2 может принимать значения от 0 до 4 и каждому значению х2 отвечает определенное значение y2, вычисляемое по формуле:
y2 = y3 +d2-х2, y2 = y3 +2-х2=2+2-х2=4-х2.
Последовательно вычисляем:
Если х2=0, то y2=4-0=4 W2(2,0)=02+0+5+2*2+F1(4)=5+4+29=38
х2=1, то y2=4-1=3 W2(2,1)=12+1+5+2*2+F1(3)=2+5+4+20=31
х2=2, то y2=4-2=2 W2(2,2)=22+2+5+2*2+F1(2)=15+13=28
х2=3, то y2=4-3=1 W2(2,3)=32+3+5+2*2+F1(1)=21+8=29
х2=4, то y2=4-4=0 W2(2,4)=42+4+5+2*2+F1(0)=29+5=34
Наименьшее значение из полученных W2- это F2(y3=2)=28, при чем минимум достигается при значении х2*(y3=2)=2.
Аналогично делаем вычисления для значения параметра y=y3=0 и y=y3=1 и находим F2(y3=0) х2*(y3=0), F2(y3=1) х2*(y3=1).
Если y=y3=0, 0≤х2≤2+0=2
х2 может принимать значения от 0 до 2 и каждому значению х2 отвечает определенное значение y2, вычисляемое по формуле:
y2 = y3 +d2-х2, y2 = y3 +2-х2=0+2-х2=2-х2.
Если х2=0, то y2=2-0=2 W2(0,0)=02+0+5+2*0+F1(2)=5+ 13=18
х2=1, то y2=2-1=1 W2(0,1)=12+1+5+2*0+F1(1)=2+5+8=15
х2=2, то y2=2-2=0 W2(0,2)=22+2+5+2*0+F1(0)=6+5+0+5=16
Наименьшее значение из полученных W2- это F2(y3=0)=15, при чем минимум достигается при значении х2*(y3=0)=1.
Если y=y3=1,0≤х2≤2+1=3
х2 может принимать значения от 0 до 3 и каждому значению х2 отвечает определенное значение y2, вычисляемое по формуле:
y2 = y3 +d2-х2, y2 = y3 +2-х2=1+2-х2=3-х2.
Если х2=0, то y2=3-0=3 W2(1,0)=02+0+5+2*1+F1(3)=5+2+ 20=27
х2=1, то y2=3-1=2 W2(1,1)=12+1+5+2*1+F1(2)=2+5+2+13=22
х2=2, то y2=3-2=1 W2(1,2)=22+2+5+2*1+F1(1)=6+5+2+8=21
х2=3, то y2=3-3=0 W2(1,3)=32+3+5+2*1+F1(0)=12+5+2+5=24
Наименьшее значение из полученных W2- это F2(y3=1)=21, при чем минимум достигается при значении х2*(y3=1)=2.
Внесем вычисленные данные в таблицу 2.
Таблица2.
0≤yk+1≤∑dj | y=yk+1 | 0≤xk≤dk+xk+1 | xk | yk=yk+1+dk-xk | W(yk+1,xk) |
0≤y3≤d3 | y=y3 | 0≤x2≤d2+y3 | х2 | y2=y3+d2-x2 | W(y3,x2)=x22+x2+5+2y3+ F1(y2 ) |
0≤y3≤2 | y=y3 | 0≤x2≤2+y3 | х2 | y2=y3+2-x2 | W(y3,x2)=x22+x2+5+2y3+ F1(y2 ) |
y=y3=0 | 0≤x2≤2 | х2=0 | y2=0+2-0=2 | W2(0,0)=02+0+5+2*0+F1(2)=5+ 13=18 | |
х2=1 | y2=0+2-1=1 | W2(0,1)=12+1+5+2*0+F1(1)=2+5+8=15 | |||
х2=2 | y2=0+2-2=0 | W2(0,2)=22+2+5+2*0+F1(0)=6+5+0+5=16 | |||
y=y3=1 | 0≤x2≤3 | х2=0 | y2=1+2-0=3 | W2(1,0)=02+0+5+2*1+F1(3)=5+2+ 20=27 | |
х2=1 | y2=1+2-1=2 | W2(1,1)=12+1+5+2*1+F1(2)=2+5+2+13=22 | |||
х2=2 | y2=1+2-2=1 | W2(1,2)=22+2+5+2*1+F1(1)=6+5+2+8=21 | |||
х2=3 | y2=1+2-3=0 | W2(1,3)=32+3+5+2*1+F1(0)=12+5+2+5=24 | |||
y=y3=2 | 0≤x2≤4 | х2=0 | y2=2+2-0=4 | W2(2,0)=02+0+5+2*2+F1(4)=5+4+29=38 | |
х2=1 | y2=2+2-1=3 | W2(2,1)=12+1+5+2*2+F1(3)=2+5+4+20=31 | |||
х2=2 | y2=2+2-2=2 | W2(2,2)=22+2+5+2*2+F1(2)=15+13=28 | |||
х2=3 | y2=2+2-3=1 | W2(2,3)=32+3+5+2*2+F1(1)=21+8=29 | |||
х2=4 | y2=2+2-4=0 | W2(2,4)=42+4+5+2*2+F1(0)=29+5=34 |
Результаты внесем в таблицу 3.
Таблица3.
y = y3 | |||
F2 (y= y3 ) | |||
x2* (y= y3 ) |
3. Полагаем k=3 и табулируем функцию F3(y4 )
F3(y4 )= min(ax22+bx2+c+h3y4+ F2(y3 ))=min (x22+x2+5+4y3+ F2(y3 )).
Вычисляем значение функции состояния только для одного значения аргумента y=y4, т.к. не хотим оставлять продукцию в запас в конце исследуемого периода.
F3(y4 )= min (x22+x2+5+4y3+ F2(y3 ))
0≤x3≤d3+y4, 0≤x3≤2+y4,
y3=y4+d3-x3=0+2- x3=2- x3
Придавая параметру состояния y=y4=0, вычисляем W3(y;x3) и определяем F3(y4) и x3*(y).
y=y4=0, 0≤х3≤2,
т.е. х3 может принимать значения 0,1,2 и каждому значению х3 отвечает определенное значение y3=2-х3.
Вычисления приведены в таблице 4.
Таблица 4
y4=0 | y=y4 | 0≤x3≤2+y4 | х3 | y3=y4+2-x3 | W(y4,x3)=x32+x3+5+4y4+ F2(y3 ) |
y=y4=0 | 0≤x3≤2 | х3=0 | y3=0+2-0=2 | W2(0,0)=02+0+5+4*0+F2(2)=5+ 28=33 | |
х3=1 | y3=0+2-1=1 | W2(0,1)=12+1+5+4*0+F2(1)=2+5+21=28 | |||
х3=2 | y3=0+2-2=0 | W2(0,2)=22+2+5+4*0+F2(0)=6+5+0+15=26 |
Таким образом, получили наименьшие минимальные общие затраты на производство и хранение продукции W3- это F3(y4=0)=26, и последнюю компоненту оптимального плана х3=2.
4. Для нахождения остальных компонент оптимального решения, необходимо воспользоваться обычными правилами динамического программирования.
Т.к. х3+y3-d3= y4, то 2+ y3-2=0, откуда y3=0, следовательно, из таблицы 3 - х2*=1.
Т.к. х2+y2-d2= y3, то 1+ y2-2=0, откуда y2=1, следовательно, из таблицы 1 - х1*=1.
Следовательно, получен оптимальный план производства, который имеет значения: х1=1, х2=1, х3=2
при этом оптимальный план производства обеспечивает минимальные общие затраты на производство и хранение продукции в размере 26 денежных единиц.
5. Самопроверка
Проверяем выполняются ли заявки потребителей на каждом этапе :
y1+х1≥d1 2+1>2
y2+х2≥d2 1+1=2
y3+х3≥d3 0+2=2
заявки выполняются.
Суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности:
y1+х1+х2+х3=d1+d2+d3,
2+1+1+2=2+2+2
6=6,
причем это достигается при наименьших возможных затратах на производство и хранение продукции:
ϕ(х1)+ ϕ(х2)+ ϕ(х3)+h1y2+h2y3=F3(y4=0),
ϕ(х1)=х12+х1+5=1+1+5=7
ϕ(х2)=х22+х2+5=1+1+5=7
ϕ(х3)=х32+х1+5=22+2+5=11
7+7+11+1*1+2*0=26, 26=26
этап | итого за 3 этапа | |||
имеем продукции к началу месяца, шт | y1=2 | |||
производим в течение месяца, шт | x1+x2+x3=4 | |||
отпускаем заказчикам, шт | d1+d2+d3=6 | |||
остаток к концу месяца (храним в течение текущего месяца,шт | ||||
затраты на производство, ден. Ед. | ||||
затраты на хранение, ден. Ед. |
Ответ: Следовательно, получен оптимальный план производства, который имеет значения: х1=1, х2=1, х3=2 при этом оптимальный план производства обеспечивает минимальные общие затраты на производство и хранение продукции в размере 26 денежных единиц.
Литература
1. Исследование операций в экономике: Учеб. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М.Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремер – М: ЮНИТИ,2000-407с.
2. Лопатников Л.И. Экономико-математический словарь: Словарь современной экономической науки-5-е изд., перераб. и доп. –М: Дело,2003-520с.
3. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов эконом. спец. вузов.- М.: Высш. шк., 1986.-319с.,ил.