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

24

и запасами

 

Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на n месяцев. Размеры заказов значительно меняются от месяца к месяцу. Поэтому иногда лучше выполнять одной партией заказы нескольких месяцев, а затем хранить изделия, пока они не потребуются, чем выполнять заказ в тот именно месяц, когда этот заказ должен быть отправлен. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение изделий. Обозначим:

x_j - число изделий, производимых в j -й месяц;

y_j - величина запаса к началу j го месяца (это число не содержит изделий, произведенных в j -м месяце);

d_j - число изделий, которые должны быть отгружены в j -й месяц;

f_j (x_j, y_j+1) - затраты на хранение и производство изделий в j -м месяце.

Будем считать, что величины запасов к началу первого месяца y₁ и к концу последнего y_n+1 заданы.

Задача состоит в том, чтобы найти план производства

 

(x₁, x₂, ..., x_n)                                                                    (1)

 

компоненты которого удовлетворяют условиям материального баланса

 

              x_j + y_j - d_j = y_j+1         j = 1, n                                            (2)

 

и минимизируют суммарные затраты за весь планируемый период

                                                                                        (3)

причем по смыслу задачи

                       x_j ³ 0, y_j ³ 0, j = 1, n                                                    (4)

Прежде чем приступить к решению поставленной задачи, заметим, что для любого месяца j величина y_j+1 запаса к концу месяца должна удовлетворять ограничениям

 

0 £ y_j+1 £ d_j+1 + d_j+2 +... + d_n                                               (5)

 

т.е. объем производимой продукции x_j на этапе j может быть настолько велик, что запас y_j+1 удовлетворяет спрос на всех последующих этапах, но не

имеет смысла иметь y_j+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная x_j должна удовлетворять ограничениям

0 £ x_j £ d_j + y_j+1                                            (6)

Следует также заметить, что переменные x_j, y_j могут принимать только целые неотрицательные значения, т.е. мы получили задачу целочисленного нелинейного программирования.

Будем решать задачу (1)-(6) методом динамического программирования.

Введем параметр состояния и составим функцию состояния.

25

За параметр состояния x примем наличный запас в конце k -го месяца

            x = y_k+1                                                                                        (7)

 

а функцию состояния F_k(x) определим как минимальные затраты за первые k месяцев при выполнении условия (5)

                                                                  (8)

где минимум берется по неотрицательным целым значениям x₁,..., x_k, удовлетворяющим условиям

                       x_j + y_j - d_j = y_j+1                       j = 1, k-1                            (9)

                       x_k + y_k - d_k = x                                                                             (10)

 

Учитывая, что

 

(11)

 

и величина запаса y_k к концу (k-1) периода, как видно из уравнения (10), равна

                       y_k = x + d_k - x_k                                                                 (12)

 

приходим к рекуррентному соотношению

           (13)

где минимум берется по единственной переменной x_k, которая, согласно (6) может изменяться в пределах

            0 £ x_k £ d_k + x                                                           (14)

 

принимая целые значения, причем верхняя граница зависит от значений параметра состояния, изменяющегося в пределах

                   0 £ x £ d_k+1 + d_k+2 +... + d_n                                                              (15)

а индекс k может принимать значения

k = 2, 3, 4, ..., n                                                   (16)

 

Если k=1, то

                       F₁(x = y₂) = min f₁(x₁, x)                                                  (17)    

                                               x₁

где

 x₁ = x + d₁ - y₁                                                         (18)

                       0£ x £ d₂ + d₃ +... + d_n                                                    (19)

26

т.е. на начальном этапе при фиксированном уровне y₁ исходного запаса каждому значению параметра x отвечает только одно значение переменной x₁, что несколько уменьшает объем вычислений.

Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты x_n* оптимального решения, а остальные компоненты определяем как

                             (20)

Рассмотрим более подробно функции затрат f_j(x_j, y_j+1) и рекуррентные соотношения. Пусть

j_j(x_j) = ax_j² + bx_j + c

j_j (x_j) - затраты на производство (закупку) x_j единиц продукции на этапе j;

h_j - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1.

Тогда затраты на производство и хранение на этапе j равны

 

            f_j(x_j, y_j+1) = j_j(x_j) + h_j y_j+1 = ax_j² + bx_j + c + h_j y_j+1.                     (21)

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

              (22)

где

k = 2, 3, ..., n                                                                        (23)

0 £ y_k+1 £ d_k+1 + d_k+1 +... + d_n                                  (24)

0 £ x_k £ d_k + y_k+1                                                       (25)

y_k = y_{k+1 +} d_k - x_k                                                        (26)

(27)

Если же k=1, то

(30)

(29)

(28)

Остается заметить, что полезно обозначить выражение в фигурных скобках через

 

W_k(x_k, y_k+1) = ax_j² + bx_j + c + h_ky_k+1 + F_k-1(y_k)                 (31)

и записать рекуррентное соотношение (22) в виде

 

            F_k(x=y_k+1) = min W_k(x_k, y_k+1)                                                   (32)

                                     x_k

27

где минимум берется по целочисленной переменной x_k, удовлетворяющей условию (25).

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

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

j_j(x_j) = x_j² + 5x_j + 2                                             (33)

 

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

Исходные данные задачи можно кратко записать одной строкой:

 

d₁ d₂ d₃ a b c  h₁  h₂    h₃  y₁

1   2  4  1 5 2 1 3    2   2

 

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

F₁ (x = y₂), F₂ (x = y₃), ..., F_k (x = y_k+1), ... и соответственно находим  ₁ (x= y₂), ₂ (x = y₃ ), ..., ` _k (x = y_k+1), ...

Положим k = 1. Согласно (27) имеем

 

                                  (34)

 

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

0  у₂  d₂ + d₃

                                                            0  y₂  2 + 4

т.е.

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

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

0  х₁  3 + у₂

 

Однако, на первом этапе объем производства х₁ не может быть меньше единицы, так как спрос d₁ = 3, а исходный запас у₁ = 2. Более того, из балансового уравнения

х₁ + у₁ - d₁ = у₂

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

            x₁ = y₂ + d₁ - y₁ = y₂ + 3 - 2 = y₂ +1                                           (35)

 

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

            F₁(x = y₂) = W₁ (x₁, y₂)          

28

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

            y₂ = 0, x₁ = 0+1 = 1, W₁ (1; 0) = 1² + 5× 1 + 2 + 1× 0 = 8

            y₂ = 1, x₁ = 1+1 = 2, W₁ (2; 1) = 2² + 5× 2 + 2 + 1× 1 = 17

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

 

                                                                                            Таблица 1

x = y2	0	1	2	3	4	5	6
F1 (x = y2)	8	17	28	41	56	73	92
x1(x=y2)	1	2	3	4	5	6	7

 

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

F₂(x = y₃) с помощью соотношения (32)

 

     (37)

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

 

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

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

 

0 £ y₃ £ d₃, т.е. 0 £ y₃ £ 4                                                          (39)

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

                       x₂ + y₂ - d₂ = y₃

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

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

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

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

0 £ x₂ £ 4,

 

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

у₂ = 4 - х₂

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

если x₂ = 0, то y₂ = 4-0 = 4, W₂ (0, 2) = 0² + 5× 0 + 2 + 3× 2 + F₁(4) = 8 + 56 = 64,

x₂ = 1,    y₂ = 4-1 = 3, W₂ (1, 2) = 1² + 5× 1 + 2 + 3× 2 + F₁(3) = 14 + 41 = 55,

x₂ = 2,    y₂ = 4-2 =2, W₂ (2, 2) = 2² + 5× 2 + 2 + 3× 2 + F₁(2) = 22 + 28 = 50,

x₂ = 3,    y₂ = 4-3 = 1,        W₂ (3, 2) = 3² + 5× 3 + 2 + 3× 2 + F₁(1) = 32 + 17 = 49*,

x₂ = 4,     y₂ = 4-4 = 0,       W₂ (3, 2) = 4² + 5× 4 + 2 + 3× 2 + F₁(0) = 44 + 8 = 52.

29

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

 

F₂ (x = y₃ = 2) = min W₂ (x₂, 2) = min (64, 55, 50, 49, 52) = 49,

                                   x₂

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

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

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

F₂ (x = y₃ = 3) = 63;    ` ₂ (x = y₃ = 3) = 3.

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

Таблица 3

x= у3	0	1	2	3	4
F2 (x= y3)	24	36	49	63	78
(x= y3)	2	2	3	3	4

 

 Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F₃ (x = y₄):

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

F₃ (x = y₄) = min W₃ (x₃, 0) = min (80, 71, 65, 62, 62) = 62,

                                          x₃

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

                       ` <sub>3</sub> (x = y<sub>4</sub> = 0) = 3 или ` ₃ (x = y₄ = 0) = 4.

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

= 3 или = 4.

Рассмотрим случай, когда на последнем этапе планируем выпускать три единицы продукции

= 3.

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

х₃ + у₃ - d₃ = y₄

или

3 + у₃ - 4 = 0,

откуда

у₃ = 1.

Из таблицы (3) значений  находим

 

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

х₂ + у₂ - d₂ = y₃

30 Таблица 2 K=2			xk	yk = yk+1 + dk - xk	W k (xk, yk+1) = j k (xk) + hkyk+1 + Fk-1(yk)
0 £ y3 £ d3	x = y3	0 £ x2 £ d2 + y3	x2	y2 = y3 + d2 - x2	W2(x2, y3) = a  + bx + c + h2y3 + F1(y2)
0 £ y3 £ 4	x = y3	0 £ x2 £ 2 + y3	x2	y2 = y3 + 3 - 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) = 02 + 5× 0 + 2 + 3× 0 + F1(2) =2+28 =30 W2(1; 0) = 12 + 5× 1 + 2 +3× 0 + F1(1)=8+17 =25 W2(2; 0) = 22 +5× 2 + 2 + 3× 0 +F1(0) =16+8=24*
	y3 = 1	0 £ x2 £ 3	x2 = 0 x2 = 1 x2 = 2 x2 = 3	y2 = 3 - 0 = 3 y2 = 3-1 = 2 y2 = 3-2 = 1 y2 = 3-3 = 0	W2(0; 1) = 02 + 5× 0 + 2 + 3× 1 + F1(3) = 5+41=46 W2(1; 1) = 12 + 5× 1 + 2 + 3× 1 + F1(2) =11+28 =39 W2(2; 1) = 22 + 5× 2 + 2 + 3× 1 + F1(1)=19+17 =36* W2(3; 1) = 32 + 5× 3 + 2 + 3× 1 + F1(0)=29+8 =37
	y3 = 2	.......................	........	............................	.............................................................
	y3 = 3	0 £ x2 £ 5	x2 = 0 x2 = 1 x2 = 2 x2 = 3 x2 = 4 x2 = 5	y2 = 5 - 0 = 5 y2 = 5 - 1 = 4 y2 = 5 - 2 = 3 y2 = 5 - 3 = 2 y2 = 5 - 4 = 1 y2 = 5 - 5 = 0	W2(0; 3) = 02 + 5× 0 + 2 + 3× 3 + F1(5) = 11+73=84 W2(1; 3) = 12 + 5× 1 + 2 + 3× 3 + F1(4) =17+56 =73 W2(2; 3) = 22 + 5× 2 + 2 + 3× 3 + F1(3)=25+41 =66 W2(3; 3) = 32 + 5× 3 + 2 + 3× 3 + F1(2)=35+28 =63* W2(4; 3) = 42 + 5× 4 + 2 + 3× 3 + F1(1)=47+17 =64 W2(5; 3) = 52 + 5× 5 + 2 + 3× 3 + F1(0)=61+8 =69
	y3 = 4	0 £ x2 £ 6	x2 = 0 x2 = 1 x2 = 2 x2 = 3 x2 = 4 x2 = 5 x2 = 6	y2 = 6 - 0 = 6 y2 = 6 - 1 = 5 y2 = 6 - 2 = 4 y2 = 6 - 3 = 3 y2 = 6 - 4 = 2 y2 = 6 - 5 = 1 y2 = 6 - 6 = 0	W2(0; 4) = 02 + 5× 0 + 2 + 3× 4 + F1(6) = 14+92=106 W2(1; 4) = 12 + 5× 1 + 2 + 3× 4 + F1(5) =20+73 =93 W2(2; 4) = 22 + 5× 2 + 2 + 3× 4 + F1(4)=28+56 =84 W2(3; 4) = 32 + 5× 3 + 2 + 3× 4 + F1(3)=38+41 =79 W2(4; 4) = 42 + 5× 4 + 2 + 3× 4 + F1(2)=50+28 =78* W2(5; 4) = 52 + 5× 5 + 2 + 3× 4 + F1(1)=64+17 =81 W2(6; 4) = 62 + 5× 6 + 2 + 3× 4 + F1(0)=80+8 =88

 

 

	31
			Таблица 4

 

K=3			xk	yk = yk+1 + dk - xk	W k (xk, yk+1) = j k (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 £ 4	x3	y3 = y4 + 4 - x3
	y4 = 0	0 £ x3 £ 4	x3 = 0 x3 = 1 x3 = 2 x3 = 3 x3 = 4	y3 = 4-0 = 4 y3 = 4- 1 = 3 y3 = 4-2 = 2 y3 = 4-3 = 1 y3 = 4-4 = 0	W3(0; 0) = 02 + 5× 0 + 2 + 2× 0 + F2(4)=2+78=80 W3(1; 0) = 12 + 5× 1 + 2 + 2× 0 + F2(3)=8+63=71 W3(2; 0) = 22 + 5× 2 + 2 + 2× 0 + F2(2)=16+49=65 W3(3; 0) = 32 + 5× 3 + 2 + 2× 0 + F2(1)=26+36=62* W3(4; 0) = 42 + 5× 4 + 2 + 2× 0 + F2(0)=38+24=62*

 

 

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

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

32

или

2 + у₂ - 2 = 1,

получаем

у₂ = 1;                                                                   

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

.

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

х ₁ = 2

х ₂ = 3

х ₃ = 3,

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

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

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

            2 + 2 ³ 3             1 + 2 ³ 2             1 + 3 ³ 4

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

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

                                     2 + 2 + 2 + 3 = 3 + 2 + 4

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

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

                       16 + 16 + 26 + 1 + 4 = 62

 

Студенту рекомендуется найти другой вариант оптимальной производственной программы, когда на последнем этапе предполагается произвести 4 единицы продукции, и так же выполнить самопроверку.

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: