£ xj £ dj + yj+1 (6)

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+1j = 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, то

(17)

где

x1 = x + d1 - y1(18)

0£ x £ d2 + d3 + ... + dn(19)

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

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

(20)

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

j j(xj) = axj2 + bxj + c

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

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

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

fj(xj, yj+1) = j j(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)

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

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

W k(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk)(31)

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

(32)

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

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

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй – d2=2, на третий - d3=4 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=1, h2=3, h3=2. Затраты на производство xj единиц продукции на j-м этапе определяются функцией

j j(xj) = xj2 + 5xj + 2 (33)

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

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

d1 d2 d3 a b c h1 h2 h3y1

1 2 4 15 2 1 3 22

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

F1 (x = y2), F2 (x = y3), ..., Fk (x = yk+1), ... и соответственно находим 1 (x = y2), 2 (x = y3 ), ..., ` k (x = yk+1), ...

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

(34)

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

0 у2 d2 + d3

0 y2 2 + 4

т.е.

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

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

0 х1 3 + у2

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

х1 + у1 - d1 = у2

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

x1 = y2 + d1 - y1 = y2 + 3 - 2 = y2 +1(35)

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

F1(x = y2) = W 1 (x1, y2)

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

y2 = 0,x1 = 0+1 = 1,W 1 (1;0) = 12 + 5× 1 + 2 + 1× 0 = 8

y2 = 1, x1 = 1+1 = 2,W 1 (2;1) = 22 + 5× 2 + 2 + 1× 1 = 17

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

Таблица 1

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

F2(x = y3) с помощью соотношения (32)

(37)

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

0 £ x2 £ d2 + y3 или 0 £ x2 £ 2 + y3(38)

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

0 £ y3 £ d3 , т.е. 0 £ y3 £ 4(39)

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

x2 + y2 - d2 = y3

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

y2 = y3 + d2 - x2 = y3 + 2 - x2(40)

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

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