Задача коммивояжера

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ПЛАН

Введение

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

Решение задачи о коммивояжере методом ветвей и границ: основная схема

Решение задачи о коммивояжере методом ветвей и границ. Примеры

Практическое задание

Заключение

Список использованных источников

ВВЕДЕНИЕ

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

Наиболее ярким и характерным примером применения задачи "О коммивояжере" стала оптимизация операций на конвейере: в 1984 году, после того как был проведен анализ последовательности и временных затрат на операции на конвейерах заводов компании "General Motors" и приняты рекомендованные меры, удалось увеличить общую производительность почти на 13% при неизменном числе рабочих и том же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые в то время являлись одними из самых производительных систем в мире. Просчет и оптимизация 200 основных и 87 вспомогательных операций занял около 230 часов. Считается, что это было первое коммерческое применение компьютерных технологий в области управления производством в целом.

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

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

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

ПОСТАНОВКА ЗАДАЧИ

Пусть имеется п городов. Расстояния между любой парой городов (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 содержат только по одному элементу. Решением задачи является определение кольцевого маршрута минимальной длины.

РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА

Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум достигается.

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

Метод ветвей и границ - это один из методов организации полного перебора. Он применим не всегда, а только тогда, когда выполняются специфические дополнительные условия на множество M и минимизируемую на нем функцию. А именно, - предположим, что имеется вещественно-значная функция на множестве подмножеств множества M со следующими двумя свойствами:

1)для (здесь - множество, состоящее из единственного элемента );

2) если и , то .

В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так:

· разобьем множество M на части (любым способом) и выберем ту из его частей 1, на которой функция минимальна;

· затем разобьем на несколько частей множество 1 и выберем ту из его частей 2, на которой минимальна функция ;

· затем разобьем 2 на несколько частей и выберем ту из них, где минимальна , и так далее, пока не придем к какому-либо одноэлементному множеству .

Это одноэлементное множество называется рекордом. Функция , которой мы при этом выборе пользуемся, называется оценочной. Очевидно, что рекорд не обязан доставлять минимум функции f; однако, вот какая возможность возникает сократить перебор при благоприятных обстоятельствах.

Описанный выше процесс построения рекорда состоял из последовательных этапов, на каждом из которых фиксировалось несколько множеств и выбиралось затем одно из них. Пусть - подмножества множества M, возникшие на предпоследнем этапе построения рекорда, и пусть множество оказалось выбранным с помощью оценочной функции. Именно при разбиении и возник рекорд, который сейчас для определенности обозначим через . Согласно сказанному выше, , ; кроме того, по определению оценочной функции, .

Предположим, что ; тогда для любого элемента m множества M, принадлежащего множеству , будут верны неравенства ; это значит, что при полном переборе элементов из M элементы из уже вообще не надо рассматривать. Если же неравенство не будет выполнено, то все элементы из надо последовательно сравнить с найденным рекордом и как только отыщется элемент, дающий меньшее значение оптимизируемой функции, надо им заменить ре-корд и продолжить перебор. Последнее действие называется улучшением рекорда.

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

Мы рассмотрим сейчас первый из двух запланированных в этом курсе примеров применения метода ветвей и границ - решение задачи о коммивояжере. Вот ее формулировка: «Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей».

Формализуем условие в терминах теории графов. Города будут вершинами графа, а дороги между городами - ориентированными (направленными) ребрами графа, на каждом из которых задана весовая функция: вес ребра - это длина соответствующей дороги. Путь, который требуется найти, это - ориентированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется ориентированным, если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все возможные ребра); такие циклы называются также гамильтоновыми.

Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес , считая, что - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.

Отсюда следует, что задачу о коммивояжере достаточно решить для полных орграфов с весовой функцией. Сформулируем теперь это в окончательном виде: пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

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

Введем некоторые термины. Пусть имеется некоторая числовая матрица. Привести строку этой матрицы означает выделить в строке минимальный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте минимального элемента окажется ноль, а все остальные элементы будут неотрицательными. Аналогичный смысл имеют слова привести столбец матрицы.

Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам.

Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

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

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

Первый шаг. Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо непусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через , то сумму констант приведения матрицы весов обозначим через (). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M1; таким образом, итог первого шага: множеству всех обходов коммивояжера сопоставлено число () и матрица M1.

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

Сопоставим множеству следующую матрицу M1,1: в матрице M1 заменим на число в клетке . Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M1,1; только что запомненную сумму констант приведения прибавим к () и результат, обозначаемый в дальнейшем через (), сопоставим множеству .

Теперь множеству тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу () и полученное число, обозначаемое в дальнейшем через (), сопоставим множеству .

Теперь выберем между множествами и то, на котором минимальна функция (т.е. то из множеств, которому соответствует меньшее из чисел () и ().

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

К выбранному множеству с сопоставленными ему матрицей и числом повторим все то же самое и так далее, пока это возможно.

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

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ

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

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

Таблица 2

	1	2	3	4	5
1		9	8	4	10
2	6		4	5	7
3	5	3		6	2
4	1	7	2		8
5	2	4	5	2

Верхняя строка и левый столбец, выделенные затемненным фоном, содержат номера вершин графа; символ , стоящий на главной диагонали, означает, естественно, отсутствие ребер-петель (начинающихся и заканчивающихся в одной и той же вершине); кроме того, символ здесь и всюду в дальнейшем обозначает «компьютерную бесконечность», т.е. самое большое из возможных в рассмотрении чисел; считается, что + любое число =.

Подсчитаем () в нашем примере. Для этого выполним приведение матрицы весов; сначала - по строкам:

Таблица 3

	1	2	3	4	5
1		9	8	4	10	4	min в строке 1
2	6		4	5	7	4	min в строке 2
3	5	3		6	2	2	min в строке 3
4	1	7	2		8	1	min в строке 4
5	2	4	5	2		2	min в строке 5

результат приведения по строкам:

Таблица 4

	1	2	3	4	5
1		5	4	0	6
2	2		0	1	3
3	3	1		4	0
4	0	6	1		7
5	0	2	3	0

Определим константы приведения по столбцам:

Таблица 5

	1	2	3	4	5
1		5	4	0	6
2	2		0	1	3
3	3	1		4	0
4	0	6	1		7
5	0	2	3	0
	0	1	0	0	0
	min в столбце 1	min в столбце 2	min в столбце 3	min в столбце 4	min в столбце 5

результат приведения матрицы:

Таблица 6

	1	2	3	4	5
1		4	4	0	6
2	2		0	1	3
3	3	0		4	0
4	0	5	1		7
5	0	1	3	0

сумма констант приведения ()=4+4+2+1+2+1=14.

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

Таблица 7

	1	2	3	4	5
1		4	4	0(4)	6
2	2		0(2)	1	3
3	3	0(1)		4	0(3)
4	0(1)	5	1		7
5	0(0)	1	3	0(0)

Самым тяжелым оказывается нуль в клетке (1,4). Следовательно, множество разбивается на (все циклы, проходящие через ребро (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.

Для множества матрица такова:

Таблица 20

	1	2	5
2			1
3		0	0
5	0	1

Приведение этой матрицы дает:

Таблица 21

	1	2	5
2			0
3		0	0
5	0	1

Для оценочной функции: =17+1=18.

Получилось, что для дальнейшей разработки можно брать любое из множеств и . В первом случае уже получена матрица размером 22; ее нулевые клетки дают те ребра, которые с найденными ранее составляют обход коммивояжера, причем вес этого обхода равен значению оценочной функции - 18. Вот этот обход:

(1,4)(4,3)(2,1)(5,2)(3,5) или 143521.

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

При ином варианте выборов по ходу разбиений можно было получить другой оптимум: 143251.

ПРАКТИЧЕСКОЕ ЗАДАНИЕ

Требуется найти легчайший простой основный ориентированный цикл в полном взвешенном ориентированном графе на четырех вершинах (рис. 2):

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

Попробуем решить данную задачу методом «жадный алгоритм».

Из пункта 1 существует только один путь - путь к пункту 2, стоимость пути равна 78. Из пункта 2 существует только один путь - путь к пункту 3, стоимость пути равна 81. Из пункта 3 существует два пути - путь к пункту 1 и путь к пункту 4. Выберем самый кратчайший путь - это путь к пункту 4, стоимость пути равна 16. Из пункта 4 существует два пути - путь к пункту 1 и путь к пункту 2. Так как в пункте 2 мы уже были, то идем в пункт 1, стоимость пути равна 25.

Полный обход коммивояжера, исходя из предыдущего решения, равен 12341, а сумма пути равна: 78+81+16+25 = 200.

ЗАКЛЮЧЕНИЕ

задача коммивояжер граф моделирование

В данной курсовой работе был рассмотрен один из видов задач теории графов и сетевого моделирования «Задачу о коммивояжере».

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Фомин Г.П. Математические методы и модели в коммерческой деятельности. Учебник. - М.: Финансы и статистика, 2001 г.

2. Степочкина С.А. Курс лекций по вычислительной математике. - 2004 г.

Размещено на Allbest.ru