ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 529
Скачиваний: 19
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
80
Максимум этого выражения достигается на некотором значении
*
k
x
, которое и является оптимальным управлением на k-м шаге для состояния системы C
k
Аналогично можно отыскать функции Беллмана и оптимальное управление вплоть до шага k=1.
Функция Беллмана F
1
(C
1
) представляет собой максимально возможную
прибыль со всех предприятий (с 1-го по n-е), а значение
*
x
1
, на котором достигается максимум прибыли, является оптимальным количеством средств, которые необходимо вложить в 1-е предприятие.
Далее, для всех последующих шагов, вычисляется величина C
k
=C
k-1
x
k
и оптимальным управлением на k-м шаге является значение x
k
, которое доставляет максимум прибыли при соответствующем состоянии системы C
k
Пример 5.1. Распределить T=40 ден. ед. по трем предприятиям с целью получения максимальной суммарной прибыли. Прибыль с предприятий задается таблицей 5.1.2
Таблица 5.1.2
X
g
1
g
2
g
3
0
0 0
0
10
17 21 19
20
23 25 24
30
34 30 29
40
40 37 32
Решение
I этап. Условная оптимизация
1-й шаг. k=3. Предполагаем, что все средства 40 ден. ед. переданы на инвестирование третьего предприятия.
В этом случае максимальная прибыль составит F
3
(C
3
)=32 (табл. 5.1.3, рис. 5.1.1, 5.1.2).
Таблица 5.1.3
C
3
x
3
F
3
(C
3
)
0
10 20 30 40
0
0 0
0
10
19 19
10
20
24 24
20
30
29 29
30
40
32 32
40
81
Рис. 5.1.1. Реализация 1-го шага, k=3 в MS Office Excel
C
D
E
F
G
H
I
J
14
C
3
x
3
F
3
(C
3
)
X
*
3
15
0 10 20 30 40
16
0 0
=МАКС(D16:H16)
0
17
10 19
=МАКС(D17:H17) 10
18
20 24
=МАКС(D18:H18) 20
19
30 29
=МАКС(D19:H19) 30
20
40 32
=МАКС(D20:H20) 40
Рис. 5.1.2. Реализация 1-го шага, k=3 в MS Office Excel (режим Формулы /
Показать формулы)
2-й шаг. k=2.
Определяем оптимальную стратегию инвестирования во втрое и третье предприятия. При этом рекуррентное соотношение
Беллмана будет иметь вид
2 2
3 2
2 2
2 2
2
max
x
C
F
x
g
C
F
C
x
На его основе рассчитываются данные таблицы 5.1.4 (рис. 5.1.3, 5.1.4).
Таблица 5.1.4
C
2
x
2
F
2
(C
2
)
0
10
20
30
40
0
0+0 0
0
10
0+19 21+0 21 10
82
Окончание таблицы 5.1.4
C
2
x
2
F
2
(C
2
)
0
10
20
30
40
20
0+24 21+19 25+0 40 10
30
0+29 21+24 25+19 30+0 45 10
40
0+32 21+29 25+24 30+19 37+0 50 10
Рис. 5.1.3. Реализация 2-го шага, k=2 в MS Office Excel
C
D
E
F
G
H
28
C
2
x
2
29
0 10 20 30 40
30
0
=$E$4+I16
31
10
=$E$4+I17 =$E$5+I16
32
20
=$E$4+I18 =$E$5+I17 =$E$6+I16
33
30
=$E$4+I19 =$E$5+I18 =$E$6+I17 =$E$7+I16
34
40
=$E$4+I2
=$E$5+I19 =$E$6+I18 =$E$7+I17
=$E$8+I16
I
J
28
F
2
(C
2
)
X
*
2
29
30
=МАКС(D30:H30) 0
31
=МАКС(D31:H31) 10
32
=МАКС(D32:H32) 10
33
=МАКС(D33:H33) 10
34
=МАКС(D34:H34) 10
Рис. 5.1.4. Реализация 2-го шага, k=2 в MS Office Excel (режим Формулы /
Показать формулы)
83
3-й шаг. k=1. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. При этом рекуррентное соотношение
Беллмана будет иметь вид
1 1
2 1
1 1
1 1
1
max
x
C
F
x
g
C
F
C
x
На его основе находят данные таблицы 5.1.5 (рис. 5.1.5, 5.1.6).
Таблица 5.1.5
C
1
x
1
F
1
(C
1
)
0
10
20
30
40
0
0+0 0
0
10
0+21 17+0 21
0
20
0+40 17+21 23+0 40
0
30
0+45 17+40 23+21 34+0 57
10
40
0+50 17+45 23+40 34+21 40+0 63
20
Рис. 5.1.5. Реализация 3-го шага, k=1 в MS Office Excel 2007
C
D
E
F
G
H
43
C
1
x
1
44
0
10
20
30
40
45
0
=$D$4+I30
46
10 =$D$4+I31
=$D$5+I30
47
20 =$D$4+I32
=$D$5+I31
=$D$6+I30
48
30 =$D$4+I33
=$D$5+I32
=$D$6+I31
=$D$7+I30
49
40 =$D$4+I34
=$D$5+I33
=$D$6+I32
=$D$7+I31
=$D$8+I30
Рис. 5.1.6. Реализация 3-го шага, k=1 в MS Office Excel (режим Формулы /
Показать формулы)
84
I
J
43
F
1
(C
1
)
X
*
1
44
45
=МАКС(D45:H45) 0
46
=МАКС(D46:H46) 0
47
=МАКС(D47:H47) 0
48
=МАКС(D48:H48) 10
49
=МАКС(D49:H49) 20
Рис. 5.1.6. Окончание
II этап. Безусловная оптимизация
1-й шаг. По данным таблицы 5.1.5 максимальный доход при распределении 40 ден. ед. между тремя предприятиями составляет
63 5
1
F
ден. ед. При этом первому предприятию нужно выделить
20 1
*
x
ден. ед. (рис. 5.4, 5.6).
2-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю второго и третьего предприятий:
20 20 40
*
1 1
2
x
C
C
ден. ед.
По данным таблицы 5.1.4 находим, что оптимальный вариант распределения денежных средств размером 20 ден. ед. между вторым и третьим предприятиями составляет
40 3
2
F
ден. ед. при выделении второму предприятию
10
*
2
x
ден. ед. (рис. 5.1.7, 5.1.8).
Рис. 5.1.7. Реализация 1-го и 2-го шага безусловной оптимизации в MS
Office Excel
85
Рис. 5.1.8. Реализация 1-го и 2-го шага безусловной оптимизации (режим
Формулы / Показать формулы)
3-й шаг. Определяем величину оставшихся денежных средств, приходящуюся на долю третьего предприятий:
10 10 20
*
2 2
3
x
C
C
ден. ед.
Из таблицы 5.1.3 находим
19 2
3
F
ден. ед. и
10
*
3
x
ден. ед.
Таким образом, оптимальный план инвестирования предприятий
)
10
,
10
,
20
(
*
X
, обеспечивающий максимальный доход, равен (рис. 5.1.9,
5.1.10):
63 19 21 23 10 10 20 40 3
2 1
g
g
g
F
ден. ед.
Рис. 5.1.9. Реализация 3-го шага безусловной оптимизации в MS Office
Excel
86
Рис. 5.1.10. Реализация безусловной оптимизации в MS Office Excel
87
Варианты заданий для самостоятельной работы
Имеются четыре предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств X представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.
Вариант 1
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20 16 14 15 15
40 30 32 36 25
60 49 50 45 22
80 51 48 57 36
100 72 60 70 51
Вариант 2
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
19 14 20 25
40
36 32 36 53
60
51 52 47 66
80
72 61 72 70
100 81 79 80 84
Вариант 3
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
10 14 14 19
40
16 14 15 15
60
30 32 36 25
80
45 43 47 36
100 60 50 55 53
Вариант 4
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
14 17 22 20
40
26 20 21 33
60
35 32 37 46
80
52 61 67 30
100 61 72 58 42
Вариант 5
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
42 40 25 45
40
34 52 36 24
60
47 50 46 32
80
51 48 57 36
100 62 60 67 54
Вариант 6
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
19 48 42 45
40
36 32 56 53
60
54 62 67 66
80
72 81 82 70
100 88 95 98 84
88
Вариант 7
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20 22 17 18 35
40 43 39 33 42
60
49 51 45 55
80
61 75 57 68
100 82 79 67 81
Вариант 8
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
12 15 11 10
40
23 27 21 19
60
30 29 34 36
80
42 46 45 47
100 58 61 58 54
Вариант 9
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
9 11 14 8
40
19 14 20 15
60
30 32 16 25
80
36 30 38 33
100 48 44 52 36
Вариант 10
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
19 33 29 35
40
26 43 36 45
60
35 52 49 56
80
47 60 62 72
100 68 79 82 94
Вариант 11
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
12 24 10 20
40
21 17 16 25
60
20 21 25 22
80
30 38 22 23
100 42 35 18 41
Вариант 12
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
22 24 28 25
40
38 32 46 33
60
45 44 57 46
80
52 56 67 58
100 51 69 70 68
Вариант 13
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
12 24 25 18
40
23 32 36 22
60
33 40 44 32
80
45 48 47 36
100 52 60 57 35
Вариант 14
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
29 24 22 25
40
36 33 36 35
60
48 22 44 46
80
52 46 53 49
100 58 39 68 38
89
Вариант 15
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20
6 4
5 8
40 10 12 16 15
60 24 25 24 22
80 21 24 27 31
100 32 30 37 45
Вариант 16
X
g
1
g
2
g
3
g
4
0
0 0
0 0
20 10 12 14 19
40 14 37 48 45
60 34 27 37 38
80 42 40 48 48
100 66 56 64 77
1 2 3 4 5 6 7 8 9 10
5.2. Задача выбора стратегии обновления оборудования
КРАТКАЯ СПРАВКА
Требуется найти оптимальный план замены оборудования с тем, чтобы суммарная прибыль за все n лет была максимальной, учитывая, что к началу эксплуатационного периода возраст оборудования составляет t
0
лет.
Уравнение Беллмана на каждом шаге имеет вид (максимально возможная прибыль за годы с k-го по n-й, если к началу k-го года возраст оборудования составляет t лет):
З
F
r
P
t
S
C
t
F
t
r
t
F
k
k
k
,
1 0
,
1
max
1 1
(5.2.1)
Здесь
− входные данные:
r(t) – доход от эксплуатации в течение одного года оборудования возраста t
лет;
S(t) – остаточная стоимость оборудования;
P – цена нового оборудования;
t
0
– начальный возраст оборудования;
r(0) – прибыль от эксплуатации нового оборудования;
1 1
t
F
k
− максимально возможная прибыль за оставшиеся годы (с (k+1)-го по n-й);
1 1
k
F
− максимально возможная прибыль от эксплуатации нового оборудования за все годы с (k+1)-го по n-й
− переменная управления на k-ом шаге − логическая переменная, которая может принимать два значения:
С – сохранить,
З – заменить оборудование в начале k-го года;
− переменная состояния системы на k-ом шаге – t лет (t – возраст оборудования).
Функция Беллмана для первого шага (k=n) – это максимально возможная прибыль только за последний n-й год:
,
0
,
max
З
r
P
t
S
C
t
r
t
F
n
(5.2.2)
90
Вычислив значение функции
t
F
n
по формуле (5.2.2), далее можно посчитать
t
F
n 1
, затем
t
F
n 2
и так далее до
0 1
t
F
Функция
0 1
t
F
представляет собой максимально возможную прибыль за все годы (с 1-го по n-й). Этот максимум достигается при некотором управлении, применяя которое в течение первого года, мы определяем возраст оборудования к началу второго года (в зависимости от того, какое управление является для первого года оптимальным, это будет 1 или t
0
+1). Для данного возраста оборудования по результатам, полученным на этапе условной оптимизации, мы смотрим, при каком управлении достигается максимум прибыли за годы со 2-го по n-й и так далее.
На этапе безусловной оптимизации отыскиваются годы, в начале которых следует произвести замену оборудования.
Пример. Найти оптимальный план замены оборудования на период продолжительностью 6 лет (годовая прибыль и остаточная стоимость в зависимости от возраста задаются таблицей 5.2.1). Стоимость нового оборудования равна 14 ден. ед., возраст оборудования к началу эксплуатационного периода составляет 1 год.
Таблица 5.2.1
t
0
1
2
3
4
5
6
r(t)
10 9
9 8
8 7
6
S(t)
12 10 9
8 6
5 4
Решение.
I этап. Условная оптимизация
1-й шаг. k=6. Возможные состояния системы t=1, 2,…, 6. Расчет будет вестись по формуле (5.2.2). Результаты вычислений представлены на рисунках 5.2.1, 5.2.2.
6 10 14 4
6
max
6
,
7 10 14 5
7
max
5
,
8 10 14 6
8
max
4
,
8 10 14 8
8
max
3
,
9 10 14 9
9
max
2
,
9 10 14 10 9
max
1 6
6 6
6 6
6
C
F
C
F
C
F
C
F
C
F
C
F