Размещено на http://www.Allbest.Ru/

Введение

В данной курсовой работе рассматривается задача коммивояжера. Целью курсовой работы является решение задачи коммивояжера методом ветвей и границ.

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

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

Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.

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

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

Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i≠j. Если прямого маршрута сообщения между городами не существует, а также для всех i=j полагаем, что dij=∞. На этом основании расстояния между городами удобно представить в виде матрицы .

Рис. 1 - Неориентированный граф задачи коммивояжера

Если городам поставить в соответствие вершины графа (рис. 1), а соединяющим их дорогам дуги, то в терминах теории графов задача заключается в определении гамильтонова контура минимальной длины. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной, а длина контура определяется суммой длин всех дуг, входящих в контур. Таким образом, необходимо построить кольцевой маршрут проезда всех городов минимальной длины, начиная с любого пункта и в любую сторону.

Поскольку всего городов п, то коммивояжер, выехав из заданного города, должен побывать в остальных (n-1) городах только один раз. Следовательно, всего существует (n-1)! возможных маршрутов, среди которых один или несколько – оптимальные. В большинстве случаев можно предположить, что расстояние между городами i и j является симметричным и равно расстоянию от города j до города i, т.е. . Расстояния между городами запишем в виде соответствующей матрицы и обозначим ее через D. Если в задаче n городов, то D является матрицей размером с неотрицательными элементами , которые отображают длины дуг в сети городов. При n=5 количество возможных, вариантов маршрутов равно . Расстояния между городами заданы матрицей в табл. 1.

Таблица 1

i j	1	2	3	4	5
1	∞	90	80	40	100
2	60	∞	40	50	70
3	50	30	∞	60	20
4	10	70	20	∞	50
5	20	40	50	20	∞

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

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

Для любого допустимого маршрута каждая строка и каждый столбец матрицы расстояний D содержат только по одному элементу. Решением задачи является определение кольцевого маршрута минимальной длины.