Дискретная математика. Громов Ю.Ю - 90 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

90
Таблица 19
j
i
1 2 3 5
1 ∞ 22 33 0
А
1
= 2 0 ∞ 10 2
4 17 3 ∞ 0
5 0 0 0 ∞
получим матрицу А
1
(табл. 19), которая соответствует множеству
)1(
1
Z
.
Далее номера 3 и 4 будем считать эквивалентными.
Приведение матрицы А
1
не изменит её, т.е.
1
~
A
= А
1
и h
1
= 0. Вычис-
лим нижнюю границу множества
)1(
1
Z
:
1
)1(
1
)()( hZZ +γ=γ
= 30 + 0 = 30.
Для приведённой матрицы
1
~
A
составим множество D:
D = {(1, 5), (2, 1), (4, 5), (5, 1), (5, 2), (5, 3)},
выберем в качестве следующей дуги ветвления дугу (1, 5) и вычислим
нижнюю границу множества
)2(
2
Z
:
pq
ZZ α
′
+γ=γ )()(
)1(
1
)2(
2
= 30 + 22 = 52.
Стянем матрицу
1
~
A
по выбранной дуге ветвления (1, 5) и получим
матрицу А
2
(табл. 20), соответствующую множеству
)2(
1
Z
, а номера 1 и 5
будем считать эквивалентными.
Вычислим нижнюю границу множества
)2(
1
Z
:
2
)1(
1
)2(
1
)()( hZZ +γ=γ
= 30 + 3 = 33.
Таблица 20
j
i
1 2 3
2 0 ∞ 10
А
2
= 4 17 3 ∞
5 ∞ 0 0

Страницы