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

Введение

      Каждый  человек ежедневно, не всегда  осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда  ограничены. Жизнь была бы менее  интересной, если бы это было  не так. Чтобы достичь наибольшего  эффекта, имея ограниченные средства, надо составить план, или программу  действий.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретическая часть     

 

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

 

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

Очевидно, что задача коммивояжера – это задача отыскания кратчайшего  гамильтонова цикла в полном графе.

Существует метод решения  задачи коммивояжера, который дает оптимальное решение. Этот метод  называется методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ по-другому называют алгоритмом Литтла.

 

1.2 Описание метода

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

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

Опишем алгоритм Литтла для  нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами X_i и X_j нет дуги, то ставится символ «∞».

Алгоритм Литтла для решения  задачи коммивояжера можно сформулировать в виде следующих правил:

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

.

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

,

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

3. Суммируем элементы  и , получим константу приведения

 

,

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

.

4. Находим степени нулей  для приведенной по строкам  и столбцам матрицы. Для этого  мысленно нули в матице заменяем  на знак «∞» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.

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

.

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

7. Приводим матрицу гамильтоновых  контуров  . Пусть - константа ее приведения. Тогда нижняя граница множества определится так:

.

8. Находим множество гамильтоновых  контуров  , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ∞.

9. Делаем приведение матрицы  гамильтоновых контуров  . Пусть - константа ее приведения. Нижняя граница множества определится так:

.

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

Процесс разбиения множеств на подмножества сопровождается построением  дерева ветвлений.

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

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

 

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

 

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

    (1)

 

 

Условия (2) – (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)).

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

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

, где  , и .

 

1.4 Алгоритм решения

 

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

Табл.1

j i	1	2	3	4	5	6
1	∞	7	16	21	2	17
2	13	∞	21	15	43	23
3	25	3	∞	31	17	9
4	13	10	27	∞	33	12
5	9	2	19	14	∞	51
6	42	17	5	9	23	∞

 

1) Справа к таблице  присоединяем столбец U_i, в котором записываем минимальные элементы соответствующих строк. Вычитаем элементы U_i из соответствующих элементов строки матрицы.

 

j i	1	2	3	4	5	6	Ui
1	∞	7	16	21	2	17	2
2	13	∞	21	15	43	23	13
3	25	3	∞	31	17	9	3
4	13	10	27	∞	33	12	10
5	9	2	19	14	∞	51	2
6	42	17	5	9	23	∞	5

 

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

 

j i	1	2	3	4	5	6
1	∞	5	14	19	0	15
2	0	∞	8	2	30	10
3	22	0	∞	28	14	6
4	3	0	17	∞	23	2
5	7	0	17	12	∞	49
6	37	12	0	4	18	∞
Vj	0	0	0	2	0	2

 

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

 

Табл.2

j i	1	2	3	4	5	6
1	∞	5	14	17	019	13
2	03	∞	8	02	30	8
3	22	04	∞	26	14	4
4	3	00	17	∞	23	04
5	7	07	17	10	∞	47
6	37	12	08	2	18	∞

 

4) Находим константу приведения:

.

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

 

5) Находим степени нулей  полностью приведенной матрицы.  Для этого как бы заменяем  в ней все нули на знак  «∞» и устанавливаем сумму минимальных элементов соответствующей строки и столбца. Степени нулей записаны в правых верхних углах клеток, для которых .

 

6) Определяем максимальную  степень нуля. Она равна 19 и  соответствует клетке (1;5). Таким  образом, претендентом на включение  в гамильтонов контур является  дуга (1;5).

 

7) Разбиваем множество  всех гамильтоновых контуров  на два: и . Матрицу с дугой (1;5) получаем табл.2 путем вычеркивания строки 1 и столбца 5. Чтобы не допускать образования негамильтонова контура, заменяем элемент (5;1) на знак «∞».

 

j i	1	2	3	4	6
2	0	∞	8	0	8
3	22	0	∞	26	4
4	3	0	17	∞	0
5	∞	0	17	10	47
6	37	12	0	2	∞