Анализ множества D.

Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

 

=> ;

 

Аналогично определяем матрицу минимальных расстояний по столбцам.

 

=> ;

;

 

Выберем начальный план: . Тогда верхняя оценка:

. Очевидно, что , где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.

2) Анализ подмножества D₁₂.

 

;

;

;

;

;

 

3) Анализ подмножества D₁₃.

 

;

;

;

;

 

4) Анализ подмножества D₁₄.

 

;

;

;

;

;

5) Анализ подмножества D₁₅.

 

;

;

;

;

;