Решение задач коммивояжёра, способов её решения

 

     После проведения процедуры приведения с  r₁=10 получим новую нижнюю границу 57 + 10 = 67.

     В матрице, соответствующей  , вычеркиваем первую строку и четвертый столбец и положим c₄₁= ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c¹_ij}: 

 

     Для приведения надо вычесть минимум  по первому столбцу: h₁=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы 
φ ( ) = 67 и φ ( ) = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины. 

     

     Рис. 1.4 Ветвление на первом шаге

 

      Приведенная платежная матрица для 

 

     Далее продолжаем процесс ветвления. Найдем степени Θ_ij нулевых элементов этой матрицы Θ₂₁ =16, Θ₃₆ = 5, Θ₄₂ = 2, Θ₅₆ = 2, Θ₆₂ = 0, Θ₆₃ =9, Θ₆₅ = 2. Наибольшая степень Θ₂₁. Затем множество разбивается дуге (2, 1) на два новых и .

     В матрице для  вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c₄₂= ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2. 

 

     Для приведения надо вычесть минимум по строке 4: r₄=2. При этом нижняя граница станет равной 48+2 = 50.

     Нижняя  граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ ( ) = 64 и φ ( ) = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

 

     

     Рис. 1.5 Ветвление на втором шаге 

     Приведенная платежная матрица для   

 

     Степени Θ_ij нулевых элементов этой матрицы Θ₃₆ = 5, Θ₄₅ = 0, Θ₅₆ = 22, Θ₆₂ = 13, Θ₆₃ =7, Θ₆₅ = 0. Наибольшая степень Θ_56. Затем множество разбивается дуге (2, 1) на два новых и .

     Нижняя  граница для равна 50 + 22 = 72. В матрице для вычеркиваем строку 5 и столбец 6 и полагаем c₆₅= ∞. Получим матрицу: 

 

     Для приведения надо вычесть минимум  по строке 3: r₃=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов . 

 

     

     Рис. 1.6 Ветвление на третьем шаге 

     Приведенная платежная матрица для   

 

     Степени Θ_ij нулевых элементов этой матрицы Θ₃₅ = 8, Θ₄₅ = 7, Θ₆₂ = 8, Θ₆₃ =7. Выбираем Θ₃₅ = 8. Разбиваем на и .

     Нижняя  граница для равна 55 + 8 = 64. В матрице для вычеркиваем строку 3 и столбец 5 и полагаем c₆₃= ∞. Получим 

 

     Для приведения надо вычесть минимум  по строке 4: r4=7. При этом нижняя граница  станет равной 55+7 = 62. После приведения получим 

 
 

     Из  матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

     Рис. 1.7 Ветвление на четвертом шаге 

     

     Рис. 1.8 Дерево ветвления с оценками 

     Полученный  маршрутом коммивояжера z₀ = (1, 4, 3, 5, 6, 2, 1) или (A-D-C-E-F-B-A). 
 
 

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

     Кроме очевидного применения задачи коммивояжера на практике, существует ещё ряд задач, сводимых к решению задачи коммивояжера. 

     Задача  о производстве красок. 

     Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке p=(j₁,j₂,..,j_n,j₁). После окончания производства краски i и перед началом производства краски j      надо отмыть оборудование от краски i. Для этого требуется время C[i,j]. Очевидно, что C[i,j] зависит как от i, так и от j, и что, вообще говоря,C[i,j]≠C[j,i]. При некотором выбранном порядке придется на цикл производства красок потратить время:

     

     Где t_k - чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.

     Таким образом, задача коммивояжера и задача о минимизации времени переналадки  – это просто одна задача, только варианты ее описаны разными словами. 

     Задача  о дыропробивном  прессе. 

     Дыропробивной пресс производит большое число  одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент подведена нужная точка листа.

     Операция  пробивки j-того отверстия характеризуется четверкой чисел (x_j,y_j,z_j,t_j),, где x_j,y_j- координаты нужного положения стола, z_j - координата нужного положения диска и t_j - время пробивки j-того отверстия.

     Производство  панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x₀, y₀) диск в положении z₀ причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x₀,y₀,z₀,0).

     Чтобы пробить j-е отверстие непосредственно после i-того необходимо произвести следующие действия:

1. Переместить стол по оси x из положения x_i в положение x_j, затрачивая при этом время t^(x)(|x_i-x_j|)=t_i,j^(x).
2. Проделать то же самое по оси y, затратив время t_i,j^(y) .  
3. Повернуть головку по кратчайшей из двух дуг из положения z_i в положение z_j, затратив время t_i,j^(z) .  
4. Пробить j-тое отверстие, затратив время t_j.

     Конкретный  вид функций t^(x), t^(y), t^(z) зависит от механических свойств пресса  и достаточно громоздок. Явно выписывать эти функции нет необходимости