Автор: Пользователь скрыл имя, 30 Марта 2011 в 19:18, курсовая работа
Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.
Введение_________________________________________________________2
Глава 1. Задача о коммивояжере_____________________________________3
Общая постановка задачи______________________________________3
Математическая модель задачи_______________________________3
Глава 2. Метод ветвей и границ____________________________________5
2.1. Основные понятия и определения_____________________________5
2.2. Постановка задачи_________________________________________5
2.3. Решение задачи методом ветвей и границ_______________________5
Глава 3. Программная реализация метода ветвей и границ_____________12
3.1. Язык программирования___________________________________12
3.2. Описание алгоритма_______________________________________12
3.3. Описание основных структур данных_________________________15
3.4. Описание интерфейса с пользователем________________________16
Заключение___________________________________________________17
Литература___________________________________________________18
Текст программы______________________________________________
Для
удобства изложения везде ниже в
платежной матрице заменим
Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r1=15, r2=1, r3=0, r4=16, r5=5, r6=5.
После
их вычитания по строкам получим:
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ∞ | 11 | 27 | 0 | 14 | 10 |
2 | 6 | ∞ | 15 | 0 | 29 | 24 |
3 | 20 | 13 | ∞ | 35 | 5 | 0 |
4 | 5 | 0 | 9 | ∞ | 2 | 2 |
5 | 7 | 41 | 22 | 43 | ∞ | 0 |
6 | 18 | 0 | 0 | 4 | 0 | ∞ |
Минимумы по столбцам: h1=5, h2=h3=h4=h5=h6.
После
их вычитания по столбцам получим
приведенную матрицу:
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ∞ | 11 | 27 | 0 | 14 | 10 |
2 | 1 | ∞ | 15 | 0 | 29 | 24 |
3 | 15 | 13 | ∞ | 35 | 5 | 0 |
4 | 0 | 0 | 9 | ∞ | 2 | 2 |
5 | 2 | 41 | 22 | 43 | ∞ | 0 |
6 | 13 | 0 | 0 | 4 | 0 | ∞ |
Найдем нижнюю границу φ(Z) = 15+1+0+16+5+5+5 = 47.
Для
выделения претендентов на включение
во множество дуг, по которым производится
ветвление, найдем степени Θij
нулевых элементов этой матрицы (суммы
минимумов по строке и столбцу). Θ14
= 10 + 0,
Θ24 = 1 + 0, Θ36
= 5+0, Θ41 = 0 + 1, Θ42
= 0 + 0, Θ56 = 2 + 0, Θ62
= 0 + 0,
Θ63 = 0 + 9, Θ65
= 0 + 2. Наибольшая степень Θ14
= 10. Ветвление проводим по дуге (1, 4).
Нижняя граница для множества остается равной 47. Для всех маршрутов множества из города A мы не перемещаемся в город D. В матрице это обозначается выставлением в ячейку (1, 4) знака ∞. В этом случае выход из города A добавляет к оценке нижней границы по крайней мере наименьший элемент первой строки. φ ( ) = 47 + 10.
В
матрице, соответствующей
полагаем c14= ∞.
1 | 2 | 3 | 4 | 5 | 6 | |
1 | ∞ | 11 | 27 | ∞ | 14 | 10 |
2 | 1 | ∞ | 15 | 0 | 29 | 24 |
3 | 15 | 13 | ∞ | 35 | 5 | 0 |
4 | 0 | 0 | 9 | ∞ | 2 | 2 |
5 | 2 | 41 | 22 | 43 | ∞ | 0 |
6 | 13 | 0 | 0 | 4 | 0 | ∞ |
После проведения процедуры приведения с r1=10 получим новую нижнюю границу 57 + 10 = 67.
В
матрице, соответствующей
, вычеркиваем первую строку и четвертый
столбец и положим c41= ∞, чтобы
предотвратить появления цикла 1→ 4 →
1. Получим новую платежную матрицу {c1ij}:
1 | 2 | 3 | 5 | 6 | |
2 | 1 | ∞ | 15 | 29 | 24 |
3 | 15 | 13 | ∞ | 5 | 0 |
4 | ∞ | 0 | 9 | 2 | 2 |
5 | 2 | 41 | 22 | ∞ | 0 |
6 | 13 | 0 | 0 | 0 | ∞ |
Для
приведения надо вычесть минимум
по первому столбцу: h1=1. При этом
нижняя граница станет равной 47+1 = 48. Сравнивая
нижние границы
φ (
) = 67 и φ (
) = 48 < 67 выделяем подмножество маршрутов
, которое с большей вероятностью содержит
маршрут минимальной длины.
Рис. 1. Ветвление на первом шаге
Приведенная платежная матрица для
1 | 2 | 3 | 5 | 6 | |
2 | 0 | ∞ | 15 | 29 | 24 |
3 | 14 | 13 | ∞ | 5 | 0 |
4 | ∞ | 0 | 9 | 2 | 2 |
5 | 1 | 41 | 22 | ∞ | 0 |
6 | 12 | 0 | 0 | 0 | ∞ |
Далее продолжаем процесс ветвления. Найдем степени Θij нулевых элементов этой матрицы Θ21 =16, Θ36 = 5, Θ42 = 2, Θ56 = 2, Θ62 = 0, Θ63 =9, Θ65 = 2. Наибольшая степень Θ21. Затем множество разбивается дуге (2, 1) на два новых и .
В
матрице для
вычеркиваем строку 2 и столбец 1. дуги
(1, 4) и (2, 1) образуют связный путь (2, 1, 4),
положим c42= ∞, чтобы предотвратить
появления цикла 2→1→ 4 → 2.
2 | 3 | 5 | 6 | |
3 | 13 | ∞ | 5 | 0 |
4 | ∞ | 9 | 2 | 2 |
5 | 41 | 22 | ∞ | 0 |
6 | 0 | 0 | 0 | ∞ |
Для приведения надо вычесть минимум по строке 4: r4=2. При этом нижняя граница станет равной 48+2 = 50.
Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ ( ) = 64 и φ ( ) = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .
Рис. 2.
Ветвление на втором шаге
Приведенная
платежная матрица для
2 | 3 | 5 | 6 | |
3 | 13 | ∞ | 5 | 0 |
4 | ∞ | 7 | 0 | 0 |
5 | 41 | 22 | ∞ | 0 |
6 | 0 | 0 | 0 | ∞ |
Степени Θij нулевых элементов этой матрицы Θ36 = 5, Θ45 = 0, Θ56 = 22, Θ62 = 13, Θ63 =7, Θ65 = 0. Наибольшая степень Θ56. Затем множество разбивается дуге (2, 1) на два новых и .
Нижняя
граница для
равна 50 + 22 = 72. В матрице для
вычеркиваем строку 5 и столбец 6 и
полагаем c65= ∞. Получим матрицу:
2 | 3 | 5 | |
3 | 13 | ∞ | 5 |
4 | ∞ | 7 | 0 |
6 | 0 | 0 | ∞ |
Для приведения надо вычесть минимум по строке 3: r3=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов .
Информация о работе Программная реализация метода ветвей и границ