Задача коммивояжера — страница 2

Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, изображенного на рис. 1, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами. Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений – задача коммивояжера,

имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем. Задача коммивояжера             Общее описание Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных

задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы. Постановка задачи следующая. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? Чтобы привести задачу к научному виду,

введём некоторые термины. Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2,..,jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал Относительно математизированной

формулировки ЗК уместно сделать два замечания. Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ: Сij³0; Cjj=∞ (2) (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j: Сij= Сji. (3) и удовлетворять неравенству треугольника, т.е. для всех: Сij+ Сjk³Cik (4) В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется

много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать