Составители:
Рубрика:
64
66
70
52 39 27 17 8
0
58 46 34 25 18 11
69 59 51 42 34 28 22
78 67 58 51 44 39 34
88 76 68 63 57 53
48
m
4
3
2
1
0
0
1
2 3 4 5
6
n
S
1
A
1
A
2
A
3
A
4
A
5
A
6
B
7
B
6
B
5
B
4
B
3
B
2
B
1
C
1
C
2
C
3
C
4
C
5
C
6
C
7
D
7
D
6
D
5
D
4
D
3
D
2
D
1
E
1
E
2
E
3
E
4
E
5
E
6
S
0
12
11
11
10
10
8
12
7
14
13
6
13 12
8
12
8
7
10
9
9
11 10
10
7
9
9
8
8
9
10
7
10
9
8
9
9
10
10
9
13
13 14
14 14
12
13
11
11
12
10
11
13
10
8
11
7
12
9
Рис 6.8. Сетевая модель связи расходов операций
В результате строим ориентированный граф от состояния S
o
к со-
стоянию S
1
, представленный на рис. 6.9, на каждом шаге безусловной
оптимизации переход почти всегда единствен и совпадает с построен-
ными условно оптимальными переходами.
17 8
0
25
34
67 58 51 44
88 76
m
4
3
2
1
0
0
1
2 3 4 5
6
n
S
1
A
1
A
2
B
3
C
3
D
6
D
5
D
4
D
3
E
6
S
0
12
9
9
7
9
8
9
10
8
7
Рис 6.9. Оптимальная последовательность операций
Минимальные издержки F
min
соответствуют следующему оптимальному
пути на графе:(S
0
→ Е
6
→ D
6
→ D
5
→ D
4
→ D
3
→ С
3
→ В
3
→A
2
→A
1
→S
1
)
и равны: F
min
= 12 + 9 + 9 + 7 + 7 + 10 + 9 + 8 + 9 + 8 = 88 усл. ед.
m
A6 14 A5 13 A4 12 A3 10 A2 9 A1 8 S1
4 66 52 39 27 17 8 0
7 6 8 7 8 10 11
B7 12 B6 13 B5 12 B4 10 B3 9 B2 13 B1
3 70 58 46 34 25 18 11
8 7 8 9 9 10 11
C7 10 C6 8 C5 9 C4 8 C3 10 C2 12 C1
2 69 59 51 42 34 28 22
10 10 9 11 10 11 12
D7 11 D6 9 D5 7 D4 7 D3 9 D2 13 D1
1 78 67 58 51 44 39 34
11 9 10 12 13 14 14
12 E6 11 E5 10 E4 9 E3 13 E2 14 E1
0 88 76 68 63 57 53 48
S0
0 1 2 3 4 5 6 n
Рис 6.8. Сетевая модель связи расходов операций
В результате строим ориентированный граф от состояния So к со-
стоянию S1, представленный на рис. 6.9, на каждом шаге безусловной
оптимизации переход почти всегда единствен и совпадает с построен-
ными условно оптимальными переходами.
m
A2 9 A1 8 S1
4 17 8 0
8
B3
3 25
9
C3
2 34
10
D6 9 D5 7 D4 7 D3
1 67 58 51 44
9
12 E6
0 88 76
S0
0 1 2 3 4 5 6 n
Рис 6.9. Оптимальная последовательность операций
Минимальные издержки Fmin соответствуют следующему оптимальному
пути на графе:(S0→ Е6 → D6 → D5 → D4 → D3 → С3 → В3 →A2 →A1 →S1)
и равны: Fmin = 12 + 9 + 9 + 7 + 7 + 10 + 9 + 8 + 9 + 8 = 88 усл. ед.
64
