Автор работы: Пользователь скрыл имя, 05 Декабря 2011 в 15:22, курсовая работа
В данной курсовой работе рассматривается задача коммивояжера. Целью курсовой работы является решение задачи коммивояжера методом ветвей и границ.
Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда.
Введение…………………………………………………………………………………. 2
Постановка задачи………………………………………………………………………3
Решение задачи о коммивояжере методом ветвей и
границ: основная схема………………………………………………………………... 5
Решение задачи о коммивояжере методом ветвей и границ. Примеры………...11 Практическое задание…………………………………………………………………19
Описание работы программы………………………………………………………...20
Приложение……………………………………………………………………………..21
Заключение……………………………………………………………………………...22
Список использованных источников……………………………………………….23
Самым тяжелым оказывается нуль в клетке (1,4). Следовательно, множество G разбивается на (все циклы, проходящие через ребро (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.
Информация о работе Решение задачи о Коммивояжере методом ветвей и границ