Файл: М.А. Тынкевич Многошаговые процессы принятия решений (динамическое программирование).pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 01.06.2024
Просмотров: 62
Скачиваний: 0
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра вычислительной техники и информационных технологий
МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ
(ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ)
Методические указания и задания к циклу практических занятий по курсам
“Исследование операций в экономике” и “Экономико-математические методы”
для студентов экономических специальностей
Составитель М.А.Тынкевич О.А.Бияков
Утверждены на заседании кафедры вычислительной техники и информационных технологий Протокол № 5 от 16.01.2001
Рекомендованы к печати учебно-методической комиссией по специальности 351400 Протокол № 2 от 16.01.2001
Кемерово 2001
1
1. Лабораторная работа 1
Задача складирования однородного продукта
1.1. Постановка задачи и описание метода решения
Предлагаемая для рассмотрения задача существенно идеализирует реальность, но дает возможность прекрасной иллюстрации метода динамического программирования (построение рекуррентных соотношений и тем самым сведение многомерной задачи оптимизации к последовательности задач меньшей размерности; аналитическое решение рекуррентных соотношений и выявление структуры полученного решения).
Пусть имеется склад вместимости В с начальным запасом V некоторого продукта, цены на который подвержены сезонным изменениям.
В начале i-го сезона часть продукта Yi можно продать по цене Pi и
в конце сезона закупить Xi этого продукта по цене Ci . Образовавшийся на складе запас хранится до следующего сезона. Найти политику продажипокупки, максимизирующую суммарный доход за N сезонов.
Если пренебречь затратами на хранение, то задачу можно свести к максимизации линейной функции
∑N [ Pi Yi |
- Ci X i ] |
( 1 ) |
|
i= |
1 |
|
|
при условиях |
|
|
|
0≤ Y1≤ V, |
X1≥ 0, |
V1=V-Y1+X1≤ B; |
|
0≤ Y2≤ V1, |
X2≥ 0, |
V2=V1-Y2+X2≤ B; |
( 2 ) |
0≤ Y3≤ V2, |
X3≥ 0, |
V3=V2-Y3+X3≤ B; …. |
|
Таким образом получена задача линейного программирования с 2N |
|||
неизвестными и 4N ограничениями, |
которую можно решить при фикси- |
||
рованном значении V. |
|
|
|
Рассмотрим задачу с других позиций, для чего введем обозначения:
-k - номер сезона, отстоящего на k шагов до конца N-шагового процесса (k=1 соответствует последнему сезону, k=2 - предпоследнему, k=N - первому);
-Y , X - объемы продажи-покупки в соответствующем сезоне (в первом из k оставшихся сезонов);
-Pk ,Ck - цены продажи-покупки в соответствующем сезоне;
-Fk(V) - максимальный доход в k-шаговом процессе при начальном запасе V;
-Yk(V) , Xk(V) - оптимальные объемы продажи-покупки на первом шаге k- шагового процесса с начальным запасом V.
2
В случае одношагового процесса (с таковым мы столкнемся, если доберемся до последнего шага и к тому же будем знать уровень запаса V перед этим шагом)
F1 (V) = max { P1 Y - C1 X } , |
( 3 ) |
где область максимизации определяется условиями 0 ≤ Y ≤ V ; X ≥ |
0 . |
Очевидно, что максимум достигается при Y = V и X=0 (естественно при завершении деятельности по купле-продаже продать весь запас и ничего не покупать), т.е.
F1(V) = P1V ; Y1(V) =V ; X1(V) = 0 .
Обратимся к случаю k-шагового процесса при k > 1, повторив традиционные рассуждения с позиций известного принципа оптимальности Р.Беллмана. Очевидно, что доход в k - шаговом процессе складывается
из дохода на первом шаге { PkY - CkX } и дохода на оставшихся k-1 шагах. Если мы желаем действовать оптимально, то обязаны руководствоваться принципом оптимальности: независимо от начального состояния (запаса V) и начального поведения (объемов Y, X продажи-покупки на первом шаге) дальнейшая политика должна быть оптимальной, исходя из возникающего состояния (запаса V-Y+X). Тогда доход на оставшихся k-1
шагах будет равен Fk-1(V-Y+X) и |
|
|
|
|
|
|
|
|
|
||||
Fk(V) = max { PkY - Ck X + Fk-1(V-Y+X) } , k = 2 .. N , |
|
( 4 ) |
|||||||||||
где область максимизации определяется условиями: |
|
|
|
|
|
||||||||
|
|
|
0 ≤ Y ≤ V ; X ≥ 0 ; V -Y + X ≤ B . |
|
|
( 5 ) |
|||||||
Легко |
видеть, что множество |
планов – выборов для начального по- |
|||||||||||
ведения (область максимизации) при любом k - |
многоугольник с коор- |
||||||||||||
динатами вершин, линейно зависящими от V. |
|
|
|
|
|
|
|||||||
|
|
|
|
Учитывая линейность по V |
функции |
||||||||
|
|
|
|
F1(V) = P1V , при поиске |
F2(V) |
мы |
стал- |
||||||
|
|
|
|
киваемся с максимизацией |
функции, |
ли- |
|||||||
|
|
|
|
нейной по X и Y , над указанным множе- |
|||||||||
|
|
|
|
ством |
планов, т.е. |
с задачей линейного |
|||||||
|
|
|
|
программирования |
c экстремумами в вер- |
||||||||
|
|
|
|
шинах множества. Можно показать, что |
|||||||||
аналогичное явление наблюдается при любом k>1. |
Cоответственно, ре- |
||||||||||||
куррентные соотношения (4) упрощается к виду: |
|
|
|
|
|
|
|||||||
|
|
|
Fk -1(V) |
|
; Yk (V) = 0 ; |
X k (V)= 0 |
|
|
|||||
|
|
|
PkV + Fk -1(0) |
; Yk (V)=V ; X k (V)= 0 |
|
|
|||||||
|
|
|
|
|
|||||||||
Fk (V)= max |
- C |
k |
(B − V)+ F |
(B) |
; Y |
k |
(V)= 0 ; X |
k |
(V)= B - V |
; k=2,..,N |
|||
|
|
k -1 |
|
|
|
|
|
|
|
|
|||
|
|
|
PkV - Ck B + Fk -1(B) |
; Yk (V)=V ; X k (V)= B |
|
|
|||||||
|
|
|
|
|
|||||||||
Так исходная задача линейного программирования с 2N |
неизвест- |
||||||||||||
ными сведена к |
|
N элементарным линейным программам с двумя неиз- |
|||||||||||
вестными. Более того, здесь мы имеем решение при произвольных V и B.
|
|
3 |
|
|
|
|
|
1.2. Пример решения задачи |
|
|
|
|
|
|
|
Пусть N = 5 и цены определяются таблицей |
|
||||||
|
Сезон |
|
1 |
2 |
3 |
4 |
5 |
|
Продажная цена(P) |
|
7 |
6 |
4 |
4 |
8 |
|
Закупочная цена (С) |
|
6 |
7 |
5 |
3 |
5 |
Решение задачи дает: |
|
||||||
|
F1(V) = 8 V ; |
|
|
Y1(V) =V; X1(V)=0; |
|||
|
|
|
|
|
|
F1(V)= 8 V |
|
|
|
|
|
|
4 V + F1(0)= 4 V |
|
|
|
|
|
|
|
=4V+5B; Y2(V)=V; X2(V)=B; |
||
F2 |
(V)= max |
|
− |
3(B |
− |
V)+ F (B)= 3V + 5 B |
|
|
|
|
|
|
|
1 |
|
|
|
|
4 V - 3 B + F (B)= 4 V + 5 B |
|
|||
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
F2 (V)= 4 V + 5 B |
|
|
|
|
|
4 V + F2 (0)= 4 V + 5 B |
|
||
|
|
|
|
=4V+5B; Y3(V)=0,V; X3(V)=0; |
|||
F3 |
(V)= max |
− |
5(B |
− |
V)+ F (B)= 5V + 4 B |
||
|
|
|
|
|
|
2 |
|
|
|
|
4 V - 5 B + F (B)= 4 V + 4 B |
|
|||
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
F3 (V)= 4 V + 5 B |
|
|
|
|
|
6 V + F3 (0)= 6 V + 5 B |
|
||
F4 (V)= max |
|
|
=6V+5B;Y4(V)=V ; X4(V)=0 ; |
||||
|
− |
7(B |
− |
V)+ F (B)=7 V + 2 B |
|||
|
|
|
|
|
|
3 |
|
|
|
|
6 V -7 B + F (B)= 6 V + 2 B |
|
|||
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
F4 (V)= 6 V + 5 B |
|
|
|
|
|
7 V + F4 (0)=7 V + 5 B |
|
||
|
|
|
|
=7V+5B;Y5(V)=V; X5(V)=0, B.. |
|||
F5 |
(V)= max |
− |
6(B |
− |
V)+ F (B)= 6 V + 5 B |
||
|
|
|
|
|
|
4 |
|
|
|
|
7 V - 6 B + F (B)=7 V + 5 B |
|
|||
|
|
|
|
|
|
4 |
|
|
Отсюда искомый максимум дохода в 5-шаговом процессе при на- |
|
чальном запасе V равен F5(V) = 7V+5B |
и оптимальная политика по |
|
шагам определяется следующей последовательностью действий . |
||
1. Объем продажи = Y5(V)=V |
- весь запас. |
|
|
Объем закупок = X5(V) = 0 или B |
- ничего или полный склад. |
2. |
Объем продажи = Y4(0 или B)=0 или B - весь запас, если он есть. |
|
|
Объем закупок = X4(0 или B)=0 |
- ничего не покупать . |
3. |
Объем продажи = Y3(0)=0 |
- можно все продать, но нечего. |
|
Объем закупок = X3(0)=0 |
- ничего не покупать . |
4. |
Объем продажи = Y2(0)=0 |
- продать запас, но его нет. |
|
Объем закупок = X2(0)=B |
- закупить полный склад. |
5. |
Объем продажи = Y1(B) =B |
- продать весь запас. |
|
Объем закупок = X1(V) |
- ничего не покупать. |
4
Обратите внимание на правила построения оптимальной политики, т. к. использованный подход типичен для решения всех подобных задач.
1.3. Контрольные задания
1.3.1. Требования
1. Ознакомьтесь с постановкой задачи и подходом к ее решению методом рекуррентных соотношений.
2.Выберите вариант контрольного задания и выполните его решение. Оцените полученное оптимальное решение с позиций здравого смысла.
3.Постройте рекуррентные соотношения и выясните структуру решения для следующих видоизменений задачи:
- хранение продукции на складе сопровождается затратами, пропорциональными хранимому объему;
- хотя бы половина имеющегося запаса на каждом этапе должна быть продана ;
- объем закупки на каждом этапе не должен превышать емкости склада.
1.3.2. Варианты заданий
В первой строке каждого варианта – продажная, во второй – закупочная цены. Число сезонов N=8.
№ |
|
|
|
Сезоны |
|
|
|
№ |
|
|
|
Сезоны |
|
|
|
||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
12 |
18 |
14 |
15 |
10 |
17 |
14 |
16 |
2 |
18 |
24 |
10 |
10 |
9 |
6 |
10 |
24 |
|
8 |
14 |
7 |
12 |
8 |
7 |
9 |
10 |
|
15 |
2 |
10 |
22 |
8 |
9 |
15 |
18 |
3 |
14 |
21 |
19 |
15 |
9 |
16 |
20 |
13 |
4 |
7 |
4 |
8 |
2 |
4 |
20 |
18 |
1 |
|
2 |
8 |
5 |
5 |
5 |
18 |
22 |
22 |
|
1 |
5 |
16 |
11 |
12 |
24 |
9 |
17 |
5 |
19 |
10 |
18 |
20 |
1 |
4 |
9 |
19 |
6 |
18 |
13 |
7 |
22 |
21 |
23 |
24 |
21 |
|
24 |
7 |
6 |
4 |
21 |
23 |
18 |
7 |
|
20 |
11 |
22 |
15 |
21 |
17 |
12 |
24 |
7 |
4 |
7 |
15 |
18 |
5 |
19 |
13 |
2 |
8 |
12 |
15 |
1 |
18 |
2 |
8 |
14 |
5 |
|
2 |
19 |
15 |
12 |
15 |
11 |
3 |
14 |
|
12 |
2 |
11 |
9 |
12 |
10 |
19 |
19 |
9 |
13 |
21 |
17 |
23 |
24 |
4 |
7 |
4 |
10 |
7 |
15 |
20 |
20 |
16 |
23 |
3 |
3 |
|
17 |
14 |
13 |
20 |
12 |
23 |
3 |
12 |
|
6 |
12 |
8 |
12 |
19 |
2 |
11 |
2 |
11 |
10 |
7 |
9 |
16 |
20 |
1 |
10 |
22 |
12 |
1 |
12 |
16 |
9 |
12 |
10 |
22 |
14 |
|
20 |
20 |
6 |
16 |
13 |
5 |
5 |
11 |
|
7 |
9 |
18 |
15 |
22 |
9 |
23 |
17 |
13 |
13 |
10 |
13 |
8 |
20 |
8 |
3 |
9 |
14 |
2 |
17 |
4 |
14 |
22 |
4 |
24 |
8 |
|
24 |
23 |
1 |
5 |
21 |
18 |
2 |
5 |
|
17 |
9 |
7 |
20 |
11 |
3 |
7 |
2 |
15 |
8 |
17 |
10 |
3 |
10 |
24 |
23 |
9 |
16 |
12 |
6 |
1 |
3 |
20 |
18 |
3 |
2 |
|
18 |
4 |
22 |
18 |
24 |
17 |
3 |
4 |
|
16 |
10 |
3 |
13 |
17 |
7 |
18 |
9 |
17 |
18 |
21 |
20 |
1 |
16 |
10 |
2 |
15 |
18 |
23 |
17 |
20 |
1 |
10 |
16 |
3 |
4 |
|
10 |
17 |
20 |
5 |
1 |
13 |
4 |
5 |
|
8 |
21 |
16 |
2 |
7 |
2 |
4 |
13 |
19 |
18 |
20 |
4 |
4 |
23 |
6 |
15 |
6 |
20 |
21 |
11 |
3 |
24 |
19 |
7 |
13 |
12 |
|
15 |
4 |
24 |
13 |
13 |
4 |
12 |
11 |
|
12 |
2 |
8 |
11 |
8 |
7 |
24 |
12 |
5
№ |
|
|
|
Сезоны |
|
|
|
№ |
|
|
|
Сезоны |
|
|
|
||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
21 |
10 |
3 |
10 |
2 |
16 |
7 |
4 |
15 |
22 |
9 |
5 |
17 |
24 |
22 |
15 |
17 |
1 |
|
5 |
14 |
23 |
2 |
15 |
3 |
8 |
7 |
|
15 |
2 |
7 |
10 |
13 |
10 |
15 |
6 |
23 |
14 |
19 |
14 |
8 |
22 |
20 |
21 |
1 |
24 |
9 |
3 |
18 |
16 |
19 |
14 |
6 |
24 |
|
1 |
3 |
5 |
13 |
22 |
22 |
1 |
11 |
|
19 |
9 |
10 |
5 |
15 |
17 |
16 |
5 |
25 |
19 |
1 |
19 |
2 |
22 |
6 |
18 |
9 |
26 |
21 |
21 |
11 |
5 |
22 |
13 |
19 |
2 |
|
6 |
19 |
2 |
15 |
5 |
9 |
7 |
3 |
|
9 |
17 |
22 |
2 |
19 |
1 |
21 |
3 |
27 |
22 |
8 |
22 |
11 |
12 |
5 |
19 |
12 |
28 |
23 |
23 |
6 |
22 |
22 |
20 |
17 |
8 |
|
6 |
12 |
3 |
18 |
23 |
10 |
6 |
3 |
|
24 |
19 |
15 |
19 |
11 |
4 |
4 |
17 |
29 |
17 |
3 |
9 |
15 |
23 |
12 |
21 |
10 |
30 |
10 |
4 |
14 |
13 |
24 |
22 |
19 |
12 |
|
21 |
22 |
18 |
21 |
9 |
14 |
14 |
8 |
|
7 |
8 |
11 |
18 |
21 |
5 |
5 |
9 |
31 |
13 |
22 |
17 |
17 |
23 |
18 |
22 |
11 |
32 |
24 |
12 |
9 |
15 |
23 |
6 |
11 |
18 |
|
9 |
3 |
24 |
3 |
10 |
24 |
21 |
14 |
|
9 |
19 |
21 |
21 |
16 |
21 |
21 |
11 |
33 |
9 |
21 |
23 |
12 |
22 |
14 |
15 |
19 |
34 |
1 |
22 |
19 |
24 |
10 |
15 |
9 |
19 |
|
19 |
14 |
24 |
20 |
14 |
17 |
27 |
5 |
|
19 |
14 |
7 |
17 |
17 |
18 |
21 |
3 |
35 |
15 |
4 |
23 |
9 |
17 |
2 |
20 |
15 |
36 |
12 |
13 |
14 |
23 |
4 |
3 |
9 |
6 |
|
10 |
9 |
22 |
23 |
9 |
4 |
3 |
14 |
|
11 |
20 |
11 |
3 |
6 |
9 |
11 |
3 |
37 |
6 |
23 |
6 |
23 |
6 |
23 |
6 |
23 |
38 |
9 |
15 |
7 |
16 |
23 |
6 |
9 |
15 |
|
21 |
9 |
4 |
9 |
21 |
9 |
4 |
9 |
|
10 |
17 |
10 |
17 |
10 |
17 |
10 |
17 |
39 |
5 |
12 |
4 |
18 |
6 |
19 |
7 |
21 |
40 |
13 |
18 |
24 |
23 |
16 |
20 |
24 |
23 |
|
21 |
13 |
11 |
13 |
11 |
13 |
11 |
8 |
|
8 |
10 |
18 |
22 |
24 |
22 |
18 |
16 |
41 |
12 |
18 |
14 |
15 |
10 |
17 |
14 |
16 |
42 |
18 |
24 |
10 |
10 |
9 |
6 |
10 |
24 |
|
9 |
14 |
8 |
13 |
8 |
7 |
9 |
10 |
|
15 |
12 |
10 |
22 |
18 |
9 |
15 |
18 |
43 |
14 |
21 |
19 |
15 |
9 |
16 |
20 |
13 |
44 |
7 |
4 |
8 |
2 |
4 |
20 |
18 |
1 |
|
2 |
8 |
15 |
15 |
15 |
18 |
22 |
22 |
|
11 |
5 |
16 |
11 |
12 |
24 |
9 |
17 |
45 |
19 |
10 |
18 |
20 |
11 |
4 |
9 |
19 |
46 |
18 |
13 |
17 |
22 |
21 |
23 |
24 |
21 |
|
14 |
7 |
6 |
4 |
21 |
23 |
18 |
7 |
|
20 |
11 |
22 |
15 |
21 |
17 |
12 |
24 |
47 |
14 |
17 |
15 |
18 |
15 |
19 |
13 |
12 |
48 |
12 |
15 |
11 |
18 |
12 |
8 |
14 |
5 |
|
12 |
19 |
15 |
12 |
15 |
11 |
8 |
14 |
|
12 |
12 |
11 |
9 |
12 |
10 |
19 |
19 |
49 |
13 |
21 |
17 |
23 |
24 |
4 |
7 |
4 |
50 |
7 |
15 |
20 |
20 |
16 |
23 |
13 |
8 |
|
17 |
15 |
23 |
20 |
12 |
23 |
3 |
12 |
|
6 |
12 |
18 |
12 |
19 |
12 |
11 |
12 |