Применение методов решения задачи коммивояжера на практике
Автор работы: Пользователь скрыл имя, 16 Апреля 2014 в 17:25, курсовая работа
Краткое описание
В современном мире происходит стремительное развитие науки и техники. С каждым годом число предприятий по производству различного рода продукции становится всё больше и больше. Но чтобы предприятие успешно развивалось и приносило прибыль, нужно взвешивать все плюсы и минусы не только вопросов касающихся затрат на закупку сырья и оборудования, но и вопросов связанных с транспортировкой груза к месту реализации, с нахождением оптимального маршрута и минимизацией затрат.
Именно задача коммивояжера помогает найти кратчайший путь с минимальными затратами.
Содержание
Введение…………………………………………………………………..…...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 Кб (Скачать файл)
После вычитания минимальных элементов получаем полностью редуцированную матрицу. Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 6). Другие нули в строке 1 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5)
Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5)
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5)
В итоге получаем следующую матрицу. (Таблица 21)
Таблица 21 Поиск допустимого решения, матрица размерностью 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 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 3), то решение недопустимое.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 6, столбец 6, строку 2, столбец 2, строку 3. Получаем сокращенную матрицу (элементы выделены). (Таблица 22)
Таблица 22 Сокращённая матрица размерностью 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 |
Минимальный элемент сокращенной матрицы (min(M, 2, 1, 3, 3, 5, M, 1, 1, 2, 6, M) =1) вычитаем из всех ее элементов. (Таблица 23)
Таблица 23 Вычитание минимального элемента сокращённой матрицы размерностью 6´6 из всех её элементов
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
1 |
0 |
2 |
0 |
2 |
0 |
M |
0 |
3 |
4 |
6 |
Продолжение таблицы 23 Вычитание минимального элемента сокращённой матрицы размерностью 6´6 из всех её элементов
3 |
5 |
3 |
M |
2 |
0 |
2 |
4 |
2 |
4 |
4 |
M |
0 |
0 |
5 |
0 |
0 |
1 |
5 |
M |
4 |
6 |
4 |
6 |
0 |
0 |
0 |
M |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов. (Таблица 24)
Таблица 24 Суммирование минимального элемента с элементами на пересечениях вычеркнутых строк и столбцов, матрица размерностью 6´6
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
1 |
0 |
2 |
0 |
2 |
0 |
M |
0 |
3 |
4 |
7 |
3 |
5 |
4 |
M |
2 |
0 |
3 |
4 |
2 |
4 |
4 |
M |
0 |
0 |
5 |
0 |
0 |
1 |
5 |
M |
4 |
6 |
4 |
7 |
0 |
0 |
0 |
M |
Проводим редукцию матрицы по строкам.
В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 25)
Таблица 25 Приведение матрицы размерностью 6´6 по строкам
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
1 |
0 |
2 |
0 |
2 |
0 |
M |
0 |
3 |
4 |
7 |
3 |
5 |
4 |
M |
2 |
0 |
3 |
4 |
2 |
4 |
4 |
M |
0 |
0 |
5 |
0 |
0 |
1 |
5 |
M |
4 |
6 |
4 |
7 |
0 |
0 |
0 |
M |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент. (Таблица 26)
Таблица 26 Приведение матрицы размерностью 6´6 по столбцам
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
1 |
0 |
2 |
0 |
2 |
0 |
M |
0 |
3 |
4 |
7 |
3 |
5 |
4 |
M |
2 |
0 |
3 |
4 |
2 |
4 |
4 |
M |
0 |
0 |
5 |
0 |
0 |
1 |
5 |
M |
4 |
6 |
4 |
7 |
0 |
0 |
0 |
M |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 1 и столбце 4 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 6). Другие нули в строке 4 и столбце 6 вычеркиваем.
Фиксируем нулевое значение в клетке (5, 2). Другие нули в строке 5 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (6, 3). Другие нули в строке 6 и столбце 3 вычеркиваем.
В итоге получаем следующую матрицу. (Таблица 27)
Таблица 27 Поиск допустимого решения, матрица размерностью 6´6
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
M |
4 |
1 |
[0] |
2 |
[-0-] |
2 |
[0] |
M |
[-0-] |
3 |
4 |
7 |
3 |
5 |
4 |
M |
2 |
[0] |
3 |
Продолжение таблицы 27 Поиск допустимого решения, матрица размерностью 6´6
4 |
2 |
4 |
4 |
M |
[-0-] |
[0] |
5 |
[-0-] |
[0] |
1 |
5 |
M |
4 |
6 |
4 |
7 |
[0] |
[-0-] |
[-0-] |
M |