Динамическое программирование
Теория игр
Задача о назначениях
Поток сети
Транспортная задача
Параметры сетевой модели
Решение дифф уравнений
Симплексный метод
Двойственная задача
Графический метод
Новое на сайте
Задачи параметрического программирования
Критерий Манна-Уитни
Интервалы возрастания и убывания функции
Коэффициент контингенции
Коэффициент конкордации
Смешанное произведение векторов
Метод Фибоначчи

Решение задачи коммивояжера

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.

Назначение сервиса. С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом.

Инструкция. Выберите размерность матрицы (количество городов). Полученное онлайн решение сохраняется в файле Word и Excel (см. примеры решений задачи коммивояжера).

Количество городов

Методы решения задачи коммивояжера

  1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ;
  2. венгерский метод. Пример решения венгерским методом.

Пример. В качестве начального маршрута выбирается любой, например, X0 = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1). Оценка для этого маршрута равна F(X0) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Для определения нижней границы множества используют операцию редукции, для чего в каждой строке матрицы D находят минимальный элемент: di = min(j) dij

i j123456 di
1 M 43 39 38 22 9 9
2 72 M 65 57 52 70 52
3 13 74 M 73 59 39 13
4 81 87 86 M 22 17 17
5 89 33 65 15 M 8 8
6 80 30 10 30 18 M 10

Затем вычитают di из элементов рассматриваемой строки. Поэтому во вновь полученной матрице в каждой строке будет как минимум один ноль.
i j123456
1 M 34 30 29 13 0
2 20 M 13 5 0 18
3 0 61 M 60 46 26
4 64 70 69 M 5 0
5 81 25 57 7 M 0
6 70 20 0 20 8 M

Такую же операцию редукции проводят по столбцам: dj = min(i) dij
i j123456
1 M 34 30 29 13 0
2 20 M 13 5 0 18
3 0 61 M 60 46 26
4 64 70 69 M 5 0
5 81 25 57 7 M 0
6 70 20 0 20 8 M
dj 0 20 0 5 0 0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
i j123456
1 M 14 30 24 13 0
2 20 M 13 0 0 18
3 0 41 M 55 46 26
4 64 50 69 M 5 0
5 81 5 57 2 M 0
6 70 0 0 15 8 M

Сумма констант приведения определяет нижнюю границу H = ∑di + ∑dj = 9+52+13+17+8+10+0+20+0+5+0+0 = 134. Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j. Длина маршрута определяется выражением: F(Mk) = ∑dij. Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.

Затем в ходе последующих итераций, определяется ребро ветвлений. Все множество маршрутов относительно этого ребра разбивается на два подмножества (i,j) и (i*,j*).

Все права защищены и охраняются законом. Copyright © ООО Новый семестр 2006-2013 Решение задач онлайн