Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Лабораторная работа 11. Применение метода ветвей и границ к решению задачи о коммивояжере





 

Рассмотрим задачу, в которой матрица расстояний имеет вид:

C(0, 1)=

 

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

Решение.

Шаг 0. Приводим матрицу C(0, 1). Находим h(i) и вычитаем из c(i, j). Получим матрицу

 

C'(0, 1) =

 

Величины H(i) записаны в последей строке этой таблицы, вычитаем их из c'(i, j), получим следующую таблицу

 

C" (0, 1)=

 

Оценка x(0, 1)=21.

Строим дерево разбиения

x(0, 1)=21

Шаг 1.

Разбиваем множество X(0, 1) на подмножества X(1, 1), X(1, 2). В качестве пары (p, q) берем (2, 3). Для нее c" (2, 3)=0 и (min{c(2, j)|j¹ 3} + min{c(i, 3)| i¹ 2}) максимально. Для подмножества X(1, 1) из пункта 2 идти в пункт 3. Матрица расстояний будет иметь вид:

 

C(1, 1)=

 

Для запрета малых циклов запрещаем переход из пункта 3 в пункт 2, получаем

 

C(1, 1)=

 

Все коэффициенты приведения равны 0, поэтому С" (1, 1)=С(1, 1), x(1, 1)=x(0, 1)=21.

Для подмножества X(1, 2) из пункта 2 непосредственно идти в пункт 3 запрещается. Матрица расстояний будет иметь вид

C(1, 2)=

 

После приведения получим матрицу C(1, 2).

 

 

C(1, 2) =

При этом оценка иметь вид: x(1, 2)=21+5=26.

 

Достраиваем дерево разбиения

x (0, 1)=21

2 идти 3 2 не идти 3

x(1, 1)=21 x(1, 2)=26

 

 

Шаг 2. Минимальная оценка x(1, 1), поэтому разбиваем подмножество X(1, 1). В качестве пары (p, q), относительно которой проводим ветвление, используем пару (4, 5). Для подмножества X(2, 1)

 

C(2, 1=)

 

 

В этой матрице с целью запрета малых циклов запрещен перeход 5 ® 4. H(2)=3, поэтому x(2, 1)=21+3=24.

C" (2, 1)=

 

Для подмножества X(2, 2)

 

C(2, 2)=

 

 

После приведения получим

 

C”(2, 2)=

 

Оценка принимает вид: x(2, 2)=21+4=25.

Достраиваем дерево разбиения

 

x (0, 1)=21

2 идти 3 2 не идти 3

x (1, 1)=21 x (1, 2)=26

       
   
 
 


4 идти 5 4 не идти 5

x (2, 1)=24 x (2, 2)=25

 

Шаг 3. Минимальная оценка x(2, 1), поэтому разбиваем подмножество X(2, 1). В качестве пары (p, q), относительно которой проводим ветвление, используем пару (1, 0).

Подмножество X(3, 1):

 

C" (3, 1)=

При этом оценка равна x(3, 1)=26.

Подмножество X(3, 2):

C”(3, 2)=

Вычислим оценку x(3, 2)=28.

Дерево разбиения при этом примет вид

x (0, 1)=21

2 идти 3 не идти 3

x (1, 1)=21 x (1, 2)=26

 
 


4 идти 5 4 не идти 5

x (2, 1)=24 x (2, 2)=25

       
   
 
 


1 идти 0 1 не идти 0

x (3, 1)=26 x (3, 2)=28

 

Шаг 4. Минимальная оценка x(2, 2), поэтому разбиваем подмножество X(2, 2). В качестве пары (p, q), относительно которой проводим ветвление, используем пару (4, 2). После его выполнения дерево разбиения примет вид

 

 

x (0, 1)=21

2 идти 3 не идти 3

x (1, 1)=21 x (1, 2)=26


4 идти 5 4 не идти 5

x (2, 1)=24 x (2, 2)=25

           
   
   
 
 
 


1 идти 0 1 не идти 0 4 идти 2 4 не идти 2

x (3, 1)=26 x (3, 2)=28 x (3, 3)=25 x (3, 4)=28

На последующих шагах получим

x (0, 1)=21

2 идти 3 2 не идти 3

x (1, 1)=21 x (1, 2)=26

 
 


4 идти 5 не идти 5

x (2, 1)=24 x (2, 2)=25

           
   
   
 
 
 


1 идти 0 1 не идти 0 4 идти 2 4 не идти 2

x (3, 1)=26 x (3, 2)=28 x (3, 3)=25 x (3, 4)=28

 
 


5 идти 1 5 не идти 1

x (4, 1)=25 x (4, 2)=27

       
   
 
 


1 идти 0 1 не идти 0

x (5, 1)=26 x (5, 2)=29

 

 

Для подмножества X(5, 1) будем иметь:

 

C”(3, 2)

j i 4 5 h(i)
0 0 М  
3 M 0  
H(j)      

 

 

т.е. остаются переходы из 0 в 4, из 3 в 5. Эти переходы и переходы, выбранные при движении по дереву от вершины для подмножества X(5, 1) до вершины подмножества X(0, 1), получаем цикл 0 ® 4 ® 2 ® 3 ® 5 ® 1 ® 0, длина которого l=26. Так как все x(r, t) для концевых вершин дерева ³ 26, то этот цикл оптимальный.

Если требуется найти все оптимальные решения, то работу алгоритма необходимо продолжить, т.к. на подмножестве X(3, 1) оценка x(3, 1)=26 и на этом подмножестве могут быть оптимальные решения.

 







Дата добавления: 2014-12-06; просмотров: 585. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


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


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

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Броматометрия и бромометрия Броматометрический метод основан на окислении вос­становителей броматом калия в кислой среде...

Метод Фольгарда (роданометрия или тиоцианатометрия) Метод Фольгарда основан на применении в качестве осадителя титрованного раствора, содержащего роданид-ионы SCN...

Измерение следующих дефектов: ползун, выщербина, неравномерный прокат, равномерный прокат, кольцевая выработка, откол обода колеса, тонкий гребень, протёртость средней части оси Величину проката определяют с помощью вертикального движка 2 сухаря 3 шаблона 1 по кругу катания...

Неисправности автосцепки, с которыми запрещается постановка вагонов в поезд. Причины саморасцепов ЗАПРЕЩАЕТСЯ: постановка в поезда и следование в них вагонов, у которых автосцепное устройство имеет хотя бы одну из следующих неисправностей: - трещину в корпусе автосцепки, излом деталей механизма...

Понятие метода в психологии. Классификация методов психологии и их характеристика Метод – это путь, способ познания, посредством которого познается предмет науки (С...

Studopedia.info - Студопедия - 2014-2025 год . (0.011 сек.) русская версия | украинская версия