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

и запасами

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

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d₁=5 единицы, на второй – d₂=2, на третий - d₃=3 единицы. К началу первого этапа на складе имеется только 4 единицы продукции, т.е. начальный уровень запаса равен y₁=4. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁=4, h₂=5, h₃=6. Затраты на производство x_j единиц продукции на j-м этапе определяются функцией

j_j(x_j) =2x_j² + 2x_j + 2 (1)

т.е. а=2; b=2; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

Решение.

Представим исходные данные задачи в виде таблицы:

Таблица 12.

Период К	1 2 3
Спрос dK, ед	5 2 2
Затраты на производство АК , руб.	2 2 2
Затраты на хранение hK , руб.	4 5 6

Воспользовавшись рекуррентными соотношениями, последовательно вычисляем

F₁ (x = y₂), F₂ (x = y₃), F₃ (x = y₄), и соответственно находим ₁ (x= y₂),

₂ (x = y₃ ), ₃ (x = y₄)

Положим k = 1. Тогда имеем

(2)

Учтем, что параметр состояния x = у₂ может принимать целые значения на отрезке

0 у₂ d₂ + d₃ (3)

0 y₂ 2 + 2

т.е.

у₂ = 0, 1, 2, 3, 4.

При этом каждому значению параметра состояния должна отвечать определенная область изменения переменной x₁, а именно

0 х₁ 2 + у₂ (4)

На первом этапе спрос d₁ = 5, исходный запас у₁ = 4. Из балансового уравнения

х₁ + у₁ - d₁ = у₂ (5)

непосредственно следует, что объем производства связан со значением параметра состояния x= у₂ соотношением

x₁ = y₂ + d₁ - y₁ = y₂ + 5 - 4 = y₂ + 1 (6)

Если задан уровень запаса к началу первого этапа, то каждому значению у₂ отвечает единственное значение х₁ и потому

F₁(x = y₂) = W₁ (x₁, y₂) = ах₁² + bx₁ + c + h₁y₂ (7)

Придавая у₂ различные целые значения от 0 до 4 и учитывая (6), находим

y₂ = 0, x₁ = 1, W₁ (0;0) = 2 ∙ 1² + 2 × 1 + 2 + 4 × 0 = 6

y₂ = 1, x₁ = 2, W₁ (1;1) = 2 ∙ 2² + 2 × 2 + 2 + 4 × 1 = 18

y₂ = 2, x₁ = 3, W₁ (2;2) = 2 ∙ 3² + 2 ∙ 3 + 2 + 4 ∙ 2 = 34

y₂ = 3, x₁ = 4, W₁ (3;3) = 2 ∙ 4² + 2 ∙ 4 + 2 + 4 ∙ 3 = 54

y₂ = 4, x₁ = 5, W₁ (4;4) = 2 ∙ 5² + 2 ∙ 5 + 2 + 4 ∙ 4 = 78

Значения функции состояния F₁(x ) представлены в табл. 13.

Таблица 13.

x = y2
F1 (x = y2)
x1(x=y2)

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию

F₂(x = y₃).

(8)

Здесь минимум берется по единственной переменной х₂, которая может изменяться в пределах

0 £ x₂ £ d₂ + y₃ или 0 £ x₂ £ 2 + y₃ (9)

где верхняя граница зависит от параметра состояния x = у₃, который, принимает значения на отрезке

0 £ y₃ £ d₃ , т.е. 0 £ y₃ £ 2 (10)

а аргумент у₂ в последнем слагаемом справа в соотношении (8) связан с х₂ и у₃ балансовым уравнением

x₂ + y₂ - d₂ = y₃

откуда следует

y₂ = y₃ + d₂ - x₂ = y₃ + 2 - x₂ (11)

Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять W₂ (x₂, x), а затем определять F₂(x ) и ₂(x ).

Положим, например x = у₃ = 2. Тогда, согласно (9),

0 £ x₂ £ 4,

т.е. переменная х₂ может принимать значения: 0, 1, 2, 3, 4, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле (11):

у₂ = 4 - х₂

Последовательно находим:

если x₂ = 0, то y₂ = 4-0 = 4, W₂ (0,2) = 2∙0² + 2×0 + 2 + 5×2 + F₁(4) = 12 + 78 = 90,

x₂ = 1, y₂ = 4-1 = 3, W₂ (1,2) =2∙1² + 2×1+ 2 + 5×2 + F₁(3) = 16 + 54 = 70,

x₂ = 2, y₂ = 4-2 = 2, W₂ (2,2) =2∙2² +2×2 + 2 + 5×2 + F₁(2) = 24 + 34 = 58,

x₂ = 3, y₂ = 4-3 = 1, W₂ (3,2) =2∙3²+2×3 + 2 + 5×2 + F₁(1) = 36 + 18 = 54*,

x₂ = 4, y₂ = 4-4 = 0, W₂ (4,2) = 2∙4² + 2×4 + 2 + 5×2 + F₁(0) = 52+ 6 = 58.

Наименьшее из полученных значений W₂ есть F₂ (2), т.е.

F₂ (x = y₃ = 2) = min W₂ (x₂,2) = min (90, 70, 58, 54, 58) = 54,

x₂

причем минимум достигается при значении х₂, равном

` ₂ (x = y₃ = 2) = 3

Аналогично для всех остальных значений у₃ = 0, 1.

F₂ (x = y₃ = 0) = 20; ` ₂ (x = y₃ = 0) = 2.

F₂ (x = y₃ = 1) = 32; ` ₂ (x = y₃ = 1) = 2.

Процесс табулирования функции F₂ (x = y₃) приведен в табл. 14, а результаты табулирования сведены в табл. 15.

Таблица 15.

x= у3
F2 (x= y3)
(x= y3)

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию

F₃ (x = y₄):

Вычисляем значение функции состояния только для одного значения аргумента x = у₄ = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 16. Получаем

F₃ (x = y₄) = min W₃ (x₃,0) = min (56, 38, 34) = 34,

x₃

минимум достигается при значении переменной х₃, равной

` ₃ (x = y₄ = 0) = 2.

Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна

= 2.

Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что

х₃ + у₃ - d₃ = y₄

или

2 + у₃ - 2 = 0,

откуда

у₃ = 0.

Из таблицы 15 находим значение

Аналогично, продолжая двигаться в обратном направлении и учитывая, что

х₂ + у₂ - d₂ = y₃

или

2 + у₂ - 2 = 0,

получаем

у₂ = 0;

из таблицы 13 находим значение х₁(x)

.

Итак, оптимальный план производства имеет вид

х₁ = 1

х₂ = 2

х₃ = 2,

а минимальные общие затраты составляют 34 единицы.

Сделаем проверку полученного результата. Для этого по исходным данным и найденному плану производства заполняем таблицу 17 и убеждаемся, что заявки потребителей на каждом этапе выполняются

у₁ + х₁ ³ d₁ у₂ + х₂ ³ d₂ у₃ + х₃ ³ d₃

4 + 1 ³ 5 0 + 2 ³ 2 0 + 2 ³ 2

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

у₁ + х₁ + х₂ + х₃ = d₁ + d₂ + d₃

4 + 1 + 2 + 2 = 5 + 2 + 2

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

j(х₁) + j(х₂) + j(х₃) + h₁у₂ + h₂у₃ = F₃(y₄=0)

(2∙1² + 2∙1 + 2) + (2∙2² + 2∙2 + 2) + (2∙2² + 2∙2 + 2) + 4∙0 + 5∙0 =

= 6 + 14 + 14 + 0 + 0 = 34

Таблица 14. K=2			xk	yk = yk+1 + dk - xk	Wk(xk, yk+1) =jk(xk) + hkyk+1 + Fk-1(yk)
0 £ y3 £ d3	x = y3	0 £ x2 £ d2 + y3	X2	y2 = y3 + d2 - x2	W2(x2, y3) = a + bx2 + c + h2y3 + F1(y2)
0 £ y3 £ 2	x = y3	0 £ x2 £ 2 + y3	X2	y2 = y3 + 2 - x2
	y3 = 0	0 £ x2 £ 2	X2 = 0 X2 = 1 X2 = 2	y2 = 2 - 0 = 2 y2 = 2 - 1 = 1 y2 = 2 - 2 = 0	W2(0;0) = 2∙02 + 2×0 + 2 + 5×0 + F1(2) = 2 + 34 =36 W2(1;0) = 2∙12 + 2×1 + 2 +5×0 + F1(1) = 6 + 18 =24 W2(2;0) = 2∙22 +2×2 + 2 + 5×0 +F1(0) = 14 + 6 =20*
	y3 = 1	0 £ x2 £ 3	X2 = 0 X2 = 1 X2 = 2 X2 = 3	y2 = 1 + 2 - 0 = 3 y2 = 1 + 2 - 1 = 2 y2 = 1 + 2 - 2 = 1 y2 = 1 + 2 - 3 = 0	W2(0;1) = 2∙02 + 2×0 + 2 + 5×1 + F1(3) = 6+54=60 W2(1;1) = 2∙12 + 2×1 + 2 + 5×1 + F1(2) =11+34 =45 W2(2;1) = 2∙22 + 2×2 + 2 + 5×1 + F1(1)=20+18 =38* W2(3;1) = 2∙32 + 2×3 + 2 + 5×1 + F1(0)=33+6 =39
	y3 = 2	.......................	........	............................	.............................................................

		Таблица 16.
	K=3

			xk	yk = yk+1 + dk - xk	Wk(xk, yk+1) = jk(xk) + hkyk+1 + Fk-1(yk)
0 £ y4 £ 0	x = y4	0 £ x3 £ d3 + y4	x3	y3 = y4 + d3 - x3	W3(x3, y4) = a + bx3 + c + h3y4 + F2(y3)
y4 = 0	x = y4	0 £ x3 £ 2	x3	y3 = y4 + 2 - x3
	y4 = 0	0 £ x3 £ 2	x3 = 0 x3 = 1 x3 = 2	y3 = 2 - 0 = 2 y3 = 2 - 1 = 1 y3 = 2 - 2 = 0	W3(0;0) = 2∙02 + 2×0 + 2 + 6×0 + F2(2)=2+54=56 W3(1;0) = 2∙12 + 2×1 + 2 + 6×0 + F2(1)=6+32=38 W3(2;0) = 2∙22 + 2×2 + 2 + 6×0 + F2(0)=14+20=34

Самопроверка результатов Таблица 17.

Этапы	январь	февраль	март	Итого за 3 месяца
Имеем продукции к началу месяца, шт.	у1 = 4	у2 = 0	у3 = 0	у1 = 4
Производим в течение месяца, шт.	х1 = 1	х2 = 2	х3 = 2	х1+ х2+ х3 = 5
Отпускаем заказчикам, шт.	d1 = 5	d2 = 2	d3 = 2	d1+ d2+ d3 = 9
Остаток к концу месяца (храним в течение текущего месяца), шт.	у2 = 0	у3 = 0	у4 = 0
Затраты на производство, руб.	j(х1)=6	j(х2)=14	j(х3)=14	j(х1) + j(х2) + j(х3) = 34
Затраты на хранение, руб.	h1у2 = 0	h2у3 = 0		h1у2 + h2у3 = 0

Задача №6