Unit Main;

Пояснювальна записка

До курсової роботи з дисципліни

«Методи оптимізації»

Виконала студентка

групи ІТЕП – 31

Факультет АІТ

Місюра Л. В.

Перевірив:

Професор Гайна Г.А.

Київ – 2014

Зміст

1. Вступ………………………………………………………………………..3

2. Математична модель задачі………………………………………………3

3. Обґрунтування вибору методу та алгоритм розв’язання задачі.….....4

4. Розв’язання задачі вручну……………………………………………….4

5. Розв’язання задачі на контрольному прикладі….……………………..6

6. Лістинг програми…………………………………………………………6

7. Список використаної літератури…………………………………….....25

Вступ

З метою закріплення знань і навичок по вирішенню задач оптимізаційного характеру в рамках даної курсової роботи мені була поставлена наступна задача:

«Будівельна колона повинна послідовно збудувати на протязі планового періоду в різних пунктах області чотири об’єкти: А1, А2, А3 і А4. Відстані між усіма пунктами задані в таблиці»

2. Математична модель задачі

Задача комівояжера є NP-важкою навіть у разі, коли (сij) - евклідові відстані на площині, тобто матриця симетрична і задовольняє нерівності трикутника

сij ≤ сik + сkj, 1 ≤ i, j, k ≤ n.

Якщо існує наближений поліноміальний алгоритм A і константа r, 1 ≤ r <∞ такі, що для будь-якого прикладу I задача комівояжера вірна A (I) ≤ r OPT (I), то P = NP.

Розглянемо NP-повну задачу в Гамільтоновому циклі: дано граф G = (V, E), чи правда, що він містить гамільтонів цикл? Якщо умови теореми вірні і такі A і r існують, то ми отримаємо точний поліноміальний алгоритм вирішення задачі про Гамільтонів цикл. По заданому графу G = (V, E) побудуємо приклад задачі комівояжера, поклавши

Застосуємо алгоритм A і подивимося на відповідь. Якщо отримали цикл довжини n, то граф G, очевидно, містить гамільтонів цикл. Якщо довжина циклу більше n, то вона не менше ніж n ⋅ r + (n - 1), так як входить вага хоча б одного з «важких» ребер. Але в цьому випадку граф G не може мати гамільтонів цикл, так як алгоритм A помиляється не більше ніж в r разів і відповідь в задачі комівояжера не повинна перевершувати n ⋅ r, якщо гамільтонів цикл є. Отже, алгоритм A завжди дає правильну відповідь для NP-повної задачі і має поліноміальну трудомісткість, тобто P = NP.

3. Обгрунтування вибору методу та алгоритму розв’язання задачі

Стандартний алгоритм локального спуску:

1. Вибрати C0 - початковий цикл і обчислити його довжину F(C0), i:= 0.

2. Знайти найкращого сусіда Ci +1 для циклу Ci:

F(Ci+1) = min {F(C) | C ∈ N(Ci) }.

3. Якщо F (Ci +1) <F (Ci), то покласти i: = i + 1 і повернутися на 2, інакше STOP, Ci - локальний мінімум.

Локальний спуск може зажадати експоненціального числа кроків.

4. Розв’язання задачі вручну

max

max

Min = (3,5), (5,4), (4,2), (2,1), (1,3).

Довжина маршруту: 135.

5. Розв’язання задачі на контрольному прикладі

Інтерфейс даної програми містить можливість введення різних за розміром матриць, оптимальне використання ресурсів пам’яті комп’ютера і часу виконання. Передбачає відстеження введення некоректних даних, виключних ситуацій, можливість збереження результатів виконання програм у файл.

6. Лістинг програми

unit Main;

interface

uses

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

Dialogs, StdCtrls, ExtCtrls, Buttons, Menus;

const

NN=10;

type

Gorod=array[1..NN,1..NN] of integer;

Dopolnit=array[1..NN] of integer;

ConPrived=array[0..NN,0..2] of integer;

Iskluch=array[1..NN] of byte;

ItogPuti=array[1..NN*2] of integer;

type

TForm1 = class(TForm)

Image1: TImage;

Label1: TLabel;

Label4: TLabel;

Label3: TLabel;

BitBtn1: TBitBtn;

Label6: TLabel;

Label7: TLabel;

ComboBox1: TComboBox;

Label2: TLabel;

Label13: TLabel;

…

Label27: TLabel;

Label21: TLabel;

Edit11: TEdit;

Edit12: TEdit;

Edit13: TEdit;

…

Edit1010: TEdit;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

N7: TMenuItem;

N8: TMenuItem;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

procedure FormCreate(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

procedure ComboBox1Change(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure N3Click(Sender: TObject);

procedure N4Click(Sender: TObject);

private

procedure InputMatrix;

procedure Etap(var GInd:integer);

procedure Konkurir(var r,m:byte);

procedure OpredilPuti;

procedure Sbros;

procedure DelStrStolb(Stroka,Stolb:byte);

procedure Tree(K,XPos,YPos,Index,RG,MG,Blok,GIn:byte);

function ObjEdit(S: string; IndexX: byte; IndexY: byte): TEdit;

function ObjLabel(S: string; IndexX: byte): TLabel;

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

ParKonkur,GorodaIJ:Gorod;

Ci,Cj:Dopolnit;

GIndexKon:ConPrived;

IsklStrok:Iskluch;

IsklStolb:Iskluch;

TreeList:TEdit;

ListName:TLabel;

Puti,NewPut:ItogPuti;

N:byte;

K:integer;

implementation

{$R *.dfm}

//Функция звернення до елементів Edit через їх Name в рядковому режимі

function TForm1.ObjEdit (S: string; IndexX: byte; IndexY: byte): TEdit;

begin

Result:=Form1.FindComponent(S + IntToStr(IndexX) + IntToStr(IndexY)) as TEdit;

end;

// Функция звернення до елементів Label через їх Name в рядковому режимі

function TForm1.ObjLabel (S: string; IndexX: byte): TLabel;

begin

Result:=Form1.FindComponent(S + IntToStr(IndexX)) as TLabel;

end;

//Процедура читання матриці із Edit`