Метод ветвей и границ (1021741), страница 3
Текст из файла (страница 3)
Теперь множеству тоже сопоставим некую матрицу M1,2. Для этого в матрице M1 заменим на ¥ число в клетке
и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M1,2. Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j(
), сопоставим множеству
.
Теперь выберем между множествами и
то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j(
) и j(
)).
Заметим теперь, что в проведенных рассуждениях использовался в качестве исходного только один фактический объект – приведенная матрица весов данного орграфа. По ней было выделено определенное ребро графа и были построены новые матрицы, к которым, конечно, можно все то же самое применить.
При каждом таком повторном применении будет фиксироваться очередное ребро графа. Условимся о следующем действии: перед тем, как в очередной матрице вычеркнуть строку и столбец, в ней надо заменить на ¥ числа во всех тех клетках, которые соответствуют ребрам, заведомо не принадлежащим тем гамильтоновым циклам, которые проходят через уже отобранные ранее ребра.
К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это возможно.
Доказывается, что в результате получится множество, состоящее из единственного обхода коммивояжера, вес которого равен очередному значению функции j; таким образом, оказываются выполненными все условия, обсуждавшиеся при описании метода ветвей и границ.
После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.
3.2 Условие задачи
Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротчайший путь. Расстояния между объектами даны в таблице
. | 12-ый корпус | Белый дом | КРК «Премьер» | Администрация | 5-ый корпус |
12-ый корпус | 0 | 6 | 4 | 5 | 2 |
Белый дом | 6 | 0 | 3 | 3,5 | 4,5 |
КРК «Премьер» | 4 | 3 | 0 | 5,5 | 5 |
Администрация | 5 | 3,5 | 5,5 | 0 | 2 |
5-ый корпус | 2 | 4,5 | 5 | 2 | 0 |
3.3 Математическая модель задачи
Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус – 1, Белый дом – 2, КРК «Премьер» – 3, Администрация – 4 и 5-ый корпус – 5. Соответственно общее количество пунктов . Далее введем
альтернативных переменных
, принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9).
(8)
(9)
Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и
дополнительных ограничений (10).
(10)
Суммарная протяженность маршрута F, которую необходимо минимизировать, запишется в следующем виде:
(11)
В нашем случае эти условия запишутся в следующем виде:
(8 а)
(9 а)
(10 а)
(11 а)
3.4 Решение задачи методом ветвей и границ
задача коммивояжер ветвь граница
1) Анализ множества D.
Найдем оценку снизу Н. Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).
=>
;
Аналогично определяем матрицу минимальных расстояний по столбцам.
=>
;
;
Выберем начальный план: . Тогда верхняя оценка:
. Очевидно, что
, где
означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.
2) Анализ подмножества D12.
;
;
;
;
;
3) Анализ подмножества D13.
;
;
;
;
4) Анализ подмножества D14.
;
;
;
;
;
5) Анализ подмножества D15.
;
;
;
;
;
6) Отсев неперспективных подмножеств.
;
Подмножества D13 и D15 неперспективные. Т.к. , но
, то далее будем рассматривать подмножество D14.
.
7) Анализ подмножества D142.
;
;
;
;
;
8) Анализ подмножества D143.
;
;
;
;
9) Анализ подмножества D145.
;
;
;
;
;
10) Отсев неперспективных подмножеств
;
Подмножество D143 неперспективное. Т.к. , но
, то далее будем рассматривать подмножество D145.
.
11) Анализ подмножества D1452.
;
;
;
;
;
12) Анализ подмножества D1453.
;
;
;
;
;
;
Оптимальное решение: .
.
Таким образом, маршрут студента: 12-ый корпус – Администрация – 5-ый корпус – Белый дом – КРК Премьер – 12-ый корпус.
Список литературы
-
Абрамов Л.А., Капустин В.Ф. Математическое программирование. – Л.: Изд-во ЛГУ, 1981. -328 с.
-
Алексеев О.Г. Комплексное применение методов дискретной оптимизации. – М.: Наука, 1987. -294 с.
-
Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с
-
Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. – 2-е изд., перераб и доп. – М.: Высшая школа, 1980. -300 с.
-
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. -213 с.
Размещено на Allbest.ru