Применение методов решения задачи коммивояжера на практике

 

Количество найденных нулей равно k = 6. В результате получаем эквивалентную матрицу Сэ. (Таблица 28)

Таблица 28 Эквивалентная матрица размерностью 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

 

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

Таблица 29 Определение матрицы назначения, матрица размерностью 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

 

Cmin = 2 + 1 + 2 + 1 + 1 + 2 = 9

Путь: (1;4), (4;6), (6;3), (3;5), (5;2), (2;1)

1→4→6→3→5→2→1

 

ЗАКЛЮЧЕНИЕ

 

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

Итак, теперь мы знаем, что сущность задачи коммивояжёра заключается в поиске оптимального маршрута с наименьшими финансовыми и временными издержками.

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

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

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

 

ГЛОССАРИЙ

 

Коммивояжер — разъездной сбытовой посредник.

Задача коммивояжера – задача математического программирования по определению оптимального маршрута движения коммивояжера, цель которого состоит в том, чтобы посетить все объекты, записанные в задании, за кратчайший срок и с наименьшими затратами.

Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

Гамильтонов путь (или гамильтонова цепь) – путь (цепь), содержащий каждую вершину графа ровно один раз.

Гамильтонов цикл - это гамильтонов путь, начальная и конечная вершины которого совпадают.

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

Целевая функция - это функция, минимум или максимум которой требуется найти.

Коммерция - это осуществление посреднической или торговой деятельности.

Редуцирование (приведение) матриц - это способ уменьшить размер расчетной модели для сокращения времени счета и затрат ресурсов.

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

 

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

 

1. Липатов Е.П. Теория графов и её применения / Е.П.Липатов. – Москва: Знание, 2008. - 258 с.;
2. Кузнецов Ю.Н. Математическое программирование: учебное пособие / Ю.Н.Кузнецов, В.И.Кузубов, А.Б.Волощенко. - Москва: Высшая школа, 2009. - 300 с.;
3. Маркова Е.В. Комбинаторные планы в задачах многофакторного эксперимента / Е.В.Маркова. – Москва: Наука, 2007. - 345 с.;
4. Бондарев В.М. Основы программирования / В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко. - Ростов-на-Дону: Феникс, 2011. - 468 с.;
5. Моисеев Н.Н. Методы оптимизации / Н.Н.Моисеев, Ю.П.Иванилова, Е.М.Столярова. – Москва: Высшая школа, 2009. - 352 с.;
6. Черноусько Ф.Л. Вариационные задачи механики и управления: Численные методы / Ф.Л.Черноусько, Н.В.Баничук. – Москва: Знание, 2011. - 125 с.;
7. Вентцель Е.С. Исследование операций: задачи, принципы, методология / У.С.Вентцель. - Москва: Высшая школа, 2009. – 208 с.;
8. Исследование операций в экономике / Под ред. Н.Ш.Кремера. – Москва: ЮНИТИ, 2011. – 407 с.;
9. Конюховский П.В. Математические методы исследования операций в экономике: краткий курс / П.В.Конюховский. – Санкт-Петербург: Питер, 2006. – 208 с.;
10. Просветов Г.И. Математические методы в экономике: учебно-методическое пособие / Г.И.Просветов. – Москва: Издательство РДЛ, 2009. – 160 с.;
11. Костевич Л.С. Математическое программирование: информационные технологии оптимальных решений / Л.С.Костевич. – Минск: Новое знание, 2007. – 424 с.;
12. Акулич И.Л. Математическое программирование в примерах и задачах / И.Л.Акулич. – Москва: Высшая школа, 2009. – 319 с.;
13. Оре О. Графы и их применение / О.Оре. – Москва: Мир, 2011. - 174 с.;
14. Акимов О.Е. Дискретная математика: логика, группы, графы / О.Е.Акимов. -  Москва: Лаборатория базовых знаний, 2010. - 376 с.;
15. Рэйнгольд Э. Комбинаторные алгоритмы: теория и практика / Э.Рэйнгольд, Ю.Нивергельт, Н.Део. - Москва: Мир, 2008. -548 с.;
16. Свами М. Графы, сети и алгоритмы / М.Свами. - Москва: Мир, 2008. – 429 с.;
17. Орлов А.И. Основы теории принятия решения / А.И.Орлов. – Москва: Высшая школа, 2011. - 249 с.;
18. Мудров В.И. Задача о коммивояжёре / В.И.Мудров. – Москва: Мир, 2009. – 364 с.

 

Приложение А

Дерево ветвлений

 

 

 

 

 

 

 

 

 

 

 

Рисунок А1 Дерево ветвлений методом ветвей и границ