Метод ветвей и границ для задачи коммивояжера

Министерство  образования и науки Российской Федерации

Южно-Уральский государственный  университет

Механико-математический факультет

Кафедра прикладной математики

 

 

 

 

 

 

Курсовая  работа

По дисциплине «Дискретная оптимизация»

Тема: «Метод ветвей и границ для задачи коммивояжера»

 

 

 

 

 

 

Выполнила студентка группы ММ-440

__________ Басалаева  Н.Н.

«___» __________ 2013 г.

Проверил

__________ Эвнин А.Ю.

«___» __________ 2013 г.

 

 

 

 

Челябинск, 2013

Содержание

1.Постановка задачи………………………………………………….....	3
Математические основы решения задачи коммивояжера
Формулировка и некоторые свойства решений задачи коммивояжера…………………………………………………………….…… Постановка задачи коммивояжера как задачи на графе...…………………………………………..……………………………….	4   6
Постановка и описание алгоритма решения задачи
Алгоритм решения задачи…………………..……………….…. Оценка трудоемкости……………………………………………. Результаты выполнения программы…………………………….	7 8 9
Приложение……………………………………………………………….	13
Литература…………………………………………………………………	17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПОСТАНОВКА ЗАДАЧИ

 

Дана  задача коммивояжера в классической формулировке: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут посещения каждого города один раз с возвращением в исходный пункт. Кратчайший маршрут находится  полным перебором без учета повторяющихся путей (например, 1-2-3-1 и 2-3-1-2). При этом на плоскости полученный маршрут является границей многоугольника.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

МАТЕМАТЧЕСКИЕ ОСНОВЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

 

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

 

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в  неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

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

…..(1)

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

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

С_ij³0; C_jj=∞     (2)

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

С_ij= С_ji       (3)

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

С_ij+ С_jk³C_ik        (4)

В математической постановке говорится о произвольной матрице. Сделано это потому, что  имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2) – (4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С_ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта задачи коммивояжера: симметричную задачу, когда условие (3) выполнено, и несимметричную – в противном случае. Условия (2) – (4) по умолчанию мы будем считать выполненными.

2) В несимметричной  задаче коммивояжера все туры t=(j₁,j₂,..,j_n,j₁) и t’=(j₁,j_n,..,j₂,j₁) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в  циклической перестановке номер j₁, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раза меньше, так как каждый засчитан два раза: как t и как t’. Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать как граф, где ребро (i,j) проведено, если С_ij=0, и не проведено, если С_ij=1. Тогда, если существует тур длины 0, то он пройдет по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путем).

В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

Дана  полная сеть с n вершинами, длина ребра (i,j) = С_ij. Найти гамильтонов цикл минимальной длины. В несимметричной задаче коммивояжера вместо «цикл» надо говорить «контур», а вместо «ребра» – «дуги» или «стрелки».

Некоторые прикладные задачи формулируются как  задачи коммивояжера, но в них нужно  минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие  задачи называются незамкнутыми. [1]

 

 

 

 

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

 

Формулировка: Множество городов: . Расстояние между городами i и j: . П – множество перестановок элементов А, перестановка

 

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

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

Здесь под  длиной контура понимают не количество дуг, входящих в контур, а сумму  их длин. Длина соответствующей дороги – вес ребра. Граф должен быть полным, т.е. в нем имеются все возможные  ребра. Если же граф не является полным, то его можно дополнить недостающими ребрами с весом равным . [2]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПОСТАНОВКА И ОПИСАНИЕ АЛГОРИТМА  РЕШЕНИЯ ЗАДАЧИ

 

3.1 Алгоритм решения задачи

 

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

Общая схема  метода такова:

1. Все  множество разбивается на N-1 подмножеств,  каждое из которых оценивается  верхней и нижней оценками.

2. Производится отсев неоптимальных множеств по следующему критерию: если нижняя оценка больше минимальной из верхних оценок, то множество считается очевидно неоптимальным и отсекается, иначе остается до следующей итерации.

3. Находится множество с лучшей нижней оценкой (прогнозом) и дробится на количество, равное размерности исходной матрицы минус количество уже пройденных (фиксированных для данного множества) городов.

4. Находятся минимальные верхняя и нижняя оценки. Если они равны и достигнуты на одном и том же множестве, то это значит, что получено оптимальное решение и алгоритм заканчивает работу, иначе возврат к шагу 2.[4]

 

 

 

 

 

 

 

 

 

 

3.2 Оценка трудоемкости

 

В задаче коммивояжера с n городами прямой перебор требует рассмотрения (n-1)! различных маршрутов. Метод ветвей и границ требует в среднем 1,26ⁿ операций. [5]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.3 Результат выполнения программы

 

В результате запуска файла main.m получаем:

1. График начального расположения точек(Рис.1)

 

Рис.1

 

2. Первоначальная( предполагаемая) траектория (Рис.2)

Рис.2

 

3. Наилучшая траектория, полученная в результате пересчета, по методу ветвей и границ. (Рис.3)

 

Рис.3

4. Минимальный цикл длиной: 434.7954

 

 

5. Цикл:

           T =       1    27    30    26    28    12    29     4     8     3    11

                                   7     2    15     9    10     6     5    13    18    19    20

              

                                   14    24    23    22    21    16    17    25

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

В результате запуска файла main2.m получаем:

1. График начального расположения точек. (Рис.4)

Рис. 4.

 

2. Первоначальная траектория (предполагаемая). (Рис.5)

Рис. 5

 

3. Наилучшая траектория, полученная в результате пересчета, по методу ветвей и границ. (Рис.6)

 

^Рис.6

4. ^{Минимальный цикл длиной :   423.9045}
5. ^Цикл:

       ^{T =     1    30    29    27    26    28    25    24    23    22    21}

                               ^{20    18    19    17    16    15    14    13    12    11     5}

 

                               ^{6    10     9     8     7     4     3     2}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение

main.m

xx(1)=45;yy(1)=7;

xx(2)=91;yy(2)=89;

xx(3)=83;yy(3)=46;

xx(4)=65;yy(4)=41;

xx(5)=64;yy(5)=60;

xx(6)=68;yy(6)=69;

xx(7)=83;yy(7)=69;

xx(8)=87;yy(8)=32;

xx(9)=74;yy(9)=78;

xx(10)=71;yy(10)=71;

xx(11)=91;yy(11)=56;

xx(12)=54;yy(12)=32;

xx(13)=59;yy(13)=67;

xx(14)=37;yy(14)=45;

xx(15)=72;yy(15)=94;

xx(16)=2;yy(16)=34;

xx(17)=7;yy(17)=22;

xx(18)=22;yy(18)=90;

xx(19)=25;yy(19)=62;

xx(20)=38;yy(20)=54;

xx(21)=4;yy(21)=50;

xx(22)=13;yy(22)=40;

xx(23)=18;yy(23)=40;

xx(24)=24;yy(24)=42;

xx(25)=25;yy(25)=1;

xx(26)=41;yy(26)=26;

xx(27)=45;yy(27)=21;

xx(28)=44;yy(28)=35;

xx(29)=58;yy(29)=35;

xx(30)=33;yy(30)=21;

tsp(xx,yy)

 

main2.m

xx(1)=87;yy(1)=7;

xx(2)=91;yy(2)=38;

xx(3)=83;yy(3)=46;

xx(4)=71;yy(4)=44;

xx(5)=64;yy(5)=60;

xx(6)=68;yy(6)=69;

xx(7)=83;yy(7)=69;

xx(8)=87;yy(8)=76;

xx(9)=74;yy(9)=78;

xx(10)=71;yy(10)=71;

xx(11)=58;yy(11)=69;

xx(12)=54;yy(12)=62;

xx(13)=51;yy(13)=67;

xx(14)=37;yy(14)=84;

xx(15)=41;yy(15)=94;

xx(16)=2;yy(16)=99;

xx(17)=7;yy(17)=64;

xx(18)=22;yy(18)=60;

xx(19)=25;yy(19)=62;

xx(20)=18;yy(20)=54;

xx(21)=4;yy(21)=50;

xx(22)=13;yy(22)=40;

xx(23)=18;yy(23)=40;

xx(24)=24;yy(24)=42;

xx(25)=25;yy(25)=38;

xx(26)=41;yy(26)=26;

xx(27)=45;yy(27)=21;

xx(28)=44;yy(28)=35;

xx(29)=58;yy(29)=35;

xx(30)=62;yy(30)=32;

tsp(xx,yy)

 

tsp.m

function tsp()

N=30;

a=0.6;

t0=10;

tf=0.001;

figure(1);

plot(xx,yy,'b+');% вывод точек на экран

xx1=xx; 

xx1(31)=xx(1);

yy1=yy;

yy1(31)=yy(1);

figure(2);

plot(xx1,yy1);%вывод первоначальной траектории на экран

for i=1:N

    for j=1:N

        if i==j

            continue;

        end

   d(i,j)=sqrt((xx(i)-xx(j)).^2+(yy(i)-yy(j)).^2); % расстояние между точками

    end

end

gen=1;

while gen<=10

    [f,T]=trp(a,d,t0,tf);% запуск задачи коммивояжера

    opf(gen)=f;

    path(gen,:)=T;

    gen=gen+1;

end 

min(opf)

T % вывод цикла на экран

for i=1:N

    xx2(i)=xx(T(i));

    yy2(i)=yy(T(i));

end

xx2(31)=xx(1);

yy2(31)=yy(1);

figure(3);

plot(xx2,yy2);% вывод наикратчайшего пути на экран

 

function [f,T]=trp(a,d,t0,tf)% задача коммивояжера

   [m,n]=size(d);

   L=1000*n;

   t=t0;

   pi0=1:n;

   min_f=0;

   for k=1:(n-1)

        min_f=min_f+d(pi0(k),pi0(k+1));

    end

    min_f=min_f+d(pi0(n),pi0(1));

    p_min=pi0;

    while t>tf

        for k=1:L

            kk=rand;

            [d_f,pi_1]=exchangе(pi0,d);% вызов метода ветвей и границ

            r_r=rand;

            if d_f<0

                pi0=pi_1;

            elseif exp(-d_f/t)>r_r

                pi0=pi_1;

            else

                pi0=pi0;

            end

        end

        f_temp=0;

        for k=1:(n-1)

            f_temp=f_temp+d(pi0(k),pi0(k+1));

        end

        f_temp=f_temp+d(pi0(n),pi0(1));

        if min_f>f_temp % выбор наикратчайшего пути

              min_f=f_temp;

              p_min=pi0;

          end

          t=a*t;

      end

      f=min_f;

      T=p_min;

    

 function [d_f,pi_r]=exchange(pi0,d)% метод ветвей и границ

      [m,n]=size(d);

      u=rand; % задаем произвольное число

      u=u*(n-2);

      u=round(u);% округляем число в сторону ближайшего целого

      if u<2

          u=2;

      end       

      if u>n-2

          u=n-2;

      end

      v=rand;

      v=v*(n-u+1);

      v=round(v);       

      if v<1

          v=1;

      end

      v=u+v;      

      if v>n

          v=n;

      end

      pi_1(u)=pi0(v);

      pi_1(v)=pi0(u);      

      if u>1

          for k=1:(u-1)

              pi_1(k)=pi0(k);

          end

      end       

      if v>(u+1)

          for k=1:(v-u-1)

              pi_1(u+k)=pi0(v-k);

          end

      end       

      if v<n

          for k=(v+1):n

              pi_1(k)=pi0(k);

          end

      end

      d_f=0;      

      if v<n % отсечение неоптимальных решений

          d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));

          for k=(u+1):n

              d_f=d_f+d(pi0(k),pi0(k-1));

          end

          d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));

          for k=(u+1):n

              d_f=d_f-d(pi0(k-1),pi0(k));

          end

      else

          d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));

          for k=(u+1):n

              d_f=d_f+d(pi0(k),pi0(k-1));

          end

          for k=(u+1):n

              d_f=d_f-d(pi0(k-1),pi0(k));

          end

      end

      pi_r=pi_1;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЛИТЕРАТУРА

 

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2004.-208с.
2. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. — Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 с.
3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002.-208с.
4. Просветов Г.И. Математические методы в экономике: Учебно – методическое пособие. – М.: Издательство РДЛ, 2004.-160с.
5. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.-479с.