Задача по системному анализу

                             Системный анализ

Решить задачу коммивояжера с матрицей расстояний.

 

Решение

Возьмем в качестве произвольного  маршрута: 
X₀ = (1,2);(2,3);(3,4);(4,5);(5,1) 
Тогда F(X₀) = 23 + 16 + 5 + 1 + 5 = 50 
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. 
d_i = min(j) d_ij 

i j	1	2	3	4	5	di
1	∞	23	24	7	27	7
2	14	∞	16	10	5	5
3	22	15	∞	5	22	5
4	20	18	22	∞	1	1
5	5	8	7	12	∞	5

 

Вычтем  d_i из элементов рассматриваемой строки.

Получим. 

i j	1	2	3	4	5
1	∞	16	17	0	20
2	9	∞	11	5	0
3	17	10	∞	0	17
4	19	17	21	∞	0
5	0	3	2	7	∞

 

Операцию редукции проводим по столбцам, и находим минимальный  элемент: 
d_j = min(i) d_ij 

i j	1	2	3	4	5
1	∞	16	17	0	20
2	9	∞	11	5	0
3	17	10	∞	0	17
4	19	17	21	∞	0
5	0	3	2	7	∞
dj	0	3	2	0	0

 

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

 

i j	1	2	3	4	5
1	∞	13	15	0	20
2	9	∞	9	5	0
3	17	7	∞	0	17
4	19	14	19	∞	0
5	0	0	0	7	∞

 

Сумма констант приведения определяет нижнюю границу H:

H = ∑d_i + ∑d_j

H = 7+5+5+1+5+0+3+2+0+0 = 28

Элементы матрицы d_ij соответствуют расстоянию от пункта i до пункта j.

D является матрицей nxn с неотрицательными элементами d_ij >=0

Длина маршрута определяется выражением:

F(M_k) = ∑d_ij

Причем каждая строка и столбец входят в маршрут  только один раз с элементом d_ij . 

Шаг 1 - определим ребро ветвления.

i j	1	2	3	4	5	di
1	∞	13	15	0(13)	20	13
2	9	∞	9	5	0(5)	5
3	17	7	∞	0(7)	17	7
4	19	14	19	∞	0(14)	14
5	0(9)	0(7)	0(9)	7	∞	0
dj	9	7	9	0	0	0

Разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. 

 

 

 

 

 

 

 

 

 

 

d(1,4) = 13 + 0 = 13;

d(2,5) = 5 + 0 = 5;

d(3,4) = 7 + 0 = 7;

d(4,5) = 14 + 0 = 14;

d(5,1) = 0 + 9 = 9;

d(5,2) = 0 + 7 = 7;

d(5,3) = 0 + 9 = 9. 
Наибольшая сумма констант приведения равна (14 + 0) = 14 для ребра (4,5), следовательно, множество разбивается на два подмножества (4,5) и (4*,5*). 
Нижняя граница гамильтоновых циклов этого подмножества: 
H(4*,5*) = 28 + 14 = 42 
Исключение ребра (4,5) проводим путем замены элемента d₄₅ = 0 на ∞, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,5*), в результате получим редуцированную матрицу. 

i j	1	2	3	4	5	di
1	∞	13	15	0	20	0
2	9	∞	9	5	0	0
3	17	7	∞	0	17	0
4	19	14	19	∞	∞	14
5	0	0	0	7	∞	0
dj	0	0	0	0	0	14

 

Включение ребра (4,5) проводится путем исключения всех элементов 4-ой строки и 5-го столбца, в которой элемент d₅₄ заменяем на ∞, для исключения образования негамильтонова цикла.

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

Сумма констант приведения сокращенной матрицы: 
∑d_i + ∑d_j = 5

После операции приведения сокращенная матрица будет иметь  вид: 

i j	1	2	3	4	di
1	∞	13	15	0	0
2	9	∞	9	5	5
3	17	7	∞	0	0
5	0	0	0	∞	0
dj	0	0	0	0	5

 

Нижняя граница подмножества (4,5) равна:

H(4,5) = 28 + 5 = 33 ≤ 42

Нижняя граница этого подмножества (4,5) меньше, чем подмножества (4*,5*), ребро (4,5) включаем в маршрут с новой границей H = 33

Шаг 2 - определим ребро ветвления.

Разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). 
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на ∞ (бесконечность) и определяем для них сумму образовавшихся констант приведения. 
d(1,4) = 13 + 0 = 13;

d(2,4) = 4 + 0 = 4;

d(3,4) = 7 + 0 = 7;

d(5,1) = 0 + 4 = 4;

d(5,2) = 0 + 7 = 7;

d(5,3) = 0 + 4 = 4. 
Наибольшая сумма констант приведения равна (13 + 0) = 13 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*). 
Нижняя граница гамильтоновых циклов этого подмножества: 
H(1*,4*) = 33 + 13 = 46 
Исключение ребра (1,4) проводим путем замены элемента d₁₄ = 0 на ∞, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.

i j	1	2	3	4	di
1	M	13	15	M	13
2	4	M	4	0	0
3	17	7	M	0	0
5	0	0	0	M	0
dj	0	0	0	0	13

 

Включение ребра (1,4) проводится путем исключения всех элементов 1-ой строки и 4-го столбца, в которой элемент d₄₁заменяем на ∞, для исключения образования негамильтонова цикла.

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

Сумма констант приведения сокращенной матрицы: 
∑d_i + ∑d_j = 11

i j	1	2	3	di
2	4	M	4	4
3	17	7	M	7
5	0	0	0	0
dj	0	0	0	11