Град 14452 шифр 01. На территории города имеется три телефонных станции А, б и В. Незадействованные емкости станций составляют на станции а q
 Скачать 207.93 Kb.
|
|
Решение. Обозначим для удобства города А,Б,В,Г,Д,Е соответственно пунктами 1,2,3,4,5,6. Возьмем в качестве произвольного маршрута: X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1) Тогда F(X0) = 7+7+19+8+12=53. Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент. di = min(j) dij
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). Около каждого нуля в скобках записываем сумму минимальных констант по строке и столбцу.
Наибольшая сумма констант приведения равна (0+10) = 10 для ребра (5,4), следовательно, множество разбивается на два подмножества (5,4) и (5*,4*). Нижняя граница гамильтоновых циклов этого подмножества:
|