Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

. Выделение памяти под элемент структуры 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);

Рекомендуем скачать другие рефераты по теме: отчет по производственной практике, экология реферат.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата