Курсовая работа: Транспортная задача по критериям стоимости и времени
w[i]:=5;
d[j]:=-1;
end;
end;
For i:=0 to length(d)-1 do
if d[i]=-1 then
for j:=0 to length(w)-1 do
z[j,i]:=z[j,i]+abs(min);
for i:=0 to Length(w)-1 do
if w[i]=-1 then
for j:=0 to length(d)-1 do
z[i,j]:=z[i,j]-abs(min);
err:=true;
i:=0;j:=0;
Repeat
j:=0;
Repeat
if z[i,j]<0 then
err:=false;
j:=j+1;
until (err=False)or(j=Length(z[1]));
i:=i+1;
until (err=false)or(i=Length(z));
end;
procedure Cikle (l,r:integer ; var x:Tmatr);
var i,j,k,min:integer;
s,q,m,n:Tmatr;
kon:boolean;
begin
//Добавляем на соответствующее место фиктивную перевозку
x[l,r]:=-2;
Setlength(s,Length(x),Length(x[1]));
For i:=0 to Length(x)-1 do
For j:=0 to Length(x[1])-1 do
s[i,j]:=x[i,j];
//ищем цикл в матрице
Repeat
kon:=true;
for i:=0 to length(s)-1 do
begin
k:=0;
For j:=0 to length(s[1])-1 do
if s[i,j]<>0 then
k:=k+1;
if k=1 then
begin
for j:=0 to length(s[1])-1 do
s[i,j]:=0;
kon:=false;
end;
end;
for i:=0 to length(s[1])-1 do
begin
k:=0;
For j:=0 to length(s)-1 do
if s[j,i]<>0 then
k:=k+1;
if k=1 then
begin
for j:=0 to length(s)-1 do
s[j,i]:=0;
kon:=false;
end;
end;
until kon=true;
k:=0;
//Записываем элементы цикла в масив
For i:=0 to Length(s)-1 do
for j:=0 to Length(s[1])-1 do
if s[i,j]<>0 then
k:=k+1;
SetLength(q,k,3);
k:=0;
For i:=0 to Length(s)-1 do
for j:=0 to Length(s[1])-1 do
If s[i,j]<>0 then
begin
q[k,0]:=s[i,j];
q[k,1]:=i;
q[k,2]:=j;
k:=k+1;
end;
//Разделяем на четные и нечетные
Setlength(n,Round(k/2),3);
Setlength(m,Round(k/2),3);
n[0,0]:=q[0,0];
n[0,1]:=q[0,1];
n[0,2]:=q[0,2];
q[0,0]:=0;
For j:=0 to length(n)-1 do
begin
i:=0;
kon:=false;
repeat
if i<=Length(q)-1 then
begin
If (q[i,0]<>0)and(q[i,1]=n[j,1]) then
begin
m[j,0]:=q[i,0];
m[j,1]:=q[i,1];
m[j,2]:=q[i,2];
q[i,0]:=0;
kon:=true;
end;
i:=i+1;
end
else kon:=true;
until kon=true;
i:=0;
kon:=false;
repeat
if i<=Length(q)-1 then
begin
If (q[i,0]<>0)and(q[i,2]=m[j,2]) then
begin
n[j+1,0]:=q[i,0];
n[j+1,1]:=q[i,1];
n[j+1,2]:=q[i,2];
q[i,0]:=0;
kon:=true;
end;
i:=i+1;
end
else kon:=true;
until kon=true;
end;
i:=0;
repeat
if (n[i,0]=s[l,r])and(n[i,1]=l)and(n[i,2]=r)then
kon:=false
else kon:=true;
i:=i+1;
until (i>length(n)-1)or(kon=false);
if kon=true then
for i:=0 to length(n)-1 do
begin
q[i,0]:=m[i,0];
q[i,1]:=m[i,1];
q[i,2]:=m[i,2];
m[i,0]:=n[i,0];
m[i,1]:=n[i,1];
m[i,2]:=n[i,2];
n[i,0]:=q[i,0];
n[i,1]:=q[i,1];
n[i,2]:=q[i,2];
end;
min:=m[0,0];
kon:=false;
i:=0;
//Ищем минимальный среди нечетных
repeat
if m[i,0]<min then
begin
min:=m[i,0];
end;
if m[i,0]=-2 then
begin
m[i,0]:=0;
min:=0;
kon:=true;
end;
i:=i+1;
until (kon=true)or(i>=length(m));
kon:=false;
i:=0;
repeat
if m[i,0]=min then
begin
m[i,0]:=0;
kon:=true;
end;
i:=i+1;
until (kon=true)or(i>=length(m));
if min>0 then
begin
for i:=0 to length(m)-1 do
if m[i,0]=min then m[i,0]:=-2
else
if m[i,0]<>0 then
m[i,0]:=m[i,0]-min;
for i:=0 to Length(n)-1 do
if n[i,0]=-2 then n[i,0]:=min
else n[i,0]:=n[i,0]+min;
end;
for i:=0 to Length(m)-1 do
begin
x[m[i,1],m[i,2]]:=m[i,0];
x[n[i,1],n[i,2]]:=n[i,0];
end;
end;
Procedure Dooptimiz(var max2:integer; var x:Tmatr);
var i,j,k,l,r,max:integer;
kon,err:boolean;
q:TMatr;
s:Tmatr;
begin
kon:=true;
SetLength(s,Length(t),Length(t[1]));
max2:=0;
for i:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
s[i,j]:=x[i,j];
Repeat
err:=true;
max:=0;k:=0;
SetLength(q,0,0);
for i:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
If (s[i,j]>0)and(t[i,j]>max) then
begin
max:=t[i,j];
l:=i;
r:=j;
end;
for i:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
If (z[i,j]=0)and(s[i,j]=0) then
begin
SetLength(q,k+1,2);
q[k,0]:=i;
q[k,1]:=j;
inc(k);
end;
for i:=0 to Length(q)-1 do
If t[q[i,0],q[i,1]]<max then
else
begin
q[i,0]:=-1;
q[i,1]:=-1;
end;
i:=0;
kon:=false;
Repeat
if q[i,0]>=0 then
begin
Cikle(q[i,0],q[i,1],s);
if s[l,r]=0 then
begin
kon:=true;
err:=false;
for k:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
x[k,j]:=s[k,j];
end
else
begin
q[i,0]:=-1;
q[i,1]:=-1;
for k:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
s[k,j]:=x[k,j];
end;
end;
inc(i);
Until (i>length(q)-1)or(kon=true);
Until (err=true)and(kon=false);
max2:=0;
for i:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
If (s[i,j]>0)and(t[i,j]>max2) then
max2:=t[i,j];
if max>max2 then
begin
for i:=0 to Length(t)-1 do
For j:=0 to Length(t[1])-1 do
x[i,j]:=s[i,j];
end;
end;
procedure TForm4.Button1Click(Sender: TObject);
var i,j,l,r,min,max:integer;
err:boolean;
begin
Opornplan(StringGrid1,x,z);
StringGrid1.RowCount:=Length(x[1]);
StringGrid1.ColCount:=Length(x);
StringGrid2.RowCount:=Length(x[1]);
StringGrid2.ColCount:=Length(x);
min:=z[0,0];
l:=0;
r:=0;
For i:=0 to length(z)-1 do
for j:=0 to length(z[1])-1 do
if z[i,j]<min then
begin
min:=z[i,j];
l:=i;
r:=j;
end;
if Min<0 then
begin
Cikle(l,r,x);
Repeat
Vicherk(z,err);
If err=false then
begin
min:=z[0,0];
l:=0;
r:=0;
For i:=0 to length(z)-1 do
for j:=0 to length(z[1])-1 do
if z[i,j]<min then
begin
min:=z[i,j];
l:=i;
r:=j;
end;
Cikle(l,r,x);
end;
until err=true;
end;
Dooptimiz(max,x);
r:=0;l:=0;
for i:=0 to StringGrid1.RowCount-1 do
begin
Memo1.Lines.add('Из пункта производства '+Form5.StringGrid1.Cells[0,i+1]+' в :');
for j:=0 to StringGrid1.ColCount-1 do
if (x[j,i]>0)and(c[j,i]<100)then
begin
r:=r+x[j,i]*c[j,i];
Memo1.Lines.add(' '+Form5.StringGrid2.Cells[0,j+1]+' '+IntToStr(x[j,i])+' ед. продукции');
end;
end;
Label1.Caption:=Label1.Caption+IntToStr(r);
label2.Caption:=label2.Caption+IntTostr(max);
for i:=0 to StringGrid1.ColCount-1 do
for j:=0 to StringGrid1.RowCount-1 do
StringGrid1.Cells[i,j]:=IntToStr(x[i,j]);
for i:=0 to StringGrid1.ColCount-1 do
for j:=0 to StringGrid1.RowCount-1 do
StringGrid2.Cells[i,j]:=IntToStr(z[i,j]);
button1.Enabled:=false;
end;
Примечания:
1. В качестве фиктивной перевозки используется " -2", т.к. для сохранения и работы с матрицами используется тип Integer.
2. Цель использования этого типа: уменьшение объемов памяти требуемой для запуска приложения, и ,как следствие, возможность использования этой программы на маломощных машинах.
7. Руководство пользователя
7.1 Системные требования
Процессор: Pentium I или аналогичный AMD 400 MHz и выше
ОЗУ: 64 Мб и более
ОС: Windows 98, 2000, ХР
7.2 Описание возможностей
транспортный издержка оптимизация перевозка
Данная программа предназначена для решения транспортной задачи методом минимального элемента и методом потенциалов. Программа оптимизирует транспортные перевозки, тем самым сокращает издержки и время перевозок. Главным критерием оптимизации является стоимость, поэтому, сначала минимизируется стоимость перевозок, а затем время. Входными данными для программы являются: количество производителей и потребителей, их названия, количество производимого и/или потребляемого продукта в каждом из пунктов, транспортные расходы на перевозку одной единицы продукции из каждого пункта производства в каждый пункт потребления, время, затрачиваемое на перевозку груза из каждого пункта производства в каждый пункт потребления
В программе есть "Инженерный" режим работы, с помощью которого можно просмотреть все этапы вычисления. Этот режим предназначен для специалистов в данной области. Включить его можно, поставив галочку при заполнении начальных данных.
7.3 Использование
Для начала работы с программой запустите файл kurs.exe.
Выберете из двух вариантов: открыть уже заполненные таблицы или рассчитать новый план.
В появившемся окне выберете число пунктов потребления и производства
В следующем окне заполните таблицы, состоящие из 2 столбцов: название и количество. В поле название впишите название пункта, а в поле количество – количество производимого или потребляемого продукта.
В появившемся окне, необходимо заполнить таблицы стоимости перевозок и временных затрат, так же в этом окне пользователь может выбрать "Инженерный" режим работы. В этом окне в левом нижнем угу находится кнопка Сохранить, которая служит для сохранения всех заполненных таблиц. Если пользователь введет неверные данные, то эти данные будут подсвечены.
В последнем окне нажмите кнопку Рассчитать.
7.4 Использование инженерного режима
В данном режиме отображаются таблицы Х(k), C(k). При нажатии на кнопку "Далее" производится переход на следующую итерацию решения. При достижении оптимального решения, эта кнопка станет недоступной, но можно будет нажать кнопку "Дооптимизация". При нажатии на нее программа дооптимизирует план по времени, если это возможно.
8. Решение задачи курсовой работы на ПЭВМ по исходным данным индивидуального варианта
Исходные данные
Первая итерация
Замечание: "-2" - фиктивная перевозка.
Последняя итерация
Результат
9. Список использованной литературы
1. Зайченко, Ю.П. Исследование операций: учебное пособие / Ю.П.Зайченко. – 2-е изд. – Киев: Вища школа, 1979. – 392 с.
2. Куцый, Н.Н. Математические методы системного анализа и теория принятия решений: пособие по курсовой работе / Н.Н. Куцый. – Иркутск: изд-во Иркутск гос. технич. ун-та, 2008. – 79 с.
