РефератыИнформатика, программированиеТрТранспортная задача по критериям стоимости и времени

Транспортная задача по критериям стоимости и времени

Министерство образования и науки Российской Федерации


Федеральное агентство по образованию


ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


Кафедра Автоматизированных систем


ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА


к курсовому проекту по дисциплине


Теория принятия решения


Иркутск 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]))<0)or(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]))<0)or(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<v then


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('Заполнитевсеполя');


procedure Potencial(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 (k<>j)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<Length(x)+Length(x[1])-1 then


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;


procedure Opornplan(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]]<b[c1[i,1]] then


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;var err: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]<min then


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]<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 с.

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

Название реферата: Транспортная задача по критериям стоимости и времени

Слов:3533
Символов:40021
Размер:78.17 Кб.