Файл: Практикум Челябинск 2019.pdf

91
Рис. 5.2.1. Реализация 1-го шага, k=6 в MS Office Excel
Рис. 5.2.2. Реализация 1-го шага, k=6 в MS Office Excel (режим Формулы /
Показать формулы)

92
Рис. 5.2.2. Окончание
2-й шаг. k=5.
Возможные состояния системы t=1, 2,…, 5. Расчет будет вестись по формуле (5.2.1). Результаты расчетов представлены на рисунках
5.2.3, 5.2.4.
 
 
,
C
max
F













18 9
10 14 10 9
9 1
5
 
 
,
C
max
F













17 9
10 14 9
8 9
2 5
 
 
,
C
max
F













16 9
10 14 8
8 8
3 5

93
 
 
,
C
max
F













15 9
10 14 6
7 8
4 5
 
 
C
max
F













13 9
10 14 5
6 7
5 5
Рис. 5.2.3. Реализация 2-го шага, k=5 в MS Office Excel
Рис. 5.2.4. Реализация 2-го шага, k=5 в MS Office Excel (режим Формулы /
Показать формулы)

94
Рис. 5.2.4. Окончание
3-й шаг. k=4. Возможные состояния системы t=1, 2,…, 4. Расчет будет вестись по формуле (5.2.1). Результаты вычислений представлены на рисунках 5.2.5, 5.2.6.
 
 
 
 
 
 
 
 
21 18 10 14 6
13 8
max
4
,
23 18 10 14 8
15 8
max
3
,
25 18 10 14 9
16 9
max
2
,
26 18 10 14 10 17 9
max
1 4
4 4
4
C
F
C
F
C
F
C
F





















































95
Рис. 5.2.5. Реализация 3-го шага, k=4 в MS Office Excel
Рис. 5.2.6. Реализация 3-го шага, k=4 в MS Office Excel (режим Формулы /
Показать формулы)

96
4-й шаг. k=3. Возможные состояния системы t=1, 2, 3. Расчет будет вестись по формуле (5.2.1). Результаты вычислений представлены на рисунках 5.2.7, 5.2.8.
 
 
 
 
 
 
30 26 10 14 8
21 8
max
3
,
32 26 10 14 9
23 9
max
2
,
34 26 10 14 10 25 9
max
1 3
3 3
З
F
C
F
C
F







































Рис. 5.2.7. Реализация 4-го шага, k=3 в MS Office Excel
Рис. 5.2.8. Реализация 4-го шага, k=3 в MS Office Excel (режим Формулы /
Показать формулы)

97
Рис. 5.2.8. Окончание
5-й шаг. k=2. Возможные состояния системы t=1, 2. Расчет будет вестись по формуле (5.2.1). Результаты вычислений представлены на рисунке 5.2.9, 5.2.10.
 
 
 


/
39 34 10 14 9
30 9
max
2
,
41 34 10 14 10 32 9
max
1 2
2
З
C
F
C
F


























Рис. 5.2.9. Реализация 5-го шага, k=2 в MS Office Excel

98
Рис. 5.2.10. Реализация 5-го шага, k=2 в MS Office Excel (режим Формулы /
Показать формулы)
6-й шаг. k=1. Возможные состояния системы t=1. Расчет будет вестись по формуле (5.2.1). Результаты вычислений представлены на рисунках
5.2.11, 5.2.12.
 
 
C
F













48 41 10 14 10 39 9
max
1 1
Рис. 5.2.11. Реализация 6-го шага, k=1 в MS Office Excel

99
Рис. 5.2.12. Реализация 6-го шага, k=1 в MS Office Excel (режим Формулы /
Показать формулы)
II этап. Безусловная оптимизация
Представим результаты вычисления функции Беллмана в виде таблицы
5.2.2. Результаты вычислений представлены на рисунке 5.2.13.
Таблица 5.2.2
k
t
1
2
3
4
5
6
1
48
2
41 39
3
34 32
30
4
26 25 23 21
5
18 17 16 15 13
6
9 9
8 8
7 6
Рис. 5.2.13. Реализация II этапа в MS Office Excel

100
Выделенное в таблице значение функции Беллмана соответствует замене оборудования. Максимально возможная прибыль от эксплуатации оборудования за годы с 1-го по 6-й F
1
(1)=48 и достигается, если замену оборудования провести один раз, − в начале третьего года эксплуатации.
Варианты заданий для самостоятельной работы
Найдите оптимальный план замены оборудования на 6-летний период, если известны производительность оборудования r(t) и остаточная стоимость оборудования S(t) в зависимости от возраста, стоимость нового оборудования P (заданы в таблицах). Возраст оборудования к началу эксплуатации равен 1 году.
Вариант 1
t
0
1
2
3
4
5
6
P
r(t)
11 10 9
9 8
8 7
11
S(t)
11 8
5 4
3 2
1
-
Вариант 2
t
0
1
2
3
4
5
6
P
r(t)
10 9
8 7
6 4
2 12
S(t)
11 10 9
7 6
5 4
-
Вариант 3
t
0
1
2
3
4
5
6
P
r(t)
12 12 11 9
7 6
6 11
S(t)
11 10 9
7 6
5 3
-
Вариант 4
t
0
1
2
3
4
5
6
P
r(t)
9 8
7 6
6 5
4 9
S(t)
9 9
8 7
6 4
3
-
Вариант 5
0
1
2
3
4
5
6
P
r(t)
15 14 14 13 12 10 8
16
S(t)
16 14 12 10 8
6 5
-
Вариант 6
t
0
1
2
3
4
5
6
P
r(t)
15 14 13 13 12 12 10 16
S(t)
16 14 13 11 10 8
6
-

101
Вариант 7
t
0
1
2
3
4
5
6
P
r(t)
10 9
9 7
7 6
6 11
S(t)
11 9
7 5
4 3
2
-
Вариант 8
t
0
1
2
3
4
5
6
P
r(t)
12 12 11 10 8
6 3
14
S(t)
13 12 11 10 8
5 2
-
Вариант 9
t
0
1
2
3
4
5
6
P
r(t)
10 9
8 8
6 5
4 11
S(t)
9 8
7 5
3 3
2
-
Вариант 10
t
0
1
2
3
4
5
6
P
r(t)
8 8
8 8
7 7
7 8
S(t)
6 5
5 5
5 4
4
-
Вариант 11
t
0
1
2
3
4
5
6
P
r(t)
10 9
6 5
5 4
3 13
S(t)
12 10 8
8 7
6 4
-
Вариант 12
t
0
1
2
3
4
5
6
P
r(t)
10 9
7 7
6 4
3 13
S(t)
12 10 9
9 7
6 5
-
Вариант 13
t
0
1
2
3
4
5
6
P
r(t)
12 12 11 11 10 10 8
14
S(t)
13 12 11 10 8
6 3
-
Вариант 14
t
0
1
2
3
4
5
6
P
r(t)
11 9
8 7
6 6
4 12
S(t)
10 7
6 5
5 4
2
-

102
Вариант 15
t
0
1
2
3
4
5
6
P
r(t)
12 12 12 11 11 10 8
11
S(t)
10 10 9
9 8
8 6
-
Вариант 16
t
0
1
2
3
4
5
6
P
r(t)
9 8
8 7
7 6
6 7
S(t)
7 6
5 4
4 3
2
-
5.3. Выбор оптимального пути в транспортной сети
КРАТКАЯ СПРАВКА
Транспортная сеть состоит из n узлов, некоторые из которых соединены магистралями. Стоимость проезда по каждой из таких магистралей известна и отмечена на схеме. Найти оптимальный маршрут проезда из 1-го пункта в n-й.
Рассмотрим решение данной задачи на конкретном примере.
Пусть сеть состоит из 10 узлов (будем называть их также городами), соединенными магистралями согласно схеме:
Стоимость проезда из пункта i в пункт j равна t
ij
и элементы этой матрицы занесены в схему.
Требуется найти оптимальный маршрут из 1-го пункта в 10-й.
В данной задаче имеется серьёзное ограничение – двигаться по магистралям можно только слева на право. Это дает возможность разбить всю транспортную сеть на пояса и отнести каждый из десяти пунктов к одному из четырех поясов.
Будем говорить, что пункт принадлежит k-му поясу, если из него можно попасть в конечный (10-й) пункт ровно за k шагов, т.е. с заездом ровно в k-1 пункт.
Таким образом, пункты 7, 8 и 9 принадлежат к первому поясу, 5 и 6 – ко второму, 2, 3 и 4 – к третьему и 1 – к четвертому.
На k-ом шаге будем находить оптимальные маршруты из городов k-го пояса до конечного пункта.
Оптимизацию будем проводить с хвоста процесса и поэтому, добравшись до
k-го шага, мы не можем знать, в какой именно из городов k-го пояса мы попадем, двигаясь из пункта 1. Поэтому для каждого из этих городов мы должны будем
6 5
3 4
9 11 8
7 5
8 6
10 1
2 7
5 6
4 3
6 9
10 9
8

103 найти оптимальный маршрут до конечного пункта. Очевидно, что минимально возможная стоимость проезда из городов k-го пояса до пункта 10 будет зависеть только от того, в каком из городов этого пояса мы оказались.
Номер S города, принадлежащего k-му поясу, и будет называться переменной
состояния данной системы на k-м шаге. Нужно помнить, что добравшись до k-го шага, мы уже осуществили предыдущие шаги, в частности, нашли оптимальные маршруты по перемещению из любого города (k-1)-го пояса в конечный пункт.
Таким образом, находясь в некотором городе S k-го пояса, мы должны принять решение о том, в какой из городов (k-1)-го пояса следует отправиться, а направление дальнейшего движения уже известно нам из предыдущих шагов.
Номер J города (k-1)-го пояса будет являться переменной управления на k-м шаге.
Функция Беллмана на k-м шаге решения задачи дает нам возможность рассчитать минимальную стоимость проезда из города S (k-го пояса) до конечного пункта.
Для первого шага (k=1) эту величину отыскать не сложно – это стоимость проезда из городов 1-го пояса непосредственно до конечного пункта:
 
10 1
i
C
i
F

Для последующих же шагов стоимость проезда складывается из двух слагаемых

стоимости из города S (k-го пояса) в город J (k-1)-го пояса и минимально возможной стоимости проезда из города J до конечного пункта, т.е.
 
J
F
к 1

. Таким образом, функциональное уравнение Беллмана на k-м шаге решения будет иметь вид
 
 


j
F
t
S
F
k
Sj
j
k
1
min



Минимум стоимости достигается на некотором значении

J
, которое и является оптимальным направлением движения из пункта S в сторону конечного пункта.
На четвертом шаге мы попадаем в 4-й пояс и состояние системы становится определенным
1

S
. Функция Беллмана
 
1 4
F
представляет собой минимально возможные затраты по перемещению из 1-го пункта в 10-й. Оптимальный маршрут можно найти, посмотрев результаты всех шагов в обратном порядке, учитывая, что выбор некоторого управления J на k-м шаге приводит к тому, что состояние системы на (k-1)-м шаге становится определенным.

104
Рис. 5.3.1. Реализация 1-го шага, k=1 в MS Office Excel
Рис. 5.3.2. Реализация 1-го шага, k=1 в MS Office Excel (режим Формулы /
Показать формулы)
2-й шаг. k=2. Функциональное уравнение на данном шаге принимает вид:
 
 


j
F
t
S
F
Sj
j
1 2
min


Результаты расчета по приведенной формуле приведены в таблице 5.3.2 и на рисунках 5.3.3, 5.3.4.
Таблица 5.3.2
S
J=7
J=8
J=9
 
S
F
2

J
5 6+9 6+3

6+3 8
6 8+9 4+3 5+11 4+3 8

105
Рис. 5.3.3. Реализация 2-го шага, k=2 в MS Office Excel
Рис. 5.3.4. Реализация 2-го шага, k=2 в MS Office Excel (режим Формулы /
Показать формулы)
3-й шаг. k=3. Функциональное уравнение на данном шаге принимает вид
 
 


j
F
t
S
F
Sj
j
2 3
min


Результаты расчета по приведенной формуле приведены в таблице 5.3.3 и на рисунках 5.3.5, 5.3.6.
Таблица 5.3.3.
S
J=5
J=6
 
S
F
3

J
2 5+9

5+9 5
3 7+9

7+9 5
4

9+7 9+7 6
Рис. 5.3.5. Реализация 3-го шага, k=3 в MS Office Excel

106
Рис. 5.3.6. Реализация 3-го шага, k=3 в MS Office Excel (режим Формулы /
Показать формулы)
4-й шаг. k=4. Функциональное уравнение на данном шаге принимает вид
 
 


j
F
t
S
F
Sj
j
3 4
min


Результаты расчета по приведенной формуле приведены в таблице 5.3.4 и на рисунках 5.3.7, 5.3.8.
Таблица 5.3.4
S
J=2
J=3
J=4
 
S
F
4

J
1 10+14 8+16 6+16 6+16 4
Рис. 5.3.7. Реализация 4-го шага, k=4 в MS Office Excel (режим Формулы /
Показать формулы)

107
Рис. 5.3.8. Реализация 4-го шага, k=4 в MS Office Excel (режим Формулы /
Показать формулы)
II этап. Безусловная оптимизация
На этапе условной оптимизации получено, что минимальные затраты на проезд из пункта 1 в пункт 10 составляют
 
22 1
4

F
, что достигается следующим движением по магистрали (см. рис. 5.3.7 и 5.3.8): из пункта 1 следует направиться в пункт 4, затем из него в пункт 6, затем в пункт 8 и из него в пункт 10. Таким образом, оптимальный маршрут будет
1→4→6→8→10.
Варианты заданий для самостоятельной работы
Задание 1
Для данной сети необходимо определить оптимальный маршрут проезда из 1-го пункта в 7-й с минимальными транспортными расходами.
Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице (T(i,j)).
T(1,2)
T(1,3)
T(1,4)
T(2,5)
T(3,5)
7 8
5 12 8
T(3,6)
T(4,5)
T(4,6)
T(5,7)
T(6,7)
9 7
13 9
6
Задание 2
Для данной сети необходимо определить оптимальный маршрут проезда из 1-го пункта в 7-й с минимальными транспортными расходами.
1 2
5 6
4 3
7

108
Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице (T(i,j)).
T(1,2)
T(1,3)
T(1,4)
T(2,5)
T(2,6) T(3,5)
5 9
8 10 17 4
T(3,6)
T(4,5)
T(4,6)
T(5,7)
T(6,7)
10 9
9 8
9
Задание 3
Для данной сети необходимо определить оптимальный маршрут проезда из 1-го пункта в 8-й с минимальными транспортными расходами.
Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице (T(i,j)).
T(1,2)
T(1,3)
T(1,4)
T(2,5)
T(2,6) T(3,5)
T(3,6)
6 3
1 4
3 5
6
T(3,7)
T(4,6)
T(4,7)
T(5,8)
T(6,8) T(7,8)
2 5
5 1
3 6
Задание 4
В предложенной транспортной сети имеется несколько маршрутов по проезду из начального пункта (1) в конечный пункт (11). Стоимость проезда между отдельными пунктами транспортной сети представлена в соответствующей таблице (T(i,j)). Необходимо определить оптимальный маршрут проезда из 1-го пункта в 11-й с минимальными транспортными расходами.
1 2
5 7
4 3
8 6
1 2
5 6
4 3
7

109
Вариант 1
T(1,2)
T(1,3)
T(1,4)
T(1,5)
T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
9 10 14 8
7 7
6 5
14
T(4,7)
T(5,6)
T(5,7)
T(6,8)
T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
9 12 10 7
6 4
9 5
11
T(8,11) T(9,11) T(10,11)
7 6
10
Вариант 2
T(1,2)
T(1,3)
T(1,4)
T(1,5)
T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
8 11 13 7
6 8
7 14 13
T(4,7)
T(5,6)
T(5,7)
T(6,8)
T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
8 11 11 9
10 8
7 7
5
T(8,11) T(9,11) T(10,11)
3 6
9
Вариант 3
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
7 12 12 6
5 9
8 14 12
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
7 10 6
13 11 5
14 10 9
T(8,11) T(9,11) T(10,11)
12 11 6
Вариант 4
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
6 13 11 5
14 10 9
12 11
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
6 9
7 12 12 6
5 9
8
T(8,11) T(9,11) T(10,11)
14 12 7
1 2
8 6
7 4
3 11 10 9
5

110
Вариант 5
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
5 14 10 14 13 11 10 11 10
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
8 5
11 15 9
13 12 12 11
T(8,11) T(9,11) T(10,11)
10 9
14
Вариант 6
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
11 15 9
13 12 12 11 10 9
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
8 12 5
14 10 14 13 11 10
T(8,11) T(9,11) T(10,11)
11 10 13
Вариант 7
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
13 16 8
12 11 12 13 11 8
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
13 6
12 17 7
11 10 14 13
T(8,11) T(9,11) T(10,11)
12 7
5
Вариант 8
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
12 17 7
11 10 14 13 12 7
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
8 5
13 16 8
12 11 12 13
T(8,11) T(9,11) T(10,11)
11 8
10
Вариант 9
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
14 19 11 18 17 7
7 14 13
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
8 11 11 9
13 12 9
6 5
T(8,11) T(9,11) T(10,11)
3 6
9
Вариант 10
T(1,2)
T(1,3)
T(1,4)
T(1,5) T(2,6) T(2,7)
T(3,6) T(3,7) T(4,6)
20
15
10
16
17
8
15
13
12
T(4,7)
T(5,6)
T(5,7)
T(6,8) T(6,9) T(6,10) T(7,8) T(7,9) T(7,10)
9
6
15
21
11
14
11
20
3
T(8,11) T(9,11) T(10,11)
17
6
18