Алгоритм решения задачи.
h1 = LiO
1 n(m)
(h(m) - число дуг контура ц).
k-й шаг.
Определяем контур |mk положительной длины, при длинах дуг lij- hk-1. LkЕсли Lk = L(mk) < 0, то h = hk-1. Если L(mk) > 0, то определяем1
hk =—Lk, nk
где nk = n(mk), и переходим к следующему шагу.
За конечное число шагов будет получена величина h такая, что в графе отсутствуют контуры положительной длины при длинах дуг 1ij - h. Соответствующие потенциалы вершин {1i} и величина h определяют оптимальное решение задачи (1.2.11), а значит (1.2.10) и (1.2.7). Определив 5i, мы можем найти уi и, следовательно, получить полное описание операции.
Пример 1.2. Возьмем t11 = 2, t21 = 3, t12 = 1, t22 = 2. Имеем
Х,о X
12 22
1 21 2
q21 = max
X,, X
11 21
= max | —;— I = —. 2 3 0 3
В данном случае задачу можно решить не переходя к логарифмам, определяя вместо длины контура его усиление.
Усиление контура(1,2,1) равно 4/3 > 1. Следовательно, e = у^, w1 = 1, w2 = л/3 . Имеем
= 1
Q1 = 1, Q2 =
max| QL;Q2|- mini Q1 ; Q
X, , X
X, , X
11 12
51 =
0,09
11 12
max| | + min| Q1 • Q2
X, , X
X, , X
11 12
11 12
max| -QL;Q2 j-mini Q1 • Q2
Хо, X
Хо, X
21 22
52 =
< 0,06 .
21 22
^ Q1 Q21
^ Q1 • Q21
max
+ min
V 21 22 0
VT 21 22 0
Соответственно получаем
Q1 Q2
0,92
VT
0,94
max
V 11 12 0
(
Q1 Q2
y1 =(1 -51 )•
max
y2
3
V 21 L22
= (1 -52 )•