Методика выполнения четвертой задачи

Пусть C =║c_ij║ - матрица, элемент c_ij которой определяет издержки коммивояжера при переезде из города с номером i в город с номером j. Коммуникацию от города i до города j будем обозначать (i,j). Пусть коммивояжер передвигается по циклу t = {(i₁,i₂), (i₂,i₃),..., (i_n-1,i_n), (i_n,i₁)}, где i_l i_u, если l u.

Общие издержки z(t) для цикла t, соответствующие матрице C, задаются равенством:

s(t)= .

Введем понятие приведенной матрицы. Пусть

с_i.=min c_ij,

^j

т.е. c_i. - минимальный элемент в строке матрицы с номером i.

Положим =c_ij-c_i..т.е. из каждого элемента строки матрицы C вычтем самый маленький в этой строке элемент. Эту операцию проделаем с каждой строкой.

Аналогичные операции проделаем со столбцами получившейся матрицы С '=║ ║. Для этого в каждом столбце матрицы С ' найдем минимальный элемент. Минимальный в j-м столбце элемент обозначим c_.j. Из каждого элемента столбца вычтем минимальный в этом столбце элемент, результат обозначим через : -c_.j.

Матрица C "=║ ║ называется приведенной, а минимальные по строкам (столбцам) элементы - приводящими константами.

Обозначим через h сумму приводящих констант:

h = c_i. + c_.j.

Пусть z(t) - издержки, связанные с движением по циклу t до приведения матрицы C, z'(t) - аналогичные издержки, связанные с матрицей C ". Очевидно, что

z(t) = z'(t) + h.

Таким образом, h является нижней границей издержек, связанных с движением по циклу t. Т.е. мы получили алгоритм для определения оценки снизу по крайней мере для множества D.

Опишем теперь процедуру ветвления. Выбранное для дробления множество (обозначим его через X) будем делить на две непересекающиеся части и . Для этого по некоторому правилу (о нем несколько позже) выбирается какая-то коммуникация, скажем (u,v). Множество состоит из всех таких циклов множества X, которые содержат переезд города u в город v; множество - множество всех тех циклов из X, в которых такого переезда нет.

Указанный процесс дробления удобно иллюстрировать с помощью графа - дерева. Его вершинам соответствуют множества маршрутов, две вершины X и W соединяются ребром, если множество W получено дроблением множества X (непосредственно), см. рис.14.

Если дробление множества X осуществлено с помощью коммуникации(u,v), то множество Y будем обозначать , а множество - .

Рис.14. Схема дробления множества планов

На рисунке 14 показано, что множество всех циклов D дробиться на две части - множество всех циклов, в которых переезд из i в j имеется и множество всех циклов, в которых такой переезд запрещен. Множество всех циклов, в которых переезд (i,j) имеется, снова делится на две части: множество всех циклов, в которых имеются переезды (i,j) и (k,l), и множество всех циклов, в которых переезд (i,j) имеется, а переезд (k,l) запрещен.

Вершине, из которой осуществляется ветвление, поставим в соответствие сумму приводящих констант матрицы расстояний, соответствующей этой вершине. Эта сумма дает нижнюю оценку значений целевой функции на циклах этого множества. Обозначать эту нижнюю границу будем W(X), X - соответствующая вершина.

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

для каждого нулевого элемента выбирается минимальный элемент строки, в которой стоит рассматриваемый нулевой элемент, и минимальный элемент столбца, в котором стоит рассматриваемый элемент (сам рассматриваемый нулевой элемент в выборе не участвует). Вычисляется оценка нулевого элемента, равная сумме указанных выбранных элементов. Выбирается нулевой элемент с максимальной оценкой, соответствующая ему коммуникация и используется для дробления.

Заметим, что обоснованием предложенных приемов служит тот факт, что они хорошо работают при решении задач коммивояжера. Вполне может оказаться, что существуют более эффективные правила вычисления оценок, выбора множества для дробления, дробления множеств на части.

Проиллюстрируем сказанное ранее на примере.

Пример. Пусть имеется 6 городов, расстояния между которыми указаны в матрице C (c_ii= , так как переезд из i в i не возможен):

1 2 3 4 5 6

C = .

Для удобства сверху и сбоку от матрицы указаны номера городов.

1. Первый шаг, m=1

2. Приводим матрицу:

1 2 3 4 5 6

C’= ,

1 2 3 4 5 6

C”= .

3. h¹=16+1+0+16+5+5+5+0+0+0+0+0=48, следовательно, оценка снизу множества всех циклов w(X)=w(D)=48.

4. Рассматриваем нулевые элементы, они находятся в клетках (1,4),(2,4),(3,6),(4,1),(4,2), (5,6),(6,2),(6,3),(6,5).

5. Вычисляем их оценки. Оценку элемента, стоящего в строке с номером i и столбце с номером j, будем обозначать Q(I,j):

Q(1,4)=10+0=10, Q(2,4)=1+0=1, Q(3,6)=5+0=5, Q(4,1)=0+1=1, Q(4,2)=0+0=0, Q(5,6)=2+0=2, Q(6,2)=0+0=0, Q(6,3)=0+9=9, Q(6,5)=0+2=2.

6. Находим максимальную оценку, это Q(1,4)=10.

7. Имеем = , = , запрет использовать коммуникацию (1,4) увеличил длину цикла как минимум на 10 единиц, следовательно, w()=48+10=58 (см.рис.15). На приводимых рисунках нижние оценки множеств планов указаны красным цветом в соответствующих прямоугольниках.

Рис.15.Первый шаг.

8. В матрице C” исключаем первую строку и четвертый столбец (ведь переезд из города 1 в город 4 предписан) и запрещаем переезд из 4-о города в 1-й (записываем в соответствующую клетку ), так как иначе возможен цикл, не охватывающий все города. Получаем матрицу:

1 2 3 5 6

C¹ = .

9. Осуществляем приведение этой матрицы, получим матрицу

1 2 3 4 6

C^1” = ,

h²=1, w(Y)=w(X)+h=48+1=49.

10. Повторяем пункты 4-10 до тех пор, пока не получим матрицу размерами 2×2.

Поясним кратко ход дальнейших вычислений.

Для дробления выбираем коммуникацию (2,1), при этом 1 2 3 4

Q(2,1)=14, w(Y)=w(X)+Q(2,1)=49+14=63 (рис.16).

Рис.16. Второй шаг.

Вычеркиваем вторую строку и первый столбец, запрещаем коммуникацию (4,2), получаем матрицу

2 3 5 6

C² = .

Приводя ее, получаем матрицу

2 3 5 6

C^2” = .

Сумма приводящих констант равна двум и, следовательно, w()=w(2,1)=49+2=51.

В клетку (4,2) мы записали бесконечность, так как иначе возможен подцикл {(1,4),(4,2),(2,1)}.

Следующей коммуникацией для ветвления является (5,6), w()=73 (рис.17).

После вычеркивания пятой строки и шестого столбца получаем матрицу:

2 3 5

C³ = ,

после приведения получаем матрицу

2 3 5

C^3” = ,

Сумма приводящих констант равна пяти, тогда w()=56.

Для ветвления выбирается коммуникация (3,5) рис.18.

Рис.17. Третий шаг

После усечения последней матрицы получаем матрицу размерами 2×2:

2 3

C⁴ = .

Коммуникация (6,3) запрещается опять же из-за возможности получения подцикла {(3,5),(5,6),(6,3)}.

После приведения получаем матрицу

2 3

C^4” = .

11. В матрице C^4” всего две допустимые коммуникации (6,3)и (4,3), дополняющие ранее предписанные коммуникации до цикла. Заметим, что так получается всегда.

Итак, мы получили цикл, состоящий из переездов

(1,4),(2,1),(5,6),(3,5),(6,2),(4,3)

переставив коммуникации получим цикл

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

его длина z(t)=63.

Используя критерий оптимальности, сравниваем это значение с оценками еще не дробленных множеств.

Мы видим, что оценка вершины , равная 58, меньше, чем 63. Остальные вершины имеют оценки, большие, чем 63. Следовательно, цикл более короткий, чем найденный, может быть только в множестве .

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

Рис.18. Четвертый шаг.

Итак, рассматриваем матрицу:

1 2 3 4 5 6

C = .

Рис.19. Пятый шаг

Приводя ее, получаем

1 2 3 4 5 6

C”=

h=58.

Для ветвления выбираем коммуникацию (6,3), результаты указаны на рисунке 19.

Итак, вершин с меньшими, чем 63, оценками нет, следовательно, ранее полученный маршрут является оптимальным.