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

 (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