Advertisement
Misha_

Untitled

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