Advertisement
Misha_

Untitled

May 23rd, 2022
835
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. TForm1 *Form1;
  2. int N,M;//Размерность задачи
  3. float *a;  //адрес массива запасов поставщиков
  4. float *b;  //адрес массива потребностей потребителей
  5. float **C; //адрес массива(двумерного) стоимости перевозки
  6. float **X;//адрес массива(двумерного) плана доставки
  7. float *u;//адрес массива потенциалов поставщиков
  8. float *v;//адрес массива потенциалов потребителей
  9. float **D;//адрес массива(двумерного) оценок свободных ячеек таблицы
  10. bool stop;//признак достижения оптимального плана
  11. bool **T;//массив будет хранить коодинаты ячеек, в коорые уже вписывались
  12.  
  13.  
  14.        
  15.    //--------------------------Метод потенциалов
  16.  
  17.    
  18.  
  19.  
  20.  
  21.  
  22.             float find1,find2;//величина перераспределения поставки для цикла
  23.             float best1=0;//наилучшая оценка улучшения среди всех допустимых перераспределений
  24.             float best2=0;
  25.             int ib1=-1;
  26.             int jb1=-1;
  27.             int ib2=-1;
  28.             int jb2=-1;
  29.             //Ищем наилучший цикл перераспределения поставок:
  30.             for(int i=0;i<N;i++)
  31.              for(int j=0;j<M;j++)
  32.               if(D[i][j]<0)//Идём по ВСЕМ ячейкам с отрицательной оценкой
  33.                 {  //и ищем допустимые циклы перераспределения ДЛЯ КАЖДОЙ такой ячейки
  34.                     //Обнуляем матрицу Y:
  35.                     for(int i=0;i<N;i++)
  36.                      for(int j=0;j<M;j++)
  37.                        Y[i][j]=0;
  38.                     //Ищем цикл для ячейки с оценкой D[i][j]:
  39.                     find1=find_gor(i,j,i,j,N,M,X,Y,0,-1);//Начинаем идти по горизонтали
  40.  
  41.                      //Обнуляем матрицу Y:
  42.                     for(int i=0;i<N;i++)
  43.                      for(int j=0;j<M;j++)
  44.                        Y[i][j]=0;
  45.                     find2=find_ver(i,j,i,j,N,M,X,Y,0,-1);//Начинаем по вертикали
  46.  
  47.                     if(find1>0)
  48.                       if(best1>D[i][j]*find1)
  49.                          {
  50.                             best1=D[i][j]*find1;//наилучшая оценка
  51.                             ib1=i;//запомминаем координаты ячейки
  52.                             jb1=j;//цикл из которой даёт наибольшее улучшение
  53.                          }
  54.                     if(find2>0)
  55.                       if(best2>D[i][j]*find2)
  56.                          {
  57.                             best2=D[i][j]*find2;//наилучшая оценка
  58.                             ib2=i;//запомминаем координаты ячейки
  59.                             jb2=j;//цикл из которой даёт наибольшее улучшение
  60.                          }
  61.                  }
  62.              if((best1==0)&&(best2==0))
  63.              {
  64.                //stop=true;
  65.                //ShowMessage("Цикл перераспределения поставок не найден");
  66.                ok=false;
  67.                d=d1;//откат назад
  68.                for(int i=0;i<N;i++)
  69.                 for(int j=0;j<M;j++)
  70.                   if(X[i][j]==0)X[i][j]=-1;
  71.                continue;
  72.              }
  73.             else
  74.             {   //Обнуляем матрицу Y:
  75.                 for(int i=0;i<N;i++)
  76.                      for(int j=0;j<M;j++)
  77.                        Y[i][j]=0;
  78.                //возвращаемся к вычислению цикла с наилучшим перераспределением:
  79.                int ib,jb;
  80.                if(best1<best2)
  81.                    {
  82.                      find_gor(ib1,jb1,ib1,jb1,N,M,X,Y,0,-1);
  83.                      ib=ib1;
  84.                      jb=jb1;
  85.                    }
  86.                else
  87.                    {
  88.                       find_ver(ib2,jb2,ib2,jb2,N,M,X,Y,0,-1);
  89.                       ib=ib2;
  90.                       jb=jb2;
  91.                    }
  92.                for(int i=0;i<N;i++)
  93.                 {
  94.                   for(int j=0;j<M;j++)
  95.                    {
  96.                     if( (X[i][j]==0)&&(Y[i][j]<0) )
  97.                        {
  98.                          stop=true;
  99.                          ok=false;
  100.                          d=d1;//откат назад
  101.                          Memo1->Lines->Add("Попытка отрицательной поставки!");
  102.                          //ShowMessage("Попытка отрицательной поставки!");
  103.                          //break;
  104.                         }
  105.                     X[i][j]= X[i][j]+Y[i][j];//перераспределяем поставки
  106.                     if((i==ib)&&(j==jb))X[i][j]=X[i][j]+1;//добавляем 1 (т.к. до этого было -1 )
  107.                     if((Y[i][j]<=0)&&(X[i][j]==0))X[i][j]=-1;//если ячейка обнулилась, то выбрасываем её из рассмотрения
  108.                    }
  109.                   //if(stop)break;
  110.                 }
  111.               }
  112.            //
  113.           Memo1->Lines->Add("Матрица цикла перерасчёта:");
  114.           Memo1->Lines->Add("");
  115.           for(int i=0;i<N;i++)
  116.            for(int j=0;j<M;j++)
  117.             {
  118.               Memo1->Text=Memo1->Text+FloatToStr(Y[i][j])+"    ";
  119.               if(j==M-1)Memo1->Lines->Add("");
  120.              }
  121.            Memo1->Lines->Add("--------");
  122.            //ShowMessage("Для продолжения нажмите "ОК" ");
  123.  
  124.           Memo1->Lines->Add("Новый план:");
  125.           Memo1->Lines->Add("");
  126.           float F=0;
  127.           for(int i=0;i<N;i++)
  128.            for(int j=0;j<M;j++)
  129.             {
  130.               Memo1->Text=Memo1->Text+FloatToStr(X[i][j])+"    ";
  131.               if(X[i][j]>0)F=F+X[i][j]*C[i][j];
  132.               if(j==M-1)Memo1->Lines->Add("");
  133.              }
  134.            Memo1->Lines->Add("F="+FloatToStr(F));
  135.            Memo1->Lines->Add("--------");
  136.            ShowMessage("Для продолжения нажмите "ОК" ");
  137.            //
  138.  
  139.            ok=true;
  140.            for(int i=0;i<N;i++)
  141.              for(int j=0;j<M;j++)
  142.                T[i][j]=false;
  143.  
  144.  
  145.             delete []Y;
  146.  
  147.             //проверка на вырожденность: (?)
  148.            L=0;
  149.            for(int i=0;i<N;i++)
  150.              for(int j=0;j<M;j++)
  151.                if(X[i][j]>=0)L++;//подсчёт заполненных ячеек
  152.             d=M+N-1-L;//если d>0,то задача - вырожденная
  153.             d1=d;
  154.             if(d>0)ok=false;
  155.  
  156.           }
  157.  
  158.           delete []u;
  159.           delete []v;
  160.           delete []ub;
  161.           delete []vb;
  162.           delete []D;
  163.  
  164.  
  165.        }while(stop==false);
  166.  
  167.      Memo1->Lines->Add("Оптимальный план:");
  168.      Memo1->Lines->Add("");
  169.      float Fmin=0;
  170.      for(int i=0;i<N;i++)
  171.           for(int j=0;j<M;j++)
  172.             {
  173.               Memo1->Text=Memo1->Text+FloatToStr(X[i][j])+"    ";
  174.               if(X[i][j]>0)Fmin=Fmin+X[i][j]*C[i][j];
  175.               if(j==M-1)Memo1->Lines->Add("");
  176.              }
  177.      Memo1->Lines->Add("Fmin="+FloatToStr(Fmin));
  178.  
  179.       delete []X;
  180.       delete []C;
  181.       delete []a;
  182.       delete []b;
  183. }
  184. //---------------------------------------------------------------------------
  185.      //Функуция поиска ячеек,подлежащих циклу перераспределения (вдоль строки)
  186. float TForm1::find_gor(int i_next,int j_next,int im,int jm,int n,int m,float** X,float** Y,int odd,float Xmin)
  187. {
  188.    int rez=-1;
  189.    for(int j=0;j<m;j++)//идём вдоль строки, на которой стоим
  190.  //ищем заполненную ячейку(кроме той,где стоим) или начальная ячейка(но уже в конце цикла:odd!=0 )
  191.      if(((X[i_next][j]>=0)&&(j!=j_next))||((j==jm)&&(i_next==im)&&(odd!=0)))
  192.        {
  193.          odd++;//номер ячейки в цикле перерасчёта(начало с нуля)
  194.          if(odd>1000)
  195.            {
  196.               ShowMessage("Угроза переполнения стека");
  197.               return -1;
  198.            }
  199.          int Xmin_old=-1;
  200.          if((odd%2)==1)//если ячейка нечётная в цикле ( начальная- нулевая )
  201.           {
  202.            Xmin_old=Xmin;//Запоминаем значение минимальной поставки в цикле (на случай отката назад)
  203.            if(Xmin<0)Xmin=X[i_next][j];//если это первая встреченная ненулевая ячейка
  204.            else if((X[i_next][j]<Xmin)&&(X[i_next][j]>=0))
  205.                      {
  206.                        Xmin=X[i_next][j];
  207.                        
  208.                      }
  209.           }
  210.          if((j==jm)&&(i_next==im)&&((odd%2)==0))//если замкнулся круг и цикл имеет чётное число ячеек
  211.            {
  212.              Y[im][jm]= Xmin;//Значение минимальной поставки, на величину которой будем изменять
  213.              return Xmin;
  214.             }
  215.            //если круг еще не замкнулся - переходим к поиску по вертикали:
  216.          else rez=find_ver(i_next,j,im,jm,n,m,X,Y,odd,Xmin);//рекурсивный вызов
  217.          if(rez>=0)//как бы обратный ход рекурсии(в случае если круг замкнулся)
  218.             {
  219.               //для каждой ячейки цикла заполняем матрицу перерасчёта поставок:
  220.               if(odd%2==0)Y[i_next][j]=Y[im][jm];//в чётных узлах прибавляем
  221.               else  Y[i_next][j]=-Y[im][jm];//в нечётных узлах вычитаем
  222.               break;
  223.             }
  224.          else //откат назад в случае неудачи(круг не замкнулся):
  225.            {
  226.              odd--;
  227.              if(Xmin_old>=0)//если мы изменяли Xmin на этой итерации
  228.                 Xmin=Xmin_old;
  229.            }
  230.        }
  231.  
  232.    return rez;//если круг замкнулся (вернулись в исходную за чётное число шагов) -
  233.    // возвращает найденное минимальное значение поставки в нечётных ячейках цикла,
  234.    // если круг не замкнулся, то возвращает -1.
  235. }
  236. //-----------------------------------------------------------------------------
  237.     //Функуция поиска ячеек,подлежащих циклу перераспределения (вдоль столбца)
  238. float TForm1::find_ver(int i_next,int j_next,int im,int jm,int n,int m,float** X,float** Y,int odd,float Xmin)
  239. {
  240.    int rez=-1;
  241.    int i;
  242.    for(i=0;i<n;i++)//идём вдоль столбца, на котором стоим
  243.  //ищем заполненную ячейку(кроме той,где стоим) или начальная ячейка(но уже в конце цикла:odd!=0 )
  244.      if(((X[i][j_next]>=0))&&(i!=i_next)||((j_next==jm)&&(i==im)&&(odd!=0)))
  245.        {
  246.          odd++;//номер ячейки в цикле перерасчёта(начало с нуля)
  247.          if(odd>1000)
  248.            {
  249.               ShowMessage("Угроза переполнения стека");
  250.               return -1;
  251.            }
  252.          int Xmin_old=-1;
  253.          if((odd%2)==1)//если ячейка нечётная в цикле ( начальная- нулевая )
  254.           {
  255.             Xmin_old=Xmin;//Запоминаем значение минимальной поставки в цикле (на случай отката назад)
  256.             if(Xmin<0)Xmin=X[i][j_next];//если это первая встреченная ненулевая ячейка
  257.             else if((X[i][j_next]<Xmin)&&(X[i][j_next]>=0))
  258.                        Xmin=X[i][j_next];
  259.  
  260.  
  261.           }
  262.          if((i==im)&&(j_next==jm)&&((odd%2)==0))//если замкнулся круг и цикл имеет чётное число ячеек
  263.             {
  264.               Y[im][jm]= Xmin;//Значение минимальной поставки, на величину которой будем изменять
  265.               return Xmin;
  266.             }
  267.             //если круг еще не замкнулся - переходим к поиску по горизонтали:
  268.          else rez=find_gor(i,j_next,im,jm,n,m,X,Y,odd,Xmin);//- рекурсивный вызов
  269.          if(rez>=0)//как бы обратный ход (в случае если круг замкнулся)
  270.             {
  271.               //для каждой ячейки цикла заполняем матрицу перерасчёта поставок:
  272.               if(odd%2==0)Y[i][j_next]=Y[im][jm];//эти прибавляются
  273.               else  Y[i][j_next]=-Y[im][jm];//эти вычитаются
  274.               break;
  275.             }
  276.          else //откат назад в случае неудачи (круг не замкнулся):
  277.            {
  278.              odd--;
  279.              if(Xmin_old>=0)//если мы изменяли Xmin на этой итерации
  280.                 Xmin=Xmin_old;
  281.            }
  282.        }
  283.  
  284.    return rez;
  285. }
Advertisement
RAW Paste Data Copied
Advertisement