Мурманский филиал Петровского Колледжа
Курсовая
по дисциплине
«Компьютерное моделирование»
на тему
«Транспортная задача»
Выполнил: Ошкин Е.С.
Проверил: Сергеев А.В.
Мурманск
2002г.
Описание Алгоритма программы
ПРОГРАММА НАПИСАНА НА BORLAND С++ версии 3.1
Программа решает Транспортную Задачу (ТЗ) 3 методами:
Северо-западным углом
Северо-восточным углом
Методом минимального элемента в строке.
Программа состоит из функций:
Main()
Data()
Opplan()
Sohran()
Bas()
Kost()
Potenzial()
Optim()
Plmi()
Abcikl()
Cikl()
Prpoisk()
Levpoisk()
Verpoisk()
Nizpoisk()
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;i rez += (*(matr1+i*n+j)) *(*(st+i*n+j)); } } printf(“\n Rezultat : %d”,rez); printf(“\n”); fprintf(fil,”%s %5d”,” Rezultat : “,rez); fprintf(fil,”\n”); getch(); free(matr1); if(zen == rez) { z=0; } zen = rez; return; } //************* KOST() //************* PODSCHET POTENCIALOV ******************** void potenzial(void) { struct poten { int v; int u; int zn; struct poten *next; int b; } *topnast = NULL, *top = NULL, *top1 = NULL; int i,j; int fl; //********** ВЫДЕЛЕНИЕ ПАМЯТИ *******************8 if((pu=(int*)calloc(m,sizeof(int)))==NULL) abort(); if((pv=(int*)calloc(n,sizeof(int)))==NULL) abort(); // ПРИСВОЕНИЕ ВСЕМ ПОТЕНЦИАЛАМ ЗНАЧЕНИЯ MIN for(i=0;i { if((top=(struct poten*)malloc(sizeof(struct poten)))==NULL) abort(); fprintf(fil,”top = %d”,top); if(!topnast){ topnast = top; fprintf(fil,”topnast = top = %d”,top); } else top1 -> next=top; top1=top; top -> next=NULL; top -> b = *(st+i*n+j); //Стоимости top -> v = j; top -> u = i; top -> zn = -1; } } } *pu = 0; i=0; j = -1; for(top = topnast;top!=NULL;top = top -> next) { if((top -> u) == i && (top -> v)!=j) { *(pv+(top -> v)) = (top -> b) – *(pu+i); j = (top->v); top -> zn = 0; } else{ for(top1 = topnast;top1 != NULL;top1 = top1->next) { if((top1->v) == j && (top1->u)!=i) { *(pu+(top1->u))=(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;i free(top); return; } // potenzial // ****** PROVERKA PLANA NA OPTIMALNOST’ void pr(char pr[],void *st); // Предварительно int prpoisk(int i1,int j1); // Объявлены int levpoisk(int i1,int j1); //ЭТИ int verpoisk(int i1,int j1); //Функции int nizpoisk(int i1,int j1); int optim(void) { int i,j; for(i=0;i { abcikl(i,j); fprintf(fil,”optim(): План не оптимален, функции main() возвращаем return(-1); } } } fprintf(fil,”Plan optimalen”); return(0); } // ******* optim() *************** // ************** UPGRADE PLAN ************************** void abcikl(int ik,int jk) { int i,j; fprintf(fil,”Мы в abcikl()”); if((matr2=(int*)calloc(n*m,sizeof(int))) == NULL) abort(); for(i=0;i top3->jck=jk; } else top3->next=top2; top3=top2; top2->next=NULL; top2->ick = ik; top2->jck = jk; ch++; fprintf(fil,”\n\nДо Условия while fl3 =%d \n”,fl3); pr(“top2″,top2); fprintf(fil,”Весь цикл поиска сейчас начнется, надеюсь – \n что он printf(“Весь цикл поиска сейчас начнется, надеюсь – \n что он будет printf(“\n \t \t\tpress anykey to contunio\n”); getch(); while(fl3) { fl3=0; fl = 0; if((nst = prpoisk(ik,jk))>=0) { fprintf(fil,”\n\nВнимание!!!\n nst = %d \n”,nst); fprintf(fil,”Ща будет поик идти ему бы…:Point found!\n”); printf(“И он пошел RIGHT:Point found !\n\r”); napr = 2; jk = nst; top2->prnapr = 1; } else if((nstr = nizpoisk(ik,jk))>=0) { fprintf(fil,”DOWN: Point found !\n”); printf(“DOWN: Point found !\n\r”); napr = 3; ik = nstr; top2->prnapr = 2; } else if((nst=levpoisk(ik,jk))>=0) { fprintf(fil,”LEFT:Point found !\n”); printf(“LEFT:Point found !\n\r”); 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 !\n\r”); 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(“founded\n\r”); fprintf(fil,”founded\n”); 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 LEFT\n”); 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(“founded\n\r”); fprintf(fil,”founded\n”); 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 UP\n”); 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(“founded\n\r”); fprintf(fil,”founded\n”); 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 RIGHT\n”); 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(“founded\n\r”); fprintf(fil,”founded\n”); 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 DOWN\n”); 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 1\n\r”); 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)=%d\n”,ik,jk,*(matr2+ik*n+jk)); fprintf(fil,”Viynimaem tochky: pr(“top2”,top2); } perpr = 0; perlev = 0; } // IF if(perver == 1 && perniz == 1) { *(matr2+ik*n+jk)=0; printf(“Zerro 2\n\r”); 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) = %d\n”,ik,jk,*(matr2+ik*n+jk)); fprintf(fil,”Viynimaem tochky: (%d,%d) = 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(“\n\r”); 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 { 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;i printf(“Koordinatiy ytoplennoy tochki : %d and fprintf(fil,”and napravlenie”); printf(“Napravlenie”); switch(ptr->prnapr) { case 1: fprintf(fil,”Vpravo\n”); printf(“Vpravo\n\r”); break; case 2: fprintf(fil,”Vniz\n”); printf(“Vniz\n\r”); break; case 3: fprintf(fil,”Vlevo\n”); printf(“Vlevo\n\r”); break; case 4: fprintf(fil,”Vverh\n”); printf(“Vverh\n\r”); break; default: fprintf(fil,”Start\n”); printf(“Start\n\r”); break; } fprintf(fil,”WORK MATRIX\n”); for(i=0;i { if(*(po+i)\n\n\n”); printf(“Решение закрытой трансп.задачи\n\n”); printf(“Базисные переменные,равные нулю, помечаются -2;\n”); printf(“Графоклетка, относительно которой строится цепь\n”); printf(“помечается -1\n”); gotoxy(1,22); printf(“press anykey to contunio…\n”); getch(); clrscr(); data(); printf(“press anykey to contunio…\n”); getch(); clrscr(); gotoxy(1,3); printf(“\n YOU selest method building first plan:\n”); printf(“1-method NORD-WEST ygol\n”); printf(“2-method NORD-EST ygol\n”); printf(“3-method minimum element to string\n”); scanf(“%d”,&met); gotoxy(1,22); printf(“press anykey, to contunie…\n”); getch(); //void opplan(void); //void opplan1(void); //void opplan2(void); clrscr(); switch(met) { case 1: opplan(); break; case 2: opplan1(); break; case 3: opplan2(); break; default: printf(“неверно выбран МЕТОД\n”); exit(-1); } basper = 0; Bas(); flagok = 0; if(basper { //Количество базисных ненулевых переменных
*****************
***********??????????????????????????????????????
-1,\n а abcikl() параметры i,j “);
будет не бесконечный или не бесполезный 🙁 \n”);
не бесконечный или не бесполезный 🙁 \n”);
******************************
(%d,%d)=%d\n”,ik,jk,*(matr2+ik*n+jk));
%d\n”,ik,jk,*(matr2+ik*n+jk));
%d\n\r”,ptr->ick,ptr->jck);
Нашли опечатку? Выделите и нажмите CTRL+Enter