TForm1 * Form1;
int N, M; //Размерность задачи
float * a; //адрес массива запасов поставщиков
float * b; //адрес массива потребностей потребителей
float ** C; //адрес массива(двумерного) стоимости перевозки
float ** X; //адрес массива(двумерного) плана доставки
float * u; //адрес массива потенциалов поставщиков
float * v; //адрес массива потенциалов потребителей
float ** D; //адрес массива(двумерного) оценок свободных ячеек таблицы
bool stop; //признак достижения оптимального плана
bool ** T; //массив будет хранить коодинаты ячеек, в коорые уже вписывались

//--------------------------Метод потенциалов

float find1, find2; //величина перераспределения поставки для цикла
float best1 = 0; //наилучшая оценка улучшения среди всех допустимых перераспределений
float best2 = 0;
int ib1 = -1;
int jb1 = -1;
int ib2 = -1;
int jb2 = -1;
//Ищем наилучший цикл перераспределения поставок:
for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
    if (D[i][j] < 0) //Идём по ВСЕМ ячейкам с отрицательной оценкой
{ //и ищем допустимые циклы перераспределения ДЛЯ КАЖДОЙ такой ячейки
  //Обнуляем матрицу Y:
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      Y[i][j] = 0;
  //Ищем цикл для ячейки с оценкой D[i][j]:
  find1 = find_gor(i, j, i, j, N, M, X, Y, 0, -1); //Начинаем идти по горизонтали

  //Обнуляем матрицу Y:
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      Y[i][j] = 0;
  find2 = find_ver(i, j, i, j, N, M, X, Y, 0, -1); //Начинаем по вертикали

  if (find1 > 0)
    if (best1 > D[i][j] * find1) {
      best1 = D[i][j] * find1; //наилучшая оценка
      ib1 = i; //запомминаем координаты ячейки
      jb1 = j; //цикл из которой даёт наибольшее улучшение
    }
  if (find2 > 0)
    if (best2 > D[i][j] * find2) {
      best2 = D[i][j] * find2; //наилучшая оценка
      ib2 = i; //запомминаем координаты ячейки
      jb2 = j; //цикл из которой даёт наибольшее улучшение
    }
}
if ((best1 == 0) && (best2 == 0)) {
  //stop=true;
  //ShowMessage("Цикл перераспределения поставок не найден");
  ok = false;
  d = d1; //откат назад
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      if (X[i][j] == 0) X[i][j] = -1;
  continue;
} else { //Обнуляем матрицу Y:
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      Y[i][j] = 0;
  //возвращаемся к вычислению цикла с наилучшим перераспределением:
  int ib, jb;
  if (best1 < best2) {
    find_gor(ib1, jb1, ib1, jb1, N, M, X, Y, 0, -1);
    ib = ib1;
    jb = jb1;
  } else {
    find_ver(ib2, jb2, ib2, jb2, N, M, X, Y, 0, -1);
    ib = ib2;
    jb = jb2;
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if ((X[i][j] == 0) && (Y[i][j] < 0)) {
        stop = true;
        ok = false;
        d = d1; //откат назад
        Memo1 -> Lines -> Add("Попытка отрицательной поставки!");
        //ShowMessage("Попытка отрицательной поставки!");
        //break;
      }
      X[i][j] = X[i][j] + Y[i][j]; //перераспределяем поставки
      if ((i == ib) && (j == jb)) X[i][j] = X[i][j] + 1; //добавляем 1 (т.к. до этого было -1 )
      if ((Y[i][j] <= 0) && (X[i][j] == 0)) X[i][j] = -1; //если ячейка обнулилась, то выбрасываем её из рассмотрения
    }
    //if(stop)break;
  }
}
//
Memo1 -> Lines -> Add("Матрица цикла перерасчёта:");
Memo1 -> Lines -> Add("");
for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++) {
    Memo1 -> Text = Memo1 -> Text + FloatToStr(Y[i][j]) + "    ";
    if (j == M - 1) Memo1 -> Lines -> Add("");
  }
Memo1 -> Lines -> Add("--------");
//ShowMessage("Для продолжения нажмите "ОК" ");

Memo1 -> Lines -> Add("Новый план:");
Memo1 -> Lines -> Add("");
float F = 0;
for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++) {
    Memo1 -> Text = Memo1 -> Text + FloatToStr(X[i][j]) + "    ";
    if (X[i][j] > 0) F = F + X[i][j] * C[i][j];
    if (j == M - 1) Memo1 -> Lines -> Add("");
  }
Memo1 -> Lines -> Add("F=" + FloatToStr(F));
Memo1 -> Lines -> Add("--------");
ShowMessage("Для продолжения нажмите "
  ОК " ");
//

ok = true;
for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
    T[i][j] = false;

delete[] Y;

//проверка на вырожденность: (?)
L = 0;
for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
    if (X[i][j] >= 0) L++; //подсчёт заполненных ячеек
d = M + N - 1 - L; //если d>0,то задача - вырожденная
d1 = d;
if (d > 0) ok = false;

}

delete[] u;
delete[] v;
delete[] ub;
delete[] vb;
delete[] D;

}
while (stop == false);

Memo1 -> Lines -> Add("Оптимальный план:");
Memo1 -> Lines -> Add("");
float Fmin = 0;
for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++) {
    Memo1 -> Text = Memo1 -> Text + FloatToStr(X[i][j]) + "    ";
    if (X[i][j] > 0) Fmin = Fmin + X[i][j] * C[i][j];
    if (j == M - 1) Memo1 -> Lines -> Add("");
  }
Memo1 -> Lines -> Add("Fmin=" + FloatToStr(Fmin));

delete[] X;
delete[] C;
delete[] a;
delete[] b;
}
//---------------------------------------------------------------------------
//Функуция поиска ячеек,подлежащих циклу перераспределения (вдоль строки)
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) {
  int rez = -1;
  for (int j = 0; j < m; j++) //идём вдоль строки, на которой стоим
    //ищем заполненную ячейку(кроме той,где стоим) или начальная ячейка(но уже в конце цикла:odd!=0 )
    if (((X[i_next][j] >= 0) && (j != j_next)) || ((j == jm) && (i_next == im) && (odd != 0))) {
      odd++; //номер ячейки в цикле перерасчёта(начало с нуля)
      if (odd > 1000) {
        ShowMessage("Угроза переполнения стека");
        return -1;
      }
      int Xmin_old = -1;
      if ((odd % 2) == 1) //если ячейка нечётная в цикле ( начальная- нулевая )
      {
        Xmin_old = Xmin; //Запоминаем значение минимальной поставки в цикле (на случай отката назад)
        if (Xmin < 0) Xmin = X[i_next][j]; //если это первая встреченная ненулевая ячейка
        else if ((X[i_next][j] < Xmin) && (X[i_next][j] >= 0)) {
          Xmin = X[i_next][j];

        }
      }
      if ((j == jm) && (i_next == im) && ((odd % 2) == 0)) //если замкнулся круг и цикл имеет чётное число ячеек
      {
        Y[im][jm] = Xmin; //Значение минимальной поставки, на величину которой будем изменять
        return Xmin;
      }
      //если круг еще не замкнулся - переходим к поиску по вертикали:
      else rez = find_ver(i_next, j, im, jm, n, m, X, Y, odd, Xmin); //рекурсивный вызов
      if (rez >= 0) //как бы обратный ход рекурсии(в случае если круг замкнулся)
      {
        //для каждой ячейки цикла заполняем матрицу перерасчёта поставок:
        if (odd % 2 == 0) Y[i_next][j] = Y[im][jm]; //в чётных узлах прибавляем
        else Y[i_next][j] = -Y[im][jm]; //в нечётных узлах вычитаем
        break;
      } else //откат назад в случае неудачи(круг не замкнулся):
      {
        odd--;
        if (Xmin_old >= 0) //если мы изменяли Xmin на этой итерации
          Xmin = Xmin_old;
      }
    }

  return rez; //если круг замкнулся (вернулись в исходную за чётное число шагов) -
  // возвращает найденное минимальное значение поставки в нечётных ячейках цикла,
  // если круг не замкнулся, то возвращает -1.
}
//-----------------------------------------------------------------------------
//Функуция поиска ячеек,подлежащих циклу перераспределения (вдоль столбца)
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) {
  int rez = -1;
  int i;
  for (i = 0; i < n; i++) //идём вдоль столбца, на котором стоим
    //ищем заполненную ячейку(кроме той,где стоим) или начальная ячейка(но уже в конце цикла:odd!=0 )
    if (((X[i][j_next] >= 0)) && (i != i_next) || ((j_next == jm) && (i == im) && (odd != 0))) {
      odd++; //номер ячейки в цикле перерасчёта(начало с нуля)
      if (odd > 1000) {
        ShowMessage("Угроза переполнения стека");
        return -1;
      }
      int Xmin_old = -1;
      if ((odd % 2) == 1) //если ячейка нечётная в цикле ( начальная- нулевая )
      {
        Xmin_old = Xmin; //Запоминаем значение минимальной поставки в цикле (на случай отката назад)
        if (Xmin < 0) Xmin = X[i][j_next]; //если это первая встреченная ненулевая ячейка
        else if ((X[i][j_next] < Xmin) && (X[i][j_next] >= 0))
          Xmin = X[i][j_next];

      }
      if ((i == im) && (j_next == jm) && ((odd % 2) == 0)) //если замкнулся круг и цикл имеет чётное число ячеек
      {
        Y[im][jm] = Xmin; //Значение минимальной поставки, на величину которой будем изменять
        return Xmin;
      }
      //если круг еще не замкнулся - переходим к поиску по горизонтали:
      else rez = find_gor(i, j_next, im, jm, n, m, X, Y, odd, Xmin); //- рекурсивный вызов
      if (rez >= 0) //как бы обратный ход (в случае если круг замкнулся)
      {
        //для каждой ячейки цикла заполняем матрицу перерасчёта поставок:
        if (odd % 2 == 0) Y[i][j_next] = Y[im][jm]; //эти прибавляются
        else Y[i][j_next] = -Y[im][jm]; //эти вычитаются
        break;
      } else //откат назад в случае неудачи (круг не замкнулся):
      {
        odd--;
        if (Xmin_old >= 0) //если мы изменяли Xmin на этой итерации
          Xmin = Xmin_old;
      }
    }

  return rez;
}