Применение методов решения задачи коммивояжера на практике
Курсовая работа, 16 Апреля 2014, автор: пользователь скрыл имя
Краткое описание
В современном мире происходит стремительное развитие науки и техники. С каждым годом число предприятий по производству различного рода продукции становится всё больше и больше. Но чтобы предприятие успешно развивалось и приносило прибыль, нужно взвешивать все плюсы и минусы не только вопросов касающихся затрат на закупку сырья и оборудования, но и вопросов связанных с транспортировкой груза к месту реализации, с нахождением оптимального маршрута и минимизацией затрат.
Именно задача коммивояжера помогает найти кратчайший путь с минимальными затратами.
Содержание
Введение…………………………………………………………………..…...6
1 Общие сведения о задаче коммивояжёра………………………………....8
Экономические ситуации, приводящие к задаче коммивояжера…....9
Постановка и математическая модель задачи коммивояжера…..…10
Методы решения задачи коммивояжера………………………..……12
Метод ветвей и границ………………………………………………….12
Венгерский метод…………………………………………..…………..14
Применение методов решения задачи коммивояжера на практике...16
3.1 Решение задачи коммивояжера методом ветвей и границ….……….16
3.2 Решение задачи коммивояжера венгерским методом……………….…25
Заключение……………………………………………………………..….…32
Глоссарий ………………………………………………………………..…..33
Список используемых источников…………
Вложенные файлы: 1 файл
TGTU_080100_62_009_-_KR_Kozhevnikova_V_A_BEK23..docx
— 168.82 Кб (Скачать файл)Таблица 13 Приведение матрицы расстояний для подмножества (6*,3*), матрица размерностью 4´4
i j |
3 |
4 |
5 |
6 |
di |
1 |
2 |
1 |
M |
0 |
0 |
3 |
M |
2 |
0 |
2 |
0 |
4 |
5 |
M |
1 |
0 |
0 |
6 |
M |
0 |
0 |
M |
0 |
dj |
2 |
0 |
0 |
0 |
2 |
Включение ребра (6,3) проводится путем исключения всех элементов 6-ой строки и 3-го столбца, в которой элемент d36 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 1
После операции приведения сокращенная матрица будет иметь вид: (Таблица 14)
Таблица 14 Сокращённая матрица размерностью 3´3
i j |
4 |
5 |
6 |
di |
1 |
1 |
M |
0 |
0 |
3 |
2 |
0 |
M |
0 |
4 |
M |
1 |
0 |
0 |
dj |
1 |
0 |
0 |
М |
Нижняя граница подмножества (6,3) равна:
H(6,3) = 8 + 1 = 9 ≤ 10
Чтобы исключить подциклы, запретим следующие переходы: (1,5),
Поскольку нижняя граница этого подмножества (6,3) меньше, чем подмножества (6*,3*), то ребро (6,3) включаем в маршрут с новой границей H = 9
Шаг №4. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 15)
Таблица 15 Определение ребра ветвления (6,3) матрица размерностью 3´3
i j |
4 |
5 |
6 |
di |
1 |
0(1) |
M |
0(0) |
0 |
3 |
1 |
0(2) |
M |
1 |
4 |
M |
1 |
0(1) |
1 |
dj |
1 |
1 |
0 |
М |
d(1,4) = 0 + 1 = 1; d(1,6) = 0 + 0 = 0; d(3,5) = 1 + 1 = 2; d(4,6) = 1 + 0 = 1;
Наибольшая сумма констант приведения равна (1 + 1) = 2 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 9 + 2 = 11
Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу. (Таблица 16)
Таблица 16 Приведение матрицы расстояний для подмножества (3*,5*) матрица размерностью 3´3
i j |
4 |
5 |
6 |
di |
1 |
0 |
M |
0 |
0 |
3 |
1 |
0 |
M |
1 |
4 |
M |
1 |
0 |
0 |
dj |
0 |
1 |
0 |
2 |
Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы: ∑di + ∑dj = 0
После операции приведения сокращенная матрица будет иметь вид: (Таблица 17)
Таблица 17 Сокращённая матрица размерностью 2´2
i j |
4 |
6 |
di |
1 |
0 |
М |
0 |
4 |
M |
0 |
0 |
dj |
0 |
0 |
0 |
Нижняя граница подмножества (3,5) равна:
H(3,5) = 9 + 0 = 9 ≤ 11
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 9
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,4) и (4,6).
Cmin = 2+1+2+2+1+1=9
Путь: (1,4); (4,6); (6;3); (3,5); (5,2); (2,1)
1→4→6→3→5→2→1
Оптимальный путь Дерево ветвлений (Приложение А).
3.2 Решение задачи коммивояжера венгерским методом.
Фирма по производству новогодних игрушек должна доставить заказ в 6 городов: Кирсанов (1); Котовск (2); Рассказово (3); Мичуринск (4) Инжавино (5); Уварово (6). Нужно найти кротчайший путь, объездив все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город 1.
Расстояния между городами заданы следующей матрицей. (Таблица 18)
Математическая модель:
Таблица 18 Исходная матрица размерностью 6´6
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
5 |
4 |
2 |
4 |
1 |
2 |
1 |
M |
2 |
4 |
5 |
7 |
3 |
7 |
5 |
M |
4 |
2 |
4 |
4 |
4 |
5 |
7 |
M |
2 |
1 |
5 |
2 |
1 |
4 |
7 |
M |
5 |
6 |
5 |
7 |
2 |
1 |
1 |
M |
Проводим редукцию матрицы по строкам, для чего в каждой строке находим минимальный элемент и вычитаем его из элементов этой же строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 19)
Таблица 19 Приведение матрицы по строкам, матрица размерностью 6´6
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
3 |
1 |
3 |
0 |
2 |
0 |
M |
1 |
3 |
4 |
6 |
3 |
5 |
3 |
M |
2 |
0 |
2 |
4 |
3 |
4 |
6 |
M |
1 |
0 |
5 |
1 |
0 |
3 |
6 |
M |
4 |
6 |
4 |
6 |
1 |
0 |
0 |
M |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент. (Таблица 20)
Таблица 20 Приведение матрицы по столбцам, матрица размерностью 6´6
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
2 |
1 |
3 |
0 |
2 |
0 |
M |
0 |
3 |
4 |
6 |
3 |
5 |
3 |
M |
2 |
0 |
2 |
4 |
3 |
4 |
5 |
M |
1 |
0 |
5 |
1 |
0 |
2 |
6 |
M |
4 |
6 |
4 |
6 |
0 |
0 |
0 |
M |