РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере.
Итак, требуется найти легчайший простой основный ориентированный цикл в полном взвешенном ориентированном графе на пяти вершинах со следующей весовой матрицей:
Таблица 2
1 |
2 |
3 |
4 |
5 |
1 |
9 |
8 |
4 |
10 |
2 |
6 |
4 |
5 |
7 |
3 |
5 |
3 |
6 |
2 |
4 |
1 |
7 |
2 |
8 |
5 |
2 |
4 |
5 |
2 |
Верхняя строка и левый столбец, выделенные затемненным фоном, содержат номера вершин графа; символ, стоящий на главной диагонали, означает, естественно, отсутствие ребер-петель (начинающихся и заканчивающихся в одной и той же вершине); кроме того, символ здесь и всюду в дальнейшем обозначает "компьютерную бесконечность", т. е. самое большое из возможных в рассмотрении чисел; считается, что + любое число =.
Подсчитаем () в нашем примере. Для этого выполним приведение матрицы весов; сначала - по строкам:
Таблица 3
1 |
2 |
3 |
4 |
5 | ||
1 |
9 |
8 |
4 |
10 |
4 |
min в строке 1 |
2 |
6 |
4 |
5 |
7 |
4 |
min в строке 2 |
3 |
5 |
3 |
6 |
2 |
2 |
min в строке 3 |
4 |
1 |
7 |
2 |
8 |
1 |
min в строке 4 |
5 |
2 |
4 |
5 |
2 |
2 |
min в строке 5 |
Результат приведения по строкам:
Таблица 4
1 |
2 |
3 |
4 |
5 |
1 |
5 |
4 |
0 |
6 |
2 |
2 |
0 |
1 |
3 |
3 |
3 |
1 |
4 |
0 |
4 |
0 |
6 |
1 |
7 |
5 |
0 |
2 |
3 |
0 |
Определим константы приведения по столбцам:
Таблица 5
1 |
2 |
3 |
4 |
5 |
1 |
5 |
4 |
0 |
6 |
2 |
2 |
0 |
1 |
3 |
3 |
3 |
1 |
4 |
0 |
4 |
0 |
6 |
1 |
7 |
5 |
0 |
2 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
Min в Столбце 1 |
Min в Столбце 2 |
Min в Столбце 3 |
Min в Столбце 4 |
Min в Столбце 5 |
Результат приведения матрицы:
Таблица 6
1 |
2 |
3 |
4 |
5 |
1 |
4 |
4 |
0 |
6 |
2 |
2 |
0 |
1 |
3 |
3 |
3 |
0 |
4 |
0 |
4 |
0 |
5 |
1 |
7 |
5 |
0 |
1 |
3 |
0 |
Сумма констант приведения ()=4+4+2+1+2+1=14.
Обозначим эту матрицу через M1; найдем в ней самый тяжелый нуль. Для этого запишем эту матрицу еще раз, указывая рядом с каждым нулем в скобках его вес:
Таблица 7
1 |
2 |
3 |
4 |
5 |
1 |
4 |
4 |
0(4) |
6 |
2 |
2 |
0(2) |
1 |
3 |
3 |
3 |
0(1) |
4 |
0(3) |
4 |
0(1) |
5 |
1 |
7 |
5 |
0(0) |
1 |
3 |
0(0) |
Самым тяжелым оказывается нуль в клетке (1,4). Следовательно, множество разбивается на (все циклы, проходящие через ребро (1,4)) и (все циклы, не проходящие через ребро (1,4)).
Построим для множества соответствующую ему матрицу и значение оценочной функции.
Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.
Учитывая это напоминание, элемент с номером (4,1) заменим на и вычеркнем строку номер 1 и столбец номер 4:
Таблица 8
1 |
2 |
3 |
5 |
2 |
2 |
0 |
3 |
3 |
3 |
0 |
0 |
4 |
5 |
1 |
7 |
5 |
0 |
1 |
3 |
Приведем теперь эту матрицу:
Таблица 9
1 |
2 |
3 |
5 |
2 |
2 |
0 |
3 |
3 |
3 |
0 |
0 |
4 |
4 |
0 |
6 |
5 |
0 |
1 |
3 |
Это - матрица M1,1; сумма констант приведения здесь равна 1, поэтому 14+1= 15.
Для M1,2 заменяем на элемент (1,4) в M1:
Таблица 10
1 |
2 |
3 |
4 |
5 |
1 |
4 |
4 |
6 | |
2 |
2 |
0 |
1 |
3 |
3 |
3 |
0 |
4 |
0 |
4 |
0 |
5 |
1 |
7 |
5 |
0 |
1 |
3 |
0 |
После этого приводим полученную матрицу:
Таблица 11
1 |
2 |
3 |
4 |
5 |
1 |
0 |
0 |
2 | |
2 |
2 |
0 |
1 |
3 |
3 |
3 |
0 |
4 |
0 |
4 |
0 |
5 |
1 |
7 |
5 |
0 |
1 |
3 |
0 |
Это - матрица M1,2; сумма констант последнего приведения равна 4, так что 14+4=18. Следовательно, дальнейшей разработке подвергается множество.
Вот веса нулей матрицы M1,1 (они указаны в скобках):
Таблица 12
1 |
2 |
3 |
5 |
2 |
2 |
0(2) |
3 |
3 |
3 |
0(1) |
0(3) |
4 |
4 |
0(4) |
6 |
5 |
0(3) |
1 |
3 |
Самым тяжелым является нуль с номером (4,3), так что теперь следует рассматривать множества и.
Обратимся к первому из них.
Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.
Следовательно, клетки с номерами (4,2), (4,5) и (3,1) надо заполнить символом ; после этого строку номер 4 и столбец номер 3 следует вычеркнуть; получим:
Таблица 13
1 |
2 |
5 |
2 |
2 |
3 |
3 |
0 |
0 |
5 |
0 |
1 |
Приведение этой матрицы:
Таблица 14
1 |
2 |
5 |
2 |
0 |
1 |
3 |
0 |
0 |
5 |
0 |
1 |
Для оценочной функции: =15+2=17.
Матрица для множества :
Таблица 15
1 |
2 |
3 |
5 |
2 |
2 |
0 |
3 |
3 |
3 |
0 |
0 |
4 |
4 |
6 | |
5 |
0 |
1 |
3 |
Результат ее приведения:
Таблица 16
1 |
2 |
3 |
5 |
2 |
2 |
0 |
3 |
3 |
3 |
0 |
0 |
4 |
0 |
2 | |
5 |
0 |
1 |
3 |
Оценочная функция: =15+4=19. Следовательно, дальнейшей разработке подлежит. "Взвешиваем" нули:
Таблица 17
1 |
2 |
5 |
2 |
0(1) |
1 |
3 |
0(1) |
0(1) |
5 |
0(1) |
1 |
Выбираем любую из соответствующих клеток; для определенности - клетку (2,1).
Теперь речь пойдет о множествах и.
Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.
Поэтому для первого множества положим в последней матрице элемент с номером (3,2) равным, вычеркнем строку номер 2 и столбец номер 1:
Таблица 18
2 |
5 |
3 |
0 |
5 |
1 |
Приведем эту матрицу:
Таблица 19
2 |
5 |
3 |
0 |
5 |
0 |
Получаем для оценочной функции: =17+1=18.
Для множества матрица такова:
Таблица 20
1 |
2 |
5 |
2 |
1 | |
3 |
0 |
0 |
5 |
0 |
1 |
Приведение этой матрицы дает:
Таблица 21
1 |
2 |
5 |
2 |
0 | |
3 |
0 |
0 |
5 |
0 |
1 |
Для оценочной функции: =17+1=18.
Получилось, что для дальнейшей разработки можно брать любое из множеств и. В первом случае уже получена матрица размером 22; ее нулевые клетки дают те ребра, которые с найденными ранее составляют обход коммивояжера, причем вес этого обхода равен значению оценочной функции - 18. Вот этот обход:
(1,4)(4,3)(2,1)(5,2)(3,5) или 143521.
Найденный рекорд на самом деле является искомым оптимумом, потому что значения оценочной функции на всех оборванных ветвях (на границах) больше или равны весу рекорда.
При ином варианте выборов по ходу разбиений можно было получить другой оптимум: 143251.
ПРАКТИЧЕСКОЕ ЗАДАНИЕ
Требуется найти легчайший простой основный ориентированный цикл в полном взвешенном ориентированном графе на четырех вершинах (рис. 2):
Рис. 2. Ориентированный граф задачи коммивояжера
Попробуем решить данную задачу методом "жадный алгоритм".
Из пункта 1 существует только один путь - путь к пункту 2, стоимость пути равна 78. Из пункта 2 существует только один путь - путь к пункту 3, стоимость пути равна 81. Из пункта 3 существует два пути - путь к пункту 1 и путь к пункту 4. Выберем самый кратчайший путь - это путь к пункту 4, стоимость пути равна 16. Из пункта 4 существует два пути - путь к пункту 1 и путь к пункту 2. Так как в пункте 2 мы уже были, то идем в пункт 1, стоимость пути равна 25.
Полный обход коммивояжера, исходя из предыдущего решения, равен 12341, а сумма пути равна: 78+81+16+25 = 200.
Похожие статьи
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
-
Провести комплексное исследование численных методов для задачи решения нелинейных уравнений. 1. Решить нелинейные уравнения А) ; Б) ; В) . 2....
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими...
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Вид сырья Запас сырья Количество единиц сырья, идущих на изготовление единицы продукции P1 P2 P3 P4 S1 4 1 1 1 3 S2 18 2 4 6 1 Прибыль от единицы...
-
Введение - Решение оптимизационных экономических задач методами линейного программирования
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения...
-
Матрицы и определители - Методы решения системы линейных уравнений
Определение. Матрицей размера mn, где m - число строк, n - число столбцов, называется таблица чисел, расположенных в определенном порядке. Эти числа...
-
Определение . Алгебраическим дополнением минора матрицы называется его Дополнительный минор , умноженный на (-1) в степени, равной сумме номеров строк и...
-
Определители (детерминанты) - Методы решения системы линейных уравнений
Определение. Определителем квадратной матрицы А= называется число, которое может быть вычислено по элементам матрицы по формуле: Det A = , где (1) М1к -...
-
Ранг матрицы. - Методы решения системы линейных уравнений
Как было сказано Выше , минором матрицы порядка s называется определитель матрицы, образованной из элементов исходной матрицы, находящихся на пересечении...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой...
-
Многокритериальный оптимизация нейронный аппроксимация Общая схема рассматриваемого метода является итерационной и состоит из следующих основных этапов....
-
Расчет верхней и нижней границы надежности схемы методом минимальных путей и сечений Как видно из схемы, она не является последовательно-параллельной,...
-
При написании программ численного интегрирования желательно, чтобы для любой функции распределение узлов являлось оптимальным или близким к нему. Однако...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Любое частное решения уравнения (1) на координатной плоскости х0у изображено в виде графика функции у=у (х, с) (с=const). В теории дифференциальных...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Тема, с которой мы сегодня ознакомимся это "Применение матриц при решении экономических задач." Рассмотрим как с помощью матриц можно решать...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера