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

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



                                  Курсовая
                                по дисциплине
                        «Компьютерное моделирование»
                                   на тему
                            «Транспортная задача»



                                                        Выполнил: Ошкин Е.С.
                                                      Проверил: Сергеев А.В.



                                  Мурманск
                                   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
Смотрите также:
Купить водительские права в Москве купить права оригинал в Москве.

Транспортная задача
Скачать реферат
Версия для печати