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

Для исследования применяются стандартные методы теории устойчивости и теории бифуркаций, обзор которых дан в книге Г. Николиса и И.Пригожина (1979) и более подробно в монографии А. А. Андронова и др. (1959). Для систем малой размерности (n=1,2) аналитические методы разработаны столь хорошо, что нужда в численном анализе отпадает. Однако системы большей размерности таят в себе немало сюрпризов.

Дальнейшее  продвижение в понимании динамики моделируемых процессов связано  с исследованием полных нелинейных уравнений модели. Аналитические методы (теория ветвления решений нелинейных уравнений) позволяют исследовать мягкое и (или) жесткое возникновение новых режимов вблизи границы устойчивости. Вдали от границы устойчивости приходится использовать численные методы. Применяется многошаговый метод интегрирования типа Адамса, сеточные методы, методы разложения в ряды Фурье в сочетании с численным интегрированием.

Учет последействия  приводит к изучению уравнений с  запаздыванием, широко применяемых  в экологии (Колесов, Швитра). Дискретность процессов делает необходимым исследование разностных систем (Рорер).  

Краткое представление  методов, применяемых для построения моделей.

-Дифференциальные  уравнения. 

-Вариационное  исчисление.

-Клеточные  автоматы.

-Нейронные  сети.

-"Организменные"  модели.  

Историческое  моделирование.

В последнее  время при анализе социально-исторических процессов математическое моделирование  играет все более заметную роль.

Имеющиеся к  настоящему времени модели можно  условно разделить на три группы:

1) модели  – концепции, основанные на выявлении и анализе общих исторических закономерностей и представлении их в виде когнитивных схем, описывающих логические связи между различными факторами, влияющими на исторические процессы. Такие модели обладают высокой степенью обобщения, но имеют не математический, а чисто логический, концептуальный характер;

2) частные  математические модели имитационного  типа, посвященные описанию конкретных  исторических событий и. В подобных  моделях основное внимание уделяется  тщательному учету и описанию факторов и процессов, оказывающих влияние на рассматриваемые явления. Применимость таких моделей, как правило, ограничена достаточно узким пространственно-временным интервалом; они «привязаны» к конкретному историческому событию и их невозможно экстраполировать на протяженные периоды времени;

3) математические  модели, являющиеся промежуточными  между двумя указанными типами. Эти модели описывают некоторый  класс социальных процессов без  претензии на детальное описание  особенностей для каждого конкретно-исторического случая. Их задачей является выявление базовых закономерностей, характеризующих протекание процессов рассматриваемого вида. В соответствии с этим данные математические модели называются базовыми.  
 
 
 
 
 

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

1.1 Основные понятия  теории графов

Пусть задано некоторое непустое множество Х  множество, состоящее из пар элементов  множества X. Пары во множестве могут  повторяться, и также могут повторяться  элементы в парах. Множества Х  задают граф 0=(Х, Y).

Элементы  множества называют вершинами графа, элементы множества V — ребрами графа.

Если пары во множестве V повторяются, то граф С  называют псевдографом или графом с  кратными ребрами.

Если элементы в парах множества не упорядочены, то граф С называют неориентированным графом. Если они упорядочены, то граф О является ориентированным графом или орграфом, а элементы множества V называют дугами.

Графически  граф задается в виде точек и линий, их соединяющих.

Введем ряд  основных понятий для неориентированного графа. Ребро, начало и конец которого совпадают, называется петлей. Вершины называются смежными или соседними, если существует ребро, их соединяющее.

Если вершина  является началом или концом ребра, то вершина и ребро называются инцидентными.

Степенью  вершины называется число инцидентных ей ребер. Вершина, степень которой равна нулю, называется изолированной. Вершина, степень которой равна единице, называется висячей или тупиковой.

Маршрутом в  графе называется последовательность вершин и ребер, в которой конец предыдущего ребра совпадает с началом следующего), это не относится к первому и последнему ребру). Число ребер в маршруте определяет его длину.

Цепью называется маршрут, в котором все ребра  попарно различны.

Простой называется цепь, в которой все вершины попарно различны.

Циклом (простым  циклом) называется цепь (простая цепь), начало и конец которой совпадают.

Граф называется связным, если для любых двух его  вершин существует цепь, соединяющая  эти вершины.

Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей вершины.

Диаметром графа  называется максимальное расстояние между  его вершинами.

Деревом называется связный граф без циклов

Граф называется регулярным степени i, если все его  вершины имеют степень i.

Граф называется полным, если любые две его вершины соединены ребром. Лесом называется граф без циклов, т.е. совокупность деревьев.

Регулярный  граф, все вершины которого имеют  степень 1, называется паросочетанием. Граф называется двудольным, если множество его вершин X может быть разделено на два непересекающихся подмножества таким образом, что каждое ребро графа соединяет вершины из двух разных подмножеств.

Гамильтоновой цепью называется простая цепь, содержащая все вершины графа.

Гамильтоновым циклом называется простой цикл, содержащий все вершины графа.

В ориентированном  графе каждая дуга имеет направление, показанное стрелкой

Маршрут в  ориентированном графе часто  называют контуром, а цепь — путем.

1.2 Формулировка и  некоторые свойства  решений задачи  коммивояжера

Классическая  постановка задачи о коммивояжере выглядит следующим образом:

Имеется N городов, выезжая из исходного города А1, коммивояжер  должен побывать во всех городах по 1 разу и вернуться в город А1. Задача заключается в определении  последовательности объезда городов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время пути, суммарное расстояние и т.д.

Для расчета  затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.

Чтобы привести задачу к научному виду, введём некоторые  термины. Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j₁,j₂,..,j_n,j₁), причём все j₁..j_n — разные номера; повторяющийся в начале и в конце j₁, показывает, что перестановка зациклена. Расстояния между парами вершин С_ij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

Относительно  математизированной формулировки задачи коммивояжера уместно сделать два замечания.

Во-первых, в  постановке С_ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ:

С_ij³0; C_jj=∞

(последнее  равенство означает запрет на  петли в туре), симметричными,  т.е. для всех i,j:

С_ij= С_ji.

и удовлетворять  неравенству треугольника, т.е. для  всех:

С_ij+ С_jk³C_ik

1.3 Постановка задачи  коммивояжера как  задачи на графе

Задача коммивояжера может быть сформулирована как задача на графе в следующей постановке: построить граф G(X, A), вершины которого соответствуют городам в зоне коммивояжера, а дуги отображают коммуникации, соединяющие пары городов. Пусть длина a(х, у) > 0 каждой дуги (х, у) є А равна расстоянию, стоимости или времени. Контур, включающий каждую вершину графа G хотя бы один раз, называется маршрутом коммивояжера. Контур, включающий каждую вершину графа G ровно один раз, называется гамильтоновым контуром (по имени ирландского математика Вильяма Роуана Гамильтона, который в 1859 г. первым начал изучение этих задач).

Города —  это вершины графа.

Дороги между  городами — это ориентированные  ребра графа.

Длина соответствующей  дороги — это вес ребра.

Граф должен быть полным, т.е. в нем имеются  все возможные ребра. Если граф не является полным, то его можно дополнить  недостающими ребрами с весом =

Путь, который  требуется найти, - это ориентированный  оставный, простой цикл, минимального веса в графе. Такие циклы называются гамильтоновыми.

Оставным  циклом называется такой цикл, который  проходит через все вершины. Вес  цикла — это сумма веса всех ребер.

1.4 Метод ветвей и  границ

К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали  удачный алгоритм решения задачи коммивояжера и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения задачи коммивояжера было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.

Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу — в задаче минимизации, сверху — в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной. Нам будет удобнее трактовать С_ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма. Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным. Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, элементов матрицы С. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. Стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

Если в  ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров.