Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
| x4x1, которую мы и выбираем для ветвления.
Матрица для подмножества дана следующей таблицей, для которой суммы постоянных приведения равна 5+17=22.
Конечно «перебор» не является оптимальной процедурой. Более приемлемым является соображение наличия «нулевой» дуги (в нашем случае x1x4 и x4x1). Матрица 2(x4x1) получается в результате следующих действий: исключаем строку А4 и столбец А1; исключаем противоположную дугу x1x4 заменой расстояния с14на «»; следим за тем, чтобы из ранее включенных в маршрут дуг и этой дуги не могли образовываться замкнутые контуры, не содержащие всех пунктов. После исключения строки А4 и столбца А1 получаем следующую матрицу:
Сумма постоянных приведения равна 18. На следующей схеме представлен результат ветвления. Большее значение нижней границы для 1 (97) по сравнению с нижней границей для 2 (93) позволяет надеяться, что в дальнейшем это множество будет отсечено. В качестве «более перспективного» выберем множество 2 и будем подвергать его ветвлению. После вычитания суммы 18 из чисел столбца А4 получим матрицу:
Нулевые дуги и сумма соответствующих постоянных приведения для данной матрицы будут следующими: x1x6 (59+9=68),x2x4 (0+9=9),x2x5 (0+4=4),x3x2 (4+15=19),x5x3 (0+9=9),x6x3 (16+0=16). Максимальной из всех сумм постоянных приведения равна 68, что соответствует дуге x1x6. Таким образом, множество 2 нужно разбить на два непересекающихся подмножества и 4(x1x6). Нижняя граница 3 равна сумме нижней границы 2 и 68, т.е. 93+68=161. Для получения нижней границы 4 нужно выполнить следующие действия: вычеркнем строку А1 и столбец А6; заменим элемент с64 на “”, так как если этого не сделать, то будет замкнутый контур x4→x1→x6→x4 в который не все вершины входят. В результате чего получим следующую матрицу расстояний для подмножества 4:
Как видно из матрицы, отличных от нуля постоянных приведения нет, поэтому нижняя граница 4 совпадает с нижней границей 2 и равна 93+0=93. Выбираем среди «нулевых» дуг дугу с максимальной суммой постоянных приведения: x2x4 (0+9=9),x2x5 (0+4=4),x3x2 (4+15=19),x5x3 (0+9=9)x6x3 (37+0=37). Это дуга x6x3. Нижняя граница для подмножества 5 равна 93+37=130 и ее дальнейшее ветвление под большим вопросом. Матрица 6 получается вычеркиванием строки А6 и столбца А3. Так как путь x4→x1→x6→x3 не должен превращаться в контур, то элемент с34 нужно заменить на «». В результате матрица 6 имеет вид:
Сумма постоянных приведения на данном этапе равна 9+0=9. Нижняя граница множества 6 будет равна 93+9=102. После вычитания числа 9 из строки А5 получим матрицу:
Рассматривая полученную матрицу 6 как множество для ветвления, выберем среди «нулевых» дуг дугу с максимальной суммой постоянных приведения: x2x4 (0+0=0),x2x5 (0+4=4),x3x2 (4+6=10),x5x4 (6+0=6). Это дуга x3x2. Множество 6 делится на два подмножества и 8(x3x2). Нижняя граница для 7 будет равна нижней границе для 6 плюс сумма постоянных приведения (10): 102+10=112. Чтобы получить матрицу 8 нужно вычеркнуть строку А3 и столбец А2 и вместо элемента с24 поставить прочерк “”:
Матрица 8 является приведенной, и поэтому нижние границы 8 и 6 совпадают и равны 102. Остается включить в маршрут единственно возможные дуги x2x5 и x5x4. Получаем замкнутый маршрут x4→x1→x6→x3→x2→x5→x4 с длиной пути l=102. Остается сделать последний шаг: проверка оптимальности решения. Для этого нужно сравнить длину полученного замкнутого маршрута (102) с нижними границами концевых множеств схемы ветвления: 112, 130, 161 и 97. В нашем случае существует множество 1 с меньшим значением длины 97<102. Применим схему ветвления к множеству 1. Так как матрица 1 не является приведенной, то вычтем из строки А4 число 17, а из столбца А1 число 5 и получим приведенную матрицу :
Нулевые дуги и сумма соответствующих постоянных приведения для данной матрицы будут следующими: жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|