|
Транспортная задачаТранспортная задачаМурманский филиал Петровского Колледжа Курсовая по дисциплине «Компьютерное моделирование» на тему «Транспортная задача» Выполнил: Ошкин Е.С. Проверил: Сергеев А.В. Мурманск 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;i0) 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 0) || (*(matr+i*n+j)==-2)) { 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;inext) free(top); return; } // potenzial // ****** PROVERKA PLANA NA OPTIMALNOST' ************************ void abcikl(int ik,int jk); int cikl(int ik,int jk); 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(*(st+i*n+j))&&((*(matr+i*n+j)) == 0)) { abcikl(i,j); fprintf(fil,"optim(): План не оптимален, функции main() возвращаем -1,\n а abcikl() параметры i,j "); 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;iick=ik; 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 что он будет не бесконечный или не бесполезный :( \n"); printf("Весь цикл поиска сейчас начнется, надеюсь - \n что он будет не бесконечный или не бесполезный :( \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: (%d,%d)=%d\n",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 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) = %d\n",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("\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=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 %d\n\r",ptr- >ick,ptr->jck); 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=0;j--) { 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(basper0) { //Количество базисных ненулевых переменных if(basper } kost(); //****** Вывод общей стоимости****** potenzial(); //*******Подсчет потенциалов******** ch2 = 0; z = optim(); if(!z) break; plmi(); iter++; fprintf(fil,"%d ШАГ ДОСТАВШЕЙ ДО СЪЕХАВШЕЙ КРЫШИ ИТЕРАЦИИ",iter); } //************* ПРОВЕРКА************ printf("\n\nOPTIMAL PLAN :\n"); for(i=0;i { for(j=0;j { printf("%5d",*(matr+i*n+j)); } printf("\n"); } fprintf(fil,"optimal PLAN :\n"); for(i=0;i { for(j=0;j { fprintf(fil,"%5d",*(matr+i*n+j)); } fprintf(fil,"\n"); } kost(); //************ВЫВОД общей стоимости*********** fclose(fil); clrscr(); printf("Отчет о проделанной работе ПРОГРАММЫ в файле otchet.txt"); getch(); return; } // main |
|
