Реферат: Нахождение опорного плана транспортной задачи

begin

cminprev:=c[i,j];

break

end;

// ищем 2-ое наименьшее значение в строке

for j:= 0 to n-1 do

if (j in set_j) and (j<>SubRow[i,1]) then

if c[i,j]<=cminprev then

cminprev:=c[i,j];

// Вычисляем разность между двумя наименьшими

SubRow[i,0]:=cminprev-cmin;

end;

// цикл по столбцам

for j:= 0 to n-1 do

if j in set_j then

begin

// ищем первоначальный минимальный элемент в столбце

for i:= 0 to m-1 do

if i in set_i then

begin

cmin:=c[i,j];

break

end;

// ищем 1-ое наименьшее значение в столбце

for i:= 0 to m-1 do

if i in set_i then

if c[i,j]<=cmin then

begin

cmin:=c[i,j];

SubCol[j,1]:=i

end;

cminprev:=cmin;

// ищем первоначальный минимальный элемент в столбце

for i:= 0 to m-1 do

if (i in set_i) and (i<>SubCol[j,1]) then

begin

cminprev:=c[i,j];

break

end;

// ищем 2-ое наименьшее значение в столбце

for i:= 0 to m-1 do

if (i in set_i) and (i<>SubCol[j,1]) then

if c[i,j]<=cminprev then

cminprev:=c[i,j];

// Вычисляем разность между двумя наименьшими

SubCol[j,0]:=cminprev-cmin;

end;

Лист

Кп-км-п-44-2203-99

// сперва находим начальный наибольший элемент

for i:= 0 to m-1 do

if i in set_i then

begin

SubRowMax:=Subrow[i,0];

break

end;

// Теперь просматриваем всю строку

for i:= 0 to m-1 do

if i in set_i then

if SubRow[i,0]>=SubRowMax then

begin

SubRowMax:=SubRow[i,0];

imax:=i

end;

//отыскиваем максимальное значение в строке

// сперва находим начальный наибольший элемент

for j:= 0 to n-1 do

if j in set_j then

begin

SubColMax:=SubCol[j,0];

break

end;

// Теперь просматриваем всю строку

for j:= 0 to n-1 do

if j in set_j then

if SubCol[j,0]>=SubColMax then

begin

SubColMax:=SubCol[j,0];

jmax:=j

end;

// сравниваем максимальное значение разности по строкам и столбцам

if SubRowMax>SubColMax then

begin

d[imax,SubRow[imax,1]]:=min(a[imax],b[SubRow[imax,1]]);

a[imax]:=a[imax]-d[imax,SubRow[imax,1]];

b[SubRow[imax,1]]:=b[SubRow[imax,1]]-d[imax,SubRow[imax,1]];

if a[imax]=0 then Exclude(set_i,imax);

if b[SubRow[imax,1]]=0 then

Exclude(set_j,SubRow[imax,1]);

z:=z+d[imax,SubRow[imax,1]]*c[imax,SubRow[imax,1]];

if set_i=[] then set_j:=[];

if set_j=[] then set_i:=[]

end

else

begin

d[SubCol[jmax,1],jmax]:=min(a[SubCol[jmax,1]],b[jmax]);

a[SubCol[jmax,1]]:=a[SubCol[jmax,1]]-d[SubCol[jmax,1],jmax];

b[jmax]:=b[jmax]-d[SubCol[jmax,1],jmax];

if a[SubCol[jmax,1]]=0 then Exclude(set_i,SubCol[jmax,1]);

if b[jmax]=0 then

Exclude(set_j,SubCol[jmax,1]);

z:=z+d[SubCol[jmax,1],jmax]*c[SubCol[jmax,1],jmax];

if set_i=[] then set_j:=[];

if set_j=[] then set_i:=[]

end

Лист

Кп-км-п-44-2203-99

ShowSolve

end;

procedure TwoWall;

var

RowMin,ColMin:integer;

i,j,jj,j0:integer;

imin,jmin:integer;

set_i,set_j:set of 0..255;

begin

set_i:=[];

for i:=0 to m-1 do include(set_i,i);

set_j:=[];

for j:=0 to n-1 do include(set_j,j);

repeat

// начинаем цикл по столбцам

for j:= 0 to n-1 do

if j in set_j then

begin

// находим начальный минимальный элемент строки

for i:= 0 to m-1 do

if i in set_i then

begin

RowMin:=c[i,j];

break

end;

// теперь просматриваем весь столбец

for i:=0 to m-1 do

if i in set_i then

if c[i,j]<=RowMin then

begin

RowMin:=c[i,j];

imin:=i

end;

// минимальный элемент в j-ом столбце найден

// проверяем , минимальный ли он в своей строке

j0:=j;

for jj:= 0 to n-1 do

if jj in set_j then

if c[imin,jj]< RowMin then

j0:=jj;

// проверяем по индексу не тот ли это элемент

if j=j0 then

begin

d[imin,j]:=min(a[imin],b[j]);

a[imin]:=a[imin]-d[imin,j];

b[j]:=b[j]-d[imin,j];

if a[imin]=0 then exclude(set_i,imin);

if b[j]=0 then exclude(set_j,j);

z:=z+d[imin,j]*c[imin,j];

end

end

until (set_i=[]) and (set_j=[]);

ShowSolve

e

Лист

Кп-км-п-44-2203-99

procedure TfmTransTask.FormCreate(Sender: TObject);

var

i,j:integer;

begin

m:=3;

n:=3;

SetLength(a,m);

for i:= 0 to m-1 do a[i]:=0;

SetLength(b,n);

for j:= 0 to n-1 do b[j]:=0;

SetLength(c,m);

for i:= 0 to m-1 do SetLength(c[i],n);

for i:= 0 to m-1 do

for j:= 0 to n-1 do

c[i,j]:=0;

SetLength(d,m);

for i:= 0 to m-1 do SetLength(d[i],n);

for i:= 0 to m-1 do

for j:= 0 to n-1 do

d[i,j]:=0;

for i:= 1 to m do

begin

stgProvider.Cells[i-1,0]:=IntToStr(i);

str(a[i-1],s);

stgProvider.Cells[i-1,1]:=s;

end;

for j:= 1 to n do

begin

stgCustomer.Cells[j-1,0]:=IntToStr(j);

str(b[j-1],s);

stgCustomer.Cells[j-1,1]:=s;

end;

for i:= 1 to m do

stgTarif.Cells[0,i]:=IntToStr(i);

for j:= 1 to n do

stgTarif.Cells[j,0]:=IntToStr(j);

for i:= 1 to m do

stgSolve.Cells[0,i]:=IntToStr(i);

for j:= 1 to n do

stgSolve.Cells[j,0]:=IntToStr(j);

end;

procedure TfmTransTask.edProviderCountChange(Sender: TObject);

var

i:integer;

b

Лист

Кп-км-п-44-2203-99

stgProvider.ColCount:=StrToInt(edProviderCount.Text);

stgTarif.RowCount:=stgProvider.ColCount+1;

stgSolve.RowCount:=stgTarif.RowCount;

m:=StrToInt(edProviderCount.Text);

SetLength(a,m);

SetLength(c,m);

for i:= 0 to m-1 do SetLength(c[i],n);

SetLength(d,m);

for i:= 0 to m-1 do SetLength(d[i],n);

stgProvider.Cells[stgProvider.ColCount-1,0]:=edProviderCount.Text;

stgTarif.Cells[0,stgProvider.ColCount]:=edProviderCount.Text;

stgSolve.Cells[0,stgProvider.Colcount]:=edProviderCount.Text;

end;

procedure TfmTransTask.edCustomerCountChange(Sender: TObject);

var

i:integer;

begin

stgCustomer.ColCount:=StrToInt(edCustomerCount.Text);

stgTarif.ColCount:=stgCustomer.ColCount+1;

stgSolve.ColCount:=stgTarif.ColCount;

n:=StrToInt(edCustomerCount.Text);

SetLength(b,n);

SetLength(c,m);

for i:= 0 to m-1 do SetLength(c[i],n);

SetLength(d,m);

for i:= 0 to m-1 do SetLength(d[i],n);

stgCustomer.Cells[stgCustomer.ColCount-1,0]:=edCustomerCount.Text;

stgTarif.Cells[stgCustomer.ColCount,0]:=edCustomerCount.Text;

stgSolve.Cells[stgCustomer.Colcount,0]:=edCustomerCount.Text;

end;

procedure TfmTransTask.btnLoadDataClick(Sender: TObject);

var

i,j:integer;

suma,sumb:integer;

begin

for i:= 0 to m-1 do

if stgProvider.Cells[i,1]<>'' then

a[i]:=StrToInt(stgProvider.Cells[i,1])

else

a[i]:=0;

suma:=0;

for i:= 0 to m-1 do suma:=suma+a[i];

lblProvider.Caption:=IntToStr(suma);

for j:= 0 to n-1 do

if stgCustomer.Cells[j,1]<>'' then

b[j]:=StrToInt(stgCustomer.Cells[j,1])

else

b[j]:=0;

sumb:=0;

for j:= 0 to n-1 do sumb:=sumb+b[j];

lblCustomer.Caption:=IntToStr(sumb);

if sumb<>suma then

Лист

Кп-км-п-44-2203-99

lblTypeTask.Caption:='Открытая';

If sumb>suma then

lblMsg.Caption:='Создать фиктивного поставщика с грузом '+IntToStr(sumb

-suma);

if sumb

lblMsg.Caption:='Создать фиктивного потребителя со спросом '+

IntToStr(suma-sumb)

end

else

begin

lblTypeTask.Caption:='Закрытая';

lblMsg.Caption:=''

end;

btnSolve.Enabled:=True

end;

procedure TfmTransTask.btnLoadDataCClick(Sender: TObject);

var

i,j:integer;

begin

for i:= 0 to m-1 do

for j:= 0 to n-1 do

if stgTarif.Cells[j+1,i+1]<>'' then

c[i,j]:=StrToInt(stgTarif.Cells[j+1,i+1]);

end;

procedure TfmTransTask.btnSolveClick(Sender: TObject);

begin

if rbMinelem.Checked then Minelem;

if rbFogel.Checked then Fogel;

if rbTwoWall.Checked then TwoWall

end;

procedure TfmTransTask.btnPrintClick(Sender: TObject);

var

i,j:integer;

out:TextFile;

begin

AssignFile(out,'rezult.txt');

Rewrite(out);

writeln(out,'Исходные данные транспортной задачи');

writeln(out,'потребность потребителей');

for j:= 0 to n-1 do write(out,b[j]:8);

writeln(out);

writeln(out,'Матрица тарифов перевозок');

for i:= 0 to m-1 do

begin

write(out,a[i]:8);

for j:= 0 to n-1 do write(out,c[i,j]:8);

writeln(out)

end;

writeln(out,'Матрица перевозок (решение)');

for i:= 0 to m-1 do

begin

Лист

Кп-км-п-44-2203-99

Лист

Кп-км-п-44-2203-99

end;

CloseFile(out);

end;

End.

7.8 Инструкция

Аппаратные и программные требования

Для нормальной работы программы необходим персональный компьютер совместимый с IBM PC , с процессором не ниже

486, тактовой частотой 120 Мгц, оперативной памятью не менее 8 МБ, занимаемое место на диске после инсталляции 5 МБ.

Операционная система Windows 95,98,NT.

Инсталляция и запуск программы.

В

Лист

Кп-км-п-44-2203-99

4.3 Критерии качества модели

К основным критериям качества любой модели относятся такие как:

• критерий адекватности;

• чувствительности;

• устойчивости модели.

Критерий адекватности

Под адекватностью модели понимается ее способность наиболее точно отражать все свойства и характеристики моделируемой среды. В качестве критериев адекватности можно выбрать , например, величину отличия (абсолютных и относительных) входных и выходных характеристик модели и реального объекта, сравнительная оценка реакции модели и объекта и т.д.

Критерий чувствительности

Под критерием чувствительности понимают степень воздействия изменения параметров модели на результаты выдаваемые моделью. Изменение параметров можно моделировать меняя коэффициенты в системе уравнений , описывающих модель, характер изменения входных данных и т.д.

Критерий устойчивости

Критерий устойчивости – это количественная или качественная оценка, которая характеризует исследуемую модель как устойчивую или неустойчивую.

П

Лист

Кп-км-п-44-2203-99

Лист

Кп-км-п-44-2203-99

6. Тестирование и отладка

6.1 Синтаксическая отладка

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

Семантическая отладка осуществляется для проверки семантики языковых конструкции и является одним из этапов синтаксической отладки.

Тестовые отчеты и анализ тестирования

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

Лист

Кп-км-п-44-2203-99

6.2 Семантическая отладка

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

Семантическая отладка подразумевает в себя проверку поэтапного хода выполнения программы. Это можно выявить при тестирование программы правильно ли мы задали тип False или True .

В Delpfi при выполнении операций в логических выражениях поддерживается две различные модели:

• вычисление по полной схеме

• вычисление по короткой схеме.

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

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

6.4 Оптимизация программы

В ходе отладки программного пакета возникает вопрос о таких показателях как скорость (быстродействие) работы программы, объем занимаемого места на диске, необходимый объем оперативной памяти

Лист

Кп-км-п-44-2203-99

Описание блок-схемы программы Transtask.pas

Описание Блок-схемы меню определение опорного плана.

Лист

Кп-км-п-44-2203-99

Описание блок-схемы Определение опорного плана транспортной задачи методом минимального элемента.

Лист

Кп-км-п-44-2203-99

Рецензия на курсовой проект

Студента группы П-44

Голубовского Дениса Николаевича

Тема: Нахождение опорного плана транспортной задачи

Председатель руководитель

курсового проекта Тлисова Л.Б

5

Лист

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

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

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

Проверка алгоритма на данных максимальной установленной размерности: по количеству перечисленных в условиях задачи объектов, по количеству связей между ними, по разрядности и точности машинного представления числовых параметров и пр. Такая проверка нужна для выявления и отсева неэффективных - медленно работающих или нерационально использующих память программ. Известны случаи, когда, в принципе, правильно работающий алгоритм приводил к ошибочному ответу из-за ошибок переполнения -- в условиях задачи оговаривается диапазон или разрядность исходных данных, но не разрядность промежуточных результатов или ответа. Типичным примером грубой ошибки такого рода может служить нахождение опорного плана транспортной задачи. Проверка работоспособности алгоритма в вырожденных случаях: срабатывание пустого или состоящего из единственного элемента цепного списка, работа программы с графом, не содержащим дуг и т.п. В некоторых случаях, например, при декомпозиции задачи, когда решение задачи сводится к решению задачи меньшей размерности переход от начального i=0 уменьшением на единицу может привести к непредусмотренному эффекту выхода за границы зарезервированной памяти. Результат работы на нижней границе размерности легко просчитывается, иногда он будет получен как и в общем случае, иногда удобней вручную просчитать его и предусмотреть особую ветку программы, но никогда о нем не следует забывать.

Следует иметь ввиду, что построение авторами заданий тестов, особенно, значительной размерности представляет собой непростую задачу. Возможно несколько подходов к построению тестов.

1. Составление тестов вручную. Это возможно, когда решение задачи не представляет собой вычислительной сложности (вся сложность -- логическая). Задача "Путь на кубе" раздела "Геометрия" -- пример именно такой задачи. Во всех остальных случаях подобный путь тупиковый. У участников олимпиады иногда выбора нет, но не забывайте проверить случаи вырожденной и максимальной размерности хотя бы в тривиальном варианте (матрица из нулей и единиц не содержит нулей или единиц, в ней единственная строка или единственный столбец, в графе нет дуг, или граф полный).

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

Лист

Кп-км-п-44-2203-99

Колледж информационных технологий и экономики КБГУ

По дисциплине Компьютерное моделирование

Наименование учебного предмета

На тему: Нахождение опорного плана транспортной задачи

Студента Голубовского Дениса Николаевича

Группа П-44

Специальность 2203 “Программное обеспечение ВТ и АС”

Председатель руководитель

курсового проектирования

Тлисова Л.Б

Оценка _________ Подпись_________________

Дата___________

1.2 Описание целей моделирования их приоритеты.

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

Система - Средство достижения цели, т,е всё то, что нужно для достижения цели.

Модель служит для исследования .

Требования к модели:

1. наглядность

2. обозримость

3. доступность для исследования

4. простота исследования

Моделирование является экспериментальной и прикладной методологией имеющая целью:

• описание поведения системы

• по строительные теории и гипотезы которые могут объяснить наблюдаемое поведение.

• Использовать эти теории для предсказания будущего поведения системы, т.е тех воздействий которые могут быть вызваны изменением в системе или изменение способов её функционирования.

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

Цель интерполяции состоит в отыскании значения функции в некоторой промежуточной точке по отношению к табличным данным.

лист

Кп-км-п-44-2203-99

2

лист

ЭВМ широко применяется для решения научных, технических и экономических задач. Они способны производить вычисления очень быстро, выводить очень точные результаты, заполнять большие массивы информации и производить длинные и сложные последовательные вычисления без вмешательства человека.

Современный компьютер имеет следующие основные компоненты:

1. центральный процессор , который выполняет арифметические и логические операции и организует процесс выполнения программ.

2. Память служащая для хранения информации

3. Внешние устройства для управления компьютеров и ввода - вывода информации.