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

1



2







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























Курсовая

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

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

на тему

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

































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

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











Мурманск

2002г.

Описание Алгоритма программы



ПРОГРАММА НАПИСАНА НА BORLAND С++ версии 3.1



Программа решает Транспортную Задачу (ТЗ) 3 методами:

Северо-западным углом

Северо-восточным углом

Методом минимального элемента в строке.

   Программа состоит из функций:

Main()

Data()

Opplan()

Sohran()

Bas()

Kost()

Potenzial()

Optim()

Plmi()

Abcikl()

Cikl()

Prpoisk()

Levpoisk()

Verpoisk()

Nizpoisk()

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