Численные методы оптимизации. Рейзлин В.И. - 98 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

98
клетки, начиная с
00
ij
, попеременно знаками + и –. Клетки со знаками + образу-
ют положительную полуцепь, а со знаками – отрицательную полуцепь. В клет-
ках отрицательной полуцепи ищем минимальную перевозку
min
ij
x

.
Теперь улучшаем план следующим образом: перевозки отрицательной по-
луцепи уменьшаем на величину
, а перевозки положительной полуцепи увели-
чиваем на
. Новые
'
,
,
.
ij
ij ij
ij
x
xx
x

В нашем примере
min
ij
x

=20.
1. Новому плану соответствует таблица.
j
v
1
v
2
v
4
v
5
v
i
u
1
u
2
30
4
80
2
10
3
8
2
u
3
5
– 6
10
6
0
+ 2
20
3
u
6
8
7
4
30
5
10
4
u
3
4
+ 2
1
– 4
60
Затраты на перевозку по построенному плану равны:
30 2 4 80 2 10 6 10 4 30 2 20 5 10 4 60 910Q
.
2. Строим систему потенциалов
11
2vu
,
21
4vu
,
31
2vu
,
32
6vu
,
52
2vu
,
43
4vu
,
53
5vu
,
54
4vu
.
Полагаем
1
0u
и находим значения остальных потенциалов:
2
4u 
,
3
7u 
,
4
6u 
,
1
2v
,
2
4v
,
3
2v
,
4
3v 
,
5
2v 
.
3. Проверяем систему на потенциальность:
12
63vu
,
13
96vu
,
14
83vu
,
22
85vu
,
23
11 8vu
,
24
10 4vu
,
33
97vu
,
34
82vu
,
41
33vu
,
44
31vu
,
51
28vu
,
42
16vu
,
Система непотенциальна.

Страницы