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

G11=G12 G22,.

где G12={(1,3), (3,6}, а G22={(1,3), (3,6)}.

• 2.3. Вычислим оценку для G22: о (G22)=о (G11)+И (3,6)= 286 + 16 = 302.
• 2.4. Построим матрицу С1(2). Для этого вычеркнем в матрице C1(1) третью строку и шестой столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 1, полагая С61>, и выполним процесс приведения. В результате получим матрицу С1(2):

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

о (G12)=о (G11)+= 262 + 0 = 262.

Так как о (G12)<�о (G22), то на следующем шаге производим ветвление подмножества G12.

Шаг 3.

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

C24=0; C42=0; C45=0; C51=0; C54=0; C65=0.

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

И (i, j)= (2.4).

И (2,4)=30; И (4,2)=10; И (4,5)=0; И (5,1)=36; И (5,4)=0; И (6,5)=10.

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

3.2. Произведем ветвление:

G12=G13 G23,.

где G13={(1,3), (3,6), (5,1)}, а G22={(1,3), (3,6), (5,1)}.

• 3.3. Вычислим оценку для G23: о (G23)=о (G12)+И (5,1)= 286 + 36 = 322.
• 3.4. Построим матрицу С1(3). Для этого вычеркнем в матрице C1(2) пятую строку и первый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 6 в город 5, полагая С65>, и выполним процесс приведения. В результате получим матрицу С1(3):

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

о (G13)=о (G12)+= 262 + 10 = 272.

Так как о (G13)<�о (G23), то на следующем шаге производим ветвление подмножества G13.

Шаг 4.

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

C24=0; C42=0; C45=0; C62=0.

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

И (i, j)=.

И (2,4)=86; И (4,2)=0; И (4,5)=30; И (6,2)=86.

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

4.2. Произведем ветвление:

G13=G14 G24,.

где G14={(1,3), (3,6), (5,1), (2,4)}, а G22={(1,3), (3,6), (5,1), (2,4)}.

4.3. Вычислим оценку для G24:

о (G24)=о (G13)+И (2,4)= 272 + 86= 358.

4.4. Построим матрицу С1(4). Для этого вычеркнем в матрице C1(3) вторую строку и четвертый столбец. Чтобы избежать образования замкнутых подциклов, запретим переезд коммивояжера из города 4 в город 2, полагая С42>, и выполним процесс приведения. В результате получим матрицу С1(4):

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

о (G14)=о (G13)+= 272 + 0 = 272.

Матрица С1(4) имеет размерность 22 и допускает включение в маршрут только двух пар городов (4,5) и (6,2), что соответствует шагам 5 — 6. В результате получаем цикл l (t)={(1,3), (3,6), (5,1), (2,4), (4,5), (6,2)}, отвечающий подмножеству G16. Длина цикла l (t) равна оценке подмножества G16: l (t)=о (G16)=272 или 24+28+60+70+42+48=272.

Последовательность объезда городов можно представить следующим образом: 1>3>6>2>4>5>1 (рисунок 2.2).

Рисунок 2.2 Оптимальный маршрут коммивояжера.

Таким образом, используя метод линейного программирования, был составлен оптимальный маршрут коммивояжера. Определяющим фактором стало расстояние между пунктами. Полученный маршрут имеет вид: 1>3>6>2>4>5>1, расстояние данного маршрута составило 378 километров.