Програмне забезпечення ЕОМ

 

Для приведения надо вычесть  минимум по первому столбцу: h₁=1. При этом нижняя граница станет равной 47+1 = 48. Сравнивая нижние границы 
φ ( ) = 67 и φ ( ) = 48 < 67 выделяем подмножество маршрутов , которое с большей вероятностью содержит маршрут минимальной длины.

 

Рис. 1 Ветвление на первом шаге

Приведенная платежная  матрица для 

	1	2	3	5	6
2	0	∞	15	29	24
3	14	13	∞	5	0
4	∞	0	9	2	2
5	1	41	22	∞	0
6	12	0	0	0	∞

 

Далее продолжаем процесс  ветвления. Найдем степени Θ_ij нулевых элементов этой матрицы Θ₂₁ =16, Θ₃₆ = 5, Θ₄₂ = 2, Θ₅₆ = 2, Θ₆₂ = 0, Θ₆₃ =9, Θ₆₅ = 2. Наибольшая степень Θ₂₁. Затем множество разбивается дуге (2, 1) на два новых и .

В матрице для  вычеркиваем строку 2 и столбец 1. дуги (1, 4) и (2, 1) образуют связный путь (2, 1, 4), положим c₄₂= ∞, чтобы предотвратить появления цикла 2→1→ 4 → 2.

 

	2	3	5	6
3	13	∞	5	0
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

 

Для приведения надо вычесть  минимум по строке 4: r₄=2. При этом нижняя граница станет равной 48+2 = 50.   

Нижняя граница для , полученная как на предыдущем шаге ветвления, равна 48 + 16 = 64. Сравнивая нижние границы φ ( ) = 64 и φ ( ) = 50 < 64 выбираем для дальнейшего разбиения подмножество маршрутов .

 Рис. 2 Ветвление на втором шаге

 

Приведенная платежная матрица для :

 

	2	3	5	6
3	13	∞	5	0
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

 

Степени Θ_ij нулевых элементов этой матрицы Θ₃₆ = 5, Θ₄₅ = 0, Θ₅₆ = 22, Θ₆₂ = 13, Θ₆₃ =7, Θ₆₅ = 0. Наибольшая степень Θ_56. Затем множество разбивается дуге (2, 1) на два новых и .

Нижняя граница для равна 50 + 22 = 72. В матрице для вычеркиваем строку 5 и столбец 6 и полагаем c₆₅= ∞. Получим матрицу:

 

	2	3	5
3	13	∞	5
4	∞	7	0
6	0	0	∞

 

Для приведения надо вычесть  минимум по строке 3: r₃=5. При этом нижняя граница станет равной 50+5 = 55. Выбираем для дальнейшего разбиения подмножество маршрутов .

Рис. 3 Ветвление на третьем шаге

Приведенная платежная  матрица для 

	2	3	5
3	8	∞	0
4	∞	7	0
6	0	0	∞

 Степени Θ_ij нулевых элементов этой матрицы Θ₃₅ = 8, Θ₄₅ = 7, Θ₆₂ = 8, Θ₆₃ =7. Выбираем Θ₃₅ = 8. Разбиваем на и .

Нижняя граница для равна 55 + 8 = 64. В матрице для вычеркиваем строку 3 и столбец 5 и полагаем c₆₃= ∞. Получим

 

	2	3
4	∞	7
6	0	∞

 

Для приведения надо вычесть  минимум по строке 4: r4=7. При этом нижняя граница станет равной 55+7 = 62. После приведения получим

 

	2	3
4	∞	0
6	0	∞

 

Из матрицы 2´2 получаем два перехода с нулевой длинной: (4, 3) и (6, 2).

Рис. 4 Ветвление на четвертом шаге

 

 

 

 

 

 

 

 

 

 

Рис. 5 Дерево ветвления с оценками

Оптимальный маршрут: 1 – 4 – 3 – 5 – 6 – 2 – 1

 

 

 

 

 

 

 

 

 

5.2 Экспериментальные  расчеты

Контрольный пример №1

 

 

 

 

Контрольный пример №2

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

В ходе выполнения данной работы были изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК – это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.

Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать метод динамического программирования;  для большого числа вершин рациональнее применять метод ветвей и границ.

Изучены практические применения ЗК и задачи сводимые к ЗК.

Проведена реализация программы, позволяющей решить ЗК различными методами.

 

 

ЛИТЕРАТУРА

 

1. О. Оре - Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с.
2. В.И. Мудров - Задача о коммивояжере. — М.: «Знание», 1969. — С. 62.
3. Таха Х.А. - Введение в исследование операций (2005)(7-e издЕ. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
4. Ф. А. Новиков - Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ

ЛИСТИНГИ ПРОГРАММЫ

unit Unit1;

interface

uses

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

  Dialogs, StdCtrls, ExtCtrls, XPMan, Grids, Spin;

type

  TForm1 = class(TForm)

    StringGrid1: TStringGrid;

    SpinEdit1: TSpinEdit;

    Button1: TButton;

    Button2: TButton;

    Label1: TLabel;

    procedure FormCreate(Sender: TObject);

    procedure SpinEdit1Change(Sender: TObject);

    procedure Button1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  C : array [0..100, 0..100] of integer;

  Form1: TForm1;

  h,b,f,x1,x2: real;

  i,j: integer;

  t: boolean;

implementation

{$R *.dfm}

// Save a TStringGrid to a file

procedure SaveStringGrid(StringGrid: TStringGrid; const FileName: TFileName);

var

   f:    TextFile;

   i, k: Integer;

begin

   AssignFile(f, FileName);

   Rewrite(f);

   with StringGrid do

   begin

     // Write number of Columns/Rows

    Writeln(f, ColCount);

     Writeln(f, RowCount);

     // loop through cells

    for i := 0 to ColCount - 1 do

       for k := 0 to RowCount - 1 do

         Writeln(F, Cells[i, k]);

   end;

   CloseFile(F);

end;

// Load a TStringGrid from a file

procedure LoadStringGrid(StringGrid: TStringGrid; const FileName: TFileName);

var

   f:          TextFile;

   iTmp, i, k: Integer;

   strTemp:    String;

begin

   AssignFile(f, FileName);

 

 

   Reset(f);

   with StringGrid do

   begin

     // Get number of columns

    Readln(f, iTmp);

     ColCount := iTmp;

     // Get number of rows

    Readln(f, iTmp);

     RowCount := iTmp;

     // loop through cells & fill in values

    for i := 0 to ColCount - 1 do

       for k := 0 to RowCount - 1 do

       begin

         Readln(f, strTemp);

         Cells[i, k] := strTemp;

       end;

   end;

   CloseFile(f);

end;

// Save StringGrid1 to 'c:\temp.txt':

procedure TForm1.Button1Click(Sender: TObject);

begin

SaveStringGrid(StringGrid1, 'temp.txt');

spinedit1.Value:=Stringgrid1.RowCount;

end;

// Load StringGrid1 from 'c:\temp.txt':

procedure TForm1.Button2Click(Sender: TObject);

begin

LoadStringGrid(StringGrid1, 'temp.txt');

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

LoadStringGrid(StringGrid1, 'temp.txt');

spinedit1.Value:=Stringgrid1.RowCount;

for i:=0 to spinedit1.Value-1 do

  stringgrid1.Cells[0,i]:=stringgrid1.cells[i,0];

end;

procedure TForm1.SpinEdit1Change(Sender: TObject);

begin

Stringgrid1.RowCount:=spinedit1.value;

Stringgrid1.colCount:=spinedit1.value;

end;

end.

 

unit Unit2;

interface

uses

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

  Dialogs, Grids, StdCtrls;

type

  TForm2 = class(TForm)

    StringGrid1: TStringGrid;

    Edit1: TEdit;

    StringGrid2: TStringGrid;

    Edit2: TEdit;

    Label1: TLabel;

    StringGrid3: TStringGrid;

    procedure FormCreate(Sender: TObject);

 

 

 

 

private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form2: TForm2;

implementation

uses Unit1;

{$R *.dfm}

procedure LoadStringGrid(StringGrid: TStringGrid; const FileName: TFileName);

var

   f:          TextFile;

   iTmp, i, k: Integer;

   strTemp:    String;

begin

   AssignFile(f, FileName);

   Reset(f);

   with StringGrid do

   begin

     // Get number of columns

    Readln(f, iTmp);

     ColCount := iTmp;

     // Get number of rows

    Readln(f, iTmp);

     RowCount := iTmp;

     // loop through cells & fill in values

    for i := 0 to ColCount - 1 do

       for k := 0 to RowCount - 1 do

       begin

         Readln(f, strTemp);

         Cells[i, k] := strTemp;

       end;

   end;

   CloseFile(f);

end;

procedure TForm2.FormCreate(Sender: TObject);

begin

LoadStringGrid(StringGrid1, 'temp.txt');

end;

end.

 

unit Unit3;

interface

uses

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

  Dialogs, Menus, StdCtrls, Buttons;

type

  TForm3 = class(TForm)

    MainMenu1: TMainMenu;

    Exit1: TMenuItem;

    ChangeData1: TMenuItem;

    Label1: TLabel;

    ComboBox1: TComboBox;

    ListBox1: TListBox;

    Label2: TLabel;

    BitBtn1: TBitBtn;

    Edit1: TEdit;

    Label3: TLabel;

    Label4: TLabel;

 

    procedure Exit1Click(Sender: TObject);

    procedure ChangeData1Click(Sender: TObject);

    procedure FormActivate(Sender: TObject);

    procedure ComboBox1Select(Sender: TObject);

    procedure BitBtn1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form3: TForm3;

implementation

uses Unit1, Unit2, Unit4;

{$R *.dfm}

procedure TForm3.Exit1Click(Sender: TObject);

begin

close;

end;

procedure TForm3.ChangeData1Click(Sender: TObject);

begin

form1.Visible:=true;

end;

procedure TForm3.FormActivate(Sender: TObject);

var  i: integer;

begin

for i:=1 to form1.SpinEdit1.Value-1 do

combobox1.Items.Add(form1.StringGrid1.Cells[0,i])

end;

procedure TForm3.ComboBox1Select(Sender: TObject);

begin

listbox1.Items.Add(combobox1.Items.Strings[combobox1.itemindex]);

edit1.Text:=inttostr(listbox1.Items.Count);

if listbox1.Items.Count=form1.SpinEdit1.Value-1 then

  begin

  combobox1.Enabled:=false;

  label4.Visible:=true;

  end;end;

function B(i: integer; j: integer) : integer;

begin

Result:=strtoint(form2.stringgrid1.Cells[j,i])+strtoint(form2.StringGrid1.Cells[1,j]);

end;

function C(i:integer; j:integer; k:integer) :integer;

begin

if (strtoint(form2.stringgrid1.Cells[j,i])+B(j,k))<(strtoint(form2.stringgrid1.Cells[k,i])+B(k,j)) then

    Result:=strtoint(form2.stringgrid1.Cells[j,i])+B(j,k)

    else Result:=strtoint(form2.stringgrid1.Cells[k,i])+B(k,j);

end;

function min3:integer;

begin if ((strtoint(form2.stringgrid1.Cells[2,1])+C(2,3,4))<=(strtoint(form2.stringgrid1.Cells[3,1])+C(3,2,4))) and ((strtoint(form2.stringgrid1.Cells[2,1])+C(2,3,4))<=(strtoint(form2.stringgrid1.Cells[4,1])+C(4,2,3))) then Result:=1;

      if ((strtoint(form2.stringgrid1.Cells[3,1])+C(3,2,4))<=(strtoint(form2.stringgrid1.Cells[2,1])+C(2,3,4))) and ((strtoint(form2.stringgrid1.Cells[3,1])+C(3,2,4))<=(strtoint(form2.stringgrid1.Cells[4,1])+C(4,2,3))) then Result:=2;