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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

94
j
b
30
80
20
30
90
i
a
120
2
30
4
80
2
3
8
10
30
3
5
6
6
2
30
40
6
8
7
4
5
40
60
3
4
2
20
1
30
4
10
Затраты на перевозку по построенному плану равны
30 2 4 80 8 10 2 30 5 40 2 20 1 30 4 10 830Q
.
Этот план лучше, но утверждать, что он оптимален, нельзя.
Определение 1. Набором называется произвольная совокупность перевозок
транспортной таблицы.
Определение 2. Цепью называют такие наборы, когда каждая пара сосед-
них клеток в цепи расположены либо в одном столбце, либо в одной строке.
Определение 3. Циклом называется цепь, крайние элементы которой нахо-
дятся либо в одной строке, либо в одном столбце.
7.5.3. Метод потенциалов
Метод позволяет находить оптимальный план перевозок транспортной
таблицы. В основе лежит следующая теорема.
Теорема. Для того, чтобы некоторый план
[]
ij m n
Xx
транспортной зада-
чи был оптимальным, необходимо и достаточно, чтобы ему соответствовала та-
кая система m+n чисел
1 2 1 2
, ,..., ; , ,...,
mn
u u u v v v
, для которой выполняются условия
j i ij
v u c
,
1,im
,
1,jn
, (7.8)
j i ij
v u c
,
0
ij
x
. (7.9)
Величины
i
u
и
j
v
называются потенциалами соответствующих пунктов
отправления и пунктов назначения. Условия (7.8-7.9) называются условиями по-
тенциальности.
План
X
будем называть потенциальным, если для него существует систе-
ма
i
u
и
j
v
, удовлетворяющая (7.8–7.9). Тогда теорема коротко формулируется
следующим образом.
Теорема. Для оптимальности транспортной задачи необходимо и доста-
точно, чтобы потенциальный план был оптимален.

Страницы