Единая транспортная система

 

Определяем оценку для G1:

 

G11 = G0 + åHi + åHj = 2602

 

Так как G11 < G12, то на следующем шаге разбиваем G1.

Выбираем пары городов – претендентов на ветвление:

С16, С24, С25, С36, С42, С61.

 

Р42 = 49 + 387 = 436                Р16 = 409               Р36 = 87

Р61 = 529 + 87 = 616                Р25 = 49                 Р24 = 689   max

 

Максимальную оценку имеет пара Р24.

Произведем ветвление  и вычислим оценку G1.2:

 

G22 = G12 + P24 = 2602 + 689 = 3291

 

Построим следующею матрицу, для этого вычеркнем в предыдущей матрице вторую строчку и четвертый столбец и выполним процесс приведения. Чтобы избежать образования замкнутых подциклов, запретим проезд из города 4 в город 2.

 

	1	2	5	6	Hi			1	2	5	6
1	Х	493	409	0	0		1	Х	493	409	0
3	87	387	Х	0	0		3	87	387	Х	0
4	610	Х	49	634	49		4	561	Х	0	585
6	0	583	529	Х	0		6	0	583	529	Х
							Hj	0	387	0	0

 

	1	2	5	6	Hi
1	Х	106	409	0	0
3	87	0	Х	0	0
4	561	Х	0	585	49
6	0	196	529	Х	0
Hj	0	387	0	0

 

Определяем оценку для G1.1:

 

G2.1 = G1 + åHi + åHj = 2602 + 49 + 387 = 3038

 

Так как G2.1 < G2.2, то на следующем шаге разбиваем G1.1.

Выбираем пары городов  – претендентов на ветвление:

С16, С36, С32, С45, С61.

 

Р45 = 561 + 409 = 970  max                Р16 = 106

Р61 = 196 + 87 = 283                          Р36 = 0                        Р32 = 106

 

Максимальную оценку имеет пара Р45.

Произведем ветвление  и вычислим оценку G1.1.2:

 

G3.2 = G2.1 + P45 = 3038 + 970 = 4008

 

Построим следующую матрицу, для этого вычеркнем в предыдущей матрице четвертую строчку и пятый столбец и выполним процесс приведения. Чтобы избежать образования замкнутых подциклов, запретим проезд из города 3 в город 2.

 

	1	2	6	Hi			1	2	6
1	Х	106	0	0		1	Х	106	0
3	87	Х	0	0		3	87	Х	0
6	0	196	Х	0		6	0	196	Х
						Hj	0	106	0

 

	1	2	6	Hi
1	Х	0	0	0
3	87	Х	0	0
6	0	90	Х	0
Hj	0	106	0

 

Определяем оценку для G3.1:

 

G3.1 = G2.1 + åHi + åHj = 3038 + 106 = 3144

 

Так как G3.1 < G3.2, то на следующем шаге разбиваем G3.1.

Выбираем пары городов  – претендентов на ветвление:

С16, С36, С12, С61.

 

Р61 = 87 + 90 = 177      max                Р12 = 90

Р36 = 87                                               Р16 = 0  

 

Максимальную оценку имеет пара Р61.

Произведем ветвление  и вычислим оценку G4.2:

 

G4.2 = G3.1 + P61 = 3144 + 177 = 3321

 

Построим следующею матрицу, для этого вычеркнем в предыдущей матрице шестую строчку и первый столбец и выполним процесс приведения. Чтобы избежать образования замкнутых подциклов, запретим проезд из города 1 в город 6.

 

	2	6	Hi
1	0	Х	0
3	Х	0	0
Hj	0	0

 

Определяем оценку для G4.1:

 

G4.1 = G3.1 + åHi + åHj = 3144

 

Так как G4.1 < G4.2, то на следующем шаге разбиваем G4.1.

Выбираем пары городов – претендентов на ветвление:

С12, С36.

 

Р12 =0                Р36 = 0 

 

Произведем ветвление  и вычислим оценку G5.1 и G6.1.:

G51 = 3144             G6.1 = 3144

 

В результате получаем цикл t1 = { 53, 24, 45, 61, 12, 36 }длина которого равна 3144. Последовательность объезда городов можно представить следующим образом 5® 3 ® 6 ®1® 2 ® 4 ® 5.

Подмножество G12 = 2946 < G6.1 = 3144 может привести к образованию цикла с меньшей оценкой, поэтому оно должно быть подвергнуто анализу. Для анализа необходимо восстановить исходную матрицу, запретить переезд из города 5 в город 3 и произвести аналогичные шаги расчетов.

 

	1	2	3	4	5	6	Hi
1	Х	493	102	962	409	0	0
2	123	Х	61	0	0	187	0
3	87	387	Х	698	151	0	0
4	610	0	393	Х	49	634	0
5	285	285	Х	292	Х	283	283
6	0	583	126	1052	529	Х	0

 

	1	2	3	4	5	6
1	Х	493	102	962	409	0
2	123	Х	61	0	0	187
3	87	387	Х	698	151	0
4	610	0	393	Х	49	634
5	2	2	Х	9	Х	0
6	0	583	126	1052	529	Х
Hj	0	0	61	0	0	0

 

	1	2	3	4	5	6	Hi
1	Х	493	41	962	409	0	0
2	123	Х	0	0	0	187	0
3	87	387	Х	698	151	0	0
4	610	0	332	Х	49	634	0
5	2	2	Х	9	Х	0	283
6	0	583	65	1052	529	Х	0
Hj	0	0	61	0	0	0

 

Определяем оценку для G2:

 

G12 = G0 + åHi + åHj = 2946

 

На следующем шаге разбиваем G2.

Выбираем пары городов  – претендентов на ветвление:

С16, С24, С25, С36, С42, С61, С23, С56.

 

Р42 = 51                Р16 = 41               Р36 = 87   max       Р23 = 41

Р61 = 67                Р25 = 49               Р24 = 9                  Р56 = 2

 

Максимальную оценку имеет пара Р36.

Произведем ветвление  и вычислим оценку G2.2:

 

G7.2 = G12 + P36 = 2946 + 87 = 3033

 

Построим следующею матрицу, для этого вычеркнем в предыдущей матрице третью строчку и шестой столбец и выполним процесс приведения.

	1	2	3	4	5	Hi			1	2	3	4	5
1	Х	493	41	962	409	41		1	Х	452	0	921	368
2	123	Х	0	0	0	0		2	123	Х	0	0	0
4	610	0	332	Х	49	0		4	610	0	332	Х	49
5	2	2	Х	9	Х	2		5	0	0	Х	7	Х
6	0	583	65	1052	529	0		6	0	583	65	1052	529