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

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ .

Общий план решения задачи коммивояжера

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

1. Построение матрицы с исходными данными.
2. Нахождение минимума по строкам.
3. Редукция строк.
4. Нахождение минимума по столбцам.
5. Редукция столбцов.
6. Вычисление оценок нулевых клеток.
7. Редукция матрицы.
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
9. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

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

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

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

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

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка .

4. Нахождение минимума по столбцам

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

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

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку ». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

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

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .

Общая длина пути: L = 30 .

Практическое применение задачи коммивояжера

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

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

Галяутдинов Р.Р.

© Копирование материала допустимо только при указании прямой гиперссылки на

5x 1 + 2x 2 ≤ 14
2x 1 + 5x 2 ≤ 16
x 1 , x 2 – целые числа
Z = 3x 1 + 5x 2 → max
Решение находим с помощью калькулятора .:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

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

Рассмотрим целевую функцию задачи F = 3x 1 +5x 2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 3x 1 +5x 2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = const (1) и (2)
5x 1 +2x 2 ≤14
2x 1 +5x 2 ≤16

Решив систему уравнений, получим: x 1 = 1.8095, x 2 = 2.4762
F(X) = 3*1.8095 + 5*2.4762 = 17.8095
Оптимальное значение переменной x 1 =1.81 оказалось нецелочисленным.
В первой из них к условиям задачи 11 добавляется условие х 1 ≥ 2, а к задаче 12 - условие х 1 ≤ 1.
Эта процедура называется ветвлением по переменной х 1 .

Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16

Решение задачи получилось целочисленным.
Новое значение текущего рекорда будет равно F(X) = 16.
Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи - текущим значением рекорда . Это значение является нижней границей оптимального значения исходной задачи Z*.

Решив систему уравнений, получим: x 1 = 1, x 2 = 2.8
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2.8 = 17

Оптимальное значение переменной x 2 =2.8 оказалось нецелочисленным.
Разбиваем задачу 12 на две подзадачи 121 и 122.
В первой из них к условиям задачи 121 добавляется условие х 2 ≥ 3, а к задаче 122 - условие х 2 ≤ 2.
Решим графически задачу 121 как задачу ЛП.

Откуда найдем максимальное значение целевой функции:
F(X) = 3*0.5 + 5*3 = 16.5

Решим графически задачу 122 как задачу ЛП.

Решив систему уравнений, получим: x 1 = 1, x 2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*1 + 5*2 = 13

Текущий рекорд Z=16≥13, поэтому прекращаем ветвление из этой вершины

Разбиваем задачу 121 на две подзадачи 1211 и 1212.
В первой из них к условиям задачи 1211 добавляется условие х 1 ≥ 1, а к задаче 1212 - условие х 1 = 0.
Решим графически задачу 1211 как задачу ЛП.

Задача не имеет допустимых решений. ОДР представляет собой пустое множество.

Задача 1211 не имеет решения, поэтому для нее процесс ветвления прерываем.
Решим графически задачу 1212 как задачу ЛП.

Откуда найдем максимальное значение целевой функции:
F(X) = 3*0 + 5*3.2 = 16

Оптимальное значение переменной x 2 =2.48 оказалось нецелочисленным.
Разбиваем задачу 1 на две подзадачи 11 и 12.
В первой из них к условиям задачи 11 добавляется условие х 2 ≥ 3, а к задаче 12 - условие х 2 ≤ 2.
Эта процедура называется ветвлением по переменной х 2 .
Решим графически задачу 11 как задачу ЛП.

Решив систему уравнений, получим: x 1 = 0.5, x 2 = 3
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0.5 + 5*3 = 16.5

Решим графически задачу 12 как задачу ЛП.

Решив систему уравнений, получим: x 1 = 2, x 2 = 2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*2 + 5*2 = 16

Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
Оптимальное значение переменной x 1 =0.5 оказалось нецелочисленным.
Разбиваем задачу 11 на две подзадачи 111 и 112.
В первой из них к условиям задачи 111 добавляется условие х 1 ≥ 1, а к задаче 112 - условие х 1 = 0.
Решим графически задачу 111 как задачу ЛП. Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (6) , то ее координаты удовлетворяют уравнениям этих прямых:
2x 1 +5x 2 ≤16
x 1 =0

Решив систему уравнений, получим: x 1 = 0, x 2 = 3.2
Откуда найдем максимальное значение целевой функции:
F(X) = 3*0 + 5*3.2 = 16

Текущий рекорд Z=16≥16, поэтому прекращаем ветвление из этой вершины
F(X) = 16
x 1 = 2
x 2 = 2

Дерево решения задачи

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

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

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

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

Здесь каждому ребру соответствует две дуги такого же веса.

«Жадный алгоритм» прежде всего включит в цикл ребро
, как имеющее минимальный вес. Включение этого ребра, как непосредственно легко проверить, необходимо ведет к гамильтонову циклу
веса 29. Оптимальный

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

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

Под методом «ветвей и границ» понимается широкий класс методов сокращенного перебора, суть которых сводится к следующему. Множество допустимых решений А разбивается на два подмножества А 0 и А 1 , затем каждое из подмножеств также разбивается на два подмножества и т.д. Схематически это можно представить в виде дерева, начинающегося с множества всех решений и заканчивающегося его одноэлементными подмножествами, т.е. допустимыми решениями, которыми в нашем случае являются гамильтоновы циклы.

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

Рассмотрим метод «ветвей и границ» на примере задачи коммивояжера. Пусть взвешенный орграф задан матрицей расстояний. Если некоторая дуга в графе отсутствует, то соответствующий элемент матрицы будем полагать равным ∞. Заметим, что если длины всех дуг, входящих в некоторую вершину, уменьшить на одно и то же число, то и длина оптимального гамильтонова цикла уменьшится на это же число. То же самое относится и к множеству выходящих дуг. Будем последовательно вычитать из строк и столбцов матрицы расстояний положительные числа так, чтобы элементы матрицы оставались неотрицательными. Так как длина оптимального гамильтонова цикла для графа с неотрицательной матрицей расстояний также неотрицательна, то сумма вычтенных количеств будет нижней границей для длины оптимального цикла исходного графа.

Рассмотрим пример. Пусть задан граф G с симметрической матрицей расстояний.

Значки « ∞ » на диагонали соответствуют отсутствию в графе петель – дуг, ведущих из вершины в эту же вершину. Получим, прежде всего, нижнюю границу для длины кратчайшего гамильтонового цикла. Из первой, второй, третьей и четвертой строк можно вычесть по единице, из пятой строки – два, а из пятого столбца можно вычесть ещё единицу. Это дает нижнюю границу 7, а матрица расстояний приобретает вид

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

из первой строки и второго столбца которой можно вычесть по единице, что увеличивает нижнюю границу на 2 и делает её равной 9.

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

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

Нижняя оценка здесь возрастает на 2 и также становится равной 9.

Нижняя оценка длины оптимального цикла остается неизменной.

Дуга (2,5) должна быть запрещена, как ведущая к появлению негамильтонова цикла, и матрица принимает вид

Нижняя оценка длины гамильтонова цикла остается, по – прежнему, равной 9.

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

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

Существует ли эффективный алгоритм для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.

Является ли описанный метод « ветвей и границ» эффективным алгоритмом для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.

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

ПОСТАНОВКА ЗАДАЧИ

Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (высокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выполнение работы с минимальным расходом фонда зарплаты при заданных ограничениях. Исходные данные приведены в таблице 1 и 2.

Таблица 1

Таблица 2

Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ ЗАДАЧИ

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

Решение задачи целочисленного программирования выполняется в два этапа.

На первом этапе выполняется задача линейного программирования без учета целочисленности.

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

Сначала решается, задача без учета условия целочисленности.

Целевая функция определяется по формуле:

где Q - общий фонд зарплаты на выполнение работы;

x 1 , x 2 , …, x n - численность работников по категориям;

n - число категорий работников;

c 1 , c 2 ,…, c n - дневная тарифная ставка одного работника по категориям;

m - число рабочих дней в неделю, m = 5.

Целевую функцию можно записать в векторной форме:

При решении задачи должны выполняться следующие ограничения. Ограничение сверху

x ≤ d (1)

задает максимальную численность работников по категориям, где d —вектор, определяющий численность по категориям.

В ограничении

учтено, что общая численность работников не должна превышать k max .

В ограничении снизу

р × х≥Р (3)

отражается, что все работники вместе должны выполнить заданный объем работ Р .

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

x ≥0 (4)

Математическая модель решения задачи без учета условия целочисленности включает следующие выражения:

x ≤ d

р × х≥Р ,

x ≥ 0 .

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

РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

Исходные данные для примера даны в табл. 1 и 2.

Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор решения задачи:

х := Minimize (Q , x ),

где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х - вектор переменных.

Сначала задача решается без учета условия целочисленности. Это решение приведено в Приложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q (x ) . После слова Given и перед функцией Minimize указаны ограничения. В результате получена нецелочисленная оптимальная численность по категориям:

х =

с фондом зарплаты Q = 135 у. е.

Из данного решения находится целочисленное решение методом ветвей и границ.

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

Для ветви с ограничением х 4 = 1 решается задача линейного программирования, данная в Приложении 1, с учетом этого ограничения.

В результате получено решение этой задачи. Переменная х 1 стала целочисленная, но переменная х 2 стала дробной х 2 = 0,9.

Для продолжения ветви создается узел х 3 и ветвь х 3 = 1. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1. С этими ограничениями задача имеет решение х Т =
= (1,938 1 1 1).

Для продолжения ветви создается узел х 1 и ветвь х 1 = 2. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1, х 1 = 2. С этими ограничениями задача имеет решение х Т = = (2 1 1 1).

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

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

Из результативных выбирается наилучшее и оно принимается как оптимальное целочисленное решение всей задачи с минимальной величиной Q (x ) . В нашем случае мы имеем два оптимальных целочисленных решения

Q (х) = 140,

x T = (2 1 1 1),

x T = (1 1 2 2).

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

Скачать решение задачи:

Если закачивание файла не начнется через 10 сек, кликните