4.3. Метод ВЕТВЕЙ И ГРАНИЦ
Метод ветвей (веток) и границ относится к группе комбинаторных методов дискретного программирования и является одним из наиболее распространенных методов этой группы.
Впервые метод ветвей и границ был предложен в работе Лэнд и Дойг в 1960 г. применительно к задаче линейного целочисленного программирования. Однако эта работа не оказала заметного влияния на развитие идей дискретного программирования. Второе рождение метода связано с работой Литтла, Мурти, Суини и Кэрел, 1963 г., посвященной задаче о коммивояжере.
Рассмотрим задачу дискретного программирования в общей форме
минимизировать z = f (x) (4.3.1)
при условиях
x Î G,
где G -конечное множество.
В основу метода ветвей и границ положены следующие построения, позволяющие в ряде случаев существенно уменьшить объем перебора вариантов [18].
Вычисление нижней границы (оценки) min z. Часто удается, не решая задачу (4.3.1), найти нижнюю границу (оценку) целевой функции на множестве решений G (или на его некотором подмножестве) x (G) такую, что для всех x Î X:
f (x) ³ x (G).
Разбиение на подмножества. Реализация метода связана с постоянным разбиением множества планов G на дерево подмножеств. Разбиение происходит по следующей схеме.
Нулевой шаг. Имеется исходное множество G = G(0). Некоторым способом его разбивают на конечное число подмножеств 
., 
...
k-ая итерация (k ³ 1). Пусть множества 
, ., 
еще не подвергались разбиению. По определенному правилу (указанному ниже), среди них выбирают множество 
и разбивают его на конечное число подмножеств (рис.4.3) 
, ., 
...
Перечисление оценок. Если G1 Ì G2, то 
Поэтому, разбивая в процессе решения множество на подмножества 
, всегда считают, что оценка для любого из них не меньше оценки для исходного множества G0, т.е. для всех множеств Gi
x (Gi) ³ x (G0)
Рис 4.3.
 |
Нахождение планов. Для конкретных задач могут быть указаны различные способы определения планов в последовательно разветвляемых подмножествах. Любой такой способ опирается на специфику задачи.
Признак оптимальности. Пусть 
и некоторый план x0 Î Gn . Если при этом f (x0) = x (Gn) £ x (Gi) для всех i, то x0 - оптимальный план.
Оценка точности приближенного решения. Пусть 
, 
. Если x - некоторый план задачи, то 
. Если разность D = f (x) - x невелика, то x можно принять за приближенное решение, а D будет оценкой его точности.
Описание алгоритма метода
Н у л е в о й ш а г. Не решая задачи (4.3.1), вычисляют оценку x (G) = x (G(0)). Если при этом удается найти такой план x0, что f (x0) = x (G(0)), то x0 - оптимальный план.
Если оптимальный план x0 не найден, то некоторым способом разбивают множество G(0) на конечное число непересекающихся подмножеств 
, 
, . ,
, таких, что G(0) = 
и переходят к первой итерации.
П е р в а я и т е р а ц и я. Вычисляют оценки x 
при i = 1, 2, . , r1... Если удается найти такой план x0, что x0 Î 
и 
при i = 1, 2, . , r1, то x0 - оптимальный план. В противном случае для дальнейшего разбиения выбирают наиболее перспективное множество 
по следующему правилу:
. (4.3.2.)
Разбивают множество на несколько подмножеств = 
. Еще не подвергавшиеся разбиению множества переобозначают 
и переходят ко второй итерации.
k-ая и т е р а ц и я. Вычисляют оценки x 
при i = 1, 2, . , rk... Если удается найти такой план x0, для которого 
для всех i = 1, 2, . , rk, то x0 -оптимальный план.
Если же оптимальный план не найден, то снова выбирают наиболее перспективное множество такое, что
. (4.3.3)
Далее разбивают множество на несколько подмножеств = 
и переходят к (k+1)-й итерации.
Примечание. При реализации описанной выше общей схемы метода ветвей и границ для отдельных задач дискретного программирования необходимо разрабатывать конкретные правила разбиения исходного множества, способы вычисления оценок и нахождение планов, исходя из специфики конкретных задач.
Метод ветвей и границ для задачи целочисленного программирования
Рассмотрим частично целочисленную задачу ЛП:
минимизировать z = f (x) = 
(4.3.4)
при условиях
(4.3.5)
0 £ xj £ dj, 
; (4.3.6)
xj - целое, (n1 < n). (4.3.7)
Как и в методе отсекающих плоскостей, процесс начинают с решения непрерывной задачи ЛП. Если полученный при этом оптимальный план x0 не удовлетворяет условию целочисленности (4.3.7), то значение целевой функции x0 = f (x0) дает нижнюю оценку (границу) для искомого решения, т.е. z = x0.
Пусть некоторая переменная 
не получила в плане x0 целочисленного значения. В целочисленном плане значение 
следует либо уменьшить, по крайней мере, до [
], либо увеличить, по крайней мере, до [ ] + 1.
Если границы изменения заранее не заданы, то их можно вычислить, решив для этого две вспомогательных задачи ЛП. Эти задачи состоят в минимизации и максимизации при условиях (4.3.5) и (4.3.6).
Далее решают задачу ЛП (4.3.4) - (4.3.6) с дополнительным ограничением 
или 
, где [ ] означает целую часть . Найденное оптимальное решение 
снова анализируют относительно выполнения условия целочисленности (4.3.7).
Этот процесс решения можно представить в виде дерева, в котором вершина 0 отвечает плану x0, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану следующей задачи: минимизировать z при условиях (4.3.5), (4.3.6) и дополнительном условии, что переменной дано значение 
или 
, где 
- целое число. Каждой из таких вершин приписывают оценку x = x( i0, k), которая равна min z при указанных выше ограничениях. Очевидно, x0 = x( i0, k) для всех k.
Если оптимальные планы полученных задач удовлетворяют условиям целочисленности, то план с минимальной оценкой 
и будет оптимальным планом исходной задачи. В противном случае возникает необходимость в продолжении ветвления. При этом каждый раз для очередного ветвления выбирают вершину с наименьшей оценкой.
Описание алгоритма
Нулевая итерация. 1. Определение множества G0. Множество определяется условиями (4.3.5), (4.3.6).
2. Находим оптимальный план x0 задачи (4.3.4) при условиях (4.3.5), (4.3.6).
3. Вычисляем оценку x (G0) = f (x0).
Если план x0 удовлетворяет условиям целочисленности, то он является искомым. В противном случае переходим к первой итерации.
Первая итерация. 1. Выбираем некоторую нецелочисленную компоненту 
. Множество G0 разбиваем на два непересекающегося подмножества , следующим образом:
(4.3.8)
(4.3.9)
2. Решаем задачу ЛП (4.3.4) на множестве и находим оптимальный план 
. Соответственно решаем задачу ЛП (4.3.4) на множестве и находим план 
.
3. Вычисляем оценки 
и 
.
Проверяем признак оптимальности.
Если 
- целочисленный и 
, то - искомый план. В противном случае переходим к следующей итерации и выполняем процедуру ветвления.
(k+1)-я итерация. Пусть проведено k итераций, в результате которых построены подмножества 
, определены оценки 
и еще не найдено оптимальное решение. Тогда выбираем наиболее перспективное подмнoжество такое, что
.
1. Разбиваем множество на подмножества 
, 
так, что = 
и 
. С этой целью выберем некоторую нецелочиселенную компоненту плана 
, например 
.
Тогда подмножества 
и 
определяются из условий
; (4.3.10)
.
2. Решаем задачу ЛП (4.3.4) на подмножествах , и находим оптимальные планы 
, 
и соответствующие им оценки x( ) = f ( ); x( ) = f ( ).
3. Если удовлетворяет условию целочисленности, то вершина - концевая и дальнейшему разбиению не подвергается. Если при этом также x ( ) = 
, где {
} - множество всех висячих вершин, то - искомый целочисленный план (это признак оптимальности). В противном случае необходимо продолжить процесс ветвления и дальше.
Укажем некоторые особенности применения метода ветвей и границ для задачи ЛЦП.
1. Если все коэффициенты cj целевой функции - целые при 1 £ j £ n1 и равны нулю при j > n1 , то оценку x ( ) можно заменить на более 'сильную' оценку x/ ( ) = 
, где знаком 
обозначено наименьшее целое, но не меньшее, чем a (т.е. ≥ a).
2. Из описания алгоритма следует, что в применении метода ветвей и границ для полностью и частично целочисленных задач нет никакой разницы.
3. Вводимые на каждой итерации новые ограничения вида 
или 
играют роль правильных отсечений по аналогии с методом отсекающих плоскостей.
4. При вводе нового ограничения нет необходимости заново решать всю задачу (4.3.4), а можно использовать результаты предыдущей итерации, непосредственно вводя в симплекс-таблицу оптимального решения предыдущей задачи новое ограничение.
5. При решении задачи ЛП максимизации методом ветвей и границ используют верхнюю границу/оценку
.
В этом случае признак оптимальности формулируется противоположным образом по сравнению с задачей min f (x).
Пример 4.3. Рассмотрим пример 4.2, решенный методом Гомори. В эквивалентной форме записи эта задача имеет вид
минимизировать - (x1 + x2) (1)
при условиях
£ 7; (2)
£ 5;
³ 0, (3)
- целые числа. (4)
Н у л е в о й ш а г. Оптимальный план задачи ЛП 
.Тогда имеем оценку 
.
Так как план 
не удовлетворяет условию целочисленности, возьмем его нецелочисленную компоненту 
и разобьем множество 
на 
и 
:
;
.
П е р в ы й ш а г. Решаем две задачи ЛП, состоящие в минимизации исходной задачи по множествам 
и 
. Покажем, как можно найти min f (x) при x 
, где = G0
. Для этого воспользуемся таблицей оптимального плана (табл.4.9).
Таблица 4.9
|
|
1 |
1 |
0 |
0 |
0 |
|||
|
|
|
|
|
|
|
|
||
|
1 |
|
40/9 |
1 |
0 |
0 |
5/9 |
1/9 |
|
|
0 |
|
1 |
0 |
0 |
1 |
-6 |
1 |
|
|
1 |
|
23/9 |
0 |
1 |
0 |
4/9 |
-1/9 |
|
|
? |
|
7 |
0 |
0 |
0 |
1 |
0 |
Необходимо ввести в систему новое ограничение £ 4. Запишем его в эквивалентном виде: +
= 4. Допишем строку 
к табл.4.9 и приходим к табл.4.10.
Таблица 4.10
|
|
|
|
|
|
|
|
|
|
|
|
|
40/9 |
1 |
0 |
0 |
5/9 |
1/9 |
0 |
||
|
|
1 |
0 |
0 |
1 |
-6 |
1 |
0 |
||
|
|
23/9 |
0 |
1 |
0 |
4/9 |
-1/9 |
0 |
||
|
|
4 |
1 |
0 |
0 |
0 |
0 |
1 |
||
|
? |
|
-4/9 |
0 |
0 |
0 |
-5/9 |
-1/9 |
1 |
Так как столбец 
должен быть базисным (в табл.4.10), то, вычтя из элементов строки элементы строки , получим строку 
, которую и используем в дальнейших итерациях.
Обратим внимание, что строка представляет собой правильное отсечение Гомори, составленное по строке .
Так как 
< 0, то строка 
табл.4.10 представляет собой псевдоплан и потому применим двойственный симплекс-метод. Так как табл. 4.10 совпадает с табл.4.1, то спустя две итерации найдем оптимальный план 
, который приведен в табл.4.3 (см. пример 4.2).
Таким образом,
.
Найдем теперь min f (x) на множестве 
. Использовав свободную переменную x7, ограничение ³ 5 запишем в виде -
= 5, или
- + = - 5.
Запишем его в дополнительную строку 
табл. 4.11, основная часть которой совпадает с табл.4.9. Чтобы снова привести столбец к единичному виду, сложим с , получим строку 
(см. табл.4.11).
Таблица 4.11
|
|
|
|
|
|
|
|
|
|
|
|
|
40/9 |
1 |
0 |
0 |
5/9 |
1/9 |
0 |
||
|
|
1 |
0 |
0 |
1 |
-6 |
1 |
0 |
||
|
|
23/9 |
0 |
1 |
0 |
4/9 |
-1/9 |
0 |
||
|
|
-5 |
-1 |
0 |
0 |
0 |
0 |
1 |
||
|
? |
|
-5/9 |
0 |
0 |
0 |
5/9 |
1/9 |
1 |
Проанализируем эту строку.
Так как 
, а 
для всех 
, то это есть признак неразрешимости данной задачи. Следовательно, 
, и поэтому 
.
Разобьем множество на 
и 
, где 
Обозначим 
.
В т о р о й ш а г . Решим две задачи ЛП, состоящие в минимизации исходной задачи на множествах , . В результате получим
.
Разобьем множество на подмножества 
, 
. 
, где
Обозначим 
Т р е т и й ш а г. Решаем две задачи ЛП, состоящие в минимизации исходной задачи по подмножествах и . Находим 
= [3; 2], 
; 
Ø, 
∞; 
, 
;
. Итак, получен целочисленный план = [3, 2], причем
План = [3, 2] - оптимальный, поскольку 
. Значение целевой функции 
= -5.
 |
Дерево решений приведено на рис. 4.4.
Рис. 4.4.
 |
На рис. 4.5 приведены графический способ решения задачи, а также графическая иллюстрация влияния вводимых дополнительных ограничений на допустимое множество решений.
Рис. 4.5.
Метод ветвей и границ для задачи о коммивояжере
Постановка задачи. Имеется n городов А1, А2, . , Аn, связанных транспортной сетью. Задана матрица расстояний С = 
, причем в общем случае cij ¹ cji.
Коммивояжер начинает двигаться, например, из города А1, должен побывать в каждом городе только один раз и возвратиться в исходный город А1. Необходимо отыскать такой замкнутый маршрут, или цикл (i1, i2, . , in), проходящий через каждый город один раз, при котором минимизируется суммарная (общая) длина пути:
l(i1, i2, . , in) = 
... (4.3.12)
Описание алгоритма. 1. Определение множества G(0), которое состоит из всех циклов (замкнутых маршрутов).
2. Определение подмножеств 
, каждое из которых состоит из всех циклов, подчиненных одному из следующих дополнительных условий:
а) из пункта i следует идти непосредственно в пункт j для всех пар (i, j), входящих в некоторое множество 
.
б) из пункта i запрещается идти непосредственно в пункт j для всех пар (i, j), входящих в некоторое множество "запретов" 
.
3. Вычисление оценки для G(0). Рассмотрим некоторый цикл i1, i2, . , in... Соответствующее ему расстояние равняется
l(i1, i2, . , in) = ... (4.3.13)
Пусть 
. Тогда 
.
Далее, пусть min
. Тогда 
, и
l(i1, i2, . , in) = 
... (4.3.14)
Описанную выше процедуру преобразования матрицы, позволяющую из исходной неотрицательной матрицы С получить матрицу С², называют приведением, а величину
(4.3.15)
суммой приводящих констант.
Имеет место следущая теорема [18].
Теорема 4.3. Оптимальный план задачи о коммивояжере с матрицей С² является оптимальным и для задачи с матрицей С. При этом длина маршрута (цикла) l(i1, i2, . , in), соответствующего матрице С, и длина маршрута l² для матрицы С² связаны соотношением
l(i1, i2, . , in) = l² (i1, i2, . , in) + x(G(0)), (4...3.16)
где x(G(0)) = hå .
Доказательство теоремы вытекает непосредственно из соотношения (4.3.14).
4. Ветвление. Каждой вершине множества дерева решений будет соответствовать своя оценка x( ) и своя приведенная матрица . Множество разбивают на два подмножества. Для этого по некоторому способу (указанному ниже) выбирают пару пунктов (r, m), не входящую в множества и . После этого производят ветвление на подмножества , так, что
.
Здесь получается с введением дополнительного условия: из пункта r осуществить непосредственный переход в пункт m, а - из условия: из пункта r запрещен непосредственный переход в пункт m.
Следовательно,
Выбор пары (r , m) основан на следующих соображениях. Подмножество выбирают так, чтобы оно с наибольшей вероятностью содержало оптимальный цикл, а - наоборот: не содержало.
Чтобы выполнить первое требование, пару (r , m) нужно выбрать так, чтобы выполнялось условие
, (4.3.17)
где 
- (r , m)-й элемент приведенной матрицы 
. Чтобы выполнить другое требование, пару (r , m) необходимо выбрать таким образом, чтобы циклам, входящим в множество 
, соответствовали как можно более длинные пути. По определению множества , для любого цикла путь из пункта r в пункт m может содержать такие переходы: из r в некоторый промежуточный пункт j (j ¹ m) и из некоторого пункта i (i ¹ r) в пункт m. Длина этого пути будет не меньше, чем
. (4.3.18)
Итак, остается выбрать пару (r, m) так, чтобы q (r, m) было максимально, т.е.
q (r, m) = 
, (4.3.19)
где 
При этом, конечно, необходимо выполнение условия
(4.3.20)
5. Вычисление оценок. Рассмотрим ветвление . Сначала рассмотрим подмножество и укажем правило перехода от матрицы 
к 
.
Матрица содержит те же строки и столбцы, что и матрица . Строим некоторую промежуточную матрицу 
по правилу
Применив к процедуру приведения, получают . При этом сумма приводящих констант равна q (r, m). Таким образом,
x ( ) = x ( ) + q (r , m). (4.3.21)
Теперь рассмотрим множество и определим правило перехода от матрицы к 
.
Так как, по определению, подмножество содержит непосредственный переход из пункта r в пункт m, то при переходе от к надо вычеркнуть строку r и столбец m.
В результате получают 
.
Далее, необходимо проверить, не состоит точно из одного цикла. Если это так, то к матрице применяют процедуру приведения. Получив суму приводящих констант 
, пересчитывают оценку
x ( ) = x ( ) + hå . (4.3.22)
При этом значение x ( ) будет равно длине этого единственного цикла.
Если подмножество содержит более одного цикла, то следует запретить возможность образования подциклов (т.е. частичных циклов), проходящих через количество пунктов меньше n. Для этого необходимо найти все маршруты, которые включают переход (r, m).
Процесс запрещения образования подциклов выполняют следующим образом.
Прежде всего возможен подцикл (r, m, r). Его исключают путем запрета перехода (m, r). Для этого принимают 
.
Если из элементов можно составить маршрут (i1, i2, . , ip, r), то возможны подциклы вида (iq, iq+1, . , ip, r, m, iq), где 1 £ q £ p. Запрещают эти подциклы, полагая 
. Аналогичным образом, если из элементов множества можно составить маршрут (m, i1, i2, . , ip), то возможны подциклы вида (r, m, i1, . , ip, r)... Чтобы их исключить, запрещают переходы (iq, r). Для этого считают 
, 1 £ q £ p. Все остальные элементы матрицы остаются без изменений. Далее к матрице применяют процедуру приведения и находят матрицу . Обозначим через 
соответствующую сумму приводящих констант. Тогда оценки x ( ) вычисляют по формуле
x ( ) = x ( ) + 
. (4.3.23)
Пример 4.4. Решить задачу о коммивояжере, определяемую матрицей С (табл.4.12).
Таблица 4.12
|
i j |
0 |
1 |
2 |
3 |
4 |
5 |
|
|
0 |
X |
4 |
10 |
13 |
4 |
8 |
|
|
1 |
2 |
X |
9 |
7 |
6 |
7 |
|
|
C = |
2 |
8 |
5 |
X |
5 |
5 |
9 |
|
3 |
5 |
8 |
5 |
X |
7 |
10 |
|
|
4 |
6 |
4 |
4 |
9 |
X |
4 |
|
|
5 |
5 |
1 |
4 |
8 |
3 |
X |
Н у л е в о й ш а г . Применив процедуру приведения, получим матрицу С0 (табл.4.13).
Таблица 4.13
|
|
i j |
0 |
1 |
2 |
3 |
4 |
5 |
hi |
ai |
|
0 |
X |
0 |
6 |
9 |
0 |
4 |
4 |
0 |
|
|
1 |
0 |
X |
7 |
5 |
4 |
5 |
2 |
4 |
|
|
2 |
3 |
0 |
X |
0 |
0 |
4 |
5 |
0 |
|
|
3 |
0 |
3 |
0 |
X |
2 |
5 |
5 |
0 |
|
|
4 |
2 |
0 |
0 |
5 |
X |
0 |
4 |
0 |
|
|
5 |
4 |
0 |
3 |
7 |
2 |
X |
1 |
2 |
|
|
Hj |
0 |
0 |
0 |
0 |
0 |
0 |
|||
|
bj |
0 |
0 |
0 |
5 |
0 |
4 |
Находим оценку
x (G(0)) = 
.
Затем вычисляют величины 
и 
: = 
; = 
, где - наименьший элемент строки i0 , отличный от 
= 0; аналогично - наименьший элемент столбца j0 , отличный от элемента .
Поскольку 
=
+
= 5; 
=
+
= 4; 
=
+
= 4, 
{
} = max { ; ; } = 5 = q (2, 3), то выбираем для первого разбиения пару (2;3) (
(2;3)=0).
П е р в ы й ш а г. Проводим ветвление
, где подмножество - такое, что = {(2; 3)}, а 
.
Вычисляем оценку x (
= x (G0) + = 21 + 5 = 26. Для вычисления x (
необходимо построить матрицу 
. Для этого в матрице 
вычеркиваем вторую строку и третий столбец и, полагая элемент 
= ¥, осуществляем процедуру приведения. В результате получаем матрицу (табл.4.14).
Таблица 4.14
|
|
i j |
0 |
1 |
2 |
4 |
5 |
hi |
ai |
|
0 |
X |
0 |
6 |
0 |
4 |
0 |
0 |
|
|
1 |
0 |
X |
7 |
4 |
5 |
0 |
4 |
|
|
3 |
0 |
3 |
X |
2 |
5 |
0 |
2 |
|
|
4 |
2 |
0 |
0 |
X |
0 |
0 |
0 |
|
|
5 |
4 |
0 |
3 |
2 |
X |
0 |
2 |
|
|
Hj |
0 |
0 |
0 |
0 |
0 |
|||
|
bj |
0 |
0 |
3 |
2 |
4 |
Найдя 
,, определим оценку для множества : x (
= x (G0) +
= 21.
Поскольку x ( < x ( , то на следующем шаге разбиваем подмножество .
В т о р о й ш а г . По матрице выбираем пару (4;5), по которой производим дальнейшее ветвление, так как
(4;5) = 0, а q (4, 5) = 4 = 
. Разобьем множество на подмножества , , 
так, что 
. Вычисляем оценку x (
= x (G
) + q (4;5) = 21 + 4 = 25. Затем строим матрицу 
. Для этого в матрице вычеркиваем четвертую строку и пятый столбец, и, полагая
= ¥, выполняем процедуру приведения. Получим матрицу 
(табл.4.15).
Таблица 4.15
|
|
i j |
0 |
1 |
2 |
4 |
hi |
ai |
|
0 |
X |
0 |
3 |
0 |
0 |
0 |
|
|
1 |
0 |
X |
4 |
4 |
0 |
4 |
|
|
3 |
0 |
3 |
X |
2 |
0 |
2 |
|
|
5 |
4 |
0 |
0 |
X |
0 |
0 |
|
|
Hj |
0 |
0 |
3 |
0 |
|||
|
bj |
0 |
0 |
3 |
0 |
Находим 
. Тогда x (
= x (G
) + 
= 21 + 3 = 24. Так как x ( < x ( , то для дальнейшего разбиения выберем множество .
Т р е т и й ш а г. На этом шаге выберем для разбиения пару (1;0) в матрице , так как q(1;0) = 4 = max q (p, q) (табл.4.15).
Производим ветвление
, где 
и вычисляем оценку x(
= x(G
) + q (1,0) = 24 + 4 = 28.
Построим матрицу 
(табл.4.16) и найдя 
= 2, вычислим оценку x(G
) = 24 + 2 = 26.
Таблица 4.16
|
|
i j |
1 |
2 |
4 |
hi |
ai |
|
0 |
X |
3 |
0 |
0 |
3 |
|
|
3 |
1 |
X |
0 |
2 |
1 |
|
|
5 |
0 |
0 |
X |
0 |
0 |
|
|
Hj |
0 |
0 |
0 |
|||
|
bj |
1 |
3 |
0 |
Так как x (
> x ( ,то далее разбиваем подмножество .
Ч е т в е р т ы й ш а г . Прежде всего построим матрицу 
. Для этого в матрице полагаем 
= ¥. Выполним процедуру приведения (табл.4.17). При этом
x ( = x (G
) + 
= 21 + 4 =25.
Таблица 4.17
|
|
i j |
0 |
1 |
2 |
4 |
5 |
hi |
ai |
|
0 |
X |
0 |
6 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
X |
7 |
4 |
1 |
0 |
1 |
|
|
3 |
0 |
3 |
X |
2 |
1 |
0 |
1 |
|
|
4 |
2 |
0 |
0 |
X |
¥ |
0 |
0 |
|
|
5 |
4 |
0 |
3 |
2 |
X |
0 |
2 |
|
|
Hj |
0 |
0 |
0 |
0 |
4 |
|||
|
bj |
0 |
0 |
3 |
2 |
1 |
В матрице выберем пару (4;2). Производим разбиение на подмножества 
и 
, где 
x (
= x( ) + q (4, 2) = 25 + 3 = 28.
Вычислим оценку x (
. Для этого в матрице вычеркнем четвертую строку и второй столбец, полагая c34 = ¥ и, выполнив процедуру приведения, получим матрицу 
(табл.4.18). Поскольку 
, то x ( = x ( = 25.
Таблица 4.18
|
|
i j |
0 |
1 |
4 |
5 |
hi |
ai |
|
0 |
X |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
X |
4 |
1 |
0 |
1 |
|
|
3 |
0 |
3 |
X |
1 |
0 |
1 |
|
|
5 |
4 |
0 |
2 |
X |
0 |
2 |
|
|
Hj |
0 |
0 |
0 |
0 |
|||
|
bj |
0 |
0 |
2 |
1 |
На следующем шаге разбиваем подмножество , потому что x ( < x (
.
П я т ы й ш а г. Выбираем пару (5;1) в матрице . Проводим разбиения на подмножества 
,
так, что 
x(
= x(G
) + q (5;1) = 25 + 2 = 27. Далее строим матрицу 
. Так как
, то x(
= x(G ) = 25 (табл.4.19).
Таблица 4.19
|
|
i j |
0 |
4 |
5 |
hi |
ai |
|
0 |
X |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
4 |
X |
0 |
4 |
|
|
3 |
0 |
X |
1 |
0 |
1 |
|
|
Hj |
0 |
0 |
0 |
|||
|
bj |
0 |
4 |
1 |
x( ≤ x(G
), поэтому далее разбиваем подмножество .
Ш е с т о й ш а г. В матрице выберем очередную пару (1;0), так как q (1;0) = 4 =
= max q ( p, q). Разобьем на подмножества 
,
так, что 
. Найдем оценку x (
= x( + q (1;0) = 25 + 4 = 29.
Таблица 4.20
|
|
i j |
4 |
5 |
hi |
ai |
|
0 |
0 |
X |
0 |
- |
|
|
3 |
X |
0 |
1 |
- |
|
|
Hj |
0 |
0 |
|||
|
bj |
- |
- |
Рис. 4.6. Рис. 4.7.
Затем строим матрицу 
(табл.4.20). Для этого в матрице вычеркиваем соответствующие строку и столбец и после приведения образованной подматрицы получаем :
x (
= x (G
) + 
= 25 + 1 = 26.
Из матрицы выбираем две последние пары (0;4) и (3;5). В результате получим цикл, отвечающий подмножеству 
= {(2;3); (4;2); (5;1); (1;0); (0;4); (3;5)}. Длина этого цикла равна оценке для множества : l = x (
= 26. В этом можно убедиться непосредственной проверкой. Оценка x (является наименьшей среди оценок для всех висячих вершин дерева решений (рис.4.6), следовательно, найден оптимальный цикл. Процесс построения дерева решений приведен на рис.4.6, а найденный минимальный цикл - на рис.4.7.
