ТОП 10:

Метод ветвей и границ для решения задачи о коммивояжере.



Пусть имеется (n+1)городов A0, A1, A2, A3,..., An. Между всеми парами городов известно расстояние ci,j³0. Коммивояжер, который находится в городе A0, должен обойти все города, побывав в каждом ровно один раз и вернуться в город A0 так, чтобы длина пройденного пути была наименьшей. Путь коммивояжера i0,i1,i2,...,in,i0 образует замкнутый маршрут. Его длина

l(i0,i1,i2,...,in,i0)=

Так как это задача на перестановках, то число таких маршрутов равно n!. Для поиска минимального (оптимального) маршрута применим метод ветвей и границ. Общая схема этого метода приведена в разделе «Комбинаторные методы решения задач целочисленного линейного программирования». Дадим описание этого метода для задачи о коммивояжере.

Алгоритм.

Шаг 1. Задание множества X0,1 и вычисление оценки x0,1.

Множество X0,1 есть множество всех возможных маршрутов коммивояжера. Оценку x0,1 получаем, используя процедуру приведения матрицы C0,1=C=(ci,j), i=1,2,3,…, n, j=1,2,3,…, n, следующим образом.

Для всех i=1,2,3,…, n, hi:=min{ci,j | j=1,2,3,…, n },

c'i,j := ci,j – hi, i=1,2,3,…, n, j=1,2,3,…, n.

Для всех j=1,2,3,…, n, Hj:=min{c'i,j | i=1,2,3,…, n },

c" i,j:= c' i,j – Hj, i=1,2,3,…, n, j=1,2,3,…, n.

Переменные hi, Hj называют коэффициентами приведения. Матрицу C"0,1=(c"i,j), i=1,2,3,…, n, j=1,2,3,…, n, называют приведенной матрицей.

Полагаем

Шаг 2 .Разбиение множества Xr,t на подмножества.

Пусть построено подмножество Xr,t и нижняя оценка функционала xr,t на нем. Этому подмножеству соответствует приведенная матрица C"r,t. Подмножество разбиваем на два: Xr+1,m+1, Xr+1,m+2, каждому из которых будут соответствовать свои оценки xr+1,m+1,xr+1,m+2 и приведенные матрицы С"r+1,m+1, С"r+1,m+2. Подмножество Xr+1,m+1получается из Xr,t добавлением условия: из пункта p непосредственно идти в пункт q. Подмножество Xr+1,m+2 получается добавлением условия: из пункта p непосредственно в пункт q идти запрещается. Пару (p,q) выбирают таким образом, чтобы с наибольшей вероятностью подмножество Xr+1,m+1содержало оптимальный цикл, а Xr+1,m+2 не содержало его. Для этого пару (p,q) выбирают таким образом, чтобы cp,q=0, при этом, чтобы величина min{cp,j| j¹q}+min{ci,q| i¹p} была максимальной, где cp,j, ci,q берутся из матрицы C"r,t

Шаг 3 . Преобразование матриц расстояний, пересчет оценок.

Матрицу C"r+1,m+2строим следующим образом. Полагаем Cr+1,m+2=Cr,t, в ней сp,q:=M, где M – достаточно большое число, принимаемое за бесконечность. Матрица C"r+1,m+2 получается из Cr+1,m+2 процедурой приведения. Для получения xr+1,m+2складываем xr,t с полученными коэффициентами приведения. Матрицу C"r+1,m+1 строим следующим образом. Полагаем Cr+1,m+1=Cr,t, и в ней вычеркиваем строку p и столбец q . Налагаем условие, иключающее образование малых циклов. Для этого восстанавливаем части маршрута, образованные непосредственными переходами в Xr+1,m+1. Если добавление любой пары (i, j) к этим маршрутам образует малый цикл, то в матрице Cr+1,m+1 ci,j:=–M. Матрица C"r+1,m+1 получается из Cr+1,m+1 процедурой приведения. Для получения xr+1,m+2 складываем xr,t с полученными коэффициентами приведения.

 

Пример.

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

C0,1 j  
hi
i M
M
M
M
M
M
    Hj  

 

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

Решение.

Шаг 0. Приводим матрицу C0,1. Находим hi и вычитаем из ci,j. Получим матрицу

C'0,1 j  
hi
i M
M
M
M
M
M
    Hj  

 

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


 

C"0,1 j  
hi
i M
M
M
M
M
M
x0,1=21
    Hj

 

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

Шаг 1.

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

C11 j  
hi
i M
M
M
M
 
    Hj  

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


 

C11 j  
hi
i M
M
M
M
M
 
    Hj  

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

Подмножество X1,2 получаем их подмножества X1,1 запретом перехода из пункта 2 непосредственно в пункт 3. Матрица расстояний будет иметь вид

C1,2 j  
hi
i M
M
M M
M
M
M
 
    Hj  

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

1,2 j  
hi
i M
M
M M
M
M
M
    Hj x1,2=26

При этом оценка получит значение: x1,2=21+5=26.

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

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

C21 j  
hi
i M
M
M
M
 
    Hj x2,1=24

В этой матрице с целью запрета малых циклов запрещен перeход из 5 в 4. H2=3,поэтому x2,1=21+3=24. Приведенная матрица будет иметь вид

  j  
C"2,1 hi
i M
M
M
M
 
    Hj  

 


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

    j    
C22 hi  
 
i M  
M  
M  
M M  
M  
   
    Hj    

 

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

    j    
C¢¢22 hi  
 
i M  
M  
M  
M M  
M  
   
    Hj x2,2=25  

Оценка принимает вид: x2,2=21+4=25. Достраиваем дерево разбиения


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

x3,4=28
x3,3=25

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

C¢¢51 hi  
 
i М  
M  
   
    Hj x 5,1=26  

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

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

Самостоятельная работа № 12.

Задание.Решить задачу коммивояжера для данных, приведенных в таблице (по вариантам)

    Вариант 1
    j
   
i
    Вариант 2
    j
   
i
    Вариант 3
    j
   
i
    Вариант 4
    j
   
i
    Вариант 5
    j
   
i
    Вариант 6
    j
   
i
    Вариант 7
    j
   
i
    Вариант 8
    j
   
i
    Вариант 9
    j
   
i
    Вариант 10
    j
   
i
    Вариант 11
    j
   
i
    Вариант 12
    j
   
i
    Вариант 13
    j
   
i
    Вариант 14
    j
   
i
    Вариант 15
    j
   
i
    Вариант 16
    j
   
i
    Вариант 17
    j
   
i
    Вариант 18
    j
   
i
                         

 

    Вариант 19
    j
   
i
    Вариант 20
    j
   
i
    Вариант 21
    j
   
i
    Вариант 22
    j
   
i
    Вариант 23
    j
   
i
    Вариант 24
    j
   
i
    Вариант 25
    j
   
i

 

    Вариант 26
    j
   
i
    Вариант 27
    j
   
i
    Вариант 28
    j
   
i
    Вариант 29
    j
   
i
    Вариант 30
    j
   
i

 


.







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.215.62.41 (0.017 с.)