Маркетинговый анализ круизного рынка

 

Шаг 2. Приведение по столбцам.                           Таблица 3

j     i	1	2	3	4	5	ai
1	∞	0	404	955	1160	344
2	0	∞	60	542	816	344
3	344	0	∞	153	428	404
4	990	577	248	∞	0	309
5	1195	851	523	0	∞	309
bj	0	0	60	0	0	1710

 

Результат по шагу 2.                                                Таблица 4

j     i	1	2	3	4	5	ai
1	∞	0	344	955	1160	344
2	0	∞	0	542	816	344
3	344	0	∞	153	428	404
4	990	577	188	∞	0	309
5	1195	851	463	0	∞	309
bj	0	0	60	0	0	1770

 

На пересечении итоговой строки i и столбца j находится величина, которая называется – «сумма приводящих констант», и равняется:

S = Σa_i + Σb_j = 1770 миль.

Данные, приведенные в  таблице 3, определим как матрицу G0, которая определяет новую задачу, которая в качестве оптимального варианта имеет ту же самую последовательность портов.

Далее находим степени каждого из нулей полностью приведенной матрицы.

 

 

 

 

 

 

Шаг 3. Нахождение степеней нулей                       Таблица 5

j     i	1	2	3	4	5	ai
1	∞	0-344	344	955	1160	344
2	0-344	∞	0-188	542	816	344
3	344	0-153	∞	153	428	404
4	990	577	188	∞	0-616	309
5	1195	851	463	0-616	∞	309
bj	344	0	188	153	428	1770

 

Клетка с максимальной степенью нуля определяет дугу, в соответствии с которой будет выполняться дальнейшее ветвление. Эта клетка – (4-5), равна 616.

Разбиваем гамильтоновы контуры на два подмножества: G1 и G2. Матрицу с дугой (4-5) получаем путем вычеркивания строки 4 и столбца 5. Заменяем элемент 4-5 на ∞.

Шаг 4. Матрица G1                                     Таблица 5

j     i	1	2	3	4
1	∞	0	344	955
2	0	∞	0	542
3	344	0	∞	153
5	1195	851	463	∞

 

Шаг 5. Матрица G2.                                          Таблица 6.

j     i	1	2	3	4	5
1	∞	0	344	955	1160
2	0	∞	0	542	816
3	344	0	∞	153	428
4	990	577	188	∞	∞
5	1195	851	463	0	∞

 

Дальнейшее ветвление  начнем с подмножества G1.

 

 

Шаг 6. Приведенная матрица G1.                    Таблица 7

j     i	1	2	3	4	ai
1	∞	0	344	955	0
2	0	∞	0	542	0
3	344	0	∞	153	0
5	1195	851	463	∞	463
bj	0	0	0	153	616

 

Как видно из таблицы 7, приведенная константа этого  подмножества равна 616. Следовательно, нижняя граница гамильтоновых контуров:

S(G1) = 1770+616 = 2386

Сделаем приведение матрицы G2.

Шаг 7. Приведенная матрица G2.                          Таблица 8.

j     i	1	2	3	4	5	ai
1	∞	0	344	955	1160	0
2	0	∞	0	542	816	0
3	344	0	∞	153	428	0
4	990	577	188	∞	∞	188
5	1195	851	463	0	∞	0
bj	0	0	0	0	428	616

 

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

 S(G2) = 1770+616 = 2386

Следовательно, ветвлению  подлежат оба подмножества. Продолжим с подмножеством G1. Оцениваем клетки с «0».

Шаг 8. Степени нулей матрицы G1.                  Таблица 9

j     i	1	2	3	4	ai
1	∞	0-344	344	802	344
2	0-344	∞	0-0	389	0
3	344	0-0	∞	0-389	0
5	732	388	0-388	∞	388
bj	344	0	0	389	616

 

Наибольшая степень  нуля в клетке (3,4) – 389.

Далее, исключая дугу (3,4), получаем два подмножества: G3 и G4.

Шаг 9. Матрица G3.                          Таблица 10

j     i	1	2	3
1	∞	0	344
2	0	∞	0
5	732	388	0

 

Шаг 10. Матрица G4.                                Таблица 11

j     i	1	2	3	4
1	∞	0	344	802
2	0	∞	0	389
3	344	0	∞	∞
5	732	388	0	∞

 

Делаем приведение матриц G3 и G4.

Шаг 11. Приведение матрицы G3      Таблица 12

j     i	1	2	3	ai
1	∞	0	344	0
2	0	∞	0	0
5	732	388	0	0
bj	0	0	0	0

 

Шаг 12. Приведение матрицы G4.          Таблица 13

j     i	1	2	3	4	ai
1	∞	0	344	802	0
2	0	∞	0	389	0
3	344	0	∞	∞	0
5	732	388	0	∞	0
bj	0	0	0	389	389