Мурманский филиал Петровского Колледжа

Курсовая по дисциплине

«Компьютерное моделирование» на тему

«Транспортная задача»

Выполнил: Ошкин Е.С.

Проверил: Сергеев А.В.

Мурманск

2002г.

Описание Алгоритма программы

ПРОГРАММА НАПИСАНА НА BORLAND С++ версии 3.1

Программа решает Транспортную Задачу (ТЗ) 3 методами:
1. Северо-западным углом
2. Северо-восточным углом
3. Методом минимального элемента в строке.

Программа состоит из функций:
1. Main()
2. Data()
3. Opplan()
4. Sohran()
5. Bas()
6. Kost()
7. Potenzial()
8. Optim()
9. Plmi()
10. Abcikl()
11. Cikl()
12. Prpoisk()
13. Levpoisk()
14. Verpoisk()
15. Nizpoisk()
16. Pr()

Главная функция main() невелика, но в ней происходит обращение функциям, выполняющим определенные действия в процессе решения ТЗ. Здесь следует обратить особое внимание на строку программы if(!z) break; - если бы не она (она показывает, что после очередной проверки базисного плана, если он оптимален, возвращаемое значение из функции optim() равно 0, что приводит к выходу из бесконечного цикла улучшения базисных планов). Иногда возникает ситуация, когда базисная переменная(одна или несколько) равна нулю, и ее следует отличать от других базисных переменных. В матрице matr() такие элементы я пометил как –2. Основные переменные я описал в комментариях в программе.

Функция data() производит ввод данных на ТЗ.

Функция opplan() выполняет задачи по составлению первоначального базисного плана методом северо-заподного угла. В этой функции используются следующие переменные:
Int *matr указатель на матрицу базисных переменных
Int *po указатель на вектор пунктов отправления
Int *pn указатель на вектор пунктов назначения
Int m количество пунктов отправления
Int n количество пунктов назначения

Функция kost() производит вывод суммарной стоимости перевозок по текущему базисному плану. Используются следующие переменные:

Int *matr, m,n;

Int *st указатель на матрицу стоимостей.

Функция potenzial() выполняет подсчет потенциалов.

Использует следующие переменные:

Int *pu указатель на вектор потенциалов строк

Int *pv указатель на вектор потенциалов столбцов

Int matr, m, n, *st;

Первоначально элементы векторов потенциалов *(pu+i) и *(pv+j) заполняются минимальными значениями для целых переменных = 32768, определенных предпроцессорным оператором define MIN – 32768. Далее пологая, что *pu=0, и используя структуру struct poten{…}, элементы векторов потенциалов приобретают свои реальные значения.

Работу этого модуля я бы разделил на эти этапы:

. Выделение памяти под элемент структуры top = (struct poten*)malloc(sizeof(struct poten)); заполнение полей элемента структуры необходимой информацией; установление связей между элементами структуры;

. Вычисление потенциалов строк и столбцов с занесением информации в секторы pu и pv;

. Проверка правильности заполнения векторов pu и pv, т.е. установление не содержат ли элементы этих векторов значения MIN. При необходимости, если существуют такие элементы векторов, производятся дополнительные вычисления;

. Вывод векторов pu и pv;

Функция optim() проверяет план на оптимальность, если он оптимален, то функция отправляет в главную функцию main() значение 0, в противном случае, если он не оптимален, то управление передается функции abcikl() и возврат главной функции main() значение –1. Функция optim() использует переменные:
Int m,n,*pu,*pv, *matr, *st. Цепь строится относительно первой попавшейся графоклетки, для которой ui + vj =cij , а не относительной характеристики.
В ходе решения ТЗ промежуточные базисные планы отличаются от тех, которые я построил, начиная с координат графоклетки с минимальным значением отрицательной характеристики, но врезультате оптимальный план будет тот же.

Функция abcicl() – использует следующие переменные
Int *matr, m, n;
Int *matr2 //указатель на рабочую (изменяемую) матрицу, по началу она является копией оригинальной.
Int ik,jk; // координаты графоклетки, с которой начинает строиться цепь. В этой функции присваивается графоклетки, с которой будет происходить поиск цикла(цепь), значение -1.

Функция cikl() производит поиск относительно графоклетки со значением
–1. Она использует следующие переменные:
Int *matr2, ik, jk;
Int ch; // счетчик количества элементов в массивах *zi и *zj
Int *zi, *zj // указатели на массивы индексов. Хранят индексы элементов matr, подлежащих перераспределению.

Функции prpoisk(), levpoisk(), verpoisk(), nizpoisk()-поиск, соответственно, вправо, влево, вверх, вниз – относительно текущей графоклетки. Поиск происходит в массиве *matr2. Если известна строка, то выполняется поиск столбца, т.е. его индекса, если известен столбец –ищется строка.

Данные функции возвращают координаты столбца или строки найденной графоклетки, либо значение –1, если графоклетка в данном направлении не найденна.

Работа модуля cikl() заключается в следующем:
. Поиск нужного элемента начинается относительно графоклетки, помеченной –1 в матрице matr2 (с координатами ik и jk согласно входным данным) по возможным направлениям (поочередно);
. Если поиск успешен, то поля структуры заполняются информацией, найденный элемент структуры включается в список(работу модуля поддерживает линейный список, в котором хранится информация о ходе поиска цепи), и за основу берется уже эта (текущая) графоклетка матрицы matr2(). Далее процедура поиска повторяется:
. Если поиск на каком-то шага не неуспешен по возможным направлениям, то найденный элемент исключается из списка и за основу берется последний элемент списка (после удаления). В рабочей матрице matr2() «обнуляется» элемент с координатами, который хранил исключенный элемент, что необходимо для того, чтобы исключить повторное обращение к элементу matr2, не входящемму в цепь;
. Поиск цикла (цепи) будет закончен, когда при прохождении по какому-либо направлению мы снова наткнемся на элемент матрицы matr2 со значением –1.

В конце модуля элементы списка, т.е. его поля с координатами, переписываются в векторы zi и zj.

Внешние переменные:
Int m, n, *matr2;

Входные данные:
Int i1, j1 // координаты текущей графоклетки, относительно которой строится цепь.
Выходные данные:

I(j)- координаты строки, столбца, если переменная найдена;

Функция pr(), осуществляет печать текстовых сообщений о ходе поиска в матрице; она вызывается из модуля cikl().

Функция plmi() перераспределяет поставки по цепи, т.е. улучшает план.

Используются следующие переменные:
Int zi,zj;
Int ch,chr; /переменные размерности массивов zi,zj
Int matr /указатель на матрицу базисных переменных
Работа с модулями выполняется в несколько этапов. Если имеется нулевой базисный элемент (помеченный как –2 в матрице matr) и индекс k нечетен для векторов zi,zj, то элементы matr, помеченные, как –1 и –2(новый элемент помеченный как –2 обнуляем), меняются местами, в противном случае(если k четно или нет нулевых базисных элементов в matr) осуществляется:

Нахождение минимального элемента в матрице базисных переменных: min=matr [i][j], где i=zi[k]; j=zj[k]; k-нечетное число;

Перераспределение поставок: a) если k четное число, то matr[i][j] = matr[i][j]+min, где i=zi[k]; j=zj[k]; b)если k нечетное число, то matr[i][j] = matr[i][j]-min, где i=zi[k]; j=zj[k];

Модуль bas() подсчитывает количество ненулевых базисных переменных в матрице matr.

Модуль sohran() находит нулевую базисную переменную в matr и устанавливает её в –2.
Int basper; /количество базисных переменных.

Функция opplan1() построение первоначального плана методом северо- восточного угла, а opplan2()- методом выбора наименьшего элемента в строке.

Ниже приведен текст программы
#include //Подключение стандартных
#include // Библиотек
#include
#include
#include
#define MIN -32768

int *po = NULL; //Указатель на массив пунктов отправления int *pn = NULL; //Указатель на массив пунктов назначения int *st = NULL; //Указатель на матрицу стоимостей int *matr=NULL; //Указатель на матрицу базисных переменных int *matr2 = NULL; //Указатель на рабочую матрицу int n ,m; //Размерность задачи int *pu,*pv; //Указатели на массивы потенциалов int *zj,*zi; // Указатель на массивы индексов int ch=0,ch2=0; //Счетчики
FILE *fpdat; //Указатель на вводной файл int iter=0; //Счетчик итерации
FILE *fil; //Указатель на выводной файл int zen = -1; //Переменная для сохранения стоимости п-на int z = 1; //Флаг для выхода при оптимальном плане int basper;

// void exit(int status);

void data(void)

{ int i,j,t; printf("Введите количество складов: "); scanf("%d",&m); printf("Kolichestvo skladov-----> %d",m); printf("n Введите количество магазинов:n"); scanf("%d",&n); printf("n Kolichestvo magazinov --->%d",n);

//*********** Выделение памяти ****************** if((po=(int*)calloc(m,sizeof(int)))==NULL) abort(); if((pn=(int*)calloc(n,sizeof(int)))==NULL) abort(); if((st=(int*)calloc(n*m,sizeof(int)))==NULL) abort();

printf("Введите элементы матрицы стоимостей: n"); for(i=0;iu))=(top1->b) - *(pv+j); i = (top1->u); top1 ->zn = 0; break;

}

}

}

}
// ********** Продолжение функции подсчета потенциалов *****************

for(;;){ fl = 0; for(top = topnast;top!=NULL;top =top -> next)

{ if((top -> zn) == -1)

{ if(*(pu+(top ->u)) !=MIN)

{

*(pv+(top->v))=(top->b) - *(pu+(top ->u)); fl = 1; top -> zn = 0;

} if(*(pv+(top->v)) !=MIN)

{

*(pu+(top->u))=(top->b) - *(pv+(top->v)); fl=1; top->zn = 0;

}

}

} if(!fl) break;

} printf("n ПОТЕНЦИАЛЫ ПО v:"); fprintf(fil,"n **** ПОТЕНЦИАЛЫ ПО v:"); for(i = 0;ijck = jk; ch++; fprintf(fil,"nnДо Условия while fl3 =%d n",fl3); pr("top2",top2); fprintf(fil,"Весь цикл поиска сейчас начнется, надеюсь -
n что он будет не бесконечный или не бесполезный :( n"); printf("Весь цикл поиска сейчас начнется, надеюсь - n что он будет не бесконечный или не бесполезный :( n"); printf("n t ttpress anykey to contunion"); getch(); while(fl3)

{ fl3=0; fl = 0; if((nst = prpoisk(ik,jk))>=0)

{ fprintf(fil,"nnВнимание!!!n nst = %d n",nst); fprintf(fil,"Ща будет поик идти ему бы...:Point found!n"); printf("И он пошел RIGHT:Point found !nr"); napr = 2; jk = nst; top2->prnapr = 1;

} else if((nstr = nizpoisk(ik,jk))>=0)

{ fprintf(fil,"DOWN: Point found !n"); printf("DOWN: Point found !nr"); napr = 3; ik = nstr; top2->prnapr = 2;

}

else if((nst=levpoisk(ik,jk))>=0)

{ fprintf(fil,"LEFT:Point found !n"); printf("LEFT:Point found !nr"); napr = 4; jk = nst; top2->prnapr = 3;

}

// **************** Prodolzhenie 1 poiska *********************** else if((nstr = verpoisk(ik,jk))>=0)

{ fprintf(fil,"UP:Point found !n"); printf("UP:Point found !nr"); napr = 1; ik = nstr; top2->prnapr = 4;

} else return(-1);

while(!fl || *(matr2+ik*n+jk)!=-1)

{ fl=1; switch(napr)

{ case 1: printf("Search to the right --->"); fprintf(fil,"Search to the right --->"); if((nst = prpoisk(ik,jk))>=0)

{ printf("foundednr"); fprintf(fil,"foundedn"); if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL) abort(); if(!topnast1) topnast1=top2; else top3 -> next=top2; top3 = top2; top2 -> next = NULL; top2->ick = ik; top2->jck = jk; ch++; top2->prnapr = 1; pr("top2",top2); napr = 2; jk = nst; perpr = perlev = 0;

} // **** IF ******* else

{ fprintf(fil,"Point not found ! Change direction to LEFTn"); napr = 3; perpr = 1;

} break;

//***************** PRODOLZHENIE 2 POISKA
****************************** case 2: printf("Search to the down --->"); fprintf(fil,"Search to the down --->"); if((nstr=nizpoisk(ik,jk))>=0)

{ if((top2=(struct cik*)malloc(sizeof(struct cik))) ==
NULL) abort(); printf("foundednr"); fprintf(fil,"foundedn"); if(!topnast1) topnast1=top2; else top3->next=top2; top3=top2; top2->next=NULL; top2->ick = ik; top2->jck = jk; ch++; top2->prnapr = 2; pr("top2",top2); napr = 3; ik = nstr; perniz=perver=0;

} //**** IF ******** else

{ fprintf(fil,"Point not found ! Change direction to UPn"); napr = 4; perniz = 1;

} break;

case 3: printf("Search to the left -->"); fprintf(fil,"Search to the left -->"); if((nst=levpoisk(ik,jk))>=0)

{ if((top2=(struct cik*)malloc(sizeof(struct cik))) == NULL) abort(); printf("foundednr"); fprintf(fil,"foundedn"); if(!topnast1) topnast1=top2; else top3->next=top2; top3=top2; top2->next=NULL; top2->ick = ik; top2->jck = jk; ch++;

//************ PRODOLZHENIE 3 POISKA ************* top2->prnapr = 3; pr("top2",top2); napr = 4; jk = nst; perlev = perpr = 0;

} // ******* IF ***** else{ fprintf(fil,"Point not found ! Change direction to RIGHTn"); napr = 1; perlev = 1;

} break; case 4: printf("Search to the up --->"); fprintf(fil,"Search to the up --->"); if((nstr=verpoisk(ik,jk))>=0)

{ if((top2=(struct cik*)malloc(sizeof(struct cik)))==NULL) abort(); printf("foundednr"); fprintf(fil,"foundedn"); if(!topnast1) topnast1=top2; else top3->next=top2; top3=top2; top2->next=NULL; top2->ick=ik; top2->jck=jk; ch++; top2->prnapr = 4; pr("top2",top2); napr = 1; ik = nstr; perver = perniz = 0;

} // *****If ************** else

{ fprintf(fil,"Point not found ! Change direction to
DOWNn"); napr = 2; perver = 1;

} break;

} // ************ SWITCH ********************

// ************** PRODOLZHENIE 4 POISKA ******************** if(perlev == 1 && perpr == 1)

{

*(matr2+ik*n+jk) = 0; ik = top3 ->ick; jk = top3 ->jck; napr = top3->prnapr; top3 = topnast1; printf("Zerro 1nr");

for(top2=topnast1;top2->next !=NULL;top2=top2->next) top3 = top2; top3 -> next=NULL; perlev = perpr = 0; // if(ch == 1) if(top2==top3)

{ fl3=1; break;

} else

{ top3->next=NULL; free(top2); ch--; printf("Viynimaem tochky:
(%d,%d)=%dn",ik,jk,*(matr2+ik*n+jk)); fprintf(fil,"Viynimaem tochky:
(%d,%d)=%dn",ik,jk,*(matr2+ik*n+jk)); pr("top2",top2);

} perpr = 0; perlev = 0;

} // IF

if(perver == 1 && perniz == 1)

{

*(matr2+ik*n+jk)=0; printf("Zerro 2nr"); ik=top3->ick; jk = top3->jck; napr = top3->prnapr; top3 = topnast1;

for(top2 = topnast1;top2->next !=NULL;top2=top2-
>next) top3 = top2; perver = perniz = 0; if(top2==top3)

{ fl3=1; break;

} else

{ top3->next = NULL; free(top2); ch--;

// ******* PRODOLZHENIE 5 POISKA ********************* printf("Viynimaem tochky: (%d,%d) =
%dn",ik,jk,*(matr2+ik*n+jk)); fprintf(fil,"Viynimaem tochky: (%d,%d) =
%dn",ik,jk,*(matr2+ik*n+jk));

pr("top2",top2);

} perver = 0; perniz = 0;

} // IF if(ch==0)

{ fl3=1; break;

}

} //while

} //while i=0; if((zi = (int*)calloc(ch,sizeof(int))) == NULL ) abort(); if((zj = (int*)calloc(ch,sizeof(int))) == NULL ) abort(); printf("nr"); ch2 = ch; for(top2 = topnast1;top2 !=NULL;top2 = top2->next)

{

*(zi+i) = top2 ->ick;

*(zj+i) = top2 ->jck; i++;

}

return(0);

} // *********** cikl ****************************

int prpoisk(int i1, int j1)

{ int j;

for(j=j1+1;j=0;j--)

{ if((*(matr2+i1*n+j))!=0) return(j);

} return(-1);

} int verpoisk(int i1,int j1)

{ int i;

for(i=i1-1;i>=0;i--)

{ if((*(matr2+i*n+j1))!=0) return(i);

} return(-1);

}

int nizpoisk(int i1, int j1)

{ int i; for(i = i1+1;iick,ptr->jck); printf("Koordinatiy ytoplennoy tochki : %d and %dnr",ptr-
>ick,ptr->jck); fprintf(fil,"and napravlenie"); printf("Napravlenie"); switch(ptr->prnapr)

{ case 1: fprintf(fil,"Vpravon"); printf("Vpravonr"); break; case 2: fprintf(fil,"Vnizn"); printf("Vniznr"); break; case 3: fprintf(fil,"Vlevon"); printf("Vlevonr"); break; case 4: fprintf(fil,"Vverhn"); printf("Vverhnr"); break; default: fprintf(fil,"Startn"); printf("Startnr"); break;

} fprintf(fil,"WORK MATRIXn"); for(i=0;i