Реферат: Транспортная задача
Реферат: Транспортная задача
Мурманский филиал Петровского Колледжа
Курсовая
по дисциплине
«Компьютерное моделирование»
на тему
«Транспортная задача»
Выполнил: Ошкин Е.С.
Проверил: Сергеев А.В.
Мурманск
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 <stdio.h> //Подключение стандартных
#include <alloc.h> // Библиотек
#include <conio.h>
#include <process.h>
#include <stdlib.h>
#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);
