называется гамильтоновым циклом или просто циклом, маршрутом коммивояжёра и обозначается через

Через Т обозначим множество всех гамильтоновых циклов, а через z(t) – издержки цикла t (длина t)

z(t) = S c_ij.

(i, j)Î t

Необходимо отыскать такой маршрут t^* , что

z(t^*) = min z(t).

tÎ T

Эту задачу можно сформулировать как задачу целочисленного линейного программирования.

Пусть

1, если коммивояжёр едет из города i в город j;

x_ij =

0, если коммивояжёр не едет из города i в город j.

Найти такой вектор `X = (x₁₁, x₁₂, …, x_nn) Î E_n*n, который

минимизирует

(2)

(3)

u_i – u_j + (n-1) x_ij £ n-2, i¹ j, i, j = 1, 2, …, n-1 (4)

x_ij ³ 0, i, j = 1, 2, …, n (5)

x_ij, u_i - целые. (6)

Условия (2) говорят о том, что коммивояжёр выезжает из каждого города ровно один раз. Условия (3) означают въезд в каждый город ровно один раз, а условия (4) служат для устранения подциклов (пример, когда маршрут распадается на два не связанных между собой подцикла, приведён ниже).

Описанная модель имеет большое прикладное значение: различные её варианты могут возникать, например, в задачах, связанных с развозкой почты, готовой продукции и т.д.

Обозначим через z₀ верхнюю границу оптимального значения функции цели z(t) на множестве Т, т.е.

z(t^*) £ z₀,

где t^* - оптимальный гамильтонов цикл (маршрут).

Определить z₀ можно, отыскав какой-либо маршрут коммивояжёра и подсчитав его издержки. Для примера 1 допустимым является следующий гамильтонов цикл

t₀ = {(1, 2); (2, 3); (3, 4); ((4, 5); (5, 1)}.

Его издержки

z(t₀) = 10 + 10 + 20 + 15 + 10 = 65.

Следовательно, z₀ = 65, а сам цикл t₀ следует запомнить. Если указать конкретный маршрут трудно, то полагают z₀ = ¥

Пусть m(Т) – нижняя граница функции цели на множестве Т, для любого tÎ T

z(t) £ m(Т).

Для вычисления m(Т) введём операцию приведения матрицы С(Т).

Приведём матрицу примера 1.

H(T) =10+1+8+10+8+9+12 = 58 = m(T).

На каждой итерации s какое-то множество маршрутов коммивояжёра, обозначим его через X, будет подлежать разбиению на два непересекающихся подмножества y_s и `y<sub>s</sub> по следующему принципу: подмножество y<sub>s</sub> содержит все гамильтоновы циклы из Х, включающие переезд из города k в город l (дугу (k, l)), а подмножество `y_s содержит все остальные маршруты из разбиваемого множества X.

На первой итерации разбиваться будет множество всех гамильтоновых циклов Т.

Ясно, что для разбиения лучше выбирать множество с минимальной нижней оценкой m(X), так как вероятнее всего именно в нём содержится оптимальный цикл t^*.

(k, l) (k, l)

Дугу (k, l) будем выбирать из следующих соображений. С одной стороны, издержка с_kl должна быть как можно меньше, чтобы в конце концов из всех фиксированных дуг получить гамильтонов цикл, близкий к оптимальному. С другой стороны, будем максимально увеличивать нижнюю оценку m(`y<sub>s</sub>) множества ` y_s, тогда возрастает вероятность того, что для разбиения всякий раз будет выбираться множество y_s, и появится возможность быстрее получить гамильтонов цикл. Если при этом окажется, что его издержки меньше z₀, то z₀ будет скорректирована (уменьшена), а это сократит число просматриваемых циклов.

Кроме того, такой подход к выбору дуги (k, l) позволяет сократить объём хранимой в памяти информации, а именно, необходимо иметь исходную матрицу издержек С(Т), рабочую матрицу C¢ (y_s) и информацию о каждом множестве: его нижнюю оценку издержек и все фиксированные и запрещённые для него дуги. Если в процессе решения задачи нужно будет разбивать множество, отличное от y_s, то соответствующую ему матрицу издержек можно восстановить их исходной матрицы С(Т) на основании этой информации.

Выбор фиксированного переезда.

Чтобы выбрать переезд (k, l), необходимо:

1) в приведенной матрице издержек С¢ (X) просмотреть все элементы c¢ _ij =0;

2) для каждого из них определить величину q_ij, равного сумме минимального элемента i -той строки и j -го столбца (за исключением самого элемента c¢ _ij);

3) выбрать фиксированный переезд (k, l) из условия

q_kl = max q_ij

(i, j), с¢ _ij =0

Процесс разбиения множества Х на два подмножества у_s и `у<sub>s</sub> можно осуществить, если есть матрица издержек С¢ (X). Поэтому прежде всего рассмотрим, как на произвольной итерации получить матрицы С¢ (у<sub>s</sub>) и С¢ (`у_s), если известны матрица С¢ (X) и дуга (k, l).

Схема построения матрицы С ¢ (у_s)

1. Так как дуга (k, l) уже входит в любой гамильтонов цикл, принадлежащий множеству y_s, то согласно постановке задачи необходимо запретить выезд из города k и въезд в город l, поэтому в матрице С¢ (X) вычеркиваем строку k и столбец l.

2. Для устранения подциклов необходимо составить из всех дуг, фиксированных для множества у_s, связный путь, обязательно содержащий последнюю фиксированную дугу (k, l) (связный путь может состоять всего лишь из одной дуги (k, l)).Полагаем C¢ _mp =¥ в матрице С¢ (X), где m и p – соответственно конец и начало связного пути, в результате получим матрицу С (у_s).

3. Приводим матрицу С(у_s), получим искомую матрицу С¢ (у_s). Обозначим через h(y_s) константу приведения матрицы С(у_s).

4. Нижняя граница издержек m(у_s) для множества y_s определится по формуле

m(у_s) = m(X) + h(y_s). (8)

Схема построения матрицы С ¢ (`у_s).

1. Так как дуга (k, l) не должна входить ни в один гамильтонов цикл, принадлежащий множеству `у<sub>s</sub>, то в матрице С¢ (X) полагаем с¢ <sub>kl</sub> =¥. Получим С (`у_s).

2. Приводим матрицу С(`у<sub>s</sub>), получим С¢ (`у_s).

Обозначим через h(`y<sub>s</sub>) константу приведения матрицы С(`у_s).

3. Нижняя граница издержек m(`у<sub>s</sub>) для множества `y_s определится по формуле

m(`у<sub>s</sub>) = m(X) + h(`y_s). (9)

Схема восстановления матрицы С ¢ (X) из исходной матрицы C(T) для любого множества Х

Пусть Х –любая вершина дерева, соответствующего процессу решения задачи о коммивояжере методом ветвей и границ, c набором фиксированных дуг

D = {(i₁, j₁), (i₂, j₂), …, (i_q, j_q) }.

1. Вычёркиваем в матрице С(Т) все фиксированные строки

i₁, i₂, …, i_q, и фиксированные столбцы j₁, j₂, …, j_q.

2. Для каждой фиксированной дуги (i_r, j_r)составляем связный путь из ранее фиксированных дуг, включающий в себя и данную дугу (i_r, j_r), и полагаем с_mp = ¥ в матрице С(Т), где m и p соответственно конец и начало связного пути.

3. Для каждой запрещённой для множества Х дуги (i, j) полагаем c_ij = ¥ в матрице С(Т), в результате получаем матрицу С(Х).

4. Приводим матрицу С(Х), получаем искомую матрицу С¢ (Х). Обозначим суммарную константу приведения С(Х) через H(X).

5. Нижняя граница издержек для множества Х определится по формуле

m(X) = (10)

Обоснование формул (8), (9), (10).

Пусть Х – любая вершина с набором фиксированных дуг D, матрица которой С¢ (Х) восстановлена из исходной матрицы С(Т) с суммарной константой приведения H(X). Покажем, что нижняя граница издержек m(X) определится по формуле (10).

Действительно, если tÎ X, то

z(t) = ,

причём вторая сумма берётся по всем (i, j)Î t, но не фиксированным для множества Х.

Так как матрица С¢ (Х) восстановлена из исходной матрицы С(Т) по рассмотренной выше схеме, то

z(t) = ,

где c¢ _ij элемент приведённой матрицы С¢ (Х).

Поскольку

³ 0, то

z(t) ³ = m(X) -

формула (10) доказана.

Рассмотрим теперь формулу (9). Так как матрица С¢ (`у<sub>s</sub>) может быть восстановлена из из исходной матрицы С(Т) и для множеств `у_s и Х фиксирован один и тот же набор дуг D, то согласно (10)

m(`y_s) = .

Но

H(`y<sub>s</sub>) = H(X) + h(`y_s),

где h(`y<sub>s</sub>) - константа приведения C(`y_s), поскольку C¢ (X) и C(`y<sub>s</sub>) отличаются лишь тем, что c¢ <sub>k, l</sub> = ¥, следовательно, h(`y_s) =θ _{k, l}.

Имеем

m(`y_s) =

C учётом (10)

m(`y<sub>s</sub>) = m(X) + h(`y_s) -

т.е. получена формула (9). Следует отметить что h(`y_s) = θ _{k, l}.

Рассмотрим теперь m(y_s). Согласно (10)

m(y_s) = , (11)

так как для множества y_s по сравнению с множеством Х фиксирована ещё одна дуга (k, l).

Рассмотрим H(y_s). Матрицы C¢ (X) и С(y_s) отличаются, во первых, тем, что в матрице С(y_s) нет k -ой строки и l -ого столбца. Следовательно, в константу приведения H(X) входит в качестве слагаемого c_kl, которой нет в H(y_s).

Во-вторых, в матрице С(y_s) по сравнению с C¢ (X) могут быть новые элементы, равные ¥, т.е. может оказаться, что матрицу С(y_s) нужно будет приводить. Следовательно, в константу приведения H(y_s) войдёт константа приведения h(y_s) матрицы С(y_s). Таким образом,

H(y_s) = H(X) - c_kl + h(y_s).

Подставив последнее равенство в (11), получим

m(y_s) = , или

m(у_s) = m(X) + h(y_s),

т.е. получена формула (8).

Решение примера 1.

I итерация.

Выше для множества всех маршрутов Т были определены z₀ =65 и m(Т) = 58. Определим теперь переезд (k, l), по которому множество всех маршрутов Т будет разбиваеться на два подмножества: y₁ и `y₁.

q₁₂ =6; q₁₅ =1; q₂₁ =0; q₂₃ =5; q₃₁ =0; q₃₄ =2; q₄₂ =4; q₅₂ =2;

Следовательно, (k, l) = (2, 3).

Нижняя граница издержек для множества `y₁ будет согласно формуле (9) равна

m(`y<sub>1</sub>) = m(Т) + h(`y₁) = m(Т) + q₂₃ = 58 + 5 = 63.

Теперь построим матрицу издержек C(y₁). Для этого вычеркнем в матрице C¢ (Т) вторую строку и третий столбец и положим c₃₂ = ¥.

Т.к. h(y₁) = 0, то, согласно формуле (8),

m(y₁) = 58 + 0 =58.

(2, 3)

Рис. 1

II итерация.

Из двух множеств: y₁ и ` y₁ выбираем для разбиения то, которому соответствует минимальная нижняя граница издержек, т.е. Х = y₁. Приведённая матрица издержек C¢ (y₁) построена на I итерации.

Определим дугу (k, l).

q₁₂ = 0; q₁₅ = 2; q₃₁ = 2; q₃₄ = 3; q₄₂ = 4; q₅₂ = 2; (k, l) = (4, 2).

В результате разбиения y₁ получим два новых множества: y₂ и ` y₂.

Для множества ` y<sub>2</sub> нижняя граница издержек m(`y₂) определится как m(`y₂) = 58 + 4 = 62.

Построим матрицу C¢ (y₂) и определим m(`у₂). Для этого в матрице C¢ (y₁) вычеркнем четвёртую строку и второй столбец. Соберём все дуги, фиксированные для множества y₂. Это (4, 2) и (2, 3). Они образуют связный путь. Положим с₃₄ = ¥. Получим матрицу С(y₂) и приведём её.

h(y₂) = 5; m(у₂) = 58 + 5 = 63.

(2, 3)

Рис.2

III итерация.

Из множеств y₂, ` y<sub>2</sub>, ` y₁ (рис.2) минимальная нижняя граница издержек соответствует множеству `y<sub>2</sub>, поэтому это множество будет подлежать разбиению. Матрица издержек для этого множества отсутствует, её необходимо восстановить из исходной матрицы С(Т). Для множества ` y₂ фиксирован переезд (2, 3) и запрещён (4, 2), поэтому в матрице С(Т) вычёркиваем строку 2 и столбец 3, полагаем с₃₂ = ¥ (предотвращаем подцикл), с₄₂ = ¥ (запрещаем переезд (4, 2)), после чего матрицу приводим.

H(`y₂) = 10 + 8 + 14 + 8 + +12 = 52.

m(`y<sub>2</sub>) = с<sub>23</sub> + H(`y₂) = 10 + 52 = 62.

Выберем дугу, по которой будет производиться разбиение `y<sub>2</sub> на два подмножества: y<sub>3</sub> и `y₃.

q₁₂ = 0; q₁₅ = 1; q₃₂ = 0; q₃₄ = 3; q₄₁ = 1; q₅₂ = 2;

m(`y₃) = 62 + 3 = 65.

Для y₃ фиксированы (2, 3), (3, 4). Эти переезды составляют связный путь, следовательно, с₄₂ = ¥.

Построим матрицу С(y₃) и приведём её.

h(y₃) = 0;

(2, 3)

(3, 4)

Рис. 3

IV итерация.

Для разбиения (рис. 3) выбираем множество с наименьшей нижней границей издержек - y₃, которое будет разбиваться на y₄ и ` y₄.

q₁₂ = 0; q₁₅ = 1; q₄₁ = 3; q₅₂ = 2;

m(`y₄) = 62 + 3 = 65.

Построим матрицу для y₄ и приведём её. Фиксированные дуги (4, 1), (3, 4), (2, 3) или (2, 3), (3, 4), (4, 1) – связный путь, с₁₂ = ¥.

(2, 3)

(3, 4)

Рис.4

Матрица С¢ (y₄) - матрица второго порядка, следовательно, множество y₄ содержит только один маршрут коммивояжёра, который состоит из всех фиксированных для множества y₄ дуг

(2, 3), (3, 4), (4, 1)

и двух дуг

(1, 5) и (5, 2),

которым в матрице С¢ (y₄) соответствуют нулевые элементы, т.е. y₄ содержит единственный маршрут

t₁ = {(1, 5), (5, 2), (2, 3), (3, 4), (4, 1)}.

z(t₁) = 10 + 8 + 10 + 20 + 14 = 62 < z₀ = 65.

Меняем значение верхней границы оптимального значения издержек.

z₀ = 62

V итерация.

Минимальная нижняя граница издержек (рис. 4) - m(`y₁) = m(y₂) = 63 > z₀ = 62, следовательно, задача решена.

z^* = 62, t^* = t₁ = {(1, 5), (5, 2), (2, 3), (3, 4), (4, 1)}.