§9. Динамическая задача управления производством и 24запасами
Предприятие производит партиями некоторые изделия. Предположим, что оно получило заказы на 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) методом динамического программирования. Введем параметр состояния и составим функцию состояния.
За параметр состояния примем наличный запас в конце k -го месяца = yk+1 (7)
а функцию состояния Fk() определим как минимальные затраты за первые k месяцев при выполнении условия (5) (8)
где минимум берется по неотрицательным целым значениям x1,...,xk, удовлетворяющим условиям
xj + yj - dj = yj+1 j = 1, k-1 (9)
xk + yk - dk = (10)
Учитывая, что
(11)
и величина запаса yk к концу (k-1) периода, как видно из уравнения (10), равна yk = + dk - xk (12)
приходим к рекуррентному соотношению
(13)
где минимум берется по единственной переменной xk, которая, согласно (6) может изменяться в пределах 0 xk dk + (14)
принимая целые значения, причем верхняя граница зависит от значений параметра состояния, изменяющегося в пределах 0 dk+1 + dk+2 + ... + dn (15)
а индекс k может принимать значения k = 2, 3, 4, ... , n (16)
Если k=1, то F1( = y2) = min f1(x1, ) (17)
x1
где x1 = + d1 - y1 (18)
0 d2 + d3 + ... + dn (19)
т.е. на начальном этапе при фиксированном уровне y1 исходного запаса каждому значению параметра отвечает только одно значение переменной x1, что несколько уменьшает объем вычислений.
Применив известную вычислительную процедуру динамического программирования, на последнем шаге (при k = n) находим значение последней компоненты xn* оптимального решения, а остальные компоненты определяем как (20)
Рассмотрим более подробно функции затрат fj(xj, yj+1) и рекуррентные соотношения. Пусть j(xj) = axj2 + bxj + c
j (xj) - затраты на производство (закупку) xj единиц продукции на этапе j; hj - затраты на хранение единицы запаса, переходящей из этапа j в этап j+1. Тогда затраты на производство и хранение на этапе j равны
fj(xj, yj+1) = 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)
Е (27)
(30) (29) (28)
Остается заметить, что полезно обозначить выражение в фигурных скобках через
k(xk, yk+1) = axj2 + bxj + c + hkyk+1 + Fk-1(yk) (31)
и записать рекуррентное соотношение (22) в виде Fk(=yk+1) = min k(xk, yk+1) (32)
xk
где минимум берется по целочисленной переменной xk, удовлетворяющей условию (25).
Пример. Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй – d2=2, на третий - d3=4 единицы. К началу первого этапа на складе имеется только 2 единицы продукции, т.е. начальный уровень запаса равен y1=2. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=1, h2=3, h3=2. Затраты на производство xj единиц продукции на j-м этапе определяются функцией j(xj) = xj2 + 5xj + 2 (33)
т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
Исходные данные задачи можно кратко записать одной строкой:
d1 d2 d3 a b c h1 h2 h3 y1
1 2 4 1 5 2 1 3 2 2
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F1 ( = y2), F2 ( = y3), ..., Fk ( = yk+1), ... и соответственно находим 1 (= y2), 2 ( = y3 ), ..., k ( = yk+1), ...
Положим k = 1. Согласно (27) имеем (34)
Учтем, что согласно (28) параметр состояния = у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 непосредственно следует, что объем производства связан со значением параметра состояния = у2 соотношением
x1 = y2 + d1 - y1 = y2 + 3 - 2 = y2 +1 (35)
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому F1( = y2) = 1 (x1, y2)
Придавая у2 различные целые значения от 0 до 6 и учитывая (35), находим
y2 = 0, x1 = 0+1 = 1, 1 (1;0) = 12 + 51 + 2 + 10 = 8
y2 = 1, x1 = 1+1 = 2, 1 (2;1) = 22 + 52 + 2 + 11 = 17
и т.д. Значения функции состояния F1( ) представлены в табл. 1
Таблица 1
= y2 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
F1 ( = y2) | 8 | 17 | 28 | 41 | 56 | 73 | 92 |
x1(=y2) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию
F2( = y3) с помощью соотношения (32)
(37)
Здесь минимум берется по единственной переменной х2, которая может изменяться, согласно (25), в пределах 0 x2 d2 + y3 или 0 x2 2 + y3 (38)
где верхняя граница зависит от параметра состояния = у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, будем последовательно вычислять 2 (x2, ), а затем определять F2( ) и 2( ).
Положим, например = у3 = 2. Тогда, согласно (38), 0 x2 4, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (40): у2 = 4 - х2
Последовательно находим:
если x2 = 0, то y2 = 4-0 = 4, 2 (0,2) = 02 + 50 + 2 + 32 + F1(4) = 8 + 56 = 64,
x2 = 1, y2 = 4-1 = 3, 2 (1,2) = 12 + 51 + 2 + 32 + F1(3) = 14 + 41 = 55,
x2 = 2, y2 = 4-2 =2, 2 (2,2) = 22 + 52 + 2 + 32 + F1(2) = 22 + 28 = 50,
x2 = 3, y2 = 4-3 = 1, 2 (3,2) = 3 + 53 + 2 + 32 + F1(1) = 32 + 17 = 49*,
x2 = 4, y2 = 4-4 = 0, 2 (3,2) = 42 + 54 + 2 + 32 + F1(0) = 44 + 8 = 52.
Н
F2 ( = y3 = 2) = min 2 (x2,2) = min (64, 55, 50, 49, 52) = 49,
x2
причем минимум достигается при значении х2, равном 2 ( = y3 = 2) = 3
Аналогично для значения параметра = у3 = 3, проведя необходимые вычисления, найдем
F2 ( = y3 = 3) = 63; 2 ( = y3 = 3) = 3.
Процесс табулирования функции F2(= y3) приведен в табл. 2, а результаты табулирования сведены в табл. 3.
Таблица 3
-
= у3
0
1
2
3
4
F2 (= y3)
24
36
49
63
78
(= y3)
2
2
3
3
4
Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 ( = y4):
Вычисляем значение функции состояния только для одного значения аргумента = у4 = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. Процесс вычислений приведен в табл. 4. Получаем F3 ( = y4) = min 3 (x3,0) = min (80, 71, 65, 62, 62) = 62, причем минимум достигается при двух значениях переменной х3, равных 3 ( = y4 = 0) = 3 или 3 ( = y4 = 0) = 4.
Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна = 3 или= 4.
Рассмотрим случай, когда на последнем этапе планируем выпускать три единицы продукции = 3.
Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что х3 + у3 - d3 = y4 или 3 + у3 - 4 = 0,
oткуда у3 = 1. Из таблицы (3) значений находим
Аналогично, продолжая двигаться в обратном направлении и учтя, что х2 + у2 - d2 = y3
Таблица 2 | xk | yk=yk+1+ + dk-xk | k(xk, yk+1) =k(xk) + + hkyk+1 + Fk-1(yk) |
| ||
0 y3 d3 | = y3 | 0 x2 d2 + + y3 | x2 | y2=y3+d2- - x2 | 2(x2, y3) = a + bx + c + h2y3 + F1(y2) | |
0 y3 4 | = 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 | 2(0;0) = 02 +50+2+30 + F1(2) =2+28 =30 2(1;0) = 12 + 51 + 2 +30 + F1(1)=8+17 =25 2(2;0) = 22 +52 + 2 + 30 +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 | 2(0;1) = 02 +50 +2 +31+ F1(3) = 5+41=46 2(1;1) = 12+51+2 +31+ F1(2) =11+28 =39 2(2;1)=22 +52 +2 +31 +F1(1)=19+17 =36* 2(3;1) = 32 +53 +2 +31+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 | 2(0;3) =02 + 50+2+33+F1(5) = 11+73=84 2(1;3) =12+51+2+33 +F1(4) =17+56 =73 2(2;3) =22 +52+2+33+F1(3)=25+41 =66 2(3;3)=32 +53+2+33+F1(2)=35+28 =63* 2(4;3) =42 +54+2+33+ F1(1)=47+17 =64 2(5;3) = 52+55+2 + 33 + 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 | 2(0;4)=02+50+2+34+F1(6) = 14+92=106 2(1;4)=12 +51+ 2+34+F1(5) =20+73 =93 2(2;4) =22+52+2+34+ F1(4)=28+56 =84 2(3;4) =32 +53+2+34+F1(3)=38+41 =79 2(4;4) =42+54+2 +34+F1(2)=50+28 =78* 2(5;4) = 52+55+ 2+34+F1(1)=64+17 =81 2(6;4) =62+56+2+34+F1(0)=80+8 =88 |
Таблица 4
K=3 | xk | yk =yk+1 + + dk - xk | k(xk, yk+1) = k(xk) + hkyk+1 + Fk-1(yk) |
| ||
0y40 | =y4 | 0 x3 d3 + y4 | x3 | y3 = y4 + +d3-x3 | 3(x3, y4) = a + bx3 + c + h3y4 + F2(y3) | |
y4 = 0 | = 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 | 3(0;0)=02 + 50 +2 +20+F2(4)=2+78=80 3(1;0)=12 +51+2+20+F2(3)=8+63=71 3(2;0)=22+52+2+20 + F2(2)=16+49=65 3(3;0)=32+53+2+20+F2(1)=26+36=62* 3(4;0)=42+54+2+20+ 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 |
| |
Затраты на производство, руб. | (х1)=16 | (х2)=16 | (х3)=26 | (х1) + (х2) + (х3) = 58 | |
Затраты на хранение, руб. | h1у2 = 1 | h2у3 = 3 | 0 | h1у2 + h2у3 = 4 |
или 2 + у2 - 2 = 1, получаем у2 = 1;
из таблицы (2) значений х1() находим .
Итак, оптимальный план производства имеет вид х1 = 2, х2 = 3, х3 = 3, а минимальные общие
затраты составляют 62 единицы.
Полезна самопроверка полученного результата. Для этого по исходным данным и найденному
плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом
этапе выполняются у1 + х1 d1 у2 + х2 d2 у3 + х3 d3
2 + 2 3 1 + 2 2 1 + 3 4
и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности у1 + х1 + х2 + х3 = d1 + d2 + d3 2 + 2 + 2 + 3 = 3 + 2 + 4
причем это достигается при наименьших возможных затратах на производство и хранение продукции
(х1) + (х2) + (х3) + h1у2 + h2у3 = F3(y4=0)
16 + 16 + 26 + 1 + 4 = 62
Студенту рекомендуется найти другой вариант оптимальной производственной программы, когда на последнем этапе предполагается произвести 4 единицы продукции, и так же выполнить самопроверку.
- §1. Цели и задачи курсового проекта
- §2. Задание на курсовОй ПрОект
- §3. Организация выполнения курсовоГо ПрОекта
- §4. Линейная производственная задача
- §5. Двойственная задача
- §6. Задача о "расшивке узких мест производства"
- §7. Транспортная задача линейного программирования
- §8. Динамическое программирование. Распределение капитальных вложений
- §9. Динамическая задача управления производством и 24запасами
- §10. Матричная модель производственной программы предприятия.
- §11. Матричная игра как модель конкуренции и сотрудничества.
- §12. Анализ доходности и риска финансовых операций.
- §13. Задача формирования оптимального портфеля ценных бумаг.
- §14. Принятие решений в условиях неопределенности.
- §15. Математико-статистический анализ данных