рефераты Знание — сила. Библиотека научных работ.
~ Портал библиофилов и любителей литературы ~
 

МЕНЮ

рефератыГлавная
рефератыБаза готовых рефератов дипломов курсовых
рефератыБанковское дело
рефератыГосударство и право
рефератыЖурналистика издательское дело и СМИ
рефератыИностранные языки и языкознание
рефератыПраво
рефератыПредпринимательство
рефератыПрограммирование и комп-ры
рефератыПсихология
рефератыУголовное право
рефератыУголовный процесс
рефератыУправление персоналом
рефератыНовые или неперечисленные

рефераты

РЕКЛАМА


рефераты

ИНТЕРЕСНОЕ

рефераты

рефераты

 

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

рефераты

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

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

Курсовая

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

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

на тему

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

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

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

Мурманск

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



рефераты





Рекомендуем



рефераты

ОБЪЯВЛЕНИЯ


рефераты

© «Библиотека»