Совершенно очевидно, что задача может быть решена перебором всех вариантов объезда и выбором оптимального. Беда в том, что количество возможных маршрутов очень быстро возрастает с ростом n (оно равно n ! - количеству способов упорядочения пунктов). К примеру, для 100 пунктов количество вариантов будет представляться 158-значным числом - не выдержит ни один калькулятор! Мощная ЭВМ, способная перебирать миллион вариантов в секунду, будет биться с задачей на протяжении примерно 3 ⋅ 10 144 лет. Увеличение производительности ЭВМ в 1000 раз даст хоть и меньшее в 1000 раз, но по-прежнему чудовищное время перебора вариантов. Не спасает ситуацию даже то, что для каждого варианта маршрута имеется 2 ⁢ n равноценных, отличающихся выбором начального пункта (n вариантов) и направлением обхода (2 варианта). Перебор с учётом этого наблюдения сокращается незначительно - до n ! 2 ⁢ n = n − 1 ! 2 вариантов.

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

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

Заметим, что интеллект человека, не вооружённый вычислительной техникой, способен отыскивать такие приближённые решения задач, требующих огромного перебора вариантов в поисках оптимального. Вспомним хотя бы шахматы. Человек может весьма успешно соперничать в этой игре с вычислительной машиной либо вовсе не прибегая к перебору, либо сводя его к минимуму. Человек руководствуется при этом интуицией и набором эвристик (находок) - правил, которые обычно помогают в решении задач, хотя эффективность таких правил и не имеет достаточного обоснования. В качестве подобной универсальной эвристики можно упомянуть категорический императив Канта : «поступай с другими так, как тебе хотелось бы, чтобы поступали с тобой». Другой, более приземлённый пример даёт золотое правило валютного спекулянта: «когда все продают доллары, ты покупай, а когда все покупают - продавай».

Многие природные процессы решают задачи выбора оптимального варианта из огромного (даже, возможно, бесконечного) множества вариантов. Например, тяжёлая гибкая однородная цепочка, подвешенная за концы на двух гвоздиках, из всевозможных доступных форм принимает именно ту, которая соответствует минимуму потенциальной энергии силы тяжести (которая пропорциональна высоте центра тяжести цепочки). Причём цепочке для поиска нужной формы (она называется катеноидой , или цепной линией ) требуется времени гораздо меньше, чем человеку, составляющему и решающему дифференциальное уравнение Эйлера - Лагранжа для нахождения этой самой катеноиды. Мыльная плёнка, натянутая на проволочный контур, принимает форму, соответствующую минимуму внутренней энергии плёнки (состоящей, в основном, из потенциальной энергии сил поверхностного натяжения, пропорциональной площади плёнки). Световой луч в прозрачной (возможно, неоднородной) среде, преломляясь, отыскивает кратчайший путь (требующий наименьшего времени прохождения любого своего участка) с учётом скорости света в каждой точке среды, через которую он проходит. Вещество, кристаллизуясь из расплава, постепенно принимает ту кристаллическую форму, которая минимизирует опять же внутреннюю энергию, складывающуюся из энергий попарного взаимодействия молекул. В последнем примере молекулы вещества, совершающие хаотическое тепловое движение, которое замедляется по мере остывания, постепенно «нащупывают» нужную, минимальную в энергетическом смысле конфигурацию среди огромного количества вариантов расположения молекул. Биологическая эволюция совершенствует виды, снижая вероятность выживания (и, соответственно, передачи потомству генетической информации) менее приспособленных особей.

Все эти соображения ведут нас к эвристике: «хочешь приближённо решить задачу - смоделируй (например, с помощью ЭВМ) природный процесс, решающий подобную задачу». Вот несколько конкретных приложений этой эвристики: «нужен эллипс - посвети фонариком на пол, слегка наклонив его (фонарик или пол)». Или «налей в цилиндрический или конический стакан воды и чуть наклони». Или «возьми батон колбасы и разрежь наискосок». «Нужна синусоида - заверни колбасу в бумагу и разрежь вместе с бумагой, а затем разверни бумажный лист». Или «присоедини колебательный контур к осциллографу» - колебательный контур мгновенно решает дифференциальное уравнение колебаний, а решения этого уравнения - синусы и косинусы. «Хочешь вычислить определённый интеграл - вырежи криволинейную трапецию из бумаги, взвесь её и подели на массу единичного бумажного квадратика».

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

Переборные задачи, нацеленные на поиск оптимального варианта, называют задачами комбинаторной оптимизации

Дадим формальную постановку задачи оптимизации. Дано конечное (обычно очень большое) множество X и числовая функция U ⁡ x на этом множестве. Эту функцию называют целевой . Требуется найти такой x * ∈ X , что U ⁡ x * будет наименьшим, то есть U ⁡ x * ⩽ U ⁡ x для всех x ∈ X . Вариант постановки задачи, когда требуется найти точки максимума целевой функции, легко сводится к поиску точек минимума функции − U .

Задача коммивояжёра может быть поставлена как задача оптимизации. В качестве множества X достаточно взять S n (множество перестановок n -элементного множества), а в качестве целевой функции U ⁡ x - длину замкнутой ломаной, проходящей через n заданных точек в порядке, заданной перестановкой x ∈ X .

Для решения задачи поиска точки минимума функции придумано множество методов. Например, для дифференцируемых функций U , определённых на числовом множестве X , как известно, точки минимума (если они есть) следует искать среди критических точек U , то есть таких x , что U ′ x = 0 . Однако о дифференцируемости функции, определённой на конечном множестве, к тому же не обязательно числовом, говорить не приходится, поэтому метод, основанный на критических точках, не годится. Полный перебор всех x мы тоже отвергаем по причинам, которые обсуждались выше.

Для множеств X , для которых определено отношение близости , годятся и другие методы. Среди них - метод градиентного спуска

Отношение близости - это способ определить для двух элементов множества, являются ли они близкими (в каком-нибудь смысле). Для числовых множеств, для множеств точек на плоскости или в пространстве близкими можно считать два числа (две точки), расстояние между которыми не превосходит некоторого маленького числа ε . Для множества S n близкими удобно считать две перестановки, отличающиеся на одну транспозицию , то есть получающиеся друг из друга «рокировкой» двух элементов множества. Например, перестановки 2 4 1 3 и 2 3 1 4 являются близкими в этом смысле, так как отличаются перестановкой элементов с номерами 2 и 4 . Можно определить и более строгое отношение близости, при котором близкие перестановки отличаются на соседнюю транспозицию , когда рокировка затрагивает элементы множества с соседними номерами. Тогда указанные выше перестановки близкими уже не будут, но близкими окажутся 2 4 1 3 и 2 4 3 1 .

Суть метода градиентного спуска отражена в его названии и заключается в следующем. Строится последовательность x 0 x 1 x 2 x 3 … ⊂ X , в которой начальный элемент x 0 выбирается произвольно (возможно, случайным образом), а каждый последующий является одним из соседей предыдущего, причём именно тем из соседей, для которого значение функции U будет наименьшим. Построение последовательности завершается тогда, когда последовательность значений целевой функции U ⁡ x 0 U ⁡ x 1 U ⁡ x 2 U ⁡ x 3 … перестанет быть монотонно убывающей.

Последний элемент построенной последовательности называют точкой локального минимума . Это такая точка, в которых значение U строго меньше, чем во всех соседних с ней. В слове «локальный» заключён главный недостаток описанного метода. Локальных минимумов у функции U может быть много, и каждому из них отвечает, как правило, своё локально минимальное значение целевой функции. Нас же интересует абсолютный минимум функции и тот элемент множества X , в котором он достигается. Если бы было легко найти все точки локального минимума, перебором среди них мы нашли бы точку абсолютного минимума. Но метод градиентного спуска не даёт рецепта поиска всех точек локального минимума, он позволяет найти лишь какую-нибудь .

Имеется вероятностная версия метода градиентного спуска. На каждом шаге для элемента множества X выбирается случайный сосед. Если значение целевой функции в случайной соседней точке уменьшилось, она добавляется в последовательность и мы переходим к следующему шагу. Если же нет, то снова выбирается случайный сосед. Алгоритм останавливается, если достаточно долго не пополняется последовательность (не происходит переход к следующему шагу): вероятно, алгоритм в этом случае привёл в точку локального минимума.

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

Метод имитации отжига является модификацией вероятностного метода градиентного спуска. Отличие заключается в поведении алгоритма, когда U ⁡ x ⩽ U ⁡ x ~ , где x - очередной элемент последовательности, а x ~ - его сосед, выбранный наугад. Вероятностный метод градиентного спуска отвергал такого соседа безусловно, а метод имитации отжига допускает добавление такого «плохого» соседа в последовательность, правда, с некоторой вероятностью p , зависящей от того, насколько плохой сосед ухудшил целевую функцию. Возьмём разность ∆ ⁡ U = U ⁡ x ~ − U ⁡ x (она неотрицательна, если сосед «плохой») и положим p = e − ∆ ⁡ U Θ . Здесь e - некоторое число, большее единицы (какое именно, не принципиально, но обычно берут e ≈ 2,718281828459045… - основание натуральных логарифмов), а Θ - некоторое положительное число, называемое температурой

На рисунке 45.1. «Вероятность мутации для метода имитации отжига» показаны зависимости вероятности мутации от величины ∆ ⁡ U при различных значениях температуры Θ . Высоким температурам соответствуют графики, чей цвет ближе к красному, низким - к синему. Как и положено, значение вероятности заключено в отрезке 0 1 . При отрицательных ∆ ⁡ U вероятность равна 1 , что соответствует случаю «хорошей» мутации.


Продолжение следует…


    (5х5) (Засчитывается за 4 условные задачи) время на исполнение 2 пары) (Презентация КОММИВОЯЖЁР) Самая сложная задача исследования операций

Методом ветвей и границ требуется найти Кратчайший маршрут объезда 5 городов с возвратом в исходный, при КОТОРОМ КАЖДЫЙ ГОРОД ПОСЕЩАЕТСЯ в ТОЧНОСТИ 1 раз (в матрице даны цены проезда из «левого» города в «верхний»).

Решение Методом ветвей и границ

      Шаг №0 Оцениваем цикл 1-2-3-4-5-1 – это первое приближение верхней оценки. Далее, если на любой ветви дерева ветвления нижняя оценка подмножества решений окажется выше верхней эта ветвь «отмирает» , т.к. все её решения хуже уже имеющегося.

      Шаг №1а) Выписываем константы редуцирования по строкам. Это минимальные числа в строках. Их надо вычесть из элементов своих строк (при этом появится не менее одного нуля в каждой строке).

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

      Шаг №1в) Вычисляем сумму констант редуцирования полученных на шагах а) и б). Очевидно, никакой маршрут не может стоить дешевле – поэтому это оценка снизу. Далее мы будем увеличивать эту оценку на величину и
      (эти величины опишем ниже), где- пара индексов ребра, по которому выбрано производить ветвление.

      Опишем, как будет происходить ветвление: выбираем ребро i,j(удовлетворяющее требованиям следующего пункта) множество гамильтоновых маршрутов можно мыслить как комбинаторно большое множество своеобразных «бус» составленных из звеньев типа Петербург-Москва, Москва-Одесса, Одесса-Белград и т.д. Примем способ разделить всё множество замкнутых путей на те, где есть дорога Одесса-Белград и те где её нет (первое множество меньше второго).

      Теоретически можно производить ветвление по любому ребру, но наша задача в том, чтобы на одном множестве нижняя оценка цены маршрута не изменилась, а на другом максимально выросла – это может способствовать тому, что в большинстве случаев комбинаторный перебор, вообще говоря, экспоненциального алгоритма решения NPполной задачи окажется не слишком большой.

      Для этого: Шаг №2. Вычисляем стоимости обхода для каждого нулевого элемента (если он превратился в бесконечность ∞) - величина на которую увеличиваются константы редуцирования соответствующей строки и столбца.

      Разбиваем текущее множество решений на два:


    1. Процесс отчасти заканчивается после выбора k-2 ребер, гдеkобщее число вершин. В задаче 2х2 решение однозначно, оно (обычно) приводит к коррекции верхней оценки. Если все (остальные) нижние оценки хуже, ответ получен. В таком примере как приведенный в этом задании как правило имеет место эта ситуация, но в более большом и сложном графе (при создании универсального алгоритма), требуется описать дальнейшие действия. Если всё ещё не все нижние оценки хуже чем скорректированная верхняя оценка, то выжившие нетривиальные множества придется ветвить до тех пор пока либо они не исчезнут из-за высокой, т.е. плохой нижней оценки, либо (что редко) до того как будет получена новая верхняя оценка - новое решение, превосходящее по качеству предыдущее. Процесс продолжается до тех пор, пока полученное решение не останется безальтернативным.

Рассмотрим матрицу стоимостей проезда из «левого» города в «верхний»

Начальная глобальная оценка Zверхняя=10+10+20+15+10 = 65 получим по циклу. (соответствующие рёбра, обведены квадратами на рисунке - одно в левом нижнем углу, остальные над диагональю).

Начинаем рисовать дерево ветвления

В полученной матрице

рассчитаем дополнительную цену «объезда» каждого отдельного нуля (то есть, на сколько возрастёт сумма констант редуцирования, если дорога перестанет существовать (цена проезда будет заменена на бесконечность)) и выберем, тот «ноль», цена объездакоторого максимальна.

(1,2)=0

(1,5)=1

(2,1)=0

(2,3)=5 (Максимальная )

(3,1)=0

(3,4)=2

(4,2)=4

(5,2)=2

Итак, максимальная цена объезда  наблюдается при выключении ребра (2,3)=5.

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

На отдельной странице начинаем вырисовывать дерево ветвления.

На начальном этапе оно содержит множество всех циклов, которое разбивается на множество содержащее (2,3) (их меньше)– слева и не содержащее (2,3) – справа.

Нижняя оценка (большего) правого множества получается суммой оценки предшествующей вершины Z min =58 и(2,3)=5:Z min =58+5=63.

В левом множестве ребро (2,3) (условно говоря путь Санкт-Петербург - Москва) является обязательным – соответственно мы более не имеем выбора куда поехать из города 2 (удалим строку 2) и как приехать в город №3 (удалим столбец).

Итоговое дерево ветвления:

Финал метода.

Получается матрица размера 2х2.

Маломерный пример.

В заключении рассмотрим матрицу 3х3.

Тогда верхняя граница длин всех маршрутов Z max = 4+9+8 = 21

Таким образом, нижняя оценка Z нижн =16 (6+3+4+3).

Оцениваем константы обхода:

объединим города 2 и 1 в левой ветке, в правой ветке нижняя оценка стоимости возрастёт с 16 на 5 до 21.

получаем матрицу

Запретим короткое замыкание - во избежание

и редуцируем матрицу

На левой ветке ΔZ_=4, новая оценка целевой функции Z_=16+ ΔZ_=16+4=20.

Выбрано ребро

Остались рёбра
.

По принципу домино восстанавливаем минимальный цикл начиная с ребра начинающегося с 1, у на с это ребро
, как бы идущего "паровозиком".

Это конкретный путь длина 20 в этот момент мы получаем новую верхнюю оценку, что лучше старой верхней оценки 21.

На дереве ветвления множеств перебора исчезает ветвь с более высокой нижней оценкой 21 (правая ветвь).

В нашем случае полученный вариант оказался лучше всех нижних оценок по другим ветвям.

Ответ:
.

Проверка


Презентация КОММИВОЯЖЁР.

Задача проверяется преподавателем по оформлению дерева ветвления. Чтобы на нём была представлена максимально полная необходимая для проверки информация в вершинах дерева отобразить нижние оценки целевых функций, на рёбрах дерева обязательно должны быть отображены все θ (рост суммы констант редуцирования на правом повороте), все ΔZ(рост суммы констант редуцирования при левом повороте). При левом повороте выбирается одно обязательное ребро (отмечается на дереве ветвления) и добавляется одно запрещённое ребро. Для объяснения его выбора рядом с деревом ветвления на соответствующем уровне должна быть изображена цепочка в которой запрещаемое ребро вкупе с ранее выбранными (включая сейчас выбранное) порождает цикл не проходящий через все рёбра (так называемое «короткое замыкание» цикла).

В ответе дается цепочка Рёбер вида (1,k)(k,l)(l,m)..(r,1)(по размеру задачи), стоимость маршрута состоит из начальной нижней оценки и её приращений ΔZ(если были только ВЫЧЁРКИВАНИЯ – левые ПОВОРОТЫ) и – что бывает очень редко - ΔZи θ, если КРОМЕ левых ПОВОРОТОВ присутствовали один или несколько правых поворотов. Провести проверку стоимости ПОЛУЧЕНОГО решения по исходной матрице, объяснить причины несовпадения – если имелись (не совпадений быть не должно).

Решение будем вести с использованием калькулятора . Возьмем в качестве произвольного маршрута:
X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Тогда F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
d i = min(j) d ij
i j 1 2 3 4 5 d i
1 M 90 80 40 100 40
2 60 M 40 50 70 40
3 50 30 M 60 20 20
4 10 70 20 M 50 10
5 20 40 50 20 M 20

Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j 1 2 3 4 5
1 M 50 40 0 60
2 20 M 0 10 30
3 30 10 M 40 0
4 0 60 10 M 40
5 0 20 30 0 M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij
i j 1 2 3 4 5
1 M 50 40 0 60
2 20 M 0 10 30
3 30 10 M 40 0
4 0 60 10 M 40
5 0 20 30 0 M
d j 0 10 0 0 0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .
i j 1 2 3 4 5
1 M 40 40 0 60
2 20 M 0 10 30
3 30 0 M 40 0
4 0 50 10 M 40
5 0 10 30 0 M

Сумма констант приведения определяет нижнюю границу H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij >=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления
i j 1 2 3 4 5 d i
1 M 40 40 0(40) 60 40
2 20 M 0(20) 10 30 10
3 30 0(10) M 40 0(30) 0
4 0(10) 50 10 M 40 10
5 0(0) 10 30 0(0) M 0
d j 0 10 10 0 30 0

d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (40 + 0) = 40 для ребра (1,4), следовательно, множество разбивается на два подмножества (1,4) и (1*,4*).

H(1*,4*) = 140 + 40 = 180
Исключение ребра (1,4) проводим путем замены элемента d 14 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,4*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 d i
1 M 40 40 M 60 40
2 20 M 0 10 30 0
3 30 0 M 40 0 0
4 0 50 10 M 40 0
5 0 10 30 0 M 0
d j 0 0 0 0 0 40

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

∑d i + ∑d j = 10
i j 1 2 3 5 d i
2 20 M 0 30 0
3 30 0 M 0 0
4 M 50 10 40 10
5 0 10 30 M 0
d j 0 0 0 0 10

Нижняя граница подмножества (1,4) равна:
H(1,4) = 140 + 10 = 150 ≤ 180
Поскольку нижняя граница этого подмножества (1,4) меньше, чем подмножества (1*,4*), то ребро (1,4) включаем в маршрут с новой границей H = 150
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 5 d i
2 20 M 0(20) 30 20
3 30 0(10) M 0(30) 0
4 M 40 0(30) 30 30
5 0(30) 10 30 M 10
d j 20 10 0 30 0

d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 150 + 30 = 180
Исключение ребра (3,5) проводим путем замены элемента d 35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.
i j 1 2 3 5 d i
2 20 M 0 30 0
3 30 0 M M 0
4 M 40 0 30 0
5 0 10 30 M 0
d j 0 0 0 30 30

Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d 53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 10
После операции приведения сокращенная матрица будет иметь вид:
i j 1 2 3 d i
2 20 M 0 0
4 M 40 0 0
5 0 10 M 0
d j 0 10 0 10

Нижняя граница подмножества (3,5) равна:
H(3,5) = 150 + 10 = 160 ≤ 180
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 160
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 d i
2 20 M 0(20) 20
4 M 30 0(30) 30
5 0(20) 0(30) M 0
d j 20 30 0 0

d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Наибольшая сумма констант приведения равна (0 + 30) = 30 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,2*) = 160 + 30 = 190
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
i j 1 2 3 d i
2 20 M 0 0
4 M 30 0 0
5 0 M M 0
d j 0 30 0 30

Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 20
После операции приведения сокращенная матрица будет иметь вид:
i j 1 3 d i
2 20 0 0
4 M 0 0
d j 20 0 20

Нижняя граница подмножества (5,2) равна:
H(5,2) = 160 + 20 = 180 ≤ 190
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 180
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (2,1) и (4,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(1,4), (4,3), (3,5), (5,2), (2,1),
Длина маршрута равна F(Mk) = 180

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

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .

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

Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n

Методы решения задачи коммивояжера

  1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
  2. венгерский метод. Пример решения венгерским методом .

Алгоритм Литтла или исключения подциклов

  1. Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
  2. Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
  3. Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
  4. Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
  5. Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
  6. Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
  7. Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
  8. Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
  9. Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
  10. Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей

1 2 3 4
1 - 5 8 7
2 5 - 6 15
3 8 6 - 10
4 7 15 10 -

Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij
i j 1 2 3 4 5 d i
1 M 20 18 12 8 8
2 5 M 14 7 11 5
3 12 18 M 6 11 6
4 11 17 11 M 12 11
5 5 5 5 5 M 5
Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 0 0 0 M
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 0 0 0 M
d j 0 0 0 0 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 0 0 0 M
Сумма констант приведения определяет нижнюю границу H: H = ∑d i + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j 1 2 3 4 5 d i
1 M 12 10 4 0(5) 4
2 0(2) M 9 2 6 2
3 6 12 M 0(5) 5 5
4 0(0) 6 0(0) M 1 0
5 0(0) 0(6) 0(0) 0(0) M 0
d j 0 6 0 0 1 0
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 d i
1 M 12 10 4 0 0
2 0 M 9 2 6 0
3 6 12 M 0 5 0
4 0 6 0 M 1 0
5 0 M 0 0 M 0
d j 0 6 0 0 0 6
Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.


i j 1 3 4 5 d i
1 M 10 4 0 0
2 0 9 2 M 0
3 6 M 0 5 0
4 0 0 M 1 0
d j 0 0 0 0 0

Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 3 4 5 d i
1 M 10 4 0(5) 4
2 0(2) 9 2 M 2
3 6 M 0(7) 5 5
4 0(0) 0(9) M 1 0
d j 0 9 2 1 0
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.
i j 1 3 4 5 d i
1 M 10 4 0 0
2 0 9 2 M 0
3 6 M 0 5 0
4 0 M M 1 0
d j 0 9 0 0 9
Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.

После операции приведения сокращенная матрица будет иметь вид:
i j 1 4 5 d i
1 M 4 0 0
2 0 2 M 0
3 6 M 5 5
d j 0 2 0 7
Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .
i j 1 2 3 4 5
1 M 12 10 4 0
2 0 M 9 2 6
3 6 12 M 0 5
4 0 6 0 M 1
5 0 M 0 0 M
Операция редукции .
i j 1 2 3 4 5
1 M 6 10 4 0
2 0 M 9 2 6
3 6 6 M 0 5
4 0 0 0 M 1
5 0 M 0 0 M
Шаг №1 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 2 3 4 5 d i
1 M 6 10 4 0(5) 4
2 0(2) M 9 2 6 2
3 6 6 M 0(5) 5 5
4 0(0) 0(6) 0(0) M 1 0
5 0(0) M 0(0) 0(0) M 0
d j 0 6 0 0 1 0
d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.
i j 1 2 3 4 5 d i
1 M 6 10 4 0 0
2 0 M 9 2 6 0
3 6 6 M 0 5 0
4 0 M 0 M 1 0
5 0 M 0 0 M 0
d j 0 6 0 0 0 6
Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 3 4 5 d i
1 M 10 4 0 0
2 0 9 M 6 0
3 6 M 0 5 0
5 0 0 0 M 0
d j 0 0 0 0 0
Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 3 4 5 d i
1 M 10 4 0(9) 4
2 0(6) 9 M 6 6
3 6 M 0(5) 5 5
5 0(0) 0(9) 0(0) M 0
d j 0 9 0 5 0
d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.
i j 1 3 4 5 d i
1 M 10 4 M 4
2 0 9 M 6 0
3 6 M 0 5 0
5 0 0 0 M 0
d j 0 0 0 5 9
Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 1 3 4 d i
2 0 9 M 0
3 6 M 0 0
5 M 0 0 0
d j 0 0 0 0
Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i j 1 3 4 d i
2 0(15) 9 M 9
3 6 M 0(6) 6
5 M 0(9) 0(0) 0
d j 6 9 0 0
d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.
i j 1 3 4 d i
2 M 9 M 9
3 6 M 0 0
5 M 0 0 0
d j 6 0 0 15
Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:
i j 3 4 d i
3 M 0 0
5 0 0 0
d j 0 0 0
Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.

1
(5*,2*), H=41 (5,2)
(4*,2*), H=47 (4,2) (4*,3*), H=44 (4,3)
(1*,5*), H=50 (1,5)
(2*,1*), H=56 (2,1)
(3,4) (3*,4*), H=41
(5,3) (5*,3*), H=41

Решение задачи коммивояжера методом ветвей и границ

Определения

Графом называется непустое конечное множество, состоящее из двух подмножеств и . Первое подмножество
(вершины) состоит из любого множества элементов. Второе подмножество (дуги) состоит из упорядоченных пар элементов первого подмножества
. Если вершины и
такие, что , то это вершины смежные.

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

Постановка задачи

Коммивояжер должен объездить n городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длинна (или цена) дуги (i , j ),
. Под маршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0  Z , такой, что l (z 0)= min l (z ), z Z .

Решение задачи

Основная идея метода ветвей и границ состоит в том, что вначале строят нижнюю границу φ длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е. φ(Z)≤ φ (), φ(Z) ≤ φ ().

Сравнивая нижние границы φ () и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

Для практической реализации метода ветвей и границ применительно к задаче коммивояжера укажем прием определения нижних границ подмножеств и разбиения множества маршрутов на подмножества (ветвление).

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

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

Константу приведения следует выбирать в качестве нижней границы длины маршрутов.

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.

Пример решения задачи коммивояжера методом ветвей и границ

Коммивояжер должен объездить 6 городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город A. Затраты на перемещение между городами заданы следующей матрицей:

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

После их вычитания по строкам получим:

Минимумы по столбцам: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

После их вычитания по столбцам получим приведенную матрицу:

Найдем нижнюю границу φ (Z ) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Наибольшая степень Θ 14 = 10. Ветвление проводим по дуге (1, 4).

Нижняя граница для множества
остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ () = 47 + 10.

В матрице, соответствующей полагаем c 14 = ∞.

После проведения процедуры приведения с r 1 =10 получим новую нижнюю границу 57 + 10 = 67.

В матрице, соответствующей , вычеркиваем первую строку и четвертый столбец и положим c 41 = ∞, чтобы предотвратить появления цикла 1→ 4 → 1. Получим новую платежную матрицу {c 1 ij }:

Для приведения надо вычесть минимум по первому столбцу: h 1 =1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы
φ () = 67 и φ () = 48 , которое с большей вероятностью содержит маршрут минимальной длины.

Рис. 1 Ветвление на первом шаге

Далее продолжаем процесс ветвления. Найдем степени Θ ij нулевых элементов этой матрицы Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2. Наибольшая степень Θ 21 . Затем множество разбивается дуге (2, 1) на два новых
и .

В матрице для вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c 42 = ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.

Для приведения надо вычесть минимум по строке 4: r 4 =2. При этом нижняя граница станет равной 48+2 = 50.

Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ () = 64 и φ () = 50 .

Рис. 2 Ветвление на втором шаге

Приведенная платежная матрица для

Для приведения надо вычесть минимум по строке 3: r 3 =5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов.

Рис. 3 Ветвление на третьем шаге

Приведенная платежная матрица для

0 Шпаргалка >> Бухгалтерский учет и аудит

Активности, влияния, участия в решении задачи . В различных ситуациях жизни... Специальные задачи математического программирования Специальные задачи математического программирования. Задача о коммивояжере .Метод ветвей и границ . Задача о коммивояжере Пусть...