Xreferat.com » Рефераты по информатике и программированию » Нахождение опорного плана транспортной задачи

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

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

nd;


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

egin

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

begin

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

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

Лист

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

writeln(out)

end;

CloseFile(out);

end;


End.



7.8 Инструкция


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


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

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

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


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


В

Лист

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


ключите компьютер, после загрузки Windows вставьте дискету в дисковод на которой находиться дистрибутив программы. После чего запустите файл setup.exe для инсталляции программы на ваш компьютер. После установки программы выберите в меню пуск папку Transtask и запустите программу. После запуска программы на экране появиться заставка "О программе" , выберите вкладку исходные данные и начинайте работу.


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


№ п/п

Содержание

1

Начало

2

Вызов главной формы

3

Выбор метода решения

4

Метод минимального элемента

5

Вызывается процедура metod 1

6

Метод Фогеля

7

Вызывается процедура metod 2

8

Метод двойного предпочтения

9

Вызывается процедура metod 3

10

Ввод размерности таблицы перевозок m,n

11

Отображение пустой таблицы перевозок m*n

12

Ввод таблицы данных:Вектор А, Вектор В, Матрица С

13

Проверяется открытая задача

14

Да. Введение фиктивного поставщика или потребителя.

15

Нет. Решение транспортной задачи.

16

Отображение результатов решения

17

Конец


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

№ п.п

Содержание

1

Начало

2

Метод минимального элемента

3

Вызывается программа miniem

4

Метод Фогеля

5

Вызывается программа Fogel

6

Метод двойного предпочтения

7

Вызывается программа Double Pref

8

Конец


Лист

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



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

№ п.п

Содержание

1

Начало

2

Выбор минимального тарифа

3

Определяем i min, j min.

4

A min = Min(a i min, b j min)

5

Корректируем элементы исходного массива

6

A i min =0

7

Исключаем строку i min

8

B j min = 0

9

Исключаем столбец j min

10

Заносим в матрицу перевозок значение A min

11

Проверяем (a i j and b i j) = 0

12

Вычисление целевой функции Z

13

Конец

Лист

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




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

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


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


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


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

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


5

Лист

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


.1 Тестирование программ

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

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

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

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

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

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

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

Лист

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




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


КУРСОВОЙ ПРОЕКТ


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

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


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


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


Группа П-44


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


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: