Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на n месяцев. Размеры заказов значительно меняются от месяца к месяцу. Поэтому иногда лучше выполнять одной партией заказы нескольких месяцев, а затем хранить изделия, пока они не потребуются, чем выполнять заказ в тот именно месяц, когда этот заказ должен быть отправлен. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение изделий. Обозначим:
xj - число изделий, производимых в j -й месяц;
yj - величина запаса к началу j -го месяца (это число не содержит изделий, произведенных в j -м месяце);
dj - число изделий, которые должны быть отгружены в j -й месяц;
fj (xj,yj+1) - затраты на хранение и производство изделий в j -м месяце.
Будем считать, что величины запасов к началу первого месяца y1 и к концу последнего yn+1 заданы.
Задача состоит в том, чтобы найти план производства (x1, x2,..., xn) (1)
компоненты которого удовлетворяют условиям материального баланса 
xj + yj - dj = yj+1 j = 1,n (2)
и минимизируют суммарные затраты за весь планируемый период
(3)
причем по смыслу задачи xj ³ 0, yj ³ 0, j = 1,n (4)
Прежде чем приступить к решению поставленной задачи, заметим, что для любого месяца j величина yj+1 запаса к концу месяца должна удовлетворять ограничениям 0 £ yj+1 £ dj+1 + dj+2 +... + dn (5)
т.е. объем производимой продукции xj на этапе j может быть настолько велик, что запас yj+1 удовлетворяет спрос на всех последующих этапах, но не имеет смысла иметь yj+1 больше суммарного спроса на всех последующих этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что переменная xj должна удовлетворять ограничениям 0 £ xj £ dj + yj+1 (6)
|
|
Следует также заметить, что переменные xj, yj могут принимать только целые неотрицательные значения, т.е. мы получили задачу целочисленного нелинейного программирования. Будем решать задачу (1)-(6) методом динамического программирования. Введем параметр состояния и составим функцию состояния.
За параметр состояния x примем наличный запас в конце k -го месяца x = yk+1 (7)
а функцию состояния Fk(x) определим как минимальные затраты за первые k месяцев при выполнении условия (5) 
(8)
где минимум берется по неотрицательным целым значениям x1,...,xk, удовлетворяющим условиям
xj + yj - dj = yj+1 j = 1, k-1 (9)
xk + yk - dk = x (10)
Учитывая, что
(11)
и величина запаса yk к концу (k-1) периода, как видно из уравнения (10), равна yk = x + dk - xk (12)
приходим к рекуррентному соотношению
(13)
где минимум берется по единственной переменной xk, которая, согласно (6) может изменяться в пределах 0 £ xk £ dk + x (14)
принимая целые значения, причем верхняя граница зависит от значений параметра состояния, изменяющегося в пределах 0 £ x £ dk+1 + dk+2 +... + dn (15)
а индекс k может принимать значения k = 2, 3, 4,..., n (16)
Если k=1, то F1(x = y2) = min f1(x1, x) (17)
x1
где x1 = x + d1 - y1 (18)
0£ x £ d2 + d3 +... + dn (19)
т.е. на начальном этапе при фиксированном уровне y1 исходного запаса каждому значению параметра x отвечает только одно значение переменной x1, что несколько уменьшает объем вычислений.
Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты xn* оптимального решения, а остальные компоненты определяем как 
(20)
Рассмотрим более подробно функции затрат fj(xj, yj+1) и рекуррентные соотношения. Пусть jj(xj) = axj2 + bxj + c
|
|
jj (xj) - затраты на производство (закупку) xj единиц продукции на этапе j; hj - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1. Тогда затраты на производство и хранение на этапе j равны
fj(xj, yj+1) = jj(xj) + hj yj+1 = axj2 + bxj + c + hj yj+1. (21)
Выведенные ранее рекуррентные соотношения динамического программирования для решения задачи управления производством и запасами в нашем случае принимают вид:
(22)
где k = 2, 3,..., n (23)
0 £ yk+1 £ dk+1 + dk+1 +... + dn (24)
0 £ xk £ dk + yk+1 (25)
yk = yk+1 + dk - xk (26)
|
|
|
|
Остается заметить, что полезно обозначить выражение в фигурных скобках через
Wk(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk) (31)
и записать рекуррентное соотношение (22) в виде Fk(x=yk+1) = min Wk(xk, yk+1) (32)
xk
где минимум берется по целочисленной переменной xk, удовлетворяющей условию (25).
Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй – d2=1, на третий - d3=2 единицы. К началу первого этапа на складе имеется 0 единиц продукции, т.е. начальный уровень запаса равен y1=0. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=6, h2=3, h3=5. Затраты на производство xj единиц продукции на j-м этапе определяются функцией jj(xj) = 4xj2 + xj + 2 
(33)
т.е. а=4; b=1; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
|
|
Исходные данные задачи можно кратко записать одной строкой:
d1 d2 d3 a b c h1 h2 h3 y1
3 1 2 4 1 2 6 3 5 0
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F1 (x = y2), F2 (x = y3),..., Fk (x = yk+1),... и соответственно находим 
1 (x= y2), 2 (x = y3),..., ` k (x = yk+1),...
Положим k = 1. Согласно (27) имеем F1(x = у2) = min {4x12 + x1 + 2 + h1у2} (34)
x1
Учтем, что согласно (28) параметр состояния x = у2 может принимать целые значения на отрезке
0 
у2 d2 + d3 0 y2 1+2, т.е. у2 = 0, 1, 2, 3.
При этом, вообще говоря, каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием (29) 0 х1 3 + у2
Однако, на первом этапе объем производства х1 не может быть меньше 3, так как спрос d1 = 3, а исходный запас у1 = 0. Более того, из балансового уравнения х1 + у1 - d1 = у2 непосредственно следует, что объем производства связан со значением параметра состояния x= у2 соотношением
x1 = y2 + d1 - y1 = y2 + 3 - 0 = y2 +3 (35)
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому F1(x = y2) = W1 (x1, y2)
Придавая у2 различные целые значения от 0 до 3 и учитывая (35), находим
y2 = 0, x1 = 0+3 = 3, W1 (3;0) = 4*32 + 3 + 2 + 6*0 = 41
y2 = 1, x1 = 1+3 = 4, W1 (4;1) = 4*42 + 4+ 2 + 6*1=76
y2 = 2, x1 = 2+3 = 5, W1 (5;2) = 4*52 + 5+ 2 + 6*2=119
y2 = 3, x1 = 3+3 = 6, W1 (6;3) = 4*62 + 6+ 2 + 6*3=170
Значения функции состояния F1(x) представлены в табл. 1
Таблица 1
| x = y2 | ||||
 F1 (x = y2)
| ||||
| x1(x=y2) |
Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию
F2(x = y3) с помощью соотношения (32)
F2(x = y3)=minW2 (x2, у3)= min{4x22 + x2 + 2 + h2у3 +F1(y2)} (37)
x2 x2
Здесь минимум берется по единственной переменной х2, которая может изменяться, согласно (25), в пределах 0 £ x2 £ d2 + y3 или 0 £ x2 £ 1 + y3 (38)
где верхняя граница зависит от параметра состояния x = у3, который, согласно (15), принимает значения на отрезке 0 £ y3 £ d3, т.е. 0 £ y3 £ 2 (39)
а аргумент у2 в последнем слагаемом справа в соотношении (37) связан с х2 и у3 балансовым уравнением x2 + y2 - d2 = y3 откуда следует y2 = y3 + d2 - x2 = y3 + 1 - x2 (40)
Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять W2 (x2, x), а затем определять F2(x) и 2(x).
Положим, например x = у3 = 2. Тогда, согласно (38), 0 £ x2 £ 3, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (40): у2 = 3 - х2
Последовательно находим:
если x2 = 0, то y2 = 3-0 = 3, W2 (0,2) = 4*02 + 0 + 2 + 3×2 + F1(3) =8+170=178,
x2 = 1, y2 = 3-1 = 2, W2 (1,2) = 4*12 + 1 + 2 + 3×2 + F1(2) = 13+119 = 132,
x2 = 2, y2 = 3-2 =1, W2 (2,2) = 4*22 + 2 + 2 + 3×2 + F1(1) = 26+76=102,
x2 = 3, y2 = 3-3 = 0, W2 (3,2) = 4*32 + 3 + 2 + 3×2 + F1(0) = 47+ 41 = 88*.
F2 (x = y3 = 2) = min W2 (x2,2) = min (178,132,102,88) = 88,
x2
причем минимум достигается при значении х2, равном ` 2 (x = y3 = 2) = 3
Процесс табулирования функции F2 (x = y3) приведен в табл. 2, а результаты табулирования сведены в табл. 3.
Таблица 3
| x= у3 | |||
| F2 (x= y3) | |||
 (x= y3)
|
Таблица 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  + bx + c + h2y3 + F1(y2)
| |||
| 0 £ y3 £ 2 | x = y3 | 0 £ x2 £ 1 + +y3 | x2 | y2=y3+1- x2 | W2(x2, y3) = 4x22 + x2 + 2 + 3у3 +F1(y2) | |||
| y3 = 0 | 0 £ x2 £ 1 | x2 = 0 x2 = 1 | y2=1-0=1 y2=1-1=0 | W2(0;0) = 4*02 +0+2+3×0 + F1(1) =2+76 =78 W2(1;0) = 4*12 +1+ 2+3×0 + F1(1)=7+41 =48* | ||||
| y3 = 1 | 0 £ x2 £ 2 | x2 = 0 x2 = 1 x2 = 2 | y2=2-0 =2 y2=2-1=1 y2=2-2 =0 | W2(0;1) = 4*02 +0+2 +3×1+ F1(2) = 5+119=124 W2(1;1) = 4*12 +1+2 +3×1+ F1(1) =10+76 =86 W2(2;1)= 4*22+2 +2 +3×1 +F1(0)=23+41 =64* | ||||
| y3 = 2 | .................... | ........ | ............ | ............................................................. | ||||
|
Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 (x = y4):
Вычисляем значение функции состояния только для одного значения аргумента x = у4 = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 4.
Таблица 4.
| 
| 
| 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 | W3(x3, y4) = 4 + x3 + 2 + 5y4 + F2(y3)
| |||
| 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)=4*02 + 0 +2 +5×0+F2(2)=2+88=90 W3(1;0)=4*12 + 1 +2 +5×0+F2(1)=7+64=71 W3(2;0)=4*22 + 2 +2 +5×0+F2(0)=20+48=68* |
Получаем F3 (x = y4) = min W3 (x3,0) = min (90,71,68) = 68, причем минимум достигается значении переменной х3, равном ` 
3 (x = y4 = 0) = 2.
Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна 
= 32.
Рассмотрим случай, когда на последнем этапе планируем выпускать две единицы продукции =2.
Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что х3 + у3 - d3 = y4 или 2 + у3 - 2 = 0,
oткуда у3 = 0. Из таблицы (3) значений 
находим х2*=` 2 (x = y3 = 0) = 1.
Аналогично, продолжая двигаться в обратном направлении и учтя, что х2 + у2 - d2 = y3 или 1 + у2 - 1 = 0, получаем у2 = 0;
из таблицы (2) значений х1(x) находим х1*=` 1 (x = y2 = 0) = 3.
Итак, оптимальный план производства имеет вид х 1 = 3, х 2 = 1, х 3 = 2, а минимальные общие
затраты составляют 68 единиц.
Самопроверка результатов Таблица 5
| Этапы | январь | февраль | март | Итого за 3 месяца | |
| Имеем продукции к началу месяца, шт. | у1 = 0 | у2 = 0 | у3 = 0 | у1 = 0 | |
| Производим в течение месяца, шт. | х1 = 3 | х2 = 1 | х3 = 2 | х1+ х2+ х3 = 6 | |
| Отпускаем заказчикам, шт. | d1 = 3 | d2 = 1 | d3 = 2 | d1+ d2+ d3 = 9 | |
| Остаток к концу месяца (храним в течение текущего месяца), шт. | у2 = 0 | у3 = 0 | у4 = 0 | ||
| Затраты на производство, руб. | j(х1)=41 | j(х2)=7 | j(х3)=20 | j(х1) + j(х2) + j(х3) = 68 | |
| Затраты на хранение, руб. | h1у2 = 0 | h2у3 = 0 | h1у2 + h2у3 = 0 |
Полезна самопроверка полученного результата. Для этого по исходным данным и найденному плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом этапе выполняются у1 + х1 ³ d1 у2 + х2 ³ d2 у3 + х3 ³ d3
0 + 3 ³ 3 0 + 1 ³ 1 0 + 2 ³2
и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности у1 + х1 + х2 + х3 = d1 + d2 + d3
0 + 3 + 1 + 2 = 3 + 1 + 2
причем это достигается при наименьших возможных затратах на производство и хранение продукции
j(х1) + j(х2) + j(х3) + h1у2 + h2у3 = F3(y4=0)
41 + 7 + 20 + 0 + 0 = 68.