xixj и всё множество маршрутов разбивается на два подмножества: подмножество маршрутов 2, содержащих дугу xixj и подмножество 1, не содержащих дугу xixj.
Множество 1 получается из множества исключением маршрутов, содержащих дугу xixj. Исключать дугу мы будем в матрице расстояний замещением расстояния cij символом “”. Дуга для ветвления выбирается так, чтобы нижняя граница множества 1(xixj) была, по возможности, большой, т.е. чтобы при исключении этой дуги была большей сумма возникающих при этом постоянных приведения. Положительные постоянные приведения возникают лишь в том случае, когда в одном из соответствующих рядов xixj матрицы расстояний нет нулевых элементов.
Дугами ветвления могут быть дуги, для которых расстояние равно нулю. В нашем случае дугами ветвления могут быть x1x4 (9+18=18),x1x6 (0+9=9),x2x5 (5+4=9),x3x2 (4+15=19),x4x1 (17+5=22),x5x3 (15+0=15),x6x3 (5+0-5). В скобках указаны суммы постоянных приведения соответствующих нулевых расстояний. Очевидно, что дугой с максимальной суммой является
Достарыңызбен бөлісу: |
