Курсовая работа: Задача коммивояжера
1.3 Практическое применение задачи
коммивояжера
Кроме
очевидного применения ЗК на практике, существует ещё ряд задач, сводимых к
решению ЗК.
Задача
о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним
процессором.. Будем считать также, что единовременно процессор производит
только одну краску, поэтому краски нужно производить в некотором порядке
Поскольку производство циклическое, то краски надо производить в циклическом
порядке p=(j1,j2,..,jn,j1). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого требуется время C[i,j].
Очевидно, что C[i,j] зависит как от i, так и
от j, и что, вообще говоря,C[i,j]≠C[j,i]. При
некотором выбранном порядке придется на цикл производства красок потратить
время.
Таким
образом, ЗК и задача о минимизации времени переналадки – это просто одна
задача, только варианты ее описаны разными словами.
Задача
о дыропробивном прессе. Дыропробивной пресс производит большое число одинаковых
панелей – металлических листов, в которых последовательно по одному пробиваются
отверстия разной формы и величины. Схематически пресс можно представить в виде
стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по
периметру которого расположены дыропробивные инструменты разной формы и
величины. Каждый инструмент присутствует в одном экземпляре. Диск может
вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на
подвешенный под него инструмент тогда, когда под инструмент подведена нужная
точка листа.
Операция
пробивки j-того отверстия характеризуется четверкой
чисел (xj,yj,zj,tj),, где
xj,yj-
координаты нужного положения стола, zj -
координата нужного положения диска и tj -
время пробивки j-того отверстия.
Производство
панелей носит циклический характер: в начале и конце обработки каждого листа
стол должен находиться в положениях (x0, y0) диск в положении z0 причем в этом положении отверстие не пробивается. Это начальное
состояние системы можно считать пробивкой фиктивного нулевого отверстия. С
параметрами (x0,y0,z0,0).
Чтобы
пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:
1.
Переместить стол по оси x из положения xi в положение xj, затрачивая при этом время t(x)(|xi-xj|)=ti,j(x)
Проделать
то же самое по оси y, затратив время ti,j(y)
Повернуть
головку по кратчайшей из двух дуг из положения zi в положение zj, затратив
время ti,j(z) .
Пробить
j-тое отверстие, затратив время tj.
Конкретный
вид функций t(x), t(y), t(z) зависит от
механических свойств пресса и достаточно громоздок. Явно выписывать эти
функции нет необходимости
Действия
1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно
после завершения самого длительного из этих действий. Поэтому
С[i,j] = max(t(x), t(y), t(z))
Теперь,
как и в предыдущем случае, задача составления оптимальной программы для
дыропробивного пресса сводится к ЗК (здесь - симметричной).
Выводы
Изучены
эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы
решения ЗК – это полный перебор или усовершенствованный перебор. Оба они,
особенно первый, не эффективны при большом числе вершин графа.
Предложен
собственный эффективный метод решения ЗК на основе построения выпуклого многоугольника
и включения в него центральных вершин (городов).
Проведён
анализ наиболее рациональных методов решения ЗК и определены области их
эффективного действия: для малого числа вершин можно использовать точный метод
лексического перебора; для большого числа вершин рациональнее применять метод
ветвей и границ или метод автора работы (Анищенко Сергея Александровича).
Изучены
практические применения ЗК и задачи с переналадками, сводимые к ЗК.
Приведены
тексты программ, позволяющие решить ЗК различными методами.
Список литературы
О.
Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир»,
1965, 174 с.
В.
П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с.
Ю.
Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование:
учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
Е.
В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного
эксперимента. – М., Наука, 1979, 345 с.
Е.
П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
В.
М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. –
Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
Ф.
А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер,
2001, 304 с., ил.
|