Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Транспортная задача

Название: Транспортная задача
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 00:01:17 29 августа 2005 Похожие работы
Просмотров: 198 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Мурманский филиал Петровского Колледжа

Курсовая

по дисциплине

«Компьютерное моделирование»

на тему

«Транспортная задача»

Выполнил: Ошкин Е.С.

Проверил: Сергеев А.В.

Мурманск

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);

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<m;i++)

{

for(j=0;j<n;j++)

{

printf("Введите [%d][%d]\n ",i,j);

scanf("%d",&t);

*(st+i*n+j)=t;

}

}

printf("\n");

fprintf(fil,"\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;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<m;i++)

{

printf("\n");

scanf("%d",po+i);

printf("%5d",*(po+i));

}

printf("\n");

printf("Введите потребности:\n");

for(j=0;j<n;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<m;i++)

{

for(j=ch1;j<n;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<m;i++)

{

for(j=0;j<n;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<m;i++)

{

for(j=0;j<n;j++)

{

*(matr1+i*n+j) = *(matr+i*n+j);

}

}

// Подсчет стоимости базисной матрицы (созданного массива)

for(i=0;i<m;i++)

{

for(j=0;j<n;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<m;i++)

*(pu+i) = MIN;

for(j=0;j<n;j++)

*(pv+j) = MIN;

// Выделение памяти под структуру и заполнение её значениями

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if((*(matr+i*n+j) > 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;i<n;i++)

{

printf("%d",*(pv+i));

fprintf(fil,"%5d",*(pv+i));

}

getch();

printf("\n ПОТЕНЦИАЛЫ ПО u: ");

fprintf(fil,"\n **** ПОТЕНЦИАЛЫ ПО u: ");

for(i=0;i<m;i++)

{

printf("%d",*(pu+i));

fprintf(fil,"%5d",*(pu+i));

}

fprintf(fil,"\n");

for(top = topnast;top!=NULL;top = top->next)

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<m;i++)

{

for(j=0;j<n;j++)

{

// ИЩЕМ ОПТИМАЛЬНОЕ РЕШЕНИЕ В НАШЕЙ МАТРИЦЕ И ЕСЛИ ЕГО НЕ НАЙДЕМ

// ТО ПО СЛЕДУЮЩЕМУ УСЛОВИЮ ПРИСВОИМ ГРАФОКЛЕТКЕ С КООРДИНАТАМИ

// ik,jk ЗНАЧЕНИЕ -1

if(( *(pu+i)+ *(pv+j))>(*(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;i<m;i++)

{

for(j=0;j<n;j++)

{

*(matr2+i*n+j) = *(matr+i*n+j); // Создаем копию рабочей матрицы

}

}

*(matr2+ik*n+jk) = -1;

// значению матрицы с параметрами ik,jk присваеваем -1

printf("\n");

printf("Поиск Цепи: \n\n");

fprintf(fil,"Поиск Цепи: \n\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

fprintf(fil,"%5d",*(matr2+i*n+j));

printf("%5d",*(matr2+i*n+j));

}

fprintf(fil,"\n");

printf("\n");

}

fprintf(fil,"\n\n Переходим в Сраную, Мать её, Функцию cikl(ik,jk) \n");

getch();

cikl(ik,jk);

return;

} // abcikl

// ********* FUNKCION POISKA CIKLA **************************

int cikl(int ik,int jk)

{

int nst,nstr,i,j,

perlev = 0,

perpr = 0;

int perver = 0,

perniz = 0,

fl = 0,

fl3 = 1;

int napr;

struct cik { int prnapr;

int ick;

int jck;

struct cik *next;

} *topnast1 = NULL,

*top2 = NULL,

*top3 = NULL;

ch = 0;

if((top2 = (struct cik*)malloc(sizeof(struct cik))) == NULL)

abort();

if(!topnast1)

{

topnast1=top2;

top3=top2;

top3->ick=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<n;j++)

{

if((*(matr2+i1*n+j))!=0)

return(j);

}

return(-1);

}

int levpoisk(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;i<m;i++)

{

if((*(matr2+i*n+j1))!=0)

return(i);

}

return(-1);

}

// ************* FUNCTION SEARCH ********************

void pr(char pr[],void *st)

{

struct cik { int prnapr;

int ick;

int jck;

struct cik *next;

} *ptr;

int i,j;

ptr = (struct cik *)st;

fprintf(fil,"Koordinatiy ytoplennoy tochki : %d and %d",ptr->ick,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<m;i++)

{

for(j=0;j<n;j++)

{

fprintf(fil,"%5d",*(matr2+i*n+j));

}

fprintf(fil,"\n");

}

fprintf(fil,"************************************\n");

return;

}

// **************** UPGRADE PLAN *********************************//

void plmi(void)

{

int i,j,k,min,i1,j1,flagok;

ch = ch2;

flagok = 0;

i1=*zi;

j1 = *zj;

for(k=1;k<ch;k+=2){

i=*(zi+k);

j = *(zj+k);

if(*(matr+i*n+j) == -2){

*(matr+i1*n+j1) = *(matr+i*n+j);

*(matr+i*n+j) = 0;

flagok = 1;

break;

}

} // for

if(!flagok){

for(k=2;k<ch;k+=2){

i = *(zi+k);

j = *(zj+k);

if(*(matr+i*n+j) == -2)

*(matr+i*n+j) = 0;

} // for

i = *(zi+1);

j = *(zj+1);

min = *(matr+i*n+j);

for(k=3;k<ch;k+=2){

i=*(zi+k);

j=*(zj+k);

if(*(matr+i*n+j)<min)

min = *(matr+i*n+j);

}

if(min == -2) min = 0;

for(k=0;k<ch;k+=2){

i = *(zi+k);

j = *(zj+k);

*(matr+i*n+j) += min;

}

for(k=1;k<ch;k+=2){

i=*(zi+k);

j=*(zj+k);

*(matr+i*n+j)-=min;

}

} //if

// ***************** PROVERKA **************************//

printf("PROVERKA\n");

for(i=0;i<m;i++){

for(j=0;j<n;j++){

printf("%5d",*(matr+i*n+j));

}

printf("\n");

}

free(matr2);free(zi);free(zj);free(pu);free(pv);

return;

}

void Bas(void)

{

int i,j;

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if(*(matr+i*n+j)!=0) basper++;

}

}

return;

}

void sohran(void)

{

// Sravnenie

int i,j,k;

for(k=0;k<ch;k++)

{

i=zi[k];

j=zj[k];

if((*(matr+i*n+j) == 0) && (basper < m+n-1))

{

*(matr+i*n+j) = -2;

basper++;

}//if

}

return;

}

// ************ SOZDANIE OPORNOGO PLANA **************************

// ************ METODOM SEVERNO-ZAPADNOGO YGLA *******************

void opplan1(void)

{

int i,j, ch1 = n-1;

//**************** Viydelenie pamyty *************************

if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();

for(i=0;i<m;i++)

{

for(j=ch1;j>=0;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--;

}

}

//*************** Proverka *************************

printf("Proverka\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

printf("%5d",*(matr+i*n+j));

}

printf("\n");

}

fprintf(fil,"matrix\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

fprintf(fil,"%5d",*(matr+i*n+j));

}

fprintf(fil,"\n");

}

fprintf(fil,"*****************\n");

return;

}//******** opplan1

//************** SOZDANIE OPORNOGO PLANA ********************

//*************** METHOD NORD-WEST YGOL *********************

void opplan2(void)

{

int i,j,k_i,k_j=0, min = 32767, *kontr,fl;

if((matr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();

if((kontr=(int*)calloc(m*n,sizeof(int))) == NULL) abort();

for(i=0;i<m;i++){

for(j=0;j<n;j++){

*(kontr+i*n+j) = 0;

}

}

for(i=0;i<m;i++){

fl = 0;

while(!fl){

for(j=0;j<n;j++){

if(*(st+i*n+j)<min){

if(*(kontr+i*n+j) == 0) {

min = *(st+i*n+j);

k_i = i; k_j = j;

}

}

}

*(kontr+k_i*n+k_j) = 1;

if(*(po+k_i)<*(pn+k_j)) {

min = 32767;

*(matr+k_i*n+k_j)=*(po+k_i);

*(pn+k_j)=*(po+k_i);

*(po+k_i)=0;

break;

}

else {

*(matr+k_i*n+k_j)=*(pn+k_j);

*(po+k_i)-=*(pn+k_j);

*(pn+k_j)=0;

min = 32767;

if(*(po+k_i) == 0) fl = 1;

}

}

}

printf("Proverka\n"); // proverka

for(i=0;i<m;i++){

for(j=0;j<n;j++){

printf("%5d",*(matr+i*n+j));

}

printf("\n");

}

fprintf(fil," matr\n");

for(i=0;i<m;i++){

for(j=0;j<n;j++){

fprintf(fil,"%5d",*(matr+i*n+j));

}

fprintf(fil,"\n");

}

fprintf(fil,"*********************************\n");

return;

}// opplan2

void main()

{

int i,j,met;

int flagok;

fil = fopen("otchet.txt","w");

clrscr();

gotoxy(1,3);

printf("WARNING USERS ---->\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<m+n-1)

{

//Если в первоначальном плане количество базисных

//переменных, отличных от нуля, меньше, чем M+N-1

while(!flagok)

{

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

if(*(matr+i*n+j)==0)

{

*(matr+i*n+j) = -2;

flagok = 1;

basper++;

break;

} //if

}

if(flagok) break;

}

if(basper<m+n-1) flagok = 0;

}//while

}//if

for(;;)

{

fprintf(fil,"*********** Начало ДОЛБАНУТОЙ Итерации**********\n");

basper = 0;

Bas();

//void sohran(void);

if(iter>0)

{

//Количество базисных ненулевых переменных <m+n-1

if(basper <m+n-1) sohran();

}

kost(); //****** Вывод общей стоимости******

potenzial(); //*******Подсчет потенциалов********

ch2 = 0;

z = optim();

if(!z) break;

plmi();

iter++;

fprintf(fil,"%d ШАГ ДОСТАВШЕЙ ДО СЪЕХАВШЕЙ КРЫШИ ИТЕРАЦИИ",iter);

}

//************* ПРОВЕРКА************

printf("\n\nOPTIMAL PLAN :\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

printf("%5d",*(matr+i*n+j));

}

printf("\n");

}

fprintf(fil,"optimal PLAN :\n");

for(i=0;i<m;i++)

{

for(j=0;j<n;j++)

{

fprintf(fil,"%5d",*(matr+i*n+j));

}

fprintf(fil,"\n");

}

kost(); //************ВЫВОД общей стоимости***********

fclose(fil);

clrscr();

printf("Отчет о проделанной работе ПРОГРАММЫ в файле otchet.txt");

getch();

return;

} // main

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:13:24 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
13:26:31 24 ноября 2015

Работы, похожие на Реферат: Транспортная задача

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150684)
Комментарии (1839)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru