Програмне забезпечення ЕОМ

Міністерство освіти і науки України

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ  УНІВЕРСИТЕТ УКРАЇНИ

«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ  ІНСТИТУТ»

Кафедра прикладної математики

 

 

 

 

Задача маршрутизації

Курсовий проект з дисципліни

«Програмне  забезпечення ЕОМ»

 

 

 

 

 

Виконав Руцький О. С.                                                    Керівник Олефір О.С.

Група КМ-71 ФПМ

№ залікової книжки КМ-7312

Допущено до захисту___________

 

Захищено з оцінкою___________

 

«______»__________________2011 р.

 

 

 

 

 

Київ – 2011

Содержание

ВВЕДЕНИЕ …………………………………………………………..………......3

1.ПОСТАНОВКА ЗАДАЧИ……….…………………………………………….4

2.ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ……………………………………………...5

       2.1 Изучение математических методов решения задач...…...…………….5

       2.2 Метод ветвей и границ ………………………………………………… 6

       2.3 Метод динамического программирования…………………………….12          

3.ПРОЕКТИРОВАНИЕ АРХИТЕКТУРЫ РАЗРАБАТЫВАЕМЫХ     ПРОГРАММНЫХ СРЕДСТВ…………………………………………………..14

         3.1 Схема взаимодействия программ……………………………………..14

         3.2 Формат  исходных данных и результаты решения задачи…………..15

        3.3 Требования к программному изделию………………………….........16

         3.4 Требования к программной документации…..……………………....16

4. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ………………………………………...17

1. ЭКСПЕРИМЕНТАЛЬНЫЕ РАСЧЕТЫ……………………………………..20

   5.1 Контрольные примеры для решения на ЭВМ………………………..20

   5.2 Экспериментальные  расчеты………………………………………….28

ЗАКЛЮЧЕНИЕ………………………………………………………………….30

ЛИТЕРАТУРА…………………………………………………………………...31

ПРИЛОЖЕНИЕ………………………………………………………………….32

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Существует несколько  частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задача коммивояжера. Также существует обобщение задачи, так называемая обобщенная задача коммивояжера.

Общая постановка задачи, впрочем как и большинство  ее частных случаев, относится к  классу NP-сложных задач.

 

 

 

 

 

 

 

 

 

 

 

 

 

2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

2.1 Изучение математических методов решения задачи

Для решения задачи коммивояжера существуют такие методы:

• Полный перебор
• Случайный перебор
• Жадный алгоритм
• Метод ближайшего соседа
• Метод включения ближайшего города
• Метод самого дешевого включения
• Метод имитации отжига
• Метод минимального остовного дерева
• Метод ветвей и границ
• Метод генетических алгоритмов
• Алгоритм муравьиной колонии
• Алгоритм Дейкстры
• Метод отсекающих плоскостей
• Методы динамического программирования

Для решения задачи коммивояжера наиболее очевидным является метод полного перебора[2]. Осуществляется оценка всех возможных вариантов маршрута и выбор наиболее экономичного. Этот метод, безусловно, гарантирует получение абсолютного минимума, но требует чрезмерного количества вычислений. Необходимо рассматривать n! маршрутов для несимметричных задач и не менее n!/2 вариантов для симметричных. Это делает метод неприемлемым для использования уже при сравнительно небольшой размерности задачи. Однако он может быть полезен для проверки эффективности других методов.

Задачу коммивояжера можно рассматривать как задачу

 

 

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

Учитывая недостатки выше перечисленных методов, наиболее оптимальным является выбор метода ветвей и границ и метода динамического программирования. Подробно эти методы будут описаны далее.

 

2.2 Метод ветвей и границ

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

Общая идея тривиальна: нужно  разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь  возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Изложим алгоритм Литтла на примере: 

 

 

 

 

-	1	2	3	4	5	6
1	-	6	4	8	7	14
2	6	-	7	11	7	10
3	4	7	-	4	3	10
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 1

Нам будет удобнее трактовать С_ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то

прежний минимальный тур будет  и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из  j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

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

-	1	2	3	4	5	6
1	-	2	0	4	3	10	4
2	0	-	1	5	1	4	6
3	1	4	-	1	0	7	3
4	4	7	0	-	1	7	4
5	4	4	0	2	-	4	3
6	7	3	3	4	0	-	7
табл. 2

 

 

 

 

 

 

 

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

-	1	2		3		4		5	6
1	-	0		0		3		3	6
2	0	-		1		4		1	0
3	1	2		-		0		0	3
4	4	5		0		-		1	3
5	4	2		0		1		-	0
6	7	1		3		3		0	-
			2		1				4
табл. 3

 

 

 

 

 

 

                              

Прочерки по диагонали  означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.

Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы  С, например, такой, как показано на табл. 1. Подчеркивание элемента       означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На табл. 1 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.