Стратегия управления доставкой груза на транспорте

Таблица 2.2 – Расстояние между пунктами

С =	∞	126	36	108	144	198
	144	∞	72	90	108	72
	54	90	∞	108	144	36
	108	54	90	∞	54	216
	72	108	144	90	∞	162
	180	90	54	216	72	∞

 

Решение

1. Осуществим приведение  матрицы С по строкам и столбцам. Приведенную матрицу С⁽⁰⁾ представим в виде таблицы, приводящие константы по строкам и столбцам запишем соответственно справа матрицы и снизу.

С' =		1	2	3	4	5	6	hi
	1	∞	90	0	72	108	162	36
	2	72	∞	0	18	36	0	72
	3	18	54	∞	72	108	0	36
	4	54	0	36	∞	0	162	54
	5	0	36	72	18	∞	90	72
	6	126	36	0	162	18	∞	54
	Hj	0	0	0	18	0	0

 

 

 

 

 

 

 

 

С(0) =		1	2	3	4	5	6	hi
	1	∞	90	0	54	108	162	36
	2	72	∞	0	0	36	0	72
	3	18	54	∞	54	108	0	36
	4	54	0	36	∞	0	162	54
	5	0	36	72	0	∞	90	72
	6	126	36	0	144	18	∞	54
	Hj	0	0	0	18	0	0	18            324

 

2. Определим  оценку множества G⁰, вычислив сумму приводящих констант

ξ(G⁰)=

= 324 + 18 = 342.

Шаг 1.

1.1 Выбираем пары городов-претендентов  на ветвление, т.е. (i,j) для которых C_ij=0:

C₁₃=0; C₂₃=0; C₂₄=0; C₂₆=0; C₃₆=0; C₄₂=0; C₄₅=0; C₅₁=0; C₅₄=0; C₆₃=0

Для выделенных претендентов подсчитаем оценки по формуле:

Θ(i,j)=

.

Θ(1,3)=54; Θ(2,3)=0; Θ(2,4)=0; Θ(2,6)=0; Θ(3,6)=18; Θ(4,2)=36; Θ(4,5)=18; Θ(5,1)=18; Θ(5,4)=0; Θ(6,3)=18.

Для ветвления  выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (1,3), так как max Θ(i,j)=Θ(1,3)=54.

1.2. Произведем  ветвление: G⁰=G₁¹ G₂¹, где G₁¹={1,3}, а G₂¹={1,3}.

1.3. Вычислим  оценку для G₂¹: ξ(G₂¹)=ξ(G⁰)+Θ(1,3)=342+54=396.

1.4. Построим  матрицу С₁⁽¹⁾. Для этого вычеркнем в матрице С⁽⁰⁾ первую строку и третий столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 3 в город 1, полагая С₃₁→¥, и выполним процесс приведения. В результате получим матрицу С₁⁽¹⁾:

С1(1) =		1	2	4	5	6	hi
	2	72	∞	0	36	0	0
	3	∞	54	54	108	0	0
	4	54	0	∞	0	162	0
	5	0	36	0	∞	90	0
	6	108	18	126	0	∞	18
	Hj	0	0	0	0	0

 

Определим оценку для множества G₁¹:

ξ(G₁¹)=ξ(G⁰)+

= 342 + 18 = 360.

Так как ξ(G₁¹)<ξ(G₂¹), то на следующем шаге производим ветвление подмножества G₁¹.

Шаг 2.

2.1 Выбираем пары городов-претендентов на ветвление, т.е. (i,j) для которых C_ij=0:

C₂₄=0; C₂₆=0; C₃₆=0; C₄₂=0; C₄₅=0; C₅₁=0; C₅₄=0; C₆₅=0.

Для выделенных претендентов подсчитаем оценки по формуле:

Θ(i,j)=

.

Θ(2,4)=0; Θ(2,6)=0; Θ(3,6)=54; Θ(4,2)=18; Θ(4,5)=0; Θ(5,1)=54; Θ(5,4)=0; Θ(6,5)=18.

Для ветвления выберем  пару претендентов с максимальной оценкой Θ(i,j), то есть пару (3,6), так как max Θ(i,j)=Θ(3,6)=54.

2.2. Произведем ветвление: G₁¹=G₁² G₂², где G₁²={(1,3), (3,6}, а G₂²={(1,3), (3,6)}.

2.3. Вычислим оценку для G₂²: ξ(G₂²)=ξ(G₁¹)+Θ(3,6)= 360 + 54 = 414.

2.4. Построим  матрицу С₁⁽²⁾. Для этого вычеркнем в матрице C₁⁽¹⁾ третью строку и шестой столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 1, полагая С₆₁→¥, и выполним процесс приведения. В результате получим матрицу С₁⁽²⁾:

С1(2) =		1	2	4	5	hi
	2	72	∞	0	36	0
	4	74	0	∞	0	0
	5	0	36	0	∞	0
	6	∞	18	126	0	0
	Hj	0	0	0	0

Определим оценку для множества G₁²:

ξ(G₁²)=ξ(G₁¹)+

= 360 + 0 = 360.

Так как ξ(G₁²)<ξ(G₂²), то на следующем шаге производим ветвление подмножества G₁².

Шаг 3.

3.1 Выбираем пары городов-претендентов  на ветвление, т.е. (i,j) для которых C_ij=0:

C₂₄=0; C₄₂=0; C₄₅=0; C₅₁=0; C₅₄=0; C₆₅=0.

Для выделенных претендентов подсчитаем оценки по формуле:

Θ(i,j)=                                        (2.4)

Θ(2,4)=36; Θ(4,2)=18; Θ(4,5)=0; Θ(5,1)=54; Θ(5,4)=0; Θ(6,5)=18.

Для ветвления выберем  пару претендентов с максимальной оценкой Θ(i,j), то есть пару (2,4), так как max Θ(i,j)=Θ(5,1)=54.

3.2. Произведем ветвление: G₁²=G₁³ G₂³, где G₁³={(1,3), (3,6), (5,1)}, а G₂²={(1,3), (3,6), (5,1)}.

3.3. Вычислим оценку  для G₂³: ξ(G₂³)=ξ(G₁²)+Θ(5,1)= 360 + 54 = 414.

3.4. Построим матрицу С₁⁽³⁾. Для этого вычеркнем в матрице C₁⁽²⁾ пятую строку и первый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 5, полагая С₆₅→¥, и выполним процесс приведения. В результате получим матрицу С₁⁽³⁾:

С1(3) =		2	4	5	hi
	2	∞	0	36	0
	4	0	∞	0	0
	6	0	108	∞	18
	Hj	0	0	0

Определим оценку для множества G₁³:

ξ(G₁³)=ξ(G₁²)+

= 360 + 18 = 378.

Так как ξ(G₁³)<ξ(G₂³), то на следующем шаге производим ветвление подмножества G₁³.

Шаг 4.

4.1 Выбираем пары городов-претендентов  на ветвление, т.е. (i,j) для которых C_ij=0:

C₂₄=0; C₄₂=0; C₄₅=0; C₆₂=0.

Для выделенных претендентов подсчитаем оценки по формуле:

Θ(i,j)=

.

Θ(2,4)=144; Θ(4,2)=0; Θ(4,5)=360; Θ(6,2)=108.

Для ветвления  выберем пару претендентов с максимальной оценкой Θ(i,j), то есть пару (3,6), так как max Θ(i,j)=Θ(2,4)=144.

4.2. Произведем  ветвление: G₁³=G₁⁴ G₂⁴, где G₁⁴={(1,3), (3,6), (5,1), (2,4)}, а G₂²={(1,3), (3,6), (5,1), (2,4)}.

4.3. Вычислим  оценку для G₂⁴: ξ(G₂⁴)=ξ(G₁³)+Θ(2,4)= 378 + 144= 522.

4.4. Построим матрицу С₁⁽⁴⁾. Для этого вычеркнем в матрице C₁⁽³⁾ вторую строку и четвертый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 4 в город 2, полагая С₄₂→¥, и выполним процесс приведения. В результате получим матрицу С₁⁽⁴⁾:

С1(4) =		2	5	hi
	4	∞	0	0
	6	0	∞	0
	Hj	0	0

Определим оценку для множества G₁⁴: