2 Разработка и описание алгоритма решения задачи

2.1 Описание работы программы Программа реализована в среде BorlandDelphi7.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.

Заключение

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

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

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Высшая школа, 2004. – 208 с.

2. Исследование операций в экономике/ Под ред. Кремера Н.Ш. – М.:ЮНИТИ, 2004. – 407 с.

3. Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. – СПб.: Питер, 2002. – 208 с.

4. Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. – М.: Издательство РДЛ, 2004. – 160 с.

5. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – М.: Вузовский учебник, 2004. – 144 с.

6. Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. – Мн.: Новое знание, 2003. – 424 с.

7. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.