Файл: М.А. Тынкевич Многошаговые процессы принятия решений (динамическое программирование).pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 01.06.2024
Просмотров: 69
Скачиваний: 0
6
2.Лабораторная работа 2
Управление запасами в процессе конечной длительности
2.1. Постановка задачи и описание метода решения
Рассмотрим задачу разработки календарной программы выпуска некоторого изделия на плановый период из N отрезков времени, если известен точный прогноз спроса на эту продукцию.
Допустим, что продукция, изготавливаемая в течение отрезка t, может быть использована для покрытия спроса на этом отрезке и имеется возможность хранения остатка до начала очередного отрезка времени.
Требуется разработать программу, |
при которой общая сумма затрат |
|
на производство и хранение минимальна |
при условии полного и своевре- |
|
менного удовлетворения спроса. |
|
|
Обозначим через k число временных интервалов до конца процесса, |
||
через Xk - объем производства |
в периоде, отстоящем от конца процес- |
|
са на k шагов (при N=5 индекс |
k=5 соответствует первому шагу, k=4 - |
|
второму и т.п.), через Yk - уровень запаса на конец этого периода, через Ck(Xk,Yk) - функцию затрат на производство и хранение в этом периоде. Аналогично обозначим через Sk - спрос на продукцию, Rk - максимальный объем производства и Tk -максимальную емкость склада.
Если обозначить через Fk(Y) минимальные затраты в k-шаговом процессе с начальным запасом Y , а через Xk(Y) - оптимальный объем
производства на первом шаге |
такого процесса, то возникает система ре- |
|||
куррентных соотношений |
|
|
|
|
Fk(Y) = min [ Ck(Xk ,Y+Xk -Sk ) + Fk-1(Y+Xk -Sk ) ] , k = 2 ... N , |
(1) |
|||
где область минимизации определяется условиями |
|
|
||
0 ≤ Xk ≤ |
Rk , 0 ≤ Y+Xk -Sk ≤ Tk . |
|
(2) |
|
При одношаговом процессе очевидна политика: производить лишь |
||||
минимум продукции, необходимый для покрытия спроса, т.е. |
|
|||
F1 (Y) = C1 (S1 -Y,0) , |
X1 (Y) = S1 -Y |
при Y ≤ |
S1 ; |
(3) |
F1 (Y) = C1 (0,Y-S1 ) , |
X1(Y) = 0 |
при Y ≥ |
S1 . |
|
2.2. Пример решения задачи
Возьмем пример с |
характеристиками, |
|||
временного интервала: |
|
|
|
|
C k (X,Y) = C k(X) + H k(Y), |
||||
|
A + B X |
, X > |
0 |
, |
Ck ( X )= C( X )= |
0 |
, X = |
0 |
|
|
|
|||
независимыми от номера
H k (Y) = H× Y , |
(4) |
7
A=13 , B=2 , H=1 , Rk =5, Tk =4, Sk =3, N = 6.
В этих условиях |
|
F1(Y) = 13 + 2× (3-Y) , |
X1(Y) = 3-Y; |
при Y ≤ |
3 |
||
при Y ≥ |
3 |
F1(Y) = 1 × (Y-3) , |
X1 (Y) = 0 ; |
F k(Y) = min [ C(X) + 1× (Y+X-3) + F k-1(Y+X-3) ] , k =2 . . 6 ,
где область минимизации определена требованиями
0 ≤ X ≤ 5 , 0 ≤ Y+X -3 ≤ 4 .
Для численного решения берем целочисленную сетку значений Y от 0 до 4 (в общем случае придется пользоваться сеткой с шагом, большим 1, и соответственно прибегать к интерполированию на очередных этапах решения).
Для k=1 имеем :
Y |
0 |
1 |
2 |
3 |
4 |
F1 (Y) |
19 |
17 |
15 |
0 |
1 |
X1 (Y) |
3 |
2 |
1 |
0 |
0 |
При k = 2 имeeм расчетную таблицу значений
С(X) + H × (Y+X-3) + F1 (Y+X-3):
Y |
X=0 |
X=1 |
X=2 |
X=3 |
X=4 |
X=5 |
F2(Y) |
X2(Y) |
0 |
|
|
|
19+0+19 |
21+1+17 23+2+15 |
38 |
3 |
|
1 |
|
|
17+0+19 |
19+1+17 |
21+2+15 23+3+0 |
26 |
5 |
|
2 |
|
15+0+19 |
17+1+17 |
19+2+15 |
21+3+0 |
23+4+1 |
24 |
4 |
3 |
0+0+19 |
15+1+17 |
17+2+15 |
19+3+0 |
21+4+1 |
|
19 |
0 |
4 |
0+1+17 15+2+15 |
17+3+0 |
19+4+1 |
|
|
18 |
0 |
|
При |
k = 3 имeeм |
|
|
|
|
|
|
|
Y |
X=0 |
X=1 |
X=2 |
X=3 |
X=4 |
X=5 |
F3(Y) |
X3(Y) |
0 |
|
|
|
19+0+38 |
21+1+26 |
23+2+24 |
48 |
4 |
1 |
|
|
17+0+38 |
19+1+26 |
21+2+24 |
23+3+19 |
45 |
5 |
2 |
|
15+0+38 |
17+1+26 |
19+2+24 |
21+3+19 |
23+4+18 |
43 |
4 |
3 |
0+0+38 |
15+1+26 |
17+2+24 |
19+3+19 |
21+4+18 |
|
38 |
0 |
4 |
0+1+26 |
15+2+24 |
17+3+19 |
19+4+18 |
|
|
27 |
0 |
|
|
|
|
|
|
|
|
|
Аналогичный расчет дает сводную таблицу F k(Y) , X k(Y) при всех k .
|
Y |
|
F1(Y) X1(Y) |
F2(Y) |
X2(Y) |
F3(Y) X3(Y) |
F4(Y) |
X4(Y) |
F5(Y) X5(Y) |
F6(Y) X6(Y) |
||||||
|
0 |
|
19 |
3 |
38 |
3 |
48 |
4 |
67 |
3,4 |
79 |
5 |
96 |
4 |
||
|
1 |
|
17 |
2 |
26 |
5 |
45 |
5 |
64 |
5 |
|
74 |
5 |
93 |
5 |
|
|
2 |
|
15 |
1 |
24 |
4 |
43 |
4 |
54 |
5 |
|
72 |
4 |
91 |
4 |
|
|
3 |
|
0 |
0 |
19 |
0 |
38 |
0 |
48 |
0 |
|
67 |
0 |
79 |
0 |
|
|
4 |
|
1 |
0 |
18 |
0 |
27 |
0 |
46 |
0 |
|
65 |
0 |
75 |
0 |
|
|
|
Если принять уровень запаса на начало процесса равным 0, то |
||||||||||||||
оптимальные объемы |
производства по периодам от начала процесса |
|||||||||||||||
равны: |
X |
= X (0) = 4 , |
X |
= X (0+4-3) = 5 , |
X |
3 |
= X (1+5-3) = 0 , |
|
||||||||
|
|
|
1 |
6 |
|
2 |
5 |
|
|
|
|
4 |
|
|
|
|
X5 = X2 (0+4-3) = 5 , X6 = X1(1+5-3) = 0 .
8
2.3. Контрольные задания
2.3.1. Требования
1. Ознакомьтесь с постановкой задачи и подходом к ее решению методом рекуррентных соотношений.
2.Выберите вариант контрольного задания и выполните его. Оцените полученное оптимальное решение с позиций здравого смысла.
3.Постройте рекуррентные соотношения и оцените соответствующие упрощения (усложнения) для следующих видоизменений задачи:
- к следующему периоду (сезону) сохраняемая продукции на складе уменьшается на P %;
- функция затрат на производство X и сохранение Z единиц продук-
ции линейная: Ck(X,Z)=Ck× X+Hk× Z .
2.3.2. Варианты заданий
№ |
Tk |
Rk |
|
|
Спрос по сезонам |
|
|
A |
B |
H |
|||
|
1 |
2 |
|
3 |
4 |
|
5 |
6 |
|||||
|
|
|
|
|
|
|
|
||||||
1 |
4 |
5 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
15 |
2 |
3 |
2 |
4 |
5 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
17 |
3 |
4 |
3 |
4 |
5 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
17 |
3 |
4 |
4 |
4 |
5 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
12 |
3 |
3 |
5 |
5 |
6 |
4 |
4 |
|
3 |
4 |
|
4 |
3 |
15 |
2 |
1 |
6 |
5 |
6 |
4 |
3 |
|
3 |
4 |
|
3 |
3 |
15 |
2 |
1 |
7 |
5 |
6 |
3 |
4 |
|
4 |
3 |
|
4 |
4 |
15 |
2 |
3 |
8 |
6 |
5 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
20 |
2 |
4 |
9 |
6 |
5 |
4 |
3 |
|
4 |
3 |
|
4 |
3 |
20 |
6 |
4 |
10 |
6 |
4 |
2 |
4 |
|
2 |
4 |
|
2 |
4 |
20 |
6 |
4 |
11 |
5 |
4 |
4 |
2 |
|
4 |
2 |
|
4 |
2 |
20 |
6 |
4 |
12 |
5 |
4 |
4 |
2 |
|
4 |
2 |
|
4 |
2 |
15 |
2 |
3 |
13 |
5 |
4 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
15 |
2 |
3 |
14 |
6 |
6 |
2 |
3 |
|
2 |
3 |
|
2 |
3 |
25 |
3 |
2 |
15 |
6 |
6 |
3 |
4 |
|
5 |
3 |
|
4 |
5 |
15 |
3 |
2 |
16 |
5 |
6 |
4 |
3 |
|
5 |
4 |
|
3 |
5 |
15 |
3 |
2 |
17 |
5 |
6 |
1 |
5 |
|
1 |
5 |
|
1 |
5 |
20 |
3 |
3 |
18 |
5 |
4 |
5 |
3 |
|
1 |
5 |
|
3 |
1 |
17 |
2 |
3 |
19 |
5 |
4 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
17 |
3 |
3 |
20 |
6 |
6 |
3 |
3 |
|
5 |
3 |
|
3 |
5 |
20 |
3 |
2 |
21 |
5 |
5 |
3 |
4 |
|
2 |
3 |
|
4 |
2 |
21 |
2 |
4 |
22 |
5 |
5 |
4 |
4 |
|
4 |
4 |
|
4 |
3 |
17 |
2 |
3 |
23 |
5 |
6 |
2 |
4 |
|
2 |
4 |
|
2 |
4 |
20 |
2 |
3 |
24 |
5 |
6 |
3 |
2 |
|
3 |
2 |
|
3 |
2 |
19 |
3 |
2 |
25 |
5 |
6 |
6 |
6 |
|
4 |
6 |
|
6 |
4 |
17 |
2 |
1 |
26 |
4 |
6 |
3 |
4 |
|
3 |
4 |
|
3 |
4 |
17 |
2 |
1 |
27 |
4 |
6 |
3 |
5 |
|
3 |
5 |
|
3 |
5 |
20 |
2 |
4 |
28 |
4 |
7 |
5 |
6 |
|
5 |
6 |
|
5 |
6 |
17 |
2 |
3 |
29 |
4 |
7 |
6 |
5 |
|
6 |
5 |
|
6 |
5 |
17 |
2 |
3 |
30 |
6 |
5 |
1 |
8 |
|
1 |
8 |
|
1 |
8 |
15 |
4 |
5 |
9
3.Лабораторная работа 3
Управление запасами в бесконечношаговом процессе
3.1. Постановка задачи и описание метода решения
При рассмотрении конечношагового процесса управления запасами проблема минимизации затрат на производство и хранение продукции для удовлетворения спроса сводилась к системе рекуррентных соотношений
Fk(Y) = min [ Ck(Xk ,Y+Xk -Sk ) + Fk-1(Y+Xk -Sk ) ] , k = 2 ... N , |
(1) |
где область минимизации определяется условиями |
|
0 ≤ Xk≤ Rk , 0 ≤ Y+Xk -Sk ≤ Tk . |
(2) |
При спросе и других характеристиках задачи (емкость склада, мак- |
|
симальный объем производства, стоимостные оценки), неизменных во времени, и больших N процесс явно становится стационарным и оптимальная политика независимой от N.
Если обозначить через F(Y) величину интегрального дисконтированного эффекта (ИДЭ) при начальном запасе Y и использовании оптимальной
политики, то возникает функциональное уравнение |
|
F(Y) = min [ C( X ,Y+X - S) + α F(Y+X - S) ] , |
(3) |
где α - коэффициент дисконтирования и область минимизации определяет-
ся условиями 0 ≤ X ≤ R , 0 ≤ Y + X- S ≤ T .
Поставленную задачу при дискретных спросе и объемах складирования и производства можно интерпретировать как систему переходов меж-
ду состояниями (уровнями запаса). |
|
|
|
||
Если обозначить Y через |
i, |
F(Y) через |
F(i), Y+X- S |
через j и |
|
C( X ,Y+X - S) через Сij, то Сi j |
мoжно понимать как затраты на переход из |
||||
состояния i в состояние j и |
функциональное уравнение (3) переписать в |
||||
виде: |
|
|
|
|
|
F(i) = min [ Сi j |
+ |
F( j ) ] , |
i = 0, 1, . . ,T . |
(4) |
|
j |
|
|
|
|
|
Естественно ожидать, что по прошествии некоторого времени значения очередных затрат стабилизируются на каком-то среднем уровне. Поэтому обозначим через C средние затраты (СЭ) и через Fi - составляющие затрат, определяемые начальным состоянием (запасом). С учетом взаимо-
связи между ИДЭ и СЭ примем : |
|
|
и при α = 1 |
F(i) = Fi + C / ( 1-α ) |
(5) |
уравнения (4) примут вид: |
|
|
|
Fi + C = min [ Сi j + Fj ] , |
i = 0, 1, . . ,T . |
|
j |
|
Решение |
этих уравнений осуществляется приближением в поведе- |
|
ниях. |
|
|