Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Теория игр Задача о назначениях Поток сети
Транспортная задача Графический метод Решение дифф уравнений
Симплексный метод Двойственная задача Параметры сетевой модели

Задача кольцевого маршрута

Дана схема маршрутов между пунктами. Построить кольцевой маршрут объезда всех пунктов, чтобы длина маршрута была наименьшей и чтобы каждый из пунктов входил только один раз.
Решение.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 10 + 11 + 3 + 12 + 14 + 17 = 67
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij
i  j 1 2 3 4 5 6 di
1 M 10 5 9 16 8 5
2 6 M 11 8 18 19 6
3 7 13 M 3 4 14 3
4 5 9 6 M 12 17 5
5 5 4 11 6 M 14 4
6 17 7 12 13 16 M 7


Затем вычитаем diиз элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
i  j 1 2 3 4 5 6
1 M 5 0 4 11 3
2 0 M 5 2 12 13
3 4 10 M 0 1 11
4 0 4 1 M 7 12
5 1 0 7 2 M 10
6 10 0 5 6 9 M


Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
dj= min(i) dij
i  j 1 2 3 4 5 6
1 M 5 0 4 11 3
2 0 M 5 2 12 13
3 4 10 M 0 1 11
4 0 4 1 M 7 12
5 1 0 7 2 M 10
6 10 0 5 6 9 M
dj 0 0 0 0 1 3


После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины diи djназываются константами приведения.
i  j 1 2 3 4 5 6
1 M 5 0 4 10 0
2 0 M 5 2 11 10
3 4 10 M 0 0 8
4 0 4 1 M 6 9
5 1 0 7 2 M 7
6 10 0 5 6 8 M


Сумма констант приведения определяет нижнюю границу H:
H = ∑di+ ∑dj
H = 5+6+3+5+4+7+0+0+0+0+1+3 = 34
Элементы матрицы dijсоответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами dij>=0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением:
F(Mk) = ∑dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j 1 2 3 4 5 6 di
1 M 5 0(1) 4 10 0(7) 0
2 0(2) M 5 2 11 10 2
3 4 10 M 0(2) 0(6) 8 0
4 0(1) 4 1 M 6 9 1
5 1 0(1) 7 2 M 7 1
6 10 0(5) 5 6 8 M 5
dj 0 0 1 2 6 7 0


d(1,3) = 0 + 1 = 1; d(1,6) = 0 + 7 = 7; d(2,1) = 2 + 0 = 2; d(3,4) = 0 + 2 = 2; d(3,5) = 0 + 6 = 6; d(4,1) = 1 + 0 = 1; d(5,2) = 1 + 0 = 1; d(6,2) = 5 + 0 = 5;
Наибольшая сумма констант приведения равна (0 + 7) = 7 для ребра (1,6), следовательно, множество разбивается на два подмножества (1,6) и (1*,6*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(1*,6*) = 34 + 7 = 41
Исключение ребра (1,6) проводим путем замены элемента d16 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,6*), в результате получим редуцированную матрицу.
i  j 1 2 3 4 5 6 di
1 M 5 0 4 10 M 0
2 0 M 5 2 11 10 0
3 4 10 M 0 0 8 0
4 0 4 1 M 6 9 0
5 1 0 7 2 M 7 0
6 10 0 5 6 8 M 0
dj 0 0 0 0 0 7 7


Включение ребра (1,6) проводится путем исключения всех элементов 1-ой строки и 6-го столбца, в которой элемент d61заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 1
После операции приведения сокращенная матрица будет иметь вид:
i  j 1 2 3 4 5 di
2 0 M 5 2 11 0
3 4 10 M 0 0 0
4 0 4 1 M 6 0
5 1 0 7 2 M 0
6 M 0 5 6 8 0
dj 0 0 1 0 0 1


Нижняя граница подмножества (1,6) равна:
H(1,6) = 34 + 1 = 35  <  41
Поскольку нижняя граница этого подмножества (1,6) меньше, чем подмножества (1*,6*), то ребро (1,6) включаем в маршрут.
Шаг №2.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j 1 2 3 4 5 di
2 0(2) M 4 2 11 2
3 4 10 M 0(2) 0(6) 0
4 0(0) 4 0(4) M 6 0
5 1 0(1) 6 2 M 1
6 M 0(4) 4 6 8 4
dj 0 0 4 2 6 0


d(2,1) = 2 + 0 = 2; d(3,4) = 0 + 2 = 2; d(3,5) = 0 + 6 = 6; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,2) = 1 + 0 = 1; d(6,2) = 4 + 0 = 4;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 35 + 6 = 41
Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу.
i  j 1 2 3 4 5 di
2 0 M 4 2 11 0
3 4 10 M 0 M 0
4 0 4 0 M 6 0
5 1 0 6 2 M 0
6 M 0 4 6 8 0
dj 0 0 0 0 6 6


Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 2
После операции приведения сокращенная матрица будет иметь вид:
i  j 1 2 3 4 di
2 0 M 4 2 0
4 0 4 0 M 0
5 1 0 M 2 0
6 M 0 4 6 0
dj 0 0 0 2 2


Нижняя граница подмножества (3,5) равна:
H(3,5) = 35 + 2 = 37  <  41
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут.
Шаг №3.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j 1 2 3 4 di
2 0(0) M 4 0(0) 0
4 0(0) 4 0(4) M 0
5 1 0(0) M 0(0) 0
6 M 0(4) 4 4 4
dj 0 0 4 0 0


d(2,1) = 0 + 0 = 0; d(2,4) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 4 = 4; d(5,2) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0; d(6,2) = 4 + 0 = 4;
Наибольшая сумма констант приведения равна (0 + 4) = 4 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(4*,3*) = 37 + 4 = 41
Исключение ребра (4,3) проводим путем замены элемента d43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.
i  j 1 2 3 4 di
2 0 M 4 0 0
4 0 4 M M 0
5 1 0 M 0 0
6 M 0 4 4 0
dj 0 0 4 0 4


Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d34заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 0
После операции приведения сокращенная матрица будет иметь вид:
i  j 1 2 4 di
2 0 M 0 0
5 1 0 0 0
6 M 0 4 0
dj 0 0 0 0


Нижняя граница подмножества (4,3) равна:
H(4,3) = 37 + 0 = 37  <  41
Чтобы исключить подциклы, запретим следующие переходы: (5,4),
Поскольку нижняя граница этого подмножества (4,3) меньше, чем подмножества (4*,3*), то ребро (4,3) включаем в маршрут.
Шаг №4.
Определяем ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.
i  j 1 2 4 di
2 0(1) M 0(4) 0
5 1 0(1) M 1
6 M 0(4) 4 4
dj 1 0 4 0


d(2,1) = 0 + 1 = 1; d(2,4) = 0 + 4 = 4; d(5,2) = 1 + 0 = 1; d(6,2) = 4 + 0 = 4;
Наибольшая сумма констант приведения равна (0 + 4) = 4 для ребра (2,4), следовательно, множество разбивается на два подмножества (2,4) и (2*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,4*) = 37 + 4 = 41
Исключение ребра (2,4) проводим путем замены элемента d24 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,4*), в результате получим редуцированную матрицу.
i  j 1 2 4 di
2 0 M M 0
5 1 0 M 0
6 M 0 4 0
dj 0 0 4 4


Включение ребра (2,4) проводится путем исключения всех элементов 2-ой строки и 4-го столбца, в которой элемент d42заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
∑di+ ∑dj= 1
После операции приведения сокращенная матрица будет иметь вид:
i  j 1 2 di
5 1 0 0
6 M 0 0
dj 1 0 1

Нижняя граница подмножества (2,4) равна: H(2,4) = 37 + 1 = 38  <  41
Поскольку нижняя граница этого подмножества (2,4) меньше, чем подмножества (2*,4*), то ребро (2,4) включаем в маршрут.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (5,1) и (6,2).
В результате по дереву ветвлений гамильтонов цикл образуют ребра: (1,6), (6,2), (2,4), (4,3), (3,5), (5,1),
Длина маршрута равна F(Mk) = 38