Метод динамического программирования

 

4.2 Работа  с помощью

 

При запуске  приложения пользователю предлагается выбрать размерность матрицы, после  чего заполнить ее и нажать кнопку «ОК». После заполнения матрицы и нужно нажать кнопку «Рассчитать» открывается новое окно, в котором представлены этапы решения задачи, кратчайший путь и длина выбранного пути. Чтобы вывести отчет, в котором будет отображен конечный ответ и кратчайший путь необходимо, нажать кнопку «Составить отчет». Отчет будет сформирован в MS Word, после чего его можно распечатать.

 

4.3 Наиболее вероятные ошибки

 

Результат ошибки, при заполнении размерности матрицы отрицательными числами или оставив поле пустым, представлен на рисунке 5:

Рисунок 5 - Ошибка при заполнении размерности матрицы

 

 

 

Результат ошибки при заполнении матрицы представлен на рисунке 6:

 

Рисунок 6 - Ошибка при заполнении матрицы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

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

Динамическое программирование хорошо приспособлено для решения  задач оптимизации многостадийных процессов, особенно тех, в которых  состояние каждой стадии характеризуется  относительно небольшим числом переменных состояния. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин.

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

 

 

 

 

 

 

 

 

 

 

 

 

Список использованных источников

 

1. Хаген Граф Создание веб-сайтов с помощью Joomla! 1.5 — Издательский дом "Вильямс", 2009.
2. Виктор Ромашев CMS Drupal: Система управления содержимым сайта — Питер, 2010. — 255 p
3.   Шелобаев С. И. Математические методы и, финансах, бизнесе: Учеб.пособие для студ.вузов, обуч. по эконом. спец. — М.: ЮНИТИ, 2000.
4. Математические методы и прикладные модели: Учеб. пособие для студ. Вузов, обуч.по эконом.спец./ Под ред. В. В. Федосеева. — М.: ЮНИТИ, 1999.
5. Математические модели в управлении производством. — Новосибирск: Наука, 1983.
6. Хавьер Пашеку. Программирование в Borland Delphi 2006 для профессионалов = Delphi for .NET Developer’s Guide — М.: Вильямс, 2006. — 944 с.
7. Нил Дж. Рубенкинг. Язык программирования Delphi для «чайников». Введение в Borland Delphi 2006 = Delphi for Dummies — М.: Диалектика, 2007. — 336 с.

САЙТЫ (добавить)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение  А - Текст программы

 

Program

unit Unit1;

interface

uses

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

  Dialogs, Grids, Buttons, ComCtrls, StdCtrls;

type

  TForm1 = class(TForm)

    Edit1: TEdit;

    UpDown1: TUpDown;

    SpeedButton1: TSpeedButton;

    StringGrid1: TStringGrid;

    SpeedButton2: TSpeedButton;

    Label1: TLabel;

    SpeedButton3: TSpeedButton;

    Label2: TLabel;

    SpeedButton4: TSpeedButton;

    procedure SpeedButton1Click(Sender: TObject);

    procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

    procedure StringGrid1Click(Sender: TObject);

    procedure SpeedButton2Click(Sender: TObject);

    procedure SpeedButton3Click(Sender: TObject);

    procedure SpeedButton4Click(Sender: TObject);

    procedure Edit1KeyPress(Sender: TObject; var Key: Char);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

  i,j:integer;

  k,c,i1,j1,a,b,l,a1,b1,c1,r,f,x,q,min2:integer;

  h,n,m,min,v,g:array [1..10] of integer;

  min1,mal:array [1..10] of string;

  y:boolean;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1.SpeedButton1Click(Sender: TObject);

begin

if StrToInt(Edit1.Text)<=0 then ShowMessage('Размерность матрицы не может быть меньше или равной нулю')

else begin

Label2.Visible:=true;

StringGrid1.Visible:=true;

SpeedButton2.Visible:=true;

StringGrid1.RowCount:=StrToInt(Edit1.Text)+1;

StringGrid1.ColCount:=StrToInt(Edit1.Text)+1;

StringGrid1.Width:=32*(StrToInt(Edit1.Text)+1);

StringGrid1.Height:=26*(StrToInt(Edit1.Text)+1);

for i:=1 to StrToInt(Edit1.Text) do

with stringgrid1 do begin

Cells[0,i]:='с'+IntToStr(i);

Cells[i,0]:='с'+IntToStr(i);end;end;end;

procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#8])then key :=#0;

end;

procedure TForm1.StringGrid1Click(Sender: TObject);

begin

for i:=1 to StrToInt(Edit1.Text) do

for j:=1 to StrToInt(Edit1.Text) do

with stringgrid1 do

if j>=i then

cells[i,j]:='0';

end;

procedure TForm1.SpeedButton2Click(Sender: TObject);

begin

for i:=1 to StrToInt(Edit1.Text) do

for j:=1 to StrToInt(Edit1.Text) do

if StringGrid1.Cells[i,j]='' then begin ShowMessage('Заполните матрицу');Exit; end;

for i:=1 to StrToInt(Edit1.Text) do

for j:=1 to StrToInt(Edit1.Text) do

with stringgrid1 do

if cells[i,j]='' then cells[i,j]:='0';

k:=0;

i1:=0;

a:=1;

c:=1;

for j:=1 to StrToInt(Edit1.Text) do

with stringgrid1 do

if cells[StrToInt(Edit1.Text),j]<>'0' then begin

k:=k+1;

i1:=i1+1;

n[i1]:=j;end;

c:=k+c;

b:=k;

a:=a+1;

repeat

k:=0; i1:=0;

for i:=1 to StrToInt(Edit1.Text) do

for j:=1 to b  do begin

if (StringGrid1.Cells[n[j],i]<> '0') and (i1=0) then begin

k:=k+1;

i1:=i1+1;

m[i1]:=i;end;

if (StringGrid1.Cells[n[j],i]<> '0') and (i1>0) and (m[i1]<>i) then begin

k:=k+1;

i1:=i1+1;

m[i1]:=i;end;

end;

b:=k;

c:=c+k;

a:=a+1;

n:=m;

until c=StrToInt(Edit1.Text);

for i:=1 to StrToInt(Edit1.Text)-1 do begin k:=0;

for j:=1 to StrToInt(Edit1.Text) do

if StringGrid1.Cells[j,i]<>'0' then k:=k+1;

h[i]:=k;

end;

SpeedButton3.Visible:=true;

end;

procedure TForm1.SpeedButton3Click(Sender: TObject);

begin

SpeedButton2.Enabled:=false;

with form2 do begin

tabl[1]:=TStringGrid.Create(Form2);

tabl[1].Parent:=Form2;

tabl[1].FixedCols:=0;

tabl[1].Top:=50;

tabl[1].Left:=32;

tabl[1].DefaultColWidth:=30;

tabl[1].ColCount:=4;

tabl[1].Width:=32*4;

tabl[1].Cells[0,0]:='X'+IntToStr(a-2);

tabl[1].Cells[1,0]:='U'+IntToStr(a-1);

tabl[1].Cells[2,0]:='X'+IntToStr(a-1);

tabl[1].Cells[3,0]:='F'+IntToStr(a-1);

k:=0;

i1:=0;

b1:=0;

c:=1;

q:=0;

for j:=1 to StrToInt(Edit1.Text) do

if StringGrid1.Cells[StrToInt(Edit1.Text),j]<>'0' then begin

k:=k+1;

i1:=i1+1;

b1:=b1+1;

n[i1]:=j;

tabl[1].RowCount:=b1+1;

tabl[1].Height:=26*(b1+1);

tabl[1].Cells[0,b1]:=StringGrid1.Cells[0,j];

tabl[1].Cells[1,b1]:='('+IntToStr(j)+','+Edit1.Text+')';

tabl[1].Cells[2,b1]:=StringGrid1.Cells[strtoint(edit1.Text),0];

tabl[1].Cells[3,b1]:=StringGrid1.Cells[strtoint(Edit1.Text),j];

min[j]:=StrToInt(tabl[1].Cells[3,b1]);

end;

q:=q+1;

for i:=1 to b1 do

if tabl[1].Cells[3,i]<>'-' then begin

min2:=strtoint(tabl[1].Cells[3,i]);

min1[q]:=tabl[1].Cells[0,i];end;

for i:=1 to b1 do

if min2>strtoint(tabl[1].Cells[3,i]) then begin

min2:=strtoint(tabl[1].Cells[3,i]);

min1[q]:=tabl[1].Cells[0,i];end;

end;

a1:=1;

c:=k+c;

b:=k;

c1:=50;

j1:=50;

repeat

k:=0;

i1:=0;

j1:=j1+26*(b1+1)+c1;

b1:=0;

a:=a-1;

a1:=a1+1;

with form2 do begin

tabl[a1]:=TStringGrid.Create(Form2);

tabl[a1].Parent:=Form2;

tabl[a1].FixedCols:=0;

tabl[a1].DefaultColWidth:=30;

tabl[a1].Top:=j1;

tabl[a1].Left:=32;

tabl[a1].ColCount:=7;

tabl[a1].Width:=32*7;

tabl[a1].Cells[0,0]:='X'+IntToStr(a-2);

tabl[a1].Cells[1,0]:='U'+IntToStr(a-1);

tabl[a1].Cells[2,0]:='X'+IntToStr(a-1);

tabl[a1].Cells[3,0]:='Z'+IntToStr(a-1);

tabl[a1].Cells[4,0]:='F'+IntToStr(a);

tabl[a1].Cells[5,0]:='Z'+IntToStr(a-1)+'+'+'F'+IntToStr(a);

tabl[a1].Cells[6,0]:='F'+IntToStr(a-1);

for i:=1 to StrToInt(Edit1.Text) do begin

x:=0;

for j:=1 to b  do begin

if (StringGrid1.Cells[n[j],i]<> '0') and (i1>0) then begin

b1:=b1+1;

tabl[a1].RowCount:=b1+1;

tabl[a1].Height:=26*(b1+1);

tabl[a1].Cells[0,b1]:=StringGrid1.Cells[0,i];

tabl[a1].Cells[1,b1]:='('+IntToStr(i)+','+IntToStr(n[j])+')';

tabl[a1].Cells[2,b1]:=StringGrid1.Cells[n[j],0];

tabl[a1].Cells[3,b1]:=StringGrid1.Cells[n[j],i];

r:=StrToInt(StringGrid1.Cells[n[j],i]);

tabl[a1].Cells[4,b1]:=IntToStr(min[n[j]]);

f:=(min[n[j]]);

tabl[a1].Cells[5,b1]:=IntToStr(f+r);

tabl[a1].Cells[6,b1]:=IntToStr(f+r);

if h[i]=1 then min[i]:=strtoint(tabl[a1].Cells[6,b1]);

if h[i]>1 then begin

x:=x+1;

v[x]:=strtoint(tabl[a1].Cells[6,b1]);g[x]:=b1; end;

if  (m[i1]<>i)  then begin

k:=k+1;

i1:=i1+1;

m[i1]:=i; end;end;

if (StringGrid1.Cells[n[j],i]<> '0') and (i1=0) then begin

k:=k+1;

i1:=i1+1;

b1:=b1+1;

m[i1]:=i;

tabl[a1].RowCount:=b1+1;

tabl[a1].Height:=26*(b1+1);

tabl[a1].Cells[0,b1]:=StringGrid1.Cells[0,i];

tabl[a1].Cells[1,b1]:='('+IntToStr(i)+','+IntToStr(n[j])+')';

tabl[a1].Cells[2,b1]:=StringGrid1.Cells[n[j],0];

tabl[a1].Cells[3,b1]:=StringGrid1.Cells[n[j],i];

r:=StrToInt(StringGrid1.Cells[n[j],i]);

tabl[a1].Cells[4,b1]:=IntToStr(min[n[j]]);

f:=(min[n[j]]);

tabl[a1].Cells[5,b1]:=IntToStr(f+r);

tabl[a1].Cells[6,b1]:=IntToStr(f+r);

if h[i]=1 then min[i]:=strtoint(tabl[a1].Cells[6,b1]);

if h[i]>1 then begin

x:=x+1;

v[x]:=strtoint(tabl[a1].Cells[6,b1]);g[x]:=b1; end;end;end;

if h[i]>1 then begin

min[i]:=v[1];

for x:=1 to h[i]-1 do begin

if min[i]>v[x+1] then begin

min[i]:=v[x+1];

tabl[a1].Cells[6,g[x]]:='-';end;

if min[i]<v[x+1] then

tabl[a1].Cells[6,g[x+1]]:='-';

end;end;end;

b:=k;

c:=c+k;

n:=m;

q:=q+1;y:=false;

for i:=1 to b1 do begin

if tabl[a1].Cells[6,i]<>'-' then begin

min2:=strtoint(tabl[a1].Cells[6,i]);

min1[q]:=tabl[a1].Cells[0,i];y:=true;end;

if y=true then Break;end;

for i:=1 to b1 do

if (tabl[a1].Cells[6,i]<>'-') and (min2>strtoint(tabl[a1].Cells[6,i])) then begin

min2:=strtoint(tabl[a1].Cells[6,i]);

min1[q]:=tabl[a1].Cells[0,i];end;

end;

until c=StrToInt(Edit1.Text);

x:=1;

mal[1]:=StringGrid1.Cells[StrToInt(Edit1.Text),0];

for i:=1 to a1 do begin

x:=x+1;

mal[x]:=min1[i];end;

for i:=a1+1 downto 1 do

Form2.Memo1.Lines.Add(mal[i]);

Form2.Visible:=True;

Form2.Label3.Caption:='Длина  крайчайшего пути ='+tabl[a1].Cells[tabl[a1].ColCount-1,tabl[a1].rowCount-1];

end;

procedure TForm1.SpeedButton4Click(Sender: TObject);

begin

close;

end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);

begin

if StrToInt(Edit1.Text)>10 then Edit1.Text:='10';end;end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение Б - Формы программы