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

Условие задачи:Рассматривается трехэтапная система управления запасами с дискретной продукцией и динамическим детерминированным спросом.

Заявки потребителей на продукцию составляют на этапе 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(y21)

Придавая х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+1k),

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 балансовым уравнением: y22-d2= y3, откуда y2= y3+ d22= 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 +d22, 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 +d22, 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 +d22, 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. Самопроверка

Проверяем выполняются ли заявки потребителей на каждом этапе :

y11≥d1 2+1>2

y22≥d2 1+1=2

y33≥d3 0+2=2

заявки выполняются.

Суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности:

y1123=d1+d2+d3,

2+1+1+2=2+2+2

6=6,

причем это достигается при наименьших возможных затратах на производство и хранение продукции:

ϕ(х1)+ ϕ(х2)+ ϕ(х3)+h1y2+h2y3=F3(y4=0),

ϕ(х1)=х121+5=1+1+5=7

ϕ(х2)=х222+5=1+1+5=7

ϕ(х3)=х321+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с.,ил.

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