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

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

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

Курсовая

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

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

на тему

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

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

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

Мурманск

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