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

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6). Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается.

Оценивая нули в матрице, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1→2→6→5→4→3→1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием.

 

 

 

 

 

 

 

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

 

2.1 Описание работы программы

 

 

Программа реализована в среде Borland Delphi 7.0. Она включает несколько процедур и функций:

1. Procedure Tkomi.Alg2 - процедура алгоритма нахождения кратчайшего пути
2. Function min - функция нахождения минимума
3. Function provall - функция провала

Интерфейс программы реализован в виде окна, в котором расположено несколько объектов:

1. Информация о программе и разработчиках
2. Поле для ввода количества городов (вершин)
3. Таблица для ввода стоимостей проезда из города в город
4. Поле для вывода конечного результата

 

 

2.3 Текст программы

 

 

Unit prog;

 

Interface

Uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

StdCtrls, ExtCtrls, Grids,ComCtrls;

Type

    Tkomi = class (TForm)

    Matr1: TStringGrid;

    Memo1: TMemo;

    Edit1: TEdit;

    Label1: TLabel;

    Button2: TButton;

    Button3: TButton;

    Button4: TButton;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    Label6: TLabel;

    Label7: TLabel;

    procedure Button2Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

    procedure Button4Click(Sender: TObject);

Private

Public

    kol:integer;

    procedure Alg2;

End;

const n=10;

var komi: Tkomi;

implementation {$R *.dfm}

 

{-------------Процедура Алгоритма нахождения  кратчайшего пути------------------}

Procedure Tkomi.Alg2;

var

  d,i:integer;

  prov:array[1..10]of boolean;

  s:string;

  sum1:integer;

 

{---Функция минимума---}

Function min(i:integer):integer;

var min1,j:integer;

        g:integer;

begin

  min1:=60000;

  for j:=1 to 10 do

  if j<>i then

  if prov[j]then

  if matr1.Cells[j,i]<>'X' then

  if min1>strtoint(matr1.Cells[j,i])then

  begin

    min1:=strtoint(matr1.Cells[j,i]);

    g:=j;

  end;

  min:=g;

end;

 

{---Функция провала---}

Function provall:boolean;

var i:integer;f:boolean;

begin

  f:=false;

  for i:=1 to 10 do f:=(f)or(prov[i]);

  provall:=not(f);

end;

 

begin

  for i:=1 to kol do prov[i]:=true;

  d:=1;s:=matr1.Cells[0,1]+'->';

  sum1:=0; prov[1]:=false;

  repeat

  s:=s+matr1.Cells[0,min(d)]+'->';

  if matr1.Cells[d,min(d)]='X' then sum1:=sum1+0

  else sum1:=sum1+strtoint(matr1.Cells[d,min(d)]);

  d:=min(d);

  prov[d]:=false;

  until provall;

  sum1:=sum1+strtoint(matr1.Cells[d,1]);

  s:=s+matr1.Cells[0,1];

  memo1.clear;

  memo1.Lines.Add('  ');

  memo1.Lines.add(' Найденный путь:  '+s);

  memo1.lines.add(' Длина пути = '+inttostr(sum1));

end;

 

//Кнопка "Ввод"

Procedure Tkomi.Button2Click(Sender: TObject);

var i,n:integer;

begin

  n:=strtoint(edit1.Text);

  matr1.ColCount:=n+1;

  matr1.RowCount:=n+1;

  kol:=n;

  for i:=1 to n do

  begin

    matr1.Cells[0,i]:=inttostr(i);

    matr1.Cells[i,0]:=inttostr(i);

    matr1.Cells[i,i]:='%';

  end;

end;

 

//Кнопка "Найти кротчайший путь"

Procedure Tkomi.Button3Click(Sender: TObject);

begin Alg2 end;

 

//Кнопка "Закрыть приложение

Procedure Tkomi.Button4Click(Sender: TObject);

begin close end;

 

End.

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

 

В данной курсовой работе были рассмотрены основные теоретические вопросы по задаче коммивояжера. Приведен текст программы, позволяющей решить задачу коммивояжера методом ветвей и границ, написанный на языке Borland Delphi 7.0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ЛИТЕРАТУРЫ

 

 

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.
2. Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.
3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002. – 208 с.
4. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. – М.: Издательство РДЛ, 2004. – 160 с.
5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004. – 144 с.
6. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.
7. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.