Метод ветвей и границ (1021741), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Теперь множеству тоже сопоставим некую матрицу M_1,2. Для этого в матрице M₁ заменим на ¥ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M_1,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) Анализ подмножества D₁₂.

;

;

;

;

;

3) Анализ подмножества D₁₃.

;

;

;

;

4) Анализ подмножества D₁₄.

;

;

;

;

;

5) Анализ подмножества D₁₅.

;

;

;

;

;

6) Отсев неперспективных подмножеств.

;

Подмножества D₁₃ и D₁₅ неперспективные. Т.к. , но , то далее будем рассматривать подмножество D₁₄.

.

7) Анализ подмножества D₁₄₂.

;

;

;

;

;

8) Анализ подмножества D₁₄₃.

;

;

;

;

9) Анализ подмножества D₁₄₅.

;

;

;

;

;

10) Отсев неперспективных подмножеств

;

Подмножество D₁₄₃ неперспективное. Т.к. , но , то далее будем рассматривать подмножество D₁₄₅.

.

11) Анализ подмножества D₁₄₅₂.

;

;

;

;

;

12) Анализ подмножества D₁₄₅₃.

;

;

;

;

;

;

Оптимальное решение: .

.

Таким образом, маршрут студента: 12-ый корпус – Администрация – 5-ый корпус – Белый дом – КРК Премьер – 12-ый корпус.

Список литературы

1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. – Л.: Изд-во ЛГУ, 1981. -328 с.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. – М.: Наука, 1987. -294 с.

3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с

4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. – 2-е изд., перераб и доп. – М.: Высшая школа, 1980. -300 с.

5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. -213 с.

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

Характеристики

Список файлов лекций