Коммивояжер (К) должен обойти N городов и вернуться в исходный город. Пронумеруем эти города 1,2….N. Известна матрица расстояний L=(l_ij)_NN так как К из города i переходит в другой город j, то l_ij не существует. Если из города i нельзя переход в j то расстояние l_ij=?. В общем случае l_ij? l_ji. Будем предполагать что К находится в 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) U_i-U_j+Nx_ij?N-1 i,j=1,N. Это условие показывает на каком шаге К посещает i и j.

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

Определение множества решений D⁽¹⁾ в задаче К

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

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

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

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

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

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

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

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

Получим матрицу L^’’= (l_ij^’’)_NN, l_ij^’’?0. Из (9) найдем l_ij^’= l_ij^’’ + H_j и подставим в (8). l= l_i1,i2^’’+l_i2,i3^’’+l_iN,i1^’’+S h_i+S H_j (10), l?S h_i+S H_j, l — длина пути, т.е. l не меньше суммы приведенных констант матрицы L. =>j(D⁽¹⁾)? S h_i+S H_j

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

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

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

Будем искать оптимальный путь в задаче с матрицей L^’’. Наиболее вероятно, что в кратчайший путь К войдут те дуги (i,j) для которых в L^’’ l_ij^’’=0. Среди этих дуг необходимо найти ту исключение которой из пути приведет к большему увеличению j(D⁽¹⁾) => такую дугу на данном этапе исключать нецелесообразно. Эта дуга называется наиболее перспективной. Чтобы найти ее рассмотрим поочередно нулевые элементы матрицы L^’’ и для l_ij^’’=0 в i-ой строке и j-ом столбце находим наименьшие элементы (исключая элемент l_ij^’’=0), складываем их. Их сумму обозначим g. Среди всех g_ij найдем max g_kr=maxg_ij – наиболее перспективной является дуга (k,r), множество D⁽¹⁾₁ – множество путей К которые не содержат дугу (k,r). Условно обозначаем D⁽¹⁾₁-(k,r). D⁽¹⁾₂ — множество путей К которые содержат дугу (k,r). Условно обозначаем (k,r).

Необходимо определить матрицу расстояний подмножества D⁽¹⁾₁ обозначим L_(k,r), для D⁽¹⁾₂ L_(k,r).

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

В матрице L_(k,r) следует запретить переезд из города k в город r т.е. l_k,r=?, а все остальные элементы l_ij переносятся из матрицы L^’’. Получим L_(k,r) => привести т.е. осуществить переход от L_(k,r) => L_(k,r)^’ => L_(k,r)^’’. Сумма приведенных констант, полученных в результате приведения S h_i+S H_j=g_k,r

Оценка j(D₁⁽¹⁾)= j(D⁽¹⁾)+ S h_i+S H_j=g( D⁽¹⁾)+g_k,r

Найдем матрицу L_(k,r), которая соответствует подмножеству D⁽¹⁾₂ а D⁽¹⁾₂ – множество всех путей в котором из города k путь лежит в город r => в матрице L_(k,r) запрещен выезд из k-города любой другой город кроме r, т.е. рассмотрим l_k,j =? j?r. Это соответствует запрещению всех элементов k-ой строки, кроме l_k,r, т.е. уравниваем их все ?. С другой стороны необходимо запретить приезд в r-й город из всех городов, кроме k, т.е. положим l_i,r =? i?k. Это соответствует тому, что все элементы r-го столбца, кроме элемента l_k,r будут равны ?, т.е. матрицы исключаем r-й столбец, необходимо запретить обратный переезд из города r в k, т.е. l_k,r=?.

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

Оценка j(D₂⁽¹⁾)= j(D⁽¹⁾)+ R_N-1.

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

Поскольку путь К еще не найден, необходимо согласно методу ветвей и границ для дальнейшего разбиения выбрать подмножество с наименьшей оценкой. Пусть это будет подмножество D⁽¹⁾₂, т.е. j( D⁽¹⁾₂)<j( D⁽¹⁾₁). (если оценки одинаковые, то выбираем любое). Подмножество D⁽¹⁾₂ бьем на два D^(1,2)₁ и D^(1,2)₂. Наиболее перспективную найдем вычислив g_ij для всех элементов L”_(k,r) ???? max g_ij=g_pq, тогда D^(1,2)₁ это множество всех путей К которые содержат дугу k,r и не содержат p,q. Ему соответствует матрица состояний L_(k,r)(h,q). D^(1,2)₂ это множество всех путей К которое содержит две дуги k,r и p,q ему соответствует L_(k,r)(h,q). Чтобы получить матрицу L_(k,r)(h,q) надо положить l_pq=?, а остальные переписываем из матрицы L”_(k,r). После этого осуществляем переход L_(k,r)(h,q) =>L’_(k,r)(h,q) =>L”_(k,r)(h,q). Sh_i+SH_j=g_pq и оценка j(D^(1,1)₁)=j(D⁽¹⁾₂)+g_pq. Чтобы получить L_(k,r)(p,q) надо исключить p-строку и q-столбец, обратный переход l_pq=?. И поскольку в пути К вошли две дуги (более одной) следует предусмотреть образование подконтура проходящего через число городов меньше чем N. Подконтур может образоваться в том случае, когда конец одной дуги совпадает с началом другой. Все остальные элементы переписываются и L’_(k,r). Затем осуществляется переход от L_(k,r)(p,q)=> L’_(k,r)(p,q)=> L”_(k,r)(p,q). Находим Sh_i+SH_j=R_N-2 и находим j(D^(1,2)₂)=j(D⁽¹⁾₂)+R_N-2.

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

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

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

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

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

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