Экономико-математические методы и иодели

 

После вычитания минимальных  элементов получаем полностью редуцированную матрицу, где величины d_i и d_j называются константами приведения.

 

i  j	1	2	3	4	5	6
1	∞	0	6	7	3	0
2	1	∞	0	0	2	4
3	6	2	∞	1	0	3
4	6	0	2	∞	0	7
5	0	6	0	1	∞	1
6	9	2	0	7	1	∞

 

1. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

 

i  j	1	2	3	4	5	6	di
1	∞	0(0)	6	7	3	0(1)	0
2	1	∞	0(0)	0(1)	2	4	0
3	6	2	∞	1	0(1)	3	1
4	6	0(0)	2	∞	0(0)	7	0
5	0(1)	6	0(0)	1	∞	1	0
6	9	2	0(1)	7	1	∞	1
dj	1	0	0	1	0	1	0

 

Наибольшая сумма констант приведения равна (0 + 1) = 1 для ребра (1,6), следовательно, множество разбивается на два подмножества (1,6) и (1*,6*).

Нижняя граница гамильтоновых  циклов этого подмножества:

 

i  j	1	2	3	4	5	6	di
1	∞	0	6	7	3	∞	0
2	1	∞	0	0	2	4	0
3	6	2	∞	1	0	3	0
4	6	0	2	∞	0	7	0
5	0	6	0	1	∞	1	0
6	9	2	0	7	1	∞	0
dj	0	0	0	0	0	1	1

 

В результате получим  другую сокращенную матрицу (5 x 5), которая  подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид:

 

i  j	1	2	3	4	5	di
2	1	∞	0	0	2	0
3	6	2	∞	1	0	0
4	6	0	2	∞	0	0
5	0	6	0	1	∞	0
6	∞	2	0	7	1	0
dj	0	0	0	0	0	0

 

Поскольку нижняя граница  этого подмножества (1,6) меньше, чем  подмножества (1*,6*), то ребро (1,6) включаем в маршрут.

 

2. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

 

i  j	1	2	3	4	5	di
2	1	∞	0(0)	0(1)	2	0
3	6	2	∞	1	0(1)	1
4	6	0(2)	2	∞	0(0)	0
5	0(1)	6	0(0)	1	∞	0
6	∞	2	0(1)	7	1	1
dj	1	2	0	1	0	0

 

Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (4,2), следовательно, множество разбивается  на два подмножества (4,2) и (4*,2*).

Нижняя граница гамильтоновых  циклов этого подмножества:

 

i  j	1	2	3	4	5	di
2	1	∞	0	0	2	0
3	6	2	∞	1	0	0
4	6	∞	2	∞	0	0
5	0	6	0	1	∞	0
6	∞	2	0	7	1	0
dj	0	2	0	0	0	2

 

В результате получим  другую сокращенную матрицу (4 x 4), которая  подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид:

 

i  j	1	3	4	5	di
2	1	0	∞	2	0
3	6	∞	1	0	0
5	0	0	1	∞	0
6	∞	0	7	1	0
dj	0	0	1	0	1

 

Поскольку нижняя граница  этого подмножества (4,2) меньше, чем  подмножества (4*,2*), то ребро (4,2) включаем в маршрут.

 

3. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

 

i  j	1	3	4	5	di
2	1	0(1)	∞	2	1
3	6	∞	0(0)	0(1)	0
5	0(1)	0(0)	0(0)	∞	0
6	∞	0(1)	6	1	1
dj	1	0	0	1	0

 

Наибольшая сумма констант приведения равна (1 + 0) = 1 для ребра (2,3), следовательно, множество разбивается  на два подмножества (2,3) и (2*,3*).

Нижняя граница гамильтоновых  циклов этого подмножества:

 

i  j	1	3	4	5	di
2	1	∞	∞	2	1
3	6	∞	0	0	0
5	0	0	0	∞	0
6	∞	0	6	1	0
dj	0	0	0	0	1

 

В результате получим  другую сокращенную матрицу (3 x 3), которая  подлежит операции приведения. После операции приведения сокращенная матрица будет иметь вид:

 

i  j	1	4	5	di
3	6	0	0	0
5	0	0	∞	0
6	∞	6	1	1
dj	0	0	0	1

Чтобы исключить подциклы, исключим следующие переходы: (3,4), так как нижняя граница этого подмножества (2,3) меньше, чем подмножества (2*,3*), то ребро (2,3) включаем в маршрут.

 

4. Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i  j	1	4	5	di
3	6	∞	0(6)	6
5	0(6)	0(5)	∞	0
6	∞	5	0(5)	5
dj	6	5	0	0