Дискретная оптимизация - 7 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

7
ветвляемому множеству, для каждого нулевого элемента
k
ij
c вычисляется
число
k
lj
l
k
il
l
k
ccS
ij
minmin += . Затем определяется пара индексов
)
,
(
r
q
, такая
что
k
ij
ji
k
qr
SS
,
max= . Первое подмножество
1
k
Ω
формируется добавлением ус -
ловия 1
=
qr
x (из
−
q
го города идти в
−
r
й ), второе подмножество
2
k
Ω
со -
держит условие 0
=
qr
x .
2) Вычисление оценок . Пусть в соответствии с предыдущим пунктом произве-
дено разбиение
21
kkk
Ω
∪
Ω
=
Ω
. Рассмотрим правило перехода от матрицы
k
C к матрицам
1
k
C и
2
k
C . Матрица
2
k
C содержит те же строки и столбцы ,
что и
k
C . Положим
=∞+
≠
=
),(),(,
),,(),(,
rqji
rqjic
c
k
ij
k
ij
. Применяя к полученной мат-
рице
k
C процедуру приведения, получим матрицу
2
k
C
. При этом сумма
приводящих констант будет равна
k
qr
S . Таким образом, оценкой множества
2
k
Ω
будет
k
qrkk
S +Ω=Ω )()(
2
ξξ . Определим теперь правило построения мат-
рицы
1
k
C . По определению , множество
1
k
Ω
заведомо содержит переход из
−
q
го города в
−
r
й . Поэтому в матрице
1
k
C
следует вычеркнуть
q
-ю стро -
ку и
r
-й столбец . Далее следует запретить возможность возникновения
подциклов (замыкания фрагментов маршрута ). С этой целью полагаем рав-
ными
+
все элементы , введение которых в маршрут даст наличие подцик -
ла (например,
+∞
=
rq
c ). К полученной в результате матрице следует приме-
нить процесс приведения и, найдя сумму приводящих констант
S
, посчи -
тать оценку S
kk
+
Ω
=
Ω
)()(
1
ξ
ξ
.
Правило обхода дерева вариантов, выбор перспективного множества при ветв -
лении и проверка критерия оптимальности осуществляются в соответствии с
общей схемой метода ветвей и границ .
Схема работы метода ветвей и границ для задачи коммивояжера
Шаг 1. Определение начального рекорда. (При отсутствии дополнительной ин-
формации можно взять длину любого маршрута ). Приведение исходной матри -
цы . Задать k=0.
Шаг 2. Выбор пары
)
,
(
r
q
.
Шаг 3. Ветвление
21
kkk
Ω
∪
Ω
=
Ω
.
Шаг 4. Преобразование матрицы
k
C . Вычисление матриц
1
k
C и
2
k
C . Если ка-
кая- то из этих матриц имеет размер 2
×
2, то переход к шагу 7.
Шаг 5. Вычисление оценок )(
2
k
Ω
ξ
и )(
1
k
Ω
ξ
.
Шаг 6. Выбор перспективного множества
s
Ω
в соответствии со стратегией .
Положить
.
s
k
=
Переход к шагу 2. 
                                               7
   ветвляемому множеству, для каждого нулевого элемента cijk вычисляется
   число S ijk =min cilk +min cljk . Затем определяется пара индексов ( q, r ) , такая
                       l          l

   что   S qrk   =max S ijk   . Первое подмножество Ω k1 формируется добавлением ус-
                   i, j
   ловия xqr =1 (из q −го города идти в r −й), второе подмножество Ω k2 со-
   держит условие xqr =0 .
2) Вычисление оценок. Пусть в соответствии с предыдущим пунктом произве-
   дено разбиение Ω k =Ω k1 ∪ Ω k2 . Рассмотрим правило перехода от матрицы
   Ck к матрицам C k 1 и Ck2 . Матрица Ck2 содержит те же строки и столбцы,
                           �� cij , (i, j ) ≠( q, r ),
                                 k
   что и Ck . Положим    =�           cijk             . Применяя к полученной мат-
                             �� +∞, (i, j ) =( q, r )
   рице Ck процедуру приведения, получим матрицу Ck2 . При этом сумма
   приводящих констант будет равна S qrk . Таким образом, оценкой множества
   Ω k2 будет ξ (Ω k2 ) =ξ (Ω k ) +S qrk . Определим теперь правило построения мат-
   рицы C k 1 . По определению, множество Ω k1 заведомо содержит переход из
   q −го города в r −й. Поэтому в матрице C k 1 следует вычеркнуть q -ю стро-
   ку и r -й столбец. Далее следует запретить возможность возникновения
   подциклов (замыкания фрагментов маршрута). С этой целью полагаем рав-
   ными +∞ все элементы, введение которых в маршрут даст наличие подцик-
   ла (например, crq =+∞). К полученной в результате матрице следует приме-
   нить процесс приведения и, найдя сумму приводящих констант S , посчи-
   тать оценку ξ (Ω k1 ) =ξ (Ω k ) +S .
Правило обхода дерева вариантов, выбор перспективного множества при ветв-
лении и проверка критерия оптимальности осуществляются в соответствии с
общей схемой метода ветвей и границ.

     Схема работы метода ветвей и границ для задачи коммивояжера

Шаг 1. Определение начального рекорда. (При отсутствии дополнительной ин-
формации можно взять длину любого маршрута). Приведение исходной матри-
цы. Задать k=0.
Шаг 2. Выбор пары ( q, r ) .
Шаг 3. Ветвление Ω k =Ω k1 ∪ Ω k2 .
Шаг 4. Преобразование матрицы Ck . Вычисление матриц C k 1 и Ck2 . Если ка-
кая-то из этих матриц имеет размер 2 ×2, то переход к шагу 7.
Шаг 5. Вычисление оценок ξ (Ω k2 ) и ξ (Ω k1 ) .
Шаг 6. Выбор перспективного множества Ω s в соответствии со стратегией.
Положить k =s. Переход к шагу 2.

Страницы