Математика (стр. 12 )

Матрица W2 не является приведенной. Проделаем операцию приведения этой матрицы. В ней всего одна положительная постоянная приведения, равная 18. Вычтем ее из элементов четвертого столбца матрицы W2 (то есть столбца А4) и получим матрицу (табл. 7).

	А2	А3	А4	А5	А6
А1	59	64	¾	61	0
А2	¾	5	0	0	81
А3	0	¾	44	4	9
А5	15	0	9	¾	55
А6	71	0	16	37	¾

Таблица 7 (матрица W02)

Нижняя граница j2 множества W2 будет на 18 больше нижней границы j множества W, то есть

j2 = j + 18 = 75 + 18 = 93

Схема ветвления будет иметь вид рис. 10.

W j = 75

W1 j1 = 97 W2 j2 = 93

х4х1 х4х1

Рис. 4

Первое применение общего шага, повторяемого многократно, закончено. Перейдем, в соответствии с алгоритмом, ко второму применению общего шага. Так как j2 = 93 < 97 = j1, то выберем в качестве «более перспективного» множество W2 и подвергнем его ветвлению. Дугу для ветвления выберем среди нулевых дуг матрицы W02(табл. 7): х1х6, х2х4, х2х5, х3х2, х5х3, х6х3. Исключение каждой дуги из маршрута (см. первое применение общего шага) приведет к увеличению нижней границы соответственно на 68, 9, 4, 19, 19 и 16. Максимальное повышение границы произойдет при исключении дуги х1х6. Произведем ветвление по этой дуге, разбив множество W2 на два непересекающихся подмножества: подмножество маршрутов W3 = W3(х1х6) не содержащих дугу х1х6, и подмножество маршрутов W4 = W4(х1х6), содержащих дугу х1х6. Нижняя граница j3 множества W3 = W3(х1х6) больше нижней границы j2 множества W2 на сумму постоянных приведения, равную 68, то есть

j3 = j2 + 68 = 93 + 68 = 161

Для получения нижней границы множества нужно преобразовать матрицу W02 следующим способом:

1) вычеркнуть первую строку и шестой столбец матрицы W02;

2) заменить прочерком “—“ один из элементов матрицы W02 , так как вводимая в маршрут на этом шаге дуга х1х6 вместе с дугой х4х1, введенной в маршрут на предыдущем шаге, образует путь х4 ® х1 ® х6, и для того, чтобы получился контур, проходящий ровно по одному разу через каждую вершину, следует поставить прочерк “—“ вместо элемента а64.

Проделав эти операции, получим матрицу W4 (табл. 8).

	А2	А3	А4	А5	min
А2	¾	5	0	0	0
А3	0	¾	44	4	0
А5	15	0	9	¾	0
А6	71	0	¾	37	0
min	0	0	0	0

Таблица 8 (матрица W4 = W04)

Матрица W4 является уже приведенной, так как для нее нет постоянных приведения, отличных от нуля. Следовательно, нижняя граница j4 множества W4 совпадает с нижней границей j2 множества W2, то есть

j4 = j2 + 0 = 93 + 0 = 93

Изобразим описанную схему ветвления на 11. Мы закончили второе применение общего шага. Перейдем к третьему применению общего шага, выбран для ветвления наиболее перспективное множество — множество W4.

W j = 75 W2 j2 = 93 W4 j4 = 93

х4х1 х1х6

j1 = 97 j3 = 161

W1 W3

x4х1 х1х6 Рис. 5

Как и прежде, дугу для ветвления выберем среди нулевых дуг матрицы W4 = W04 : х2х4, х2х5, х3х2, х5х3, х6х3. Исключение каждой дуги из маршрута (см. первое применение общего шага) приведет к увеличению нижней границы соответственно на 9, 4, 19, 9, 37. Максимальное повышение границы произойдет при исключения дуги х6х3. Произведем ветвление по этой дуге, разбив множество W4 на два непересекающихся подмножества: подмножество маршрутов W5 = W5(х6х3) не содержащих дугу х6х3, и подмножество маршрутов W6=W6 (х6х3), содержащих дугу х6х3. Нижняя граница j5 множества W5 = W5(х6х3) больше нижней границы j4 множества W4 на сумму постоянных приведения, равную 37, то есть

j5 = j4 + 37= 93+37 130.

для вычисления нижней границы множества W6 нужно:

1) вычеркнуть шестую строку и третий столбец матрицы W4=W04;

	А2	А4	А5	min
А2	¾	0	0	0
А3	0	¾	4	0
А5	15	9	¾	9
min	0	0	0

2) так как дуги х4х1, х1х6, х6х3 образуют путь х4 ® х1 ® х6 ® х3, то заменить элемент а34 матрицы W4 = W04 прочерком “—“. Проделав эти операции, получим матрицу W6 (табл. 9).

Таблица 9 (матрица W6)

Матрица W6 не является приведенной. Проделав операцию приведения описанным выше способом, получим матрицу W06 (табл. 10),

	А2	А4	А5
А2	¾	0	0
А3	0	¾	4
А5	6	0	¾

Таблица 10 (матрица W06)

причем нижняя граница j6 множества будет больше нижней границы j4 множества W4 на сумму постоянных приведения, равную 9, то есть

j6 = j4 + 9 = 93 + 9 = 102

Продолжив схему ветвления, получим рис.6

j=75 j2=93 j4=93 j6=102

W W2 W4 W6

х4х1 х1х6 х6х3

j1=97 j3=161 j5=130

W1 W3 W5

х4х1 х1х6 х6х3 Рис. 6

Для получения контура, проходящего через все пункты ровно по одному разу, рассмотрим ветвление множества б. Как и раньше, выберем в матрице дуги нулевой длины: х2х4, х2х5, х3х2, х5х4. Исключение каждой такой дуги из искомых маршрутов увеличивает нижнюю границу соответственyо на 0, 4, 10 и 6. Значит, по изложенной выше схеме, множество W6 следует разбить на два под множества: W7 = W7(х3х2), не содержащее дугу х3х2, и W8=W8(х3х2), содержащее эту дугу. Нижняя граница j7 множества будет

j7 = j6 + 10 = 102 + 10 = 112.

Для получения нижней границы множества из матрицы нужно вычеркнуть третью строку и второй столбец и вместо элемента а24 поставить прочерк “-”. Для множества W8 получим матрицу, задаваемую табл. 11

Таблица 11 (матрица W8=W08)

	А4	А5
А2	-	0
А5	0	-

Так как матрица W8 оказалась приведенной, то нижние границы множеств W8 и W6 совпадают, то есть j8 = j6 = 102. Схема ветвления при этом будет выглядеть следующим образом (рис. 6).

j = 75 j2 = 93 j4 = 93 j6 = 102 j8 = 102