Применение методов решения задачи коммивояжера на практике

При вычислении оценки затрат для учитывают, что, если ребро (h,k) входит в маршрут, то ребро (k,h) не может входить в маршрут, поэтому принимаем: ; если в маршрут включено ребро (h,k), то ни одно другое ребро, начинающееся в пункте h или заканчивающееся в пункте k не может входить в маршрут, поэтому строка h и столбец k вычеркиваются. Полученная матрица приводится, т.е. выполняется предварительный этап алгоритма. Пусть сумма приводящих констант матрицы: .

Из множеств и для дальнейшего ветвления выбирается множество, имеющее меньшую оценку. При выборе нужно вернуться к шагу 1, используя на этом шаге приведенную матрицу, полученную на шаге 3.2. При выборе нужно вернуться к матрице , принять и привести полученную в результате матрицу, после чего перейти к шагу 2, используя на нем эту приведенную матрицу. Если несколько множеств имеют равную минимальную оценку, то дальнейшее ветвление производится для всех множеств с минимальной оценкой. [17, c. 94]

Таким образом, метод ветвей и границ позволяет находить все оптимальные решения.

Алгоритм продолжается до тех пор, пока в подмножестве маршрутов с наименьшей оценкой не останется всего один маршрут. В расчетах это соответствует ситуации, когда исследуемая матрица имеет размерность . [18, c. 225]

 

 

2.3 Венгерский метод

 

Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу.

Алгоритм венгерского метода:

1. Проводим предварительные преобразования матрицы C (получаем эквивалентную матрицу Сэ).

Преобразование в столбцах:

 

Преобразование в строках:

 

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

2. Рассматривая строки и столбцы матрицы сверху вниз, слева направо поочередно, отмечаем первый попавшийся ноль и берём его в квадратные скобки, другие нули в этой же строке и в этом же столбце вычеркиваем.
3. Затем, вычёркиваем строки и столбцы с возможно большим количеством нулевых элементов. Получаем сокращённую матрицу.
4. Минимальный элемент сокращённой матрицы вычитаем из всех её элементов, а затем складываем минимальный элемент с элементами расположенными на пересечении вычеркнутых строк и столбцов. Таким образом, получаем следующую эквивалентную матрицу. После этого повторяет выполнение шага 2.
5. Производим построение цепочки из нулей стоящих в квадратных скобках и вычисляем оптимальный маршрут.

 

3 Применение методов решения задачи коммивояжера на практике

 

 

3.1 Решение задачи коммивояжера методом ветвей и границ

 

Фирма по производству новогодних игрушек должна доставить заказ в 6 городов: Кирсанов (1); Котовск (2); Рассказово (3); Мичуринск (4) Инжавино (5); Уварово (6). Нужно найти кротчайший путь, объездив все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город 1.

Расстояния между городами заданы следующей матрицей. (Таблица 1)

Таблица 1 Исходные данные, матрица размерностью 6´6

i  j	1	2	3	4	5	6
1	M	5	4	2	4	1
2	1	M	2	4	5	7
3	7	5	M	4	2	4
4	4	5	7	M	2	1
5	2	1	4	7	M	5
6	5	7	2	1	1	M

 

 

Математическая модель:

 

 

 

Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы С найти минимальный элемент: di = min(j) dij . (Таблица 2)

Таблица 2 Приведение матрицы по строкам, матрица размерностью 6´6

i  j	1	2	3	4	5	6	di
1	M	5	4	2	4	1	1
2	1	M	2	4	5	7	1
3	7	5	M	4	2	4	2
4	4	5	7	M	2	1	1
5	2	1	4	7	M	5	1
6	5	7	2	1	1	M	1

 

Затем вычитаем di из элементов рассматриваемой строки. Во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 3)

Таблица 3 Результат вычитания минимальных элементов рассматриваемой строки, матрица размерностью 6´6

i  j	1	2	3	4	5	6
1	M	4	3	1	3	0
2	0	M	1	3	4	6
3	5	3	M	2	0	2
4	3	4	6	M	1	0
5	1	0	3	6	M	4
6	4	6	1	0	0	M

 

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij . (Таблица 4)

Таблица 4 Приведение матрицы по столбцам, матрица размерностью 6´6

i  j	1	2	3	4	5	6
1	M	4	3	1	3	0
2	0	M	1	3	4	6
3	5	3	M	2	0	2
4	3	4	6	M	1	0
5	1	0	3	6	M	4
6	4	6	1	0	0	M

 

Продолжение таблицы 4 Приведение матрицы по столбцам, матрица размерностью 6´6

dj

0

0

1

0

0

0

 

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения. (Таблица 5)

Таблица 5 Результат вычитания минимальных элементов рассматриваемого столбца, матрица размерностью 6´6

i  j	1	2	3	4	5	6
1	M	4	2	1	3	0
2	0	M	0	3	4	6
3	5	3	M	2	0	2
4	3	4	5	M	1	0
5	1	0	2	6	M	4
6	4	6	0	0	0	M

 

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

H = 1+1+2+1+1+1+0+0+1+0+0+0 = 8

Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то С является матрицей nxn с неотрицательными элементами dij >=0 .

Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.

Длина маршрута определяется выражением: F(Mk) = ∑dij

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

Шаг №1. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

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

Таблица 6 Определение ребра ветвления, матрица размерностью 6´6

i  j	1	2	3	4	5	6	di
1	M	4	2	1	3	0(1)	1
2	0(1)	M	0(0)	3	4	6	0
3	5	3	M	2	0(2)	2	2
4	3	4	5	M	1	0(1)	1
5	1	0(4)	2	6	M	4	1
6	4	6	0(0)	0(1)	0(0)	M	0
dj	1	3	0	1	0	0	0