Лекция: Алгоритм метода

1. Осуществить приведение исходной матрицы С=|| Cij || по строкам. В результате чего получить С’=|| C’ij ||. C’ij = Cij – min Cij

j

2. Осуществить приведение матрицы С’ по столбцам и получить матрицу Ск = || Cкij ||. Cкij = C’ij – min C’ij

i n n

3. Вычислить сумму приводящих констант: hk = ∑ min Cij + ∑ min C’ij

i=1 j j=1 i

Cумма приводящих констант на 1 этапе приведения h’ является нижней границей для множества Х. W(x) = h1 .

4. Выбрать претендентов для ветвления в множество y. Это будут все пары городов (i=1,n), (j=1,n), (i≠j), для которых сij =0.

5. Для выделенных претендентов подсчитываем величину Qij: Qij = min C’ij + min C’ij

j’≠j i’≠i

min C’ij — в строке i выбирается тот город, исключая j, которому соответствует минимальное j’≠j расстояние приведенной матрицы.

min C’ij – в столбце j выбирается тот город, исключая i, которому соответствует минимальный i’≠i элемент.

6. Из подсчитанных Qij выбрать максимальное: Qkl = max Qij.

7. Пару городов (k,l) включить в множество y (она же является запретной для y).

8. Подсчитать оценку для множества y. Она будет равна ранее произведенным затратам и величине Qkl. W(k,l) = W(x) + Qkl.

9. Из каждого города можно выехать только 1 раз, поэтому из дальнейшего рассмотрения исключить строку к. В каждый город можно въехать только 1 раз, поэтому исключить столбец l. Чтобы избежать замкнутых подциклов, запретить переезд из города l в город к. То есть соответствующему элементу присвоить ∞. Сlk=∞.

10. Полученная усеченная матрица содержит 2 допустимые пары городов, которые являются замыкающими для некоторого цикла без петель. Поэтому на данном шаге проверяется размерность матрицы. Если она 2х2, то перейти к пункту 12, в противном случае – к пункту 11.

11. Проверить, является ли полученная матрица приведенной, если да, то оценка для множества y равна оценке того множества, из которого она получена. W(Ym) = W(Ym-1). Если нет, то осуществить приведение полученной матрицы и подсчитать сумму приводящих констант hk. Тогда оценка для множества y будет равна: W(Ym) = W(Ym-1) + hk.

12. Проверить условие оптимальности, если оценка замкнутого цикла не больше оценок всех допустимых для дальнейшего ветвления множества, то полученный замкнутый маршрут является оптимальным. Если существует хотя бы одно множество с меньшей оценкой. То полученный маршрут запомнить и продолжить исходя из множества с меньшей оценкой.

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