Задача коммивояжора

 

*- ЗК с таким количеством  городов методом лексического  перебора современный компьютер  не смог бы решить даже за  всё время существования Вселенной.

Как видим по результатам  этой таблицы, алгоритм лексического перебора можно применять лишь в случае с количеством городов 5..12. Метод ветвей и границ, наряду с моим методом, можно применять всегда. Хотя мой метод я отнёс к приближённым алгоритмам, он фактически является точным, так как доказать обратное ещё не удалось.

 

 

 

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

 

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

Задача  о производстве красок. Имеется производственная линия для производства 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) зависит от механических свойств пресса  и достаточно громоздок. Явно выписывать эти функции нет необходимости

Действия 1-3 (переналадка с  i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому

С[i,j] = max(t^(x), t^(y), t^(z))

Теперь, как и в предыдущем случае, задача составления оптимальной  программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).

 

 

Выводы

 

1. Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
2. Предложен собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника и включения в него центральных вершин (городов).
3. Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора;  для большого числа вершин рациональнее применять метод ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
4. Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
5. Приведены тексты программ, позволяющие решить ЗК различными методами.

 

Литература

 

1. О. Оре  Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с.
2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с.
3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.

 

 

8. Приложения