Кирсанова О.В., Семёнова Г.А. Математическое программирование (типовой расчёт)
Подождите немного. Документ загружается.
170
Таблица 111
S
i
S
j
F
6
(S
i
)
*
j
S
S
17
S
18
c
i 17
+ F
7
(S
17
)
c
i 18
+ F
7
(S
18
)
S
14
16 + 19 =35
–
35
S
17
S
15
16 + 19 =35
18 + 12 = 30
30
S
18
S
16
–
11 + 12 = 23
23
S
18
Составим вспомогательную табл. 111 с учѐтом рис. 23, используя
функцию Беллмана
)(min)(
76 jiji
SFcSF
.
Соединим на рис. 24 S
14
c S
17
, S
15
с S
18
и S
16
с S
18
.
Таблица 112
S
i
S
j
F
5
(S
i
)
*
j
S
S
14
S
15
S
16
c
i 14
+ F
6
(S
14
)
c
i 15
+ F
6
(S
15
)
c
i 16
+ F
6
(S
16
)
S
10
14 + 35 = 49
–
–
49
S
14
S
11
19 + 35 = 54
9 + 30 = 39
–
39
S
15
S
12
–
17 + 30 = 47
19 + 23 = 42
42
S
16
S
13
–
–
19 + 23 = 42
42
S
16
Третий шаг. k = 5. Из рис. 23 видно, что переменная состояния
может принимать значения S
i
= S
10
, S
11
, S
12
, S
13
.
Составим вспомогательную табл. 112 с учѐтом рис. 24, используя
функцию Беллмана
)(min)(
65 jiji
SFcSF
.
Соединим на рис. 24 S
10
c S
14
, S
11
c S
15
, S
12
c S
16
.
Четвѐртый шаг. k = 4. Из рис. 23 видно, что переменная состоя-
ния может принимать значения S
i
= S
6
, S
7
, S
8
, S
9
.
Составим вспомогательную табл. 113 с учѐтом рис. 23, используя
функцию Беллмана
)(min)(
54 jiji
SFcSF
.
Таблица 113
S
i
S
j
F
4
(S
i
)
*
j
S
S
10
S
11
S
12
S
13
c
i 10
+ F
5
(S
10
)
c
i 11
+ F
5
(S
11
)
c
i 12
+ F
5
(S
12
)
c
i 13
+ F
5
(S
13
)
S
6
17+49=66
21+39=60
–
–
60
S
11
S
7
–
13+39=52
12+42=54
–
52
S
11
S
8
–
–
15+42=57
21+42=63
57
S
12
S
9
–
–
–
20+42=62
62
S
13
171
Пятый шаг. k = 3. Из рис. 23 видно, что переменная состояния
может принимать значения S
i
= S
3
, S
4
, S
5
.
Составим вспомогательную табл. 114 с учѐтом рис. 24, используя
функцию Беллмана
)(min)(
43 jiji
SFcSF
.
Соединим на рис. 24 S
3
c S
7
, S
4
c S
8
и S
5
c S
8
.
Таблица 114
S
i
S
j
F
3
(S
i
)
*
j
S
S
6
S
7
S
8
S
9
c
i 6
+ F
4
(S
6
)
c
i 7
+ F
4
(S
7
)
c
i 8
+ F
4
(S
8
)
c
i 9
+ F
4
(S
9
)
S
3
15+60=75
8+52=60
–
–
60
S
7
S
4
–
20+52=72
14+57=71
–
71
S
8
S
5
–
–
6+57=63
13+62=75=62
63
S
8
Шестой шаг. k = 2. Из рис. 23 видно, что переменная состояния
может принимать значения S
i
= S
1
, S
2
.
Составим вспомогательную табл. 115 с учѐтом рис. 24, используя
функцию Беллмана
)(min)(
32 jiji
SFcSF
.
Соединим на рис. 24 S
1
c S
3
и S
2
c S
5
.
Таблица 115
S
i
S
j
F
2
(S
i
)
*
j
S
S
3
S
4
S
5
c
i 3
+ F
3
(S
3
)
c
i 4
+ F
3
(S
4
)
c
i 5
+ F
3
(S
5
)
S
1
13+60=73
9+71=80
–
73
S
3
S
2
–
9+71=80
8+63=71
71
S
5
Седьмой шаг. k = 1. Из рис. 23 видно, что переменная состояния
может принимать значение S
i
= S
о
.
Таблица 116
S
i
S
j
F
1
(S
i
)
*
j
S
S
1
S
2
c
i 2
+ F
2
(S
1
)
c
i 2
+ F
2
(S
2
)
S
о
14+73=87
16+71=87
23
S
1
или S
2
Составим вспомогательную табл. 116 с учѐтом рис. 24, используя
функцию Беллмана
)(min)(
21 jiji
SFcSF
.
Соединим на рис. 24 S
0
c S
1
и S
2
172
Безусловная оптимизация
Определим компоненты оптимальной стратегии. Из табл. 116 и
рис. 24 следует, что в данной задаче возможны две стратегии с мини-
мальными затратами (на рис. 25 одна отмечена сплошной, вторая –
пунктирной линиями):
*
1
X
(S
2
, S
5
, S
8
, S
12
, S
16
, S
18
, S
19
),
*
2
X
(S
1
, S
3
, S
7
, S
11
, S
15
, S
18
, S
19
),
при этом минимальные затраты составляют F
*
= 38.
Рис. 25
Ответ:
Процесс обслуживания машин с минимальными суммарными из-
держками в размере 38 у.е. можно провести двумя способами
а) 2 машины загрузить, 2 машины разгрузить, 1 машину загру-
зить, 2 машины разгрузить;
б) 2 машины разгрузить, 1 машину загрузить, 1 машину разгру-
зить, 2 машины загрузить, 1 машину разгрузить.
4.5. Задача о прокладке пути между двумя пунктами
Упражнение 5. Прокладывается участок железнодорожного пути
между пунктами А и В. Пункт В лежит к северо-востоку от А. Различ-
ные варианты трассы требуют неодинаковых затрат в связи с неодно-
87
0
19
16
14
18
9
21
13
8
16
21
14
9
19
12
8
14
13
15
17
9
20
13
19
6
15
17
16
20
19
11
12
49
39
42
42
35
30
23
12
19
71
60
63
52
57
60
71
73
62
k=1 k=2 k=3 k=4 k=5
k=7
k=6
x
2
x
1
173
родностью грунта, наличием лесных зон, болот, рек, через которые
необходимо строить мосты и так далее (рис. 26).
Рис. 26
Требуется так провести дорогу от А к В, чтобы суммарные затра-
ты на еѐ сооружение были минимальными.
Решение.
Предположим, что весь процесс прокладки пути можно разделить
на ряд элементарных последовательных шагов. Изобразим область
допустимых состояний точками плоскости. По оси Ox
1
отложим чис-
ло участков пути в восточном направлении (их общее количество
равно n), по оси Ox
2
– число участков пути в северном направлении
(их общее количество равно m).
Соединив точки с координатами (i,j), получим граф состояний
процесса прокладки пути. Каждому ребру ставятся в соответствие из-
держки, связанные с выполнением соответствующей операции. Точка
S
o
определяет начало процесса, S
19
– конечное состояние, соответст-
вующее прокладке всего пути.
При такой постановке задачи еѐ решение аналогично решению,
приведѐнному в упражнении 4 данной главы.
4.6. Задача о выборе траектории движения
Упражнение 6. Пусть самолѐт, находящийся в точке S
o
на высоте
H
o
и движущийся со скоростью v
o
, должен набрать высоту H
кон
и его
скорость должна быть доведена до v
кон
. Известен расход горючего
А
В
19
16
14
18
9
21
13
8
16
21
14
9
19
12
8
14
13
15
17
9
20
13
19
6
15
17
16
20
19
11
12
174
(рис. 27) для подъѐма с любой высоты H
1
на высоту H
2
при постоян-
ной скорости v и расход горючего для увеличения скорости от v
1
до
v
2
при неизменной высоте H.
Рис. 27
Найдите оптимальную траекторию набора высоты и скорости,
при которой общий расход горючего будет минимальным.
Решение.
Предположим, что весь процесс набора высоты и скорости можно
разделить наряд элементарных последовательных шагов, на любом из
которых самолѐт увеличивает только высоту или только скорость.
Изобразим область допустимых состояний точками плоскости. По
оси Ox
1
отложим число участков набора скорости (общее их количе-
ство равно n), по оси Ox
2
– число участков набора высоты (общее их
количество равно m).
Соединив точки с координатами (i,j), получим граф состояний
процесса набора высоты. Каждому ребру ставятся в соответствие из-
держки, связанные с выполнением соответствующей операции. Точка
S
o
определяет начало процесса, S
19
– конечное состояние.
При такой постановке задачи еѐ решение аналогично решению,
приведѐнному в упражнении 4 данной главы.
Задача 4.
4.1 – 4.10. На оптовую базу прибыло n машин с товаром для раз-
грузки и m машин для загрузки товара. Машины обслуживаются по-
очерѐдно, одна за другой.
Издержки от операции обслуживания обусловлены:
– простоем транспорта;
– типом операции (приѐм или отправка).
Спланируйте процесс обслуживания машин таким образом, чтобы
суммарные издержки были минимальны.
S
0
S
19
19
16
14
18
9
21
13
8
16
21
14
9
19
12
8
14
13
15
17
9
20
13
19
6
15
17
16
20
19
11
12
175
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
S
1
19
19
19
13
13
15
13
18
15
10
14
18
14
18
11
17
15
11
17
18
14
3
5
18
13
16
10
17
15
12
13
18
11
14
20
14
12
11
S
0
S
1
14
11
17
14
8
18
18
18
14
12
16
14
10
15
17
12
17
12
19
10
12
11
13
16
11
14
19
12
13
10
11
16
8
12
18
12
7
9
S
0
S
1
9
11
15
15
10
4
7
11
17
11
8
12
14
13
6
5
7
18
14
5
13
12
14
9
3
7
2
16
19
6
4
8
14
12
17
6
7
4
S
0
S
1
15
13
18
15
10
19
19
19
13
13
17
15
11
17
18
14
18
14
18
11
13
12
14
17
12
15
10
16
14
11
12
17
10
13
19
13
11
10
S
0
S
0
S
1
17
21
10
22
21
14
17
18
21
18
14
19
23
17
12
20
19
15
11
18
17
22
19
20
11
13
10
15
14
19
14
19
20
17
21
11
12
10
16
13
S
0
S
1
11
12
10
7
7
10
11
8
13
9
12
10
13
9
17
14
10
13
15
12
8
10
12
9
9
7
14
8
6
11
13
12
11
13
7
10
15
9
9
7
176
4.7.
4.8.
4.9.
4.10.
4.11. – 4.20. Прокладывается участок железнодорожного пути ме-
жду пунктами А и В. Пункт В лежит к северо-востоку от А. Различные
варианты трассы требуют неодинаковых затрат в связи с неоднород-
ностью грунта, наличием лесных зон, болот, рек, через которые необ-
ходимо строить мосты и так далее.
Требуется так провести дорогу от А к В, чтобы суммарные затра-
ты на еѐ сооружение были минимальны.
4.11.
4.12.
S
0
S
1
7
3
2
1
9
1
4
4
8
1
7
9
11
6
6
6
2
2
4
7
2
7
5
4
3
4
8
4
2
3
4
1
4
5
10
8
6
9
5
1
S
0
S
1
15
19
12
15
12
9
18
10
17
6
11
14
11
11
9
19
19
8
14
7
16
18
5
19
16
13
19
20
19
17
21
14
12
7
14
18
18
10
11
17
S
0
S
1
18
20
19
17
17
13
28
25
14
19
12
17
26
15
19
23
20
27
21
14
13
24
23
16
17
18
17
24
22
21
16
15
17
22
28
13
21
19
15
25
S
0
S
1
12
16
12
12
11
10
13
18
10
15
14
15
9
19
7
10
14
11
18
13
11
13
15
19
17
19
14
11
9
12
13
18
18
17
11
18
13
15
14
19
18
25
17
S
0
S
1
23
23
21
28
19
22
14
23
19
17
21
18
27
17
20
16
14
19
15
13
13
25
14
19
15
24
22
28
16
13
21
28
17
15
29
19
11
14
S
0
S
1
10
18
12
17
13
15
15
10
17
16
15
13
11
16
16
15
18
16
15
12
9
18
12
19
15
19
14
18
17
12
12
19
13
11
17
177
4.13.
4.14.
4.15.
4.16.
4.17.
4.18.
S
1
25
23
28
25
20
29
29
29
23
23
27
25
21
27
28
24
28
24
28
21
23
22
24
27
22
25
20
26
24
21
22
27
20
23
29
23
21
20
S
0
S
1
11
8
14
10
11
7
9
6
13
3
17
12
12
6
5
14
13
14
12
8
14
12
7
14
9
7
5
11
7
14
9
7
10
13
12
13
11
10
S
0
8
2
7
S
0
S
1
9
3
8
6
5
3
8
3
6
4
8
10
3
3
5
3
5
8
9
12
6
2
8
9
4
10
8
7
11
9
3
5
7
1
2
S
0
S
1
23
21
16
20
21
18
19
15
19
15
18
17
10
14
24
23
26
17
27
21
18
25
23
17
15
19
28
20
22
18
13
26
25
11
19
12
13
12
17
20
S
0
S
1
25
12
14
24
13
22
8
13
22
10
19
15
16
12
21
16
9
17
16
17
22
19
10
17
14
12
20
12
18
15
12
17
11
23
19
17
21
13
17
11
18
22
27
S
0
S
1
19
23
18
16
25
23
17
23
26
24
18
14
23
24
15
23
25
18
19
22
26
22
28
19
24
20
28
27
21
29
23
15
17
21
22
178
4.19.
4.20.
4.21 – 4.30. Пусть самолѐт, находящийся в точке S
o
на высоте H
o
и
движущийся со скоростью v
o
, должен набрать высоту H
кон
и его ско-
рость должна быть доведена до v
кон
. Известен расход горючего для
подъѐма с любой высоты H
1
на высоту H
2
при постоянной скорости v
и расход горючего для увеличения скорости от v
1
до v
2
при неизмен-
ной высоте H.
Найдите оптимальную траекторию набора высоты и скорости,
при которой общий расход горючего будет минимальным.
4.21.
4.22.
S
1
5
3
8
5
1
9
9
9
3
3
7
5
1
7
8
4
8
4
8
1
3
4
7
7
11
5
8
6
10
8
2
7
7
3
9
3
6
3
S
0
S
1
13
9
11
15
17
14
15
15
20
11
18
17
11
17
18
19
12
14
13
13
13
17
14
17
18
15
10
21
14
18
18
17
10
13
14
13
13
11
3
S
0
9
11
4
S
0
S
1
10
8
12
7
13
15
5
10
7
16
15
13
11
16
16
15
8
14
15
12
9
18
12
9
15
9
14
8
7
12
12
9
13
11
17
14
22
12
S
0
S
1
19
23
14
26
11
23
17
23
26
24
18
21
23
23
25
23
25
17
19
22
26
22
18
19
24
16
11
27
21
19
23
12
17
21
22
179
4.23.
4.24.
4.25.
4.26.
4.27.
4.28.
9
11
4
S
0
S
1
10
8
12
7
13
5
15
10
7
16
15
13
11
6
6
5
8
16
5
12
9
8
12
9
15
9
14
8
17
12
12
9
13
11
7
28
22
27
S
0
S
1
19
23
28
26
25
23
28
23
26
24
18
30
23
23
25
23
25
28
19
22
26
22
28
29
24
30
28
27
21
29
23
25
17
21
22
18
12
17
S
0
S
1
19
13
18
16
15
13
18
13
16
14
18
20
13
13
15
13
15
18
19
22
16
12
18
19
12
20
18
17
21
19
13
15
17
11
12
8
15
7
S
0
S
1
13
13
11
18
9
12
4
13
9
7
11
18
17
7
10
16
14
9
15
13
13
5
14
19
15
14
12
18
6
3
11
18
7
5
19
S
0
S
1
13
9
14
15
12
7
10
17
7
18
8
9
17
17
11
7
9
15
12
12
14
15
10
11
9
7
8
9
6
11
12
11
18
14
6
13
11
15
15
10
S
0
S
1
9
2
7
5
7
7
6
7
2
5
4
10
5
1
5
9
5
6
3
6
4
5
8
9
15
15
15
15
1
5
3
7
4
8
1
3
8
5
4
3