§9. Динамическая задача управления производством и 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) методом динамического программирования. Введем параметр состояния и составим функцию состояния.

За параметр состояния  примем наличный запас в конце k -го месяца  = y_k+1 (7)

а функцию состояния F_k() определим как минимальные затраты за первые 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 =  (10)

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

(11)

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

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

(13)

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

принимая целые значения, причем верхняя граница зависит от значений параметра состояния, изменяющегося в пределах 0    d_k+1 + d_k+2 + ... + d_n (15)

а индекс k может принимать значения k = 2, 3, 4, ... , n (16)

Если k=1, то F₁( = y₂) = min f₁(x₁, ) (17)

x₁

где x₁ =  + d₁ - y₁ (18)

0   d₂ + d₃ + ... + d_n (19)

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

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

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

_j (x_j) - затраты на производство (закупку) x_j единиц продукции на этапе j; h_j - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1. Тогда затраты на производство и хранение на этапе j равны

f_j(x_j, y_j+1) = _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)

(30)

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

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

и записать рекуррентное соотношение (22) в виде F_k(=y_k+1) = min _k(x_k, y_k+1) (32)

x_k

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

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

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d₁=3 единицы, на второй – d₂=2, на третий - d₃=4 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y₁=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h₁=1, h₂=3, h₃=2. Затраты на производство x_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₁ ( = y₂), F₂ ( = y₃), ..., F_k ( = y_k+1), ... и соответственно находим ₁ (= y₂), ₂ ( = y₃ ), ..., _k ( = y_k+1), ...

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

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

0 у₂ d₂ + d₃ 0 y₂ 2 + 4 т.е. у₂ = 0, 1, 2, 3, 4, 5, 6.

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

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

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

В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у₂ отвечает единственное значение х₁ и потому F₁( = y₂) = ₁ (x₁, y₂)

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

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

y₂ = 1, x₁ = 1+1 = 2, ₁ (2;1) = 2² + 52 + 2 + 11 = 17

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

Таблица 1

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

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

(37)

Здесь минимум берется по единственной переменной х₂, которая может изменяться, согласно (25), в пределах 0  x₂  d₂ + y₃ или 0  x₂  2 + y₃ (38)

где верхняя граница зависит от параметра состояния  = у₃, который, согласно (15), принимает значения на отрезке 0  y₃  d₃ , т.е. 0  y₃  4 (39)

а аргумент у₂ в последнем слагаемом справа в соотношении (37) связан с х₂ и у₃ балансовым уравнением x₂ + y₂ - d₂ = y₃ откуда следует y₂ = y₃ + d₂ - x₂ = y₃ + 2 - x₂ (40)

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

Положим, например  = у₃ = 2. Тогда, согласно (38), 0  x₂  4, т.е. переменная х₂ может принимать значения: 0, 1, 2, 3, 4, а каждому значению х₂ отвечает определенное значение у₂, вычисляемое по формуле (40): у₂ = 4 - х₂

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

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

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

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

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

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

Н

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

x₂

причем минимум достигается при значении х₂, равном ₂ ( = y₃ = 2) = 3

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

F₂ ( = y₃ = 3) = 63; ₂ ( = y₃ = 3) = 3.

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

Таблица 3

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

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

Вычисляем значение функции состояния только для одного значения аргумента  = у₄ = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 4. Получаем F₃ ( = y₄) = min ₃ (x₃,0) = min (80, 71, 65, 62, 62) = 62, причем минимум достигается при двух значениях переменной х₃, равных ₃ ( = y₄ = 0) = 3 или ₃ ( = y₄ = 0) = 4.

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

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

Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что х₃ + у₃ - d₃ = y₄ или 3 + у₃ - 4 = 0,

oткуда у₃ = 1. Из таблицы (3) значений находим

Аналогично, продолжая двигаться в обратном направлении и учтя, что х₂ + у₂ - d₂ = y₃

Таблица 4

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

или 2 + у₂ - 2 = 1, получаем у₂ = 1;

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

Итак, оптимальный план производства имеет вид х₁ = 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

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

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

16 + 16 + 26 + 1 + 4 = 62

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