45474 (Транспортная задача)
Описание файла
Документ из архива "Транспортная задача", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "45474"
Текст из документа "45474"
24
Мурманский филиал Петровского Колледжа
Курсовая
по дисциплине
«Компьютерное моделирование»
на тему
«Транспортная задача»
Выполнил: Ошкин Е.С.
Проверил: Сергеев А.В.
Мурманск
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 { for(j=0;j { printf("Введите [%d][%d]\n ",i,j); scanf("%d",&t); *(st+i*n+j)=t; } } printf("\n"); fprintf(fil,"\n"); for(i=0;i { for(j=0;j { printf("%5d",*(st+i*n+j)); fprintf(fil,"%5d",*(st+i*n+j)); } printf("\n"); fprintf(fil,"\n"); } printf("Введите количество запасов на каждом складе:\n"); for(i=0;i { printf("\n"); scanf("%d",po+i); printf("%5d",*(po+i)); } printf("\n"); printf("Введите потребности:\n"); for(j=0;j { printf("\n"); scanf("%d",pn+j); printf("%5d",*(pn+j)); } return; }//**** data //************* SOZDANIE OPORNOGO PLANA ******************** //************* METHOD NORD-WEST YGLA ********************** void opplan(void) { int i,j,ch1 = 0; //*************** ВЫДЕЛЕНИЕ ПАМЯТИ ************************* if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort(); // ЦИКЛ ПРОСТОГО РАСПРЕДЕЛЕНИЯ ПОТРЕБНОСТЕЙ по ячейкам рабочей матрицы for(i=0;i { for(j=ch1;j { if(*(po+i)<*(pn+j)) { *(matr+i*n+j)=*(po+i); *(pn+j)-=*(po+i); *(po+i)=0; break; } *(matr+i*n+j)=*(pn+j); *(po+i) -= *(pn+j); *(pn+j)=0; ch1++; } } //********* ПРОВЕРКА И ВЫвод получившейся матрицы *********************** printf("PROVERKA\n"); fprintf(fil,"PROVERKA MATRIX - Северо заподный УГОЛ,\n просмотр получившегося распределения в матрице \n"); for(i=0;i { for(j=0;j { printf("%5d",*(matr+i*n+j)); fprintf(fil,"%d",*(matr+i*n+j)); } printf("\n"); fprintf(fil,"\n"); } fprintf(fil,"********************\n"); return; } // opplan void kost(void) { int i,j, *matr1,rez=0; //выделение памяти if((matr1=(int*)calloc(n*m,sizeof(int))) == NULL) abort(); //присвоение новой матрице значения базисной(старой) матрицы for(i=0;i { for(j=0;j { *(matr1+i*n+j) = *(matr+i*n+j); } } // Подсчет стоимости базисной матрицы (созданного массива) for(i=0;i { for(j=0;j { if(*(matr1+i*n+j)>0) 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 *(pu+i) = MIN; for(j=0;j *(pv+j) = MIN; // Выделение памяти под структуру и заполнение её значениями for(i=0;i { for(j=0;j