Автор работы: Пользователь скрыл имя, 21 Мая 2013 в 12:17, курсовая работа
Целью данной работы является построение математической модели, выбор метода и разработка алгоритма решения задачи, а также экспериментальная проверка и разработка рекомендаций по практическому использованию результатов решения транспортной задачи и определения стоимости транспортировки товара в зависимости от потребности в разных пунктах назначения и вместимости отдельных транспортных средств. В качестве методов решения данной задачи были выбраны: метод северо-западного угла, метод потенциалов и построение циклов.
Введение
1. Содержательное и формализованное описание задачи
2. Математическая модель задачи
3. Выбор метода и разработка алгоритма решения задачи
3.1 Получение начального базисного решения
3.2 Нахождение вводимой переменной. Метод потенциалов
3.3 Поиск выводимой переменной. Построение циклов
4. Программная реализация
5. Экспериментальная проверка и разработка рекомендаций по практическому использованию результатов
6. Руководство пользователя
Заключение
Библиографический список
Получили новое базисное решение (таблица 10).
Таблица 10 – Новое базисное решение.
300 |
350 |
50 | |
650 | |||
400 |
200 |
200 | |
100 |
Данное решение является оптимальным. Т.к. для четвертого пункта назначения мы вводили фиктивный маршрут, то туда не будет доставлено 100 единиц товара. Суммарные расходы на обслуживание всех пунктов назначения составят 3475 денежных единиц.
Если в написанную программу нижеописанным способом ввести исходные данные используемые в данном пункте, то, как можно наблюдать на рисунке 1, результаты работы программы полностью совпадают с результатами, полученными при решении задачи вручную. Это говорит о том, что написанная программа работает без ошибок.
Рисунок 1 – Результат работы программы
6 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ
Данная программа
Для входа в программу необходимо запустить файл transport.exe, после чего на экране появится главное окно программы (рисунок 2), в котором производится ввод данных.
Рисунок 2 – Главное окно программы
В левом верхнем углу находится кнопка «Задание», нажав на которую можно просмотреть задание к курсовой работе (рисунок 3).
Рисунок 3 – Окно задания
В главном окне имеется два поля для ввода: «Количество пунктов назначения» и «Количество маршрутов». Эти поля формируют размерность исходной транспортной матрицы. Введенные значения должны быть целого типа. Если это не так, или какое-либо из значений вообще не введено, то выдается сообщение об ошибке. Выполнение программы не продолжится, пока данные не будут введены корректно. После правильного введения размерности следует нажать кнопку «Применить», чтобы внести данные в программу.
Далее необходимо ввести значение потребностей каждого пункта назначения (число заказов, которое нужно доставить в каждый пункт) и вместимость каждого транспортного средства, а так же заполнить транспортную таблицу либо путем непосредственного ввода значений с клавиатуры, либо нажатием кнопки «Заполнить», которая формирует матрицу автоматически.
Выполнив вышеописанные действия, нужно нажать кнопку «Решить», после чего, начнется пошаговое выполнение итераций решения. Сначала в случае несбалансированной задачи происходит ее балансировка путем введения дополнительной строки или столбца. Затем находится оптимальное решение задачи, ход которого отображаемых в вспомогательном окне. Результат выводится в поле вывода результата, расположенном в нижней части главного окна программы как показано на рисунке 4.
Рисунок 4 – Выполнение решения задачи
ЗАКЛЮЧЕНИЕ
В результате выполнения курсовой работы была написана программа, решающая транспортные задачи по оптимизации распределения конечного числа маршрутов доставки товаров в конечное число пунктов назначения с различными начальными данными. Для реализации решения задачи были выбраны наиболее удобные для этого методы: метод северо-западного угла и метод потенциалов.
Для программной реализации задачи в силу своей удобности была выбрана современная среда визуального программирования Borland Delphi 7, с помощью которой был реализован составленный алгоритм решения выданной задачи в удобном для дальнейшего практического применения виде.
БИБИЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ Б
Листинг программного модуля
unit intr;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
Grids, ExtCtrls, StdCtrls, Buttons, Db, DBTables;
type
TForm1 = class(TForm)
tab1: TStringGrid;
potreb: TStringGrid;
capacity: TStringGrid;
BitBtn1: TBitBtn;
Button1: TButton;
Button2: TButton;
Label5: TLabel;
Label6: TLabel;
Label8: TLabel;
Memo1: TMemo;
Image1: TImage;
Label2: TLabel;
Label1: TLabel;
prdl: TEdit;
spr: TEdit;
Button3: TButton;
Label3: TLabel;
procedure BitBtn1Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
function read_data(): bool;
procedure balancing;
procedure north_west;
procedure search_uv();
procedure maxnotbas(var max:real;var xi,yi:integer);
procedure create_matr();
end;
var
Form1: TForm1;
implementation
uses task, dec, otv;
{$R *.DFM}
var
c: array [1..100, 1..100] of real;
ch: array [1..6] of char;
spl, dmd: array [1..100] of real;
u,v: array [1..100] of real;
sspl,sdmd:real;
cycle,x: array [1..100, 1..100] of string;
xnb: array [1..100, 1..100] of real;
rw1,bn,ed,t,it,jt,it0,jt0,cl,
way:string;
ways: array [1..100] of string;
step: real;
procedure cross(x,x1,y,y1:integer);
var n,m:integer;
begin
for n:=y to y1 do
for m:=x to x1 do
if not (cycle[n,m]='~') then cycle[n,m]:='~'+cycle[n,m] else cycle[n,m]:='~';
end;
//поиск узлов
procedure search(q:string);
var i,j:integer;
begin
j:=jt; i:=it;
if q='up' then
for i:=1 to it-1 do
if not(x[i,j]='------------') then begin way:='up'; cross(j,j,i,it); it:=i; break;end;
if q='right' then
for j:=cl downto jt+1 do
if not(x[i,j]='------------') then begin way:='right'; cross(jt,j,i,i); jt:=j; break;end;
if q='down' then
for i:=rw downto it+1 do
if not(x[i,j]='------------') then begin way:='down'; cross(j,j,it,i); it:=i; break;end;
if q='left' then
for j:=1 to jt-1 do
if not(x[i,j]='------------') then begin way:='left'; cross(j,jt,i,i); jt:=j; break;end;
end;
procedure TForm1.BitBtn1Click(Sender: TObject);
var
z,ind,i,j: integer;
ci,ri: byte;
s: string;
cd:integer;
bl,bln: boolean;
min,max,tmp,r:real;
zikl:integer;
uzli: array [1..100,1..2] of integer;
begin
if(not read_data()) then exit;
balancing();
showmessage('Шаг №'+floattostr(step));
step:=step+1;
showmessage('Начальное решение');
north_west();
form3.Show();
create_matr();
repeat
search_uv();
//проверка оптимальности
it:=1; jt:=1;
maxnotbas(max,it,jt);
it0:=it; jt0:=jt;
if max<=0 then break;
x[it,jt]:='X'; //вводимая переменная
//-----------
for j:=1 to cl do
for i:=1 to rw do
form3.sg2.Cells[j-1,i-1]:=
create_matr();
it:=-1; jt:=-1;
for i:=1 to 4 do begin
way:='non';
it:=it0;jt:=jt0;
if(i=1) then search('up');
if(i=2) then search('down');
if(i=3) then search('left');
if(i=4) then search('right');
if(way='non') then continue;
zikl:=1;
ways[1]:='first';
uzli[1][1]:=it;
uzli[1][2]:=jt;
repeat
it:=uzli[zikl][1]; jt:=uzli[zikl][2];
s:=way;
if(ways[zikl]='first') then begin
if((way='up')or(way='down')) then begin way:='none'; search('left'); end
if(way='none') then begin ways[zikl]:='second'; way:=s; end
else begin
ways[zikl]:='second';
zikl:=zikl+1;
uzli[zikl][1]:=it;
uzli[zikl][2]:=jt;
ways[zikl]:='first';
end;
end;
if(ways[zikl]='second') then begin
if((way='up')or(way='down')) then begin way:='none'; search('right'); end
if(way='none') then ways[zikl]:='end'
else begin
ways[zikl]:='end';
zikl:=zikl+1;
uzli[zikl][1]:=it;
uzli[zikl][2]:=jt;
ways[zikl]:='first';
end;
if(ways[zikl]='end') then begin
if((s='up')or(s='down')) then way:='right'
else way:='down';
if(zikl=1) then break
else zikl:=zikl-1;
end;
until (it=it0) and (jt=jt0);
if((it=it0)and(jt=jt0)) then break;
end;
//Найдем выводимую переменную
for i:=1 to rw do
for j:=1 to cl do cycle[i,j]:='';
min:=32000;
if(way='non') then min:=0
else
for i:=1 to zikl-1 do
if((i mod 2)=1) then begin
tmp:=strtofloat(x[uzli[i][1],
if(tmp<min) then min:=tmp;
end;
x[it0][jt0]:=floattostr(min);
bln:=false;
if(way<>'non') then
for i:=1 to zikl-1 do begin
tmp:=strtofloat(x[uzli[i][1],
if((i mod 2)=0) then
begin tmp:=tmp+min; cycle[uzli[i][1],uzli[i][2]]:=
else begin tmp:=tmp-min; cycle[uzli[i][1],uzli[i][2]]:=
x[uzli[i][1],uzli[i][2]]:=
if(((i mod 2)=1)and(tmp=0)and(not bln)) then begin//Вывод базисной переменной
x[uzli[i][1],uzli[i][2]]:='---
bln:=true;
end;
for j:=1 to cl do
for i:=1 to rw do
form3.sg2.Cells[j-1,i-1]:=
showmessage('Шаг №'+floattostr(step));
step:=step+1;
create_matr();
until false;
form3.Visible:=true;
//ответ
for i:=1 to rw1 do begin
s:=inttostr(i)+'-е
for j:=1 to cl do
if not (x[i,j]='------------') then begin s:=s+inttostr(j)+'-й '; tmp:=tmp+1;
r:=r+strtofloat(x[i,j])*c[i,j]
if tmp>1 then s:=s+'пункты ' else s:=s+'пункт ';
s:=s+' ('+inttostr(i)+'-й пункт).';
form1.Memo1.Lines.Append(s);
end;
tmp:=0;
if rw1<rw then begin
for j:=1 to cl do if not (x[rw,j]='------------')
then tmp:=tmp+strtofloat(x[rw,j]);
form1.Memo1.Lines.Append('Не доставлено '+floattostr(tmp)+' единиц товара.');
end;
s:='Затраты составят '+floattostr(r)+' денежных единиц.';
form1.Memo1.Lines.Append(s);
form1.Memo1.Lines.Append('----
end;
// Cоздание окон и таблиц
procedure TForm1.Button3Click(Sender: TObject);
var i,j:integer;
s:string;
begin
if (form1.prdl.text='')or(form1.
MessageDLG('Проверьте правильность введенных данных!', mtError, [mbOK], 0);
val(form1.prdl.text,cl,t);
val(form1.spr.text,rw,t);
if (cl>7)or(rw>7) then begin beep;
MessageDLG('Введите размерность поменьше!', mtError, [mbOK], 0);
exit;end;
form1.potreb.colcount:=cl;
form1.capacity.rowcount:=rw;
step:=1;
form1.bitbtn1.Enabled:=true;
Button2.Enabled:=true;
form1.capacity.Enabled:=true;
form1.potreb.Enabled:=true;
form1.tab1.Enabled:=true;
form1.Memo1.Enabled:=true;
//Очистка таблиц
for t:=0 to 100 do
for i:=0 to 100 do begin
form1.tab1.Cells[i,t]:='';
form3.sg1.Cells[i,t]:='';
end;
//Надписи в таблице
for t:=1 to rw do begin
str(t,s);
form1.tab1.Cells[0,t]:=s;
form3.sg1.Cells[0,t]:=s;
end;
ch[1]:='A'; ch[2]:='B'; ch[3]:='C';
ch[4]:='D'; ch[5]:='E'; ch[6]:='F';
for t:=0 to cl do begin
form1.tab1.Cells[t,0]:=ch[t];
form3.sg1.Cells[t,0]:=ch[t];
end;
form1.tab1.Cells[0,0]:='';
form3.sg1.Cells[0,0]:='';
end;
//defaulte
procedure TForm1.Button2Click(Sender: TObject);
var i,j:integer;
begin
step:=1;
c[1,1]:=1.5; c[1,2]:=2.5; c[1,3]:=1; c[1,4]:=2;
c[2,1]:=2; c[2,2]:=3; c[2,3]:=2; c[2,4]:=1.5;
c[3,1]:=1; c[3,2]:=1.5; c[3,3]:=2.5; c[3,4]:=3;
for t:=1 to cl do
for i:=1 to rw do form1.tab1.Cells[t,i]:=
spl[1]:=700; spl[2]:=650; spl[3]:=800;
dmd[1]:=400; dmd[2]:=500; dmd[3]:=350; dmd[4]:=1000;
for t:=1 to rw do form1.capacity.Cells[0,t-1]:=
for t:=1 to cl do form1.potreb.Cells[t-1,0]:=
end;
function TForm1.read_data():bool;
var i,j: integer;
begin
try
for i:=1 to rw do
for j:=1 to cl do
c[i,j]:=strtofloat(form1.tab1.
sspl:=0;
for i:=1 to rw do begin
spl[i]:=strtofloat(form1.
sspl:=sspl+spl[i];
end;
sdmd:=0;
for i:=1 to cl do begin
dmd[i]:=strtofloat(form1.
sdmd:=sdmd+dmd[i];
end;
read_data:=true;
except on EConvertError do
begin
MessageDLG('Проверьте
правильность введенных данных!
read_data:=false;
exit;
end;
end;
end;
//проверка сбалансированности
procedure TForm1.balancing();
var i,j: integer;
begin
rw1:=rw;
if sspl>sdmd then begin
showmessage('Задача не сбалансирована! Добавляем столбец.');
cl:=cl+1;
for i:=1 to rw do begin form1.tab1.Cells[cl,i]:='0'; x[i,cl]:='0'; end;
form1.tab1.Cells[cl,0]:=ch[cl]
form3.sg1.Cells[cl,0]:=ch[cl];
dmd[cl]:=sspl-sdmd;
form1.potreb.colcount:=cl;
form1.potreb.cells[cl-1,0]:=
end;
if sspl<sdmd then begin
showmessage('Задача не сбалансирована! Добавляем строку.');
rw1:=rw;
rw:=rw+1;
for i:=1 to cl do begin form1.tab1.Cells[i,rw]:='0'; x[rw,i]:='0'; end;
form1.tab1.Cells[0,rw]:=
form3.sg1.Cells[0,rw]:=
spl[rw]:=sdmd-sspl;
form1.capacity.rowcount:=rw;
form1.capacity.cells[0,rw-1]:=
end; end;
//начальное базисное решение
procedure TForm1.north_west();
var
ci,ri: byte;
i,j: integer;
tmp:real;
begin
for i:=1 to rw+1 do
for j:=1 to cl+1 do x[i,j]:='------------';