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

Задача на пошук найкоротшої відстані, маршруту і шляху холостого пробігу машин. Обгрунтування вибору методу та алгоритм розв'язання задачі. Опис математичної моделі задачі. Інтерфейс та лістинг программи. Заповнення таблиці суміжності для заданого графу.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык украинский
Дата добавления 26.05.2015
Размер файла 315,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Зміст

Вступ

1. Постановка задачі

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

3. Опис математичної моделі задачі

4. Інтерфейс програми

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

6. Контрольний приклад

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

Вступ

Оптимiзацiя в широкому значеннi слова знаходить застосування в науцi, технiцi i у будь-який iншiй областi людської дiяльностi. Оптимiзацiя - цiлеспрямована дiяльнiсть, що полягає в одержаннi найкращих результатiв при вiдповiдних умовах.

Пошуки оптимальних розв'язкiв привели до створення спецiальних математичних методiв i вже в 18 столiттi були закладенi математичнi основи оптимiзацiї (варiацiйне числення, чисельнi методи й iншi). Однак до другої половини 20 столiття методи оптимiзацiї в багатьох областях науки i технiки застосовувалися дуже рiдко, оскiльки практичне використання математичних методiв оптимiзацiї вимагало величезної обчислювальної роботи, що без ЕОМ реалiзувати було вкрай важко, а в рядi випадкiв - неможливо. Особливо великi труднощi виникали при розв'язку задач оптимiзацiї процесiв у хiмiчнiй технологiї через велике число параметрiв i їхнього складного взаємозв'язку мiж собою. При наявностi ЕОМ задачi помiтно спрощуються.

Постановка задачi оптимiзацiї припускає iснування конкуруючих властивостей процесу, наприклад:

- кiлькiсть продукцiї - "витрата сировини"

- кiлькiсть продукцiї - "якiсть продукцiї"

Вибiр компромiсного варiанта для зазначених властивостей i являє собою процедуру розв'язку оптимiзацiйнної задачi.

При постановцi завдання оптимiзацiї необхiдно:

Наявнiсть об'єкта оптимiзацiї i мети оптимiзацiї. При цьому формулювання кожної задачi оптимiзацiї повинно вимагати екстремального значення лише одного розміру, тобто одночасно системi не повинно приписуватися два i бiльш критерiїв оптимiзацiї, тому що практично завжди экстремум одного критерiю не вiдповiдає экстремуму iншого.

1. Постановка задачі

Необхідно знайти найкоротшу відстань і маршрут від заводу збірного залізобетону, що знаходиться в пункті 1 до будівельних майданчиків 2-9 при заданій схемі автомобільних шляхів (рис.1). Знайти також найкоротший шлях холостого пробігу машин за умови, що частина доріг має односторонній напрямок руху (вказано стрілками на схемі).

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

В даній задачі стоїть завдання знайти найкоротшу відстань і маршрут від заводу збірного залізобетону до будівельних майданчиків, а це є алгоритм Дейкстри (задача про найкоротший ланцюг).

Алгоритм знаходження найкоротшої відстані ґрунтується на тому, що даний граф представляється у вигляді матриці суміжності G[n,n], де n - кількість вершин в графі. Якщо існує шлях із i-ї вершини в j-ту, і вартість цього шляху складає х, то записується G[i,j]=x. Якщо шляху не існує, то х дорівнює нескінченості. Для знаходження найкоротшого шляху застосовуємо алгоритм Дейкстри. Вирішення цієї задачі (за алгоритмом Дейксти) базується на наступному принципі: якщо відомо найкоротший ланцюг з Х в Y і на цьому ланцюзі знаходиться вершина Z, то найкоротший ланцюг з XZ співпадає з ZY .

3. Опис математичної моделі

Графом G(V,E) називається сукупність двох множин - не порожньої множини V (множини його вершин) та множини Е невпорядкованих пар елементів в множині V, Е - множина ребер графа.

Ш

Маємо орієнтований граф G=(V,E), кожній дузі v->w цьго графа зіставлена невід'ємна віртість C[v,w]. Загальна задача знаходження найкоротших шляхів полягає у знаходженні для кожної впорядкованої пари вершин (v,w) будь-якого шляху від вершини v у вершину w, довжина якого найкоротша з усіх можливих.

Матриця суміжностей графа G(V,E) - це квадратна матриця, елементи якої визначаються так:

Основою розв'язання даної задачі є алгоритм Дейкстри, загальна рекурентна форма якого:

Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k]+Ak-1[k,j]).

Якщо від вершини i до j не існує ребра то G[i,j]=? // нескінченість G` - граф мінімальних вартостей G* - граф найкоротших проміжних шляхів.

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

4. Інтерфейс програми

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

unit Unit1;

interface

uses

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

Dialogs, Grids, StdCtrls, Buttons, Menus, ExtCtrls;

const

maxn = 20;

inf = maxint div 2;

type

TForm1 = class(TForm)

G: TStringGrid;

Label1: TLabel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

GroupBox1: TGroupBox;

G1: TStringGrid;

G2: TStringGrid;

GroupBox2: TGroupBox;

Label3: TLabel;

Edit1: TEdit;

BitBtn3: TBitBtn;

Panel1: TPanel;

SpeedButton1: TSpeedButton;

BitBtn1: TBitBtn;

BitBtn2: TBitBtn;

Memo1: TMemo;

procedure FormCreate(Sender: TObject);

procedure BitBtn3Click(Sender: TObject);

procedure init(sender: tobject);

procedure floyd;

procedure N3Click(Sender: TObject);

procedure Clear(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure path(i, j: integer);

procedure N6Click(Sender: TObject);

procedure N5Click(Sender: TObject);

private

d, a: array [1..maxn, 1..maxn] of integer;

p: array [1..maxn, 1..maxn] of integer;

n: longint;

str: string;

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

uses Unit4, Unit2, Unit3;

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

var i,j: longint;

begin

for i:=1 to G.ColCount do

for j:=1 to G.ColCount do begin

G.Cells[i,j]:=' ';

G2.Cells[i,j]:=' ' end;

G.Cells[0,0]:='G';

G1.Cells[0,0]:='G*';

G2.Cells[0,0]:='G`';

for i:=1 to 10 do begin

G.Cells[0,i]:=IntToStr(i);

G1.Cells[0,i]:=IntToStr(i);

G2.Cells[0,i]:=IntToStr(i);

G.Cells[i,0]:=IntToStr(i);

G1.Cells[i,0]:=IntToStr(i);

G2.Cells[i,0]:=IntToStr(i);

//Cells[i,i]:='0';

end; //for

end; //procedure

procedure TForm1.BitBtn3Click(Sender: TObject);

begin

n:=StrToInt(Edit1.Text);

if (n>0) and (n<=10) then begin

G.Enabled:=True;

G2.Enabled:=True;

BitBtn2.Enabled:=true end

else

MessageDlg('Невірні дані',MtError,[mbOk],0);

end;

procedure TForm1.init(sender: tobject);

var

i, j, x, y, nn, z: longint;

begin

N2.Enabled:=true;

for i := 1 to maxn do

for j := 1 to maxn do

a[i, j] := inf;

for i := 1 to maxn do

a[i, i] := 0;

fillchar(d, sizeof(d), 0);

fillchar(p, sizeof(p), 0);

n:=StrToInt(Edit1.Text);

for i:=1 to n do

for j:=1 to n do

if G.Cells[i,j][1] in ['0'..'9'] then

a[i,j]:=StrToInt(G.Cells[i,j]);

floyd;

end;

procedure TForm1.floyd;

var

k, i, j: integer;

begin

for i := 1 to n do

for j := 1 to n do

begin

p[i, j] := i;

d[i, j] := a[i, j];

end;

for k := 1 to n do

for i := 1 to n do

for j := 1 to n do

if d[i, j] > d[i, k] + d[k, j] then

begin

d[i, j] := d[i, k] + d[k, j];

p[i, j] := k;

end;

for i:=1 to n do

for j:=1 to n do begin

if p[i,j]=i then p[i,j]:=0;

G1.Cells[i,j]:=IntToStr(p[i,j]);

if d[i,j]>=1000 then G2.Cells[i,j]:='#' else

G2.Cells[i,j]:=IntToStr(d[i,j]) end;

for i:=1 to n do

for j:=1 to n do

if (p[i,j]=0) and (g.Cells[i,j][1] in ['1'..'9']) then

memo1.Lines.Add(IntToStr(j)+'-->'+IntToStr(i));

memo1.Lines.Add('Всі шляхи, що не перетинаються по ребрам');

memo1.Lines.Add('--------------------------------------------------------------------------------');

for i:=1 to n do

for j:=1 to n do begin

str:='';

if G2.Cells[i,j][1] in ['1'..'9'] then begin

path(j,i);

memo1.Lines.Add(IntToStr(i)+'-->'+str+IntToStr(j)); end; end;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

close;

end;

procedure TForm1.Clear(Sender: TObject);

var i,j: longint;

begin

for i:=1 to G.ColCount do

for j:=1 to G.ColCount do begin

G.Cells[i,j]:=' ';

G1.Cells[i,j]:=' ';

G2.Cells[i,j]:=' ' end;

memo1.Lines.Clear;

memo1.Lines.Add('Bсі шляхи, що не перетинаються по вершинам:');

memo1.Lines.Add('--------------------------------------------------------------------------------');

end;

procedure TForm1.N2Click(Sender: TObject);

var f: textFile;

i,j: integer;

begin

SaveDlg.Show;

assignFile(f, SaveDlg.LEdit1.Text);

ReWrite(f);

Writeln(f);

Writeln(f,'Таблиця суміжності графа G');

for i:=1 to n do begin

for j:=1 to n do

write(f,G.Cells[i,j],' ');

writeln(f) end;

Writeln(f);

Writeln(f,'Найкоротші шляхи графа G');

for i:=1 to n do begin

for j:=1 to n do

write(f,G2.Cells[i,j],' ');

writeln(f) end;

CloseFile(f);

end;

procedure TForm1.path(i, j: integer);

var k: integer;

begin

k:= P[i,j];

if k=0 then exit;

path(i,k);

str:=str+' '+IntToStr(k)+'-->';

path(k,j);

end;

procedure TForm1.N6Click(Sender: TObject);

begin

AboutBox.Show;

end;

procedure TForm1.N5Click(Sender: TObject);

begin

form3.show;

end;

end.

алгоритм математичний лістинг програма

6. Контрольний приклад

Для заданого графу, що зображений на Рис.1 заповнюємо таблицю суміжності у відповідності до завдання, враховуючи те, що в ньому присутні деякі орієнтовані дуги.

В результаті ми отримуємо дві матриці - матрицю мінімальних відстаней між заводом залізобетону та будівельними майданчиками:

Враховуючи те, що деяка частина доріг має односторонній напрямок руху, для прикладу наведемо такі данні:

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 2 (буд. майданчик )становить 22 , проте якщо ми будемо рухатись від пункту 2 до пункту 1, відстань між ними буде становити 2.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 3 (буд. майданчик )становить 15, проте якщо ми будемо рухатись від пункту 3 до пункту 1, відстань між ними буде становити 7. і т.д.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 4 (буд. майданчик ) становить 10, проте якщо ми будемо рухатись від пункту 4 до пункту 1, відстань між ними збільшиться і буде становити 11.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 5 (буд. майданчик ) становить 9.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 6 (буд. майданчик ) становить 4.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 7 (буд. майданчик ) становить 5.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 8 (буд. майданчик ) становить 8.

· Найкоротша відстань від пункту 1 (завод ЗБК) до пункту 9 (буд. майданчик ) становить 6.

В результаті роботи програми формується ще одна матриця- матриця найкоротших проміжних шляхів:

Тут вказуються проміжні пункти від заводу ЗБК (тобто пункту 1), через який можна потрапити до потрібного будівельного майданчику.

Наприклад, якщо рухатись від 1 до 2 пункту, то проміжним для них буде пункт 9. Проте враховуючи односторонній напрямок руху деяких доріг рухаючись від 2 до 1 проміжного пункту між ними не існує, тому відповідь програми - 0 .

· Проміжним пунктом між 1 та 3 є пункт 9, проте рухаючись з 3 в 1 проміжним пунктом є 2.

· Проміжним пунктом між 1 та 4 є пункт 7, проте рухаючись з 4 в 1 проміжним пунктом є 8.

· Проміжним пунктом між 1 та 5 є пункт 7.

· Проміжного пункту між 1 та 6 , а також 1 та 7 не існує.

· Проміжним пунктом між 1 та 8 є пункт 8.

· Проміжного пункту між 1 та 9 не існує.

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

1. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. - М.: Мир, 1972.

2. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, 1986.

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

Размещено на Allbest.ru


Подобные документы

  • Технологія візуального проектування. Аналітичне розв’язання задачі в загальному вигляді. Програмування в консольному режимі. Сценарій розв’язання задачі в Delphi та блок-схема алгоритму. Програмний код додатку та опис інтерфейсу з екранними копіями.

    курсовая работа [2,4 M], добавлен 22.06.2009

  • Варіантний аналіз та вибір методів розв’язування, основні поняття та визначення, особливості розробки баз даних. Описовий алгоритм головної програми та її структури, опис авторської заставки. Структура модулів та опис функцій, лістинг програми.

    курсовая работа [2,6 M], добавлен 30.11.2009

  • Задача про хід коня, відома ще з XVIII сторіччя: спосіб знаходити безліч розв’язків для ходів коня, не роблячи спроб. Алгоритм першої спроби ходіння конем. Алгоритм та блок-схема задачі "Хід коня" та її підпрограми. Розробка лістингу програми "Хід коня".

    задача [20,3 K], добавлен 21.04.2011

  • Дослідження методу сплайнів для вирішення задачі інтерполяції. Вибір методів технічних та інструментальних засобів вирішення задачі, їх алгоритми. Розробка логічної частини програми, результати обчислень. Розв’язання задачі в пакетах прикладних програм.

    курсовая работа [278,5 K], добавлен 03.12.2009

  • Постановка та описання алгоритму розв’язання задачі про оптимальне призначення, формулювання вимог. Обґрунтування вибору засобів програмування. Розробка структури програми та системи її візуалізації, тестування та верифікація, оцінка ефективності.

    курсовая работа [1,1 M], добавлен 12.05.2013

  • Розв’язання нелінійних алгебраїчних рівнянь методом хорд. Опис структури програмного проекту та алгоритмів розв’язання задачі. Розробка та виконання тестового прикладу. Інші математичні способи знаходження коренів рівнянь, та опис виконаної програми.

    курсовая работа [4,1 M], добавлен 28.09.2010

  • Дослідження застосування різницевого методу для розв’язання крайової задачі. Дослідження проводиться на прикладі заданого диференційного рівняння. Дається опис методу та задачі в цілому. Застосування при обчисленні формули Чебишева і формули Гаусса.

    курсовая работа [157,2 K], добавлен 03.12.2009

  • Проектування програми за допомогою мови асемблера, яка б дозволяла відобразити на екрані дерево каталогів на диску і перейти в потрібний користувачеві каталог. Вибір методу розв’язання задачі та обґрунтування доцільності. Проведення лістингу програми.

    курсовая работа [13,1 K], добавлен 08.08.2009

  • Побудова інформаційно-математичної моделі та алгоритм задачі. Визначення структури даних. Розробка інтерфейсу програми з користувачем. Складання коду програми. Реалізація проекту у візуальному середовищі. Тестування та інструкція з експлуатації програми.

    курсовая работа [1,3 M], добавлен 14.04.2009

  • Написання програм для перейменування файлів та копіювання файлів і підкаталогів (аналоги REN, XCOPY). Вибір методу розв'язки задачі та його обґрунтування. Алгоритм та реалізація програми, її системні вимоги. Інструкція для користувача та лістинг.

    курсовая работа [14,7 K], добавлен 08.08.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.