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

Задача коммивояжера в коммерческой деятельности

В коммерческой деятельности коммерсанты, торговые агенты постоянно проводят работу по поиску партнеров или клиентов для заключения договоров на поставку и покупку товаров. Для решения этих задач коммерсантам необходимо выезжать в командировки, выполнять вояж по целой сети городов как по нашей стране, так и за рубежом. Поскольку продолжительность командировки и транспортные расходы следует сокращать, то необходимо перед поездкой составить кратчайший маршрут, предусматривающий посещение каждого пункта только один раз, и возвращение обратно. Задача коммивояжера заключается в определении такой последовательности объезда городов, которая обеспечит минимальное время переезда, или минимальную стоимость проезда, или минимальное расстояние переезда.
Постановка задачи. Пусть имеется n городов. Расстояния между любой парой городов (i, j) известны и составляют dij где i=1,m; j=1,n, Если прямого маршрута сообщения между городами не существует, а также для всех i =j полагаем, что dij = ∞. На этом основании расстояния между городами удобно представить в виде матрицы D = (dij)nxn. Если городам поставить в соответствие вершины графа, а соединяющим их дорогам ребра, то в терминах теории графов задача заключается в определении гамильтонова цикла минимальной длины. Гамильтонов цикл включает все вершины графа ровно один раз, причем начальная вершина совпадает с конечной, а длина определяется суммой длин всех ребер. Таким образом, необходимо построить кольцевой маршрут проезда всех городов минимальной длины, начиная с любого пункта и в любую сторону.
Поскольку всего городов п, то коммивояжер, выехав из заданного города, должен побывать в остальных (n-1) городах только один раз. Следовательно, всего существует (n-1)! возможных маршрутов, среди которых один или несколько — оптимальные. В большинстве случаев можно предположить, что расстояние между городами i и j является симметричным и равно расстоянию от города j до города i, т. е. dij = dji. Расстояния между городами запишем в виде матрицы D. Если в задаче n городов, то D является матрицей размером (nхn) с неотрицательными элементами dij ≥0, которые отображают длины ребер в сети городов. Так, при n = 5 количество возможных вариантов маршрутов равно (5-1)! = 24.

Использование задачи коммивояжера в жилищно-коммунальном хозяйстве

Задача коммивояжера (или задача кольцевого маршрута) используется в тех случаях, когда необходимо с совершить обход некоторых объектов с минимальными затратами. Затраты в этом случае могут выражаться как в стоимостном выражении (рубли), так и временном (часы). Особенностью решения задачи коммивояжера является кольцевое движение по определнному маршруту с посещением каждого пункта только один раз. Например, если необходимо посетить 5 объектов, то начать можно с любого из них, но обход будет совершаться последовательно. В коммунальном хозяйстве использовать решение задачи коммивояжера могут службы обслуживания населения, там, где необходимо совершать обход населения: опломбирование счетчиков воды, текущие ремонты и др. В этом случае минимизировать можно будет как стоимостные затраты, временные, или комбинированные.

Рассмотрим пример решения задачи коммивояжера с помощью калькулятора.
Возьмем в качестве произвольного маршрута:
X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)
Тогда F(X0) = 13 + 13 + 12 + 19 + 6 + 14 = 77
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент.
di = min(j) dij

i  j 1 2 3 4 5 6 di
1 M 13 8 5 10 10 5
2 21 M 13 10 16 11 10
3 7 14 M 12 15 14 7
4 6 10 10 M 19 6 6
5 9 13 14 16 M 6 6
6 14 10 14 7 6 M 6


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


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


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


Сумма констант приведения определяет нижнюю границу H:
H = ∑di+ ∑dj
H = 5+10+7+6+6+6+0+4+3+0+0+0 = 47
Элементы матрицы 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 4 0(0) 0(0) 5 5 0
2 11 M 0(0) 0(0) 6 1 0
3 0(3) 3 M 5 8 7 3
4 0(0) 0(0) 1 M 13 0(0) 0
5 3 3 5 10 M 0(3) 3
6 8 0(0) 5 1 0(5) M 0
dj 0 0 0 0 5 0 0


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


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


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


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


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


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


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


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


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


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


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

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

Перейти к онлайн решению своей задачи

Фомин г. П. Математические методы и модели в коммерческой деятельности: Учебник. — 2-е изд., перераб. и доп. — М.: Финансы и статистика, 2005. — 616 с: ил.