Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра Автоматизированных систем
ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту по дисциплине
Теория принятия решения
Иркутск 2009г.
Содержание:
1. Постановка задачи
2. Обоснование математической модели
3. Краткие сведения о методе решения задачи
4. Проверка достоверности полученных результатов
5. Алгоритм решения задачи
6. Листинг программы, реализующий алгоритм задачи
7. Руководство пользователя
7.1Системные требования
7.2Описание возможностей
7.3Использование
7.4Использование инженерного режима
8. Решение задачи курсовой работы на ПЭВМ по исходнымданным индивидуального варианта
9. Список использованной литературы
/>/>1. Постановка задачи
Имеется /> пунктовотправления, в каждом из которых сосредоточено определенное количество единицоднородного продукта, предназначенного к отправке: в первом пункте имеется /> единиц этого продукта, вовтором — /> единиц, в />м пункте /> единиц, и, наконец, в />м пункте /> единиц продукта. Этотпродукт следует доставить в /> пунктовназначения (потребления), причем в первый пункт назначения следует доставить />единиц продукта, во второй- /> единиц, в />й пункт />единиц, и, наконец, в />й пункт /> единиц продукта.
Каждый пункт отправления соединен с каждым пунктом назначения некоторыммаршрутом (число таких маршрутов />),причем известна удельная стоимость /> перевозкиодной единицы продукта из />гопункта отправления в />й пунктназначения. Общая стоимость перевозки по любому маршруту пропорциональнаколичеству перевозимого продукта. Известно также время /> перевозки продукта из />го пункта отправления в />й пункт назначения, причемэто время не зависит от количества перевозимого груза.
Удельные стоимости /> и времяперевозок /> приведены в таблице, приэтом:
1) на пропускные способности коммуникаций ограничения не накладываются;
2) /> и /> - количество условныхединиц продукта;
3) в верхних отделениях клеток таблицы помещены удельные стоимости /> в рублях, а в нижних — время перевозок /> в часах.
/>
Составить план, минимизирующий общую стоимость перевозок; определитьуровень временных затрат при этом плане; произвести, если это возможно,дооптимизацию по времени. Поставленную задачу решить методом потенциалов, использовавдля нахождения начального опорного плана метод минимального элемента.
Разработанный программный продукт должен обрабатывать числовые значенияиз заданного диапазона:
а) количество пунктов отправления может быть или 6, или 7, или 8;
б) количество пунктов отправления может быть или 7, или 8, или 9;
в) количество единиц продукта, предназначенного к отправке может бытьвзято из диапазона />;
г) количество единиц продукта, которое следует доставить в пунктыназначения может быть взято из диапазона />;
д) удельные стоимости могут быть назначены из диапазона />;
е) значения времени перевозок могут быть назначены из диапазона />
/>2. Обоснованиематематической модели
В пункте /> производится />единиц однородногопродукта. В пункте /> требуется /> единиц этого продукта.
Пусть /> — количество единицпродукта, перевозимого из пункта />в пункт />, а затраты на перевозку /> — материальные, /> — временные. Необходимоопределить множество переменных />(/>; />), удовлетворяющихусловиям:
/>, />
/>, />
и таких, что целевая функция /> достигаетминимума.
· Так как во всехпунктах производства не должно остаться не вывезенного товара, необходимоусловие />, />. Оно гарантирует полный вывоз продукта из всех пунктовпроизводства
· Так как во всехпунктах потребления товара необходимо доставить согласно спросу, необходимоусловие />, />. Оно означает полное удовлетворение спроса во всех пунктахпотребления.
· Количество едиництовара, перевозимого из пункта />в пункт />, не может бытьотрицательным, следовательно, необходимо ввести условие неотрицательности/> (/>; />)
· Так как нам необходимоминимизировать суммарные материальные транспортные издержки при перевозе всеготовара из пунктов производства в пункт потребления, целевая функция будет иметьвид:
/>
Для дооптимизации по времени необходимо использовать следующую целевуюфункцию:
· />, при этом необходимо учитывать, что стоимостьперевозок не должна изменяться.
/>/>3. Краткие сведения о методе решения задачи Сведениеоткрытой модели транспортной задачи к открытой
В некоторых случаях модель транспортной задачиполучается открытой, т.е. />возможны2 случая:
1. />, тогда вводят фиктивный пункт потребления />, а дополнительный столбикматрицы С заполняют очень большими числами (М). После того, как решениеполучено, все перевозки xi,n+1 (/>), воптимальном плане Хk считают равными нулю.
2. />, тогда вводят фиктивный пункт производства />, а дополнительную строкуматрицы С заполняют очень большими числами (М). После того, как решениеполучено, все перевозки xm+1,j (/>), в оптимальном плане Хk считают равными нулюМетод минимального элемента
Используют для нахождения начального опорного плана Т-задачи.
1. Элементы матрицы Снумеруют, начиная от минимального в порядке возрастания, а затем в этом жепорядке заполняют матрицу Х0:
Допустим, уже проделано k шагов метода, тогда среди незаполненной части матрицыX0отыскиваем элемент с минимальным порядковым номером.
Пусть элементом с минимальным порядковым номером оказался
/>.
Возможны три случая:
а) если />, то /> и всю оставшуюся i-ю строку заполняют нулями, а />,/>;
б) если />, то /> и весь оставшийся j-й столбец заполняют нулями, а />,/>;
в) если />, то /> и оставшийся j-й столбец и i-ю строку заполняютнулями, а />, />.
На этом один шаг метода заканчивается.
Далее этот процесс повторяют с незаполненной частью матрицы X0.Метод потенциалов:
Теорема. Если план /> транспортнойзадачи является оптимальным, то ему соответствует система из /> чисел /> , удовлетворяющих условиям/> для />
Числа /> называются потенциаламисоответственно />го поставщика и />го потребителя.
Для оптимального плана Т-задачи необходимо выполнение условий:
каждой занятой клетке в распределительной таблице соответствует суммапотенциалов, равная тарифу этой клетки, т.е. />;
каждой свободной клетке соответствует сумма потенциалов, не превышающаятарифа этой клетки, т.е. />.
Если хотя бы одна незанятая клетка не удовлетворяет второму условию, тоопорный план является неоптимальным и его можно улучшить, переместив в даннуюклетку некоторое количество единиц груза
Данная теорема носит название теоремы о потенциалах. На ней основанспециальный метод решения ТЗ, названный методом потенциалов.
Для применения метода потенциалов необходимо, чтобы заранее построенныйопорный план методом северо-западного угла (или другим методом) являлсяневырожденным, т.е. число базисных элементов равнялось />. Если план являетсявырожденным, то добавляют перевозку бесконечно малой величины ε. При этомсмотрят, чтобы план не перестал быть опорным.
Метод потенциалов позволяет, исходя из некоторого опорного планаперевозок, найти за конечное число итераций решение транспортной задачи.
Общая схема метода.
В начальном опорном плане каждому пункту ставят в соответствие некотороечисло, называемое его предварительным потенциалом. Предварительные потенциалывыбирают так, чтобы их разность для любой пары пунктов Аi и Вj,связанных основной коммуникацией, была равна сi,j. Если окажется,что разность предварительных потенциалов для всех других коммуникаций не превосходит/>, то данный план перевозок- оптимальное решение задачи. В противном случае указывают способ улучшенияопорного плана Т-задачи.
Описание алгоритма метода потенциалов. Алгоритм складывается изпредварительного этапа и конечного числа однотипных итераций.
Предварительный этап. С помощью известного метода определяют начальныйопорный план Х0и вычисляют предварительные потенциалы />.
Вычисление предварительных потенциалов производят так. По найденномуплану Х0строят схему Т-задачи из основных коммуникаций плана.
Поскольку на выполнение условий оптимальности плана оказывают влияниелишь разности />, то за началоотсчета (нуль) можно принять потенциал любого из пунктов (как правило, за нульпринимается />).
После того как потенциалы всех пунктов найдены, строят матрицу
/>
Если матрица C1 не содержит отрицательных элементов, то Х0 — оптимальный план. В противном случае Х0 — неоптимальный план,который может быть улучшен. Тогда переходят к выполнению однотипных итераций.Цель (k + 1)-й итерации — построение матрицы Сk, а также либоустановление оптимальности плана Хk, либо нахождение болееэкономичного плана Хk+1.
Каждая итерация, кроме первой, где отсутствует первый этап, состоит издвух этапов.
Первый этап.Вычисляют матрицу Ck+1. Преобразование матрицы Ck вматрицу Ck+1 состоит в следующем. Выбирают наибольший по модулюотрицательней элемент матрицы Ck. Выделяют строку, в которойсодержится этот элемент, а множество существенных элементов этой строки. Приэтом Xk-существенными элементами называют те элементы матрицы Ck,которые отвечают базисным перевозкам плана Xk.
Затем выделяют столбцы матрицы Ck, которые содержат элементымножества Xk-существенных элементов, которые находятся в столбцахматрицы Ck и отличны от элементов множества.
Процесс выделения продолжают до тех пор, пока очередное множество неокажется пустым. Поскольку каждые строка и столбец не могут быть выделеныдважды, то весь процесс заканчивается за m+n-1 шагов.
Далее строят матрицу Ck+1. Для этого наибольший по модулюотрицательней элемент матрицы Ck прибавляют ко всем выделеннымстолбцам и вычитают из всех выделенных строк матрицы Ck. При этомвсе выделенные Xk-существенные элементы матрицы Ckостаются равными нулю.
Если все элементы матрицы Ck+1 окажутся неотрицательными, то Xk—оптимальный план, и на этом процесс заканчивается. В противном случае переходятко второму этапу.
Второй этап.Производят улучшение плана Хk. Выбирают наибольший помодулю отрицательный элемент матрицы Ck+1. Затем составляют,применив, например метод вычеркивания, цепочку из положительных элементов планаXk, которая замыкается на выбранном элементе.
После того как цепочка построена, в ней находят минимальный нечетный попорядку следования элемент и прибавляют его ко всем четным элементам цепочки ивычитают из всех нечетных элементов. Остальные элементы Xk оставляютбез изменения.
Новый план Xk+1.построен. Он является опорным, так как числоего ненулевых перевозок не изменилось.
/>4.Проверка достоверности полученных результатов
В общем случае проверка полученных результатов после очередной итерациивычисления осуществляется следующим образом:
Целевая функция считается 2 способами:/>/>
1. />
2. Пусть минимальным элементомматрицы С(k) оказалсяэлемент с индексами μ, κ, тогда значение целевой функции на этом шагебудет равно:
/>
Если значения не совпадают то, то на экран выводится ошибка.
Если условие выполняется, то полученный результат (на данной итерации)достоверен.
При выполнении дооптимизации единственным подтверждениемправильности результатов может служить уменьшение целевой функции
/>.
5. Алгоритм решения задачи
/>1. Проверка правильности вводаданных.
2. Проверка условия баланса.
3. Построение начального опорногоплана Х(0) методом минимального элемента.
4. Проверка плана на вырожденность,если нужно добавляем фиктивные перевозки.
5. Расчет начальных потенциалов изаполнение матрицы С(1).
6. Поиск минимального элемента вматрице С(1).
7. Если этот элемент меньше нуля, тозаменяем нулевой элемент, соответствующий минимальному в С(1), вплане Х(0) на фиктивную перевозку, иначе на пункт 12.
8. Производим процедуру вычеркивания.
9. Оставшиеся не вычеркнутымиэлементы разделяем на четные и нечетные, учитывая, что добавленный элементпринадлежит к четным.
10. Находим минимальный нечетныйэлемент и прибавляем его ко всем четным и отнимаем от нечетных элементов.Причем, если минимальных элементов окажется 2 или более, то один из нихобнуляем, а остальные делаем фиктивными. В итоге получаем план Х(1).
11. Производим процедуру вычеркивания.Получаем матрицу С(2).
12. Проверяем матрицу С(2)на наличие отрицательных элементов. Если такие элементы присутствуют, топовторяем пункты с 5 по11.
13. Если во время решениядостоверность результатов нарушается, прекращаются дальнейшие вычисления,пользователю выдается информация об ошибке.
14. Дооптимизация по времени.
14.1. Ищем отличный от нуля элемент вматрице X(k), которому соответствует наибольший элемент матрицы Т=tmax.
14.2. Ищем в матице С(k) нули соответствующие такимнулям в матрице X(k), что соответствующие им элементы матрицы Т меньше tmax.
14.3. Если в предыдущем пункте нашелсяхоть один ноль, то производим процедуры пунктов 7-10.
14.4. Переходим к пункту 14.1.
15. Вывод результатов.
6. Листингпрограммы, реализующий алгоритм задачи
const
color=TColor(Clred);
var i,j,v,w:integer;
err,kon:boolean;
str:String;
begin
kon:=true;
Label3.Caption:='';
for j:=1 to StringGrid1.RowCount-1 do
if(StringGrid1.Cells[1,j]='')or(StringGrid1.Cells[0,j]='')then
kon:=false;
for j:=1 to StringGrid2.RowCount-1 do
if(StringGrid2.Cells[1,j]='')or(StringGrid2.Cells[0,j]='')then
kon:=false;
if kon=true then
begin
err:=true;
for j:=1 to StringGrid1.RowCount-1 do
begin
Str:=Trim(StringGrid1.Cells[1,j]);
Recurs(str,1,err);
If err=false then
begin
StringGrid1.Canvas.Brush.color := color;
StringGrid1.canvas.fillRect(StringGrid1.CellRect(1,j));
StringGrid1.canvas.TextOut(StringGrid1.CellRect(1,j).Left,StringGrid1.CellRect(1,j).Top,StringGrid1.Cells[1,j]);
Label3.Caption:= ’Выделенные значения не верны';
end;
Err:=true;
end;
for j:=1 to StringGrid2.RowCount-1 do
begin
Str:=Trim(StringGrid2.Cells[1,j]);
Recurs(str,1,err);
If err=false then
begin
StringGrid2.Canvas.Brush.color := color;
StringGrid2.canvas.fillRect(StringGrid2.CellRect(1,j));
StringGrid2.canvas.TextOut(StringGrid2.CellRect(1,j).Left,StringGrid2.CellRect(1,j).Top,StringGrid2.Cells[1,j]);
Label3.Caption:= ‘Выделенные значения не верны';
end;
Err:=true;
end;
for j:=1 to StringGrid1.RowCount-1 do
begin
Str:=Trim(StringGrid1.Cells[1,j]);
Recurs(str,1,err);
end;
for j:=1 to StringGrid2.RowCount-1 do
begin
Str:=Trim(StringGrid2.Cells[1,j]);
Recurs(str,1,err);
end;
If err=true then
begin
for j:=1 to StringGrid1.RowCount-1 do
begin
If(StrToInt(trim(StringGrid1.Cells[1,j]))190)
then
begin
StringGrid1.Canvas.Brush.color := color;
StringGrid1.canvas.fillRect(StringGrid1.CellRect(1,j));
StringGrid1.canvas.TextOut(StringGrid1.CellRect(1,j).Left,StringGrid1.CellRect(1,j).Top,StringGrid1.Cells[1,j]);
err:=false;
Label3.Caption:= ‘Выделенные значения не верны';
end;
end;
for j:=1 to StringGrid2.RowCount-1 do
begin
If(StrToInt(trim(StringGrid2.Cells[1,j]))160)
then
begin
StringGrid2.Canvas.Brush.color := color;
StringGrid2.canvas.fillRect(StringGrid2.CellRect(1,j));
StringGrid2.canvas.TextOut(StringGrid2.CellRect(1,j).Left,StringGrid2.CellRect(1,j).Top,StringGrid2.Cells[1,j]);
err:=false;
Label3.Caption:= ‘Выделенные значения не верны';
end;
end;
if err=true then
begin
w:=0;//ai
v:=0;//bj
SetLength(c,StringGrid2.RowCount-1,StringGrid1.RowCount-1);
SetLength(t,StringGrid2.RowCount-1,StringGrid1.RowCount-1);
SetLength(a,StringGrid1.RowCount-1);
SetLength(b,StringGrid2.RowCount-1);
//Проверка условия баланса
For i:=1 to StringGrid1.RowCount-1 do
w:=w+StrToint(Trim(StringGrid1.cells[1,i]));
For i:=1 to StringGrid2.RowCount-1 do
v:=v+StrToint(Trim(StringGrid2.cells[1,i]));
if w
begin
Setlength(c,(StringGrid2.RowCount-1),(StringGrid1.RowCount));
SetLength(a,StringGrid1.RowCount);
for i:=0 to Length(c)-1 do
begin
c[i,Length(c[1])-1]:=1000;
end;
a[length(a)-1]:=v-w;
end;
if w>v then
begin
Setlength(c,(StringGrid2.RowCount),(StringGrid1.RowCount-1));
SetLength(b,StringGrid2.RowCount);
for i:=0 to Length(c[1])-1 do
begin
c[length(c)-1,i]:=1000;
end;
b[length(b)-1]:=w-v;
end;
For i:=0 to StringGrid1.RowCount-2 do
a[i]:=StrtoInt(Trim(StringGrid1.cells[1,i+1]));
For i:=0 to StringGrid2.RowCount-2 do
b[i]:=StrtoInt(Trim(StringGrid2.Cells[1,i+1]));
For i:=1 to StringGrid1.RowCount-1 do
begin
Form3.StringGrid1.Cells[0,i]:=StringGrid1.cells[0,i];
Form3.StringGrid2.Cells[0,i]:=StringGrid1.cells[0,i];
end;
For i:=1 to StringGrid2.RowCount-1 do
begin
Form3.StringGrid1.Cells[i,0]:=StringGrid2.cells[0,i];
Form3.StringGrid2.Cells[i,0]:=StringGrid2.cells[0,i];
end;
Form3.Show;
Form5.Close;
end;
end;
end
else ShowMessage('Заполните все поля');
procedurePotencial(x:Tmatr; u,v:Tmas; var z:Tmatr );
var
i,j,k,r:integer;
begin
SetLength(u,length(x[1]));
SetLength(v,Length(x));
For r:=0 to Length(x)-1 do
v[r]:=-1000;
for j:=0 to Length(x[1])-1 do
u[j]:=-1000;
u[0]:=0;
For r:=0 to Length(x)-1 do
for j:=0 to Length(x[1])-1 do
begin
for i:=0 to Length(x)-1 do
if (x[i,j]0) and (v[i]=-1000)then
if (u[j]-1000)then
v[i]:=c[i,j]+u[j];
For i:=0 to Length(x)-1 do
if v[i]-1000 then
for k:=0 to Length(x[1])-1 do
if(kj)and(x[i,k]0)and(u[k]=-1000)then
u[k]:=v[i]-c[i,k];
end;
Setlength(z,Length(c),Length(c[1]));
For i:=0 to Length(x)-1 do
For j:=0 to Length(x[1])-1 do
z[i,j]:=c[i,j]-(v[i]-u[j]);
end;
//Проверканавырожденость
procedure Virogden(var x:Tmatr);
var i,j,r,k,d:integer;
h,g:boolean;
begin
d:=0;
For i:=0 to Length(x)-1 do
for j:=0 to length(x[1])-1 do
if x[i,j]0 then d:=d+1;
if d
For i:=0 to Length(x)-2 do
for j:=0 to Length(x[1])-2 do
begin
if x[i,j]>0 then
begin
h:=true;
g:=true;
for r:=i+1 to Length(x)-1 do
if x[r,j]>0 then
h:=false;
for k:=j+1 to Length(x[1])-1 do
if x[i,k]>0 then
g:=false;
if(h=true)and(g=true) then
x[i,j+1]:=-2;
end;
end;
end;
procedureOpornplan(StringGrid1:TStringGrid; var x,z:Tmatr);
var i,j:integer;
c1:TMatr;
begin
Setlength(x,Length(c),Length(c[1]));
Setlength(c1,Length(x)*Length(x[1]),3);
For i:=0 to Length(x)-1 do
for j:=0 to Length(x[1])-1 do
begin
c1[(Length(x[1]))*i+j,0]:=c[i,j];
c1[(Length(x[1]))*i+j,1]:=i;
c1[(Length(x[1]))*i+j,2]:=j;
end;
Setlength(z,1,3);
//Сортировка
For i:=0 to Length(c1)-2 do
for j:=0 to Length(c1)-2 do
if c1[j,0]>c1[j+1,0] then
begin
z[0]:=c1[j+1];
c1[j+1]:=c1[j];
c1[j]:=z[0];
end;
for i:=0 to Length(x)-1 do
for j:=0 to Length(x[1])-1 do
x[i,j]:=-1;
For i:=0 to Length(x)*Length(x[1])-1 do
if x[c1[i,1],c1[i,2]]=-1 then
begin
//Если à>b
If a[c1[i,2]]>b[c1[i,1]] then
begin
x[c1[i,1],c1[i,2]]:=b[c1[i,1]];
For j:=0 to Length(x[1])-1 do
If x[c1[i,1],j]=-1 then
x[c1[i,1],j]:=0;
a[c1[i,2]]:=a[c1[i,2]]-b[c1[i,1]];
b[c1[i,1]]:=0;
end;
//Если b>a
If a[c1[i,2]]
begin
x[c1[i,1],c1[i,2]]:=a[c1[i,2]];
For j:=0 to Length(x)-1 do
if x[j,c1[i,2]]=-1 then
x[j,c1[i,2]]:=0;
b[c1[i,1]]:=b[c1[i,1]]-a[c1[i,2]];
a[c1[i,2]]:=0;
end;
//Еслиравны
If a[c1[i,2]]=b[c1[i,1]] then
begin
x[c1[i,1],c1[i,2]]:=a[c1[i,2]];
For j:=0 to Length(x[1])-1 do
if x[c1[i,1],j]=-1 then
x[c1[i,1],j]:=0;
For j:=0 to Length(x)-1 do
If x[j,c1[i,2]]=-1 then
x[j,c1[i,2]]:=0;
a[c1[i,2]]:=0;
b[c1[i,1]]:=0;
end;
end;
//Проверка на вырожденность
Virogden(x);
potencial(x,u,v,z);
end;
procedure Vicherk(var z:TMatr;varerr:boolean);
var i,j,min,k:integer;
w,d:Tmas;
begin
SetLength(w,Length(z));
SetLength(d,Length(z[1]));
min:=z[0,0];
k:=0;
For i:=0 to length(w)-1 do
for j:=0 to length(d)-1 do
if z[i,j]
begin
min:=z[i,j];
k:=j;
end;
for i:=0 to length(w)-1 do
if (z[i,k]=0)and(x[i,k]0) then
w[i]:=5;
d[k]:=-1;
For k:=0 to length(d)*Length(w)-2 do
begin
for i:=0 to Length(w)-1 do
if w[i]>0 then
begin
for j:=0 to Length(d)-1 do
if(z[i,j]=0)and(x[i,j]0)and(d[j]-1) then
d[j]:=5;
w[i]:=-1;
end;
For j:=0 to Length(d)-1 do
if d[j]>0 then
begin
for i:=0 to Length(w)-1 do
if(z[i,j]=0)and(x[i,j]0)and(w[i]-1) then
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]
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; varx: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
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
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]
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; varx: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]]
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]
begin
min:=z[i,j];
l:=i;
r:=j;
end;
if Min
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]
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]
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 с.