Задача Комивояжора и ее решение методом ветвей и границ


Коммивояжер (К) должен обойти N городов и вернуться в исходный город. Пронумеруем эти города 1,2….N. Известна матрица расстояний L=(lij)NN так как К из города i переходит в другой город j, то lij не существует. Если из города i нельзя переход в j то расстояние lij=?. В общем случае lij? lji. Будем предполагать что К находится в 1 городе. Он должен побывать в каждом из последующих городов один раз и вернуться в исходный город. Необходимо определить в какой последовательности К должен посещать все города, чтобы его суммарно пройденный путь имел минимальную длину.

Изобразим города в виде точек на плоскости а расстояние между городами в виде дуг. Получим полный ориентированный граф. Путь К на этом графе представляет собой гамильтоновой контур.

Задача заключается в том, чтобы из всех гамильтоновых контуров выбрать контур с наименьшей длиной. Если решать задачу методом перебора то задача К с N городами имеет (N-1)!.

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

Поставим в соответствие каждой дуге графа (i,j) переменную хij, (1) хij=(1, если из города i К следует в j; 0, если иначе), так как в каждом городе должен побывать 1 раз, то он 1 раз въезжает в любой город j и 1 раз выезжает из любого города.

Условие, что К 1 раз выезжает в любой город j изображается схематически: (2) Sхij=1, j=1,N i?j.

Аналогично, записывается условие что К 1 раз выезжает из любого города i: (3) S хij=1, i=1,N i?j

Условий (1) (2) (3) недостаточно для образования пути К.

(4) Ui-Uj+Nxij?N-1 i,j=1,N. Это условие показывает на каком шаге К посещает i и j.

Длина пути К: (5) Z=SSlijxij®min

Определение множества решений D(1) в задаче К

Решением задачи К является путь К или гамильтонов контур графа с N вершинами => D(1) множество всевозможных путей К или множество гамильтоновых контуров графа. необходимо найти нижнюю границу, оценку длины любого пути К то есть j( D(1))

Нахождение j( D(1)) Теорема 1 и 2

Теорема 1: длина любого пути К не меньше суммы приведенных констант соответствующей матрицы расстояний L.

Доказательство: пусть К должен посетить N городов, задана матрица L=(lij)NN – расстояний между городами.

Рассмотрим любой путь К f=(i1,i2…..iN,i1), где i1,i2…..iN,i1 некоторая перестановка из чисел 1,2….N.

В самом начале пути К находится в некотором городе i1. Длина этого пути l=li1,i2+li2,i3+liN,i1 (6).

В любой i-ой строке матрицы расстояний L найдем наименьший элемент и обозначим его hi, то есть hi=min lij, i=1,N — где hi приведенная константа i-ой строки матрицы L. Из элементов каждой i-ой строки вычитаем соответствующую приведенную константу hi,то есть вычисляем значение lij=lij— hi,i,j=1,N i?j (7).

Получим L, lij?0. Из (7) lij = lij + hi. Подставим эти значения в (6) получим l=li1,i2+li2,i3+liN,i1+S hi (8). В каждом j-ом столбце матрицы L найдем наименьшее значение Hj=min lij, Hj – приведенная константа столбца j. Из элементов каждого j-ого столбца вычитаем соответствующее значение Hj, lij’’=lij— Hj (9).

Получим матрицу L’’= (lij’’)NN, lij’’?0. Из (9) найдем lij= lij’’ + Hj и подставим в (8). l= li1,i2’’+li2,i3’’+liN,i1’’+S hi+S Hj (10), l?S hi+S Hj, l — длина пути, т.е. l не меньше суммы приведенных констант матрицы L. =>j(D(1))? S hi+S Hj

Теорема 2: оптимальный путь (оптимальное решение) Задачи К с матрицей L совпадает с оптимальным путем задачи К с матрицей L’’. Длина пути в задаче с матрицей L больше длины соответствующего пути в задаче с матрицей L’’ на сумму приведенных констант.

Процесс перехода от L®L ®L’’ называется приведением матрицы L,а L’’ приведенной матрицей

Процесс разбиения (ветвления) множества D(1).

Будем искать оптимальный путь в задаче с матрицей L’’. Наиболее вероятно, что в кратчайший путь К войдут те дуги (i,j) для которых в L’’ lij’’=0. Среди этих дуг необходимо найти ту исключение которой из пути приведет к большему увеличению j(D(1)) => такую дугу на данном этапе исключать нецелесообразно. Эта дуга называется наиболее перспективной. Чтобы найти ее рассмотрим поочередно нулевые элементы матрицы L’’ и для lij’’=0 в i-ой строке и j-ом столбце находим наименьшие элементы (исключая элемент lij’’=0), складываем их. Их сумму обозначим g. Среди всех gij найдем max gkr=maxgij – наиболее перспективной является дуга (k,r), множество D(1)1 – множество путей К которые не содержат дугу (k,r). Условно обозначаем D(1)1-(k,r). D(1)2 — множество путей К которые содержат дугу (k,r). Условно обозначаем (k,r).

Необходимо определить матрицу расстояний подмножества D(1)1 обозначим L(k,r), для D(1)2 L(k,r).

Нахождение матриц L(k,r) и L(k,r).

В матрице L(k,r) следует запретить переезд из города k в город r т.е. lk,r=?, а все остальные элементы lij переносятся из матрицы L’’. Получим L(k,r) => привести т.е. осуществить переход от L(k,r) => L(k,r) => L(k,r)’’. Сумма приведенных констант, полученных в результате приведения S hi+S Hj=gk,r

Оценка j(D1(1))= j(D(1))+ S hi+S Hj=g( D(1))+gk,r

Найдем матрицу L(k,r), которая соответствует подмножеству D(1)2 а D(1)2 – множество всех путей в котором из города k путь лежит в город r => в матрице L(k,r) запрещен выезд из k-города любой другой город кроме r, т.е. рассмотрим lk,j =? j?r. Это соответствует запрещению всех элементов k-ой строки, кроме lk,r, т.е. уравниваем их все ?. С другой стороны необходимо запретить приезд в r-й город из всех городов, кроме k, т.е. положим li,r =? i?k. Это соответствует тому, что все элементы r-го столбца, кроме элемента lk,r будут равны ?, т.е. матрицы исключаем r-й столбец, необходимо запретить обратный переезд из города r в k, т.е. lk,r=?.

Все остальные элементы в матрицу L(k,r) переносятся из матрицы L’’. Размерность L(k,r) уменьшена. После этого матрицу L(k,r) необходимо привести. Найдем сумму приведенных констант RN-1= S hi+S Hj

Оценка j(D2(1))= j(D(1))+ RN-1.

Нахождение второй наиболее перспективной дуги

Поскольку путь К еще не найден, необходимо согласно методу ветвей и границ для дальнейшего разбиения выбрать подмножество с наименьшей оценкой. Пусть это будет подмножество D(1)2, т.е. j( D(1)2)<j( D(1)1). (если оценки одинаковые, то выбираем любое). Подмножество D(1)2 бьем на два D(1,2)1 и D(1,2)2. Наиболее перспективную найдем вычислив gij для всех элементов L”(k,r) ???? max gij=gpq, тогда D(1,2)1 это множество всех путей К которые содержат дугу k,r и не содержат p,q. Ему соответствует матрица состояний L(k,r)(h,q). D(1,2)2 это множество всех путей К которое содержит две дуги k,r и p,q ему соответствует L(k,r)(h,q). Чтобы получить матрицу L(k,r)(h,q) надо положить lpq=?, а остальные переписываем из матрицы L”(k,r). После этого осуществляем переход L(k,r)(h,q) =>L’(k,r)(h,q) =>L”(k,r)(h,q). Shi+SHj=gpq и оценка j(D(1,1)1)=j(D(1)2)+gpq. Чтобы получить L(k,r)(p,q) надо исключить p-строку и q-столбец, обратный переход lpq=?. И поскольку в пути К вошли две дуги (более одной) следует предусмотреть образование подконтура проходящего через число городов меньше чем N. Подконтур может образоваться в том случае, когда конец одной дуги совпадает с началом другой. Все остальные элементы переписываются и L’(k,r). Затем осуществляется переход от L(k,r)(p,q)=> L’(k,r)(p,q)=> L”(k,r)(p,q). Находим Shi+SHj=RN-2 и находим j(D(1,2)2)=j(D(1)2)+RN-2.

И так как путь К еще не найден, то для дальнейшего разбиения выбираем подмножество с наименьшей оценкой: min(j(D(1)1), j(D(1,2)1), j(D(1,2)2), j(D(1)2)). Тогда D(1)1 будем бить на два подмножества аналогично тому, как били D(1)2. Процесс разбиения прекращаем тогда когда на очередном этапе будет найдено подмножество с наименьшей оценкой, которой будет соответствовать матрица состояний размером 2х2. Из этой матрицы выписываем дуги недостающие в пути К – дуги соответствуют нулевым элементам. Это наименьшая оценка и равна длине кротчайшего пути К.

Задачи сводящиеся к задаче К

1) О переналадке станка: N партий деталей следует обработать на станке в заданное времена tij. Переналадка станка при переходе от обработки i-детали к j-детали. Эти времена образуют T=(tij)NN. Найти порядок обработки партий деталей при котором суммарное время переналадки станка будет min.

Замечание: время обработки парий деталей является постоянным и поэтому на суммарное min время обработки всех деталей не влияет.

Если вместо станка рассмотреть К. а вместо N партий деталей N-городов и в качестве матрицы расстояний L рассмотреть T, то получим задачу К, решив которую найдем последовательность обработки которая обеспечивает min суммарное время их обработки.

2) О переналадки поточной линии: на поточной линии необходимо разлить N видов сока. Задаются времена Tij переналадки (промывки) поточной линии при переходе от разлива i-сока к j-соку. Имеем матрицу T=(tij)NN. Найти последовательность разливки соков при которой суммарное время разлива будет минимальное (для этого суммарное время обработки линии должно быть min). Переход аналогично предыдущей задачи (поточная линия – К, N видов – N городов и T – L). Решив задачу К найдем оптимальную последовательность.