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

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

Курсовая

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

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

на тему

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

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

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

Мурманск

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