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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
Формулировка и некоторые свойства решений задачи коммивояжера
Постановка задачи коммивояжера как задачи на графе
Метод ветвей и границ. Основная схема.
Решение задачи о коммивояжере методом ветвей и границ.
Заключение
Список литературы

Заменяем на ( элемент (1,4) в M1:
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 ( Таблица 9
приводим полученную матрицу:
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 ( Таблица 10
Получили матрицу M1.2. Сумма констант приведения в этом случае равна 4, так что 14+4=18.
Следовательно, дальше работаем с множеством .
Найдем веса нулей в M1.1 (они указаны в скобках):
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 ( Таблица 11
Самым тяжелым является нуль в клетке (4,3). Значит рассматривать будем множества и .
Рассмотрим . Снова заменяем на ( числа в клетках с номерами (4,2), (4,5) и (3,1). После этого строку номер 4 и столбец номер 3 следует вычеркнуть, получим:
1 2 5 2 2 ( 3 3 ( 0 0 5 0 1 ( Таблица 12
Приведение этой матрицы:
1 2 5 2 0 ( 1 3 ( 0 0 5 0 1 ( Таблица 1
Оценочная функция для этого случая: =15+2=17.
Теперь запишем матрицу для множества :
1 2 3 5 2 2 ( 0 3 3 3 0 ( 0 4 ( 4 ( 6 5 0 1 3 ( Таблица 14
Результат ее приведения:
1 2 3 5 2 2 ( 0 3 3 3 0 ( 0 4 ( 0 ( 2 5 0 1 3 ( Таблица 15
Оценочная функция: =15+4=19. Следовательно, дальнейшему рассмотрению подлежит .
Найдем веса нулей:
1 2 5 2 0(1) ( 1 3 ( 0(1) 0(1) 5 0(1) 1 ( Таблица 16
Так как вес нулей одинаковый, выбираем любую из соответствующих клеток. Для определенности возьмем (2,1).
Теперь речь пойдет о множествах и .
Для первого множества заменяем в последней матрице элемент с номером (3,2) на (. Вычеркиваем строку номер 2 и столбец номер 1:
2 5 3 ( 0 5 1 ( Таблица 17
Эта матрица после приведения:
2 5 3 ( 0 5 0 ( Таблица 18
Находим значение оценочной функции: =17+1=18.
Повторим это для множества . Запишем матрицу:
1 2 5 2 ( ( 1 3 ( 0 0 5 0 1 ( Таблица 19
После приведения эта матрица выглядит так:
1 2 5 2 ( ( 0 3 ( 0 0 5 0 1 ( Таблица 20
Вычисляем значение оценочной функции: =17+1=18.
Значение оценочных функций для обоих множеств получились равными, это означает, что для дальнейшего рассмотрения подходят оба множества. Выберем любое из множеств и .
Рассмотрим первый случай, так как там уже получена матрица размером 2(2. Её нулевые клетки дают те ребра, которые дополняют ранее найденные до конечного маршрута коммивояжера. Заметим что вес полученного обхода равен значению оценочной функции - 18.
Найденный таким образом обход : (1,4)(4,3)(2,1)(5,2)(3,5) или 1(4(3(5(2(1.
Легко заметить, что найденный рекорд на самом деле является искомым оптимумом, так как значения оценочной функции на всех оборванных ветвях (на границах) больше или равны весу рекорда.
Если бы в ходе разбиения при равных значениях оценочных функции были выбраны другие множества, можно было получить другой оптимум: 1(4(3(2(5(1.

Заключение
Задачу коммивояжера можно рассматривать как частичный случай Гамильтоновой задаче о круговом путешествии. Суть задачи сводится к нахождению маршрута, при котором коммивояжер должен пройти все города, посетив каждый из них ровно один раз и вернуться в первый город. При этом маршрут должен быть минимизирован относительно некоторой характеристики (километраж, время затраченной на дорогу, расход горючего, стоимость проезда или другие).
Известно несколько методов решения данной задачи: полный перебор возможных маршрутов, “деревянный алгоритм”, алгоритм Крускала, метод ветвей и границ и др. Отличие метода ветвей и границ заключается в том, что оно дает оптимальное решение и позволяет избежать полного перебора, таким образом, сократить ресурсы, затрачиваемые на решение задачи.
Основная идея данного метода состоит в том, что сначала находится множество всех возможных гамильтоновых контуров и нижняя граница весов маршрутов для этого множества. Затем все множество контуров разбивается на две части. Одна часть содержит маршруты, проходящие через некоторое ребро графа(i,j), а другая не содержит это ребро. После чего выбирается то множество, на котором оценочная функция достигает минимума.
Основная задача в практической реализации метода ветвей и границ состоит в нахождении метода определения нижних границ подмножества и в самом разбиении гамильтоновых маршрутов на части. Определение нижних границ основано на утверждении: если ко всем элементам i-й строки или j-го столбца матрицы C прибавить или отнять некоторое число , то задача останется эквивалентной исходной и на оптимальность маршрута это не повлияет.
Список литературы
Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.
Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.
Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».
Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.
Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.
О. Е. Акимов «Дискретная математика. Логика, группы, графы», Москва, 2003, 376 с., ил., изд. дом «Лаборатория базовых знаний».
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.
Ф. А. Новиков «Дискретная математика для программистов» С.-Петербург, 2002 г. 304 с., ил., изд. дом «Питер».
22