Применение методов линейного программирования

p>     } plan_t; 
 

     int cn=0;   // длина вектора исходного ур-я

     int cnr=0;   /* cn, только без членов == 0 (cnr==cn_real)

                                         нужно только для  вывода сокращенной таблицы */

     float *c = NULL; // исходное ур-е 

     int m=0, n=0;  // размеры матрицы условий

     float **a = NULL; // матрица условий

     float *b = NULL; // столбец свободных членов матрицы условий 

     int *base = NULL; // базовые переменные 

     float zb=0;   // оценки оптимальности b

     float *za = NULL; // оценки оптимальности a 

     int base_column = -1; // разрешающий столбец

     int base_row = -1;  // разрешающая строка 

     bool full_table = true; // вид выводимой таблицы: true==полная, false==сжатая 
 

     void FreeMem ()

     {

           delete[] za;

           delete[] base;

           delete[] b; 

           for (int i=0; i<m; i++)

                 delete[] a[i];

           delete[] a; 

           delete[] c;

     } 

     bool ReadInput (char *filename)

     {

           int i,j;

           FILE *f = fopen(filename, "r");

           if (NULL == f)

                 return false; 
 

           // исходное ур-е

           fscanf(f, "%i", &cn);

           c = new float [cn]; 

           cnr=cn; 

           for (i=0; i<cn; i++)

           {

                 fscanf(f, "%f", &c[i]);

                 if (0 == c[i]) cnr--;

           } 
 

           // матрица условий

           fscanf(f, "%i %i", &n, &m);

           a = new float* [m]; 

           for (i=0; i<m; i++)

                 a[i] = new float[n]; 

           b = new float [m]; 

           for (j=0; j<m; j++)

           {

                 for (i=0; i<n; i++)

                       fscanf(f, "%f", &a[j][i]); 

                 fscanf(f, "%f", &b[j]);

           } 
 

           // базовые переменные

           base = new int [m]; 

           for (j=0; j<m; j++)

           {

                 fscanf(f, "%i", &base[j]);

                 --base[j];

           } 
 

           // флаг - полную или  сжатую таблицу выводить ?

           int flag = 1; 

           fscanf(f, "%i", &flag);

           full_table = flag ? true : false; 
 

           fclose(f); 

           za = new float[n]; 

     // for(i=0;i<n;i++)za[i]=0;// !!! только для отладки !!! 

           return true;

     } 

     // Вычисление оценок оптимальности  {za==delta_j[] and zb==Z}

     void EvaluationOptimal ()

     {

           int i,j;

           zb=0;

           for (i=0; i<n; i++) za[i]=0; 

           for (j=0; j<m; j++)

           {

                 for (i=0; i<n; i++)

                       za[i] += c[base[j]]*a[j][i]; 

                 zb += c[base[j]]*b[j];

           } 

           for (i=0; i<n; i++)

                 za[i] -= c[i];

     } 

     // Построение опорного плана (этот  этап только в двойственном  симплекс-методе)

     plan_t BuildPsevdoPlan ()

     {

           int i,j;

           base_column = -1; // разрешающий столбец

           base_row = -1;  // разрешающая строка

           float acc; // временно: аккумулятор - будет хранить min, max, etc. 
 

           acc = 0; // min отрицательное значение b

           for (j=0; j<m; j++)

                 if (b[j] < acc)

                 {

                       acc = b[j];

                       base_row = j;

                 } 

           if (-1 == base_row)

                 return DUAL_DONE; 
 

           acc = -MAXDIGIT; // max отношение za к отрицат. эл-там в строке base_row

           for (i=0; i<n; i++)

           {

                 float temp;

                 if (a[base_row][i] < 0 && (temp = za[i]/a[base_row][i]) > acc)

                 {

                       acc = temp;

                       base_column = i;

                 }

           } 

           if (-1 == base_column)

                 return ODR_EMPTY; 
 

           return NEXT_ITERATION;

     } 

     // Проверка опорного плана на  оптимальность

     plan_t CheckStrongPlan ()

     {

           int i,j;

           float za_min = 0;

           base_column = -1; // разрешающий столбец

           base_row = -1;  // разрешающая строка 

           // выбор разрешающего  столбца

           for (i=0; i<n; i++)

           {

                 if (za[i] >= 0)

                       continue;

                 else if (za[i] < za_min)

                 {

                       za_min = za[i];

                       base_column = i;

                 }

           } 

           if (-1 == base_column)

                 return PLAN_OPTIMAL; 
 

           za_min = MAXDIGIT; 

           // выбор разрешающей  строки

           for (j=0; j<m; j++)

           {

                 if (a[j][base_column] > 0)

                 {

                       float t = b[j]/a[j][base_column];

                       if (t < za_min)

                       {

                             za_min = t;

                             base_row = j;

                       }

                 }

           } 

           if (-1 == base_row)

                 return ODR_BREAK; 

           return NEXT_ITERATION;

     } 

     // Преобразование таблицы по ф-лам  Жордана-Гаусса

     void JGTransformation (int base_row, int base_column)

     {

           // проверка на  всякий случай: чтобы не было  деления на нуль

           if (0 == a[base_row][base_column]) return; 

           base[base_row] = base_column; 

           int i,j; 

           float **a2 = new float* [m]; // матрица условий

           float *b2 = new float [m]; // столбец свободных членов матрицы условий

           memcpy(b2,b,m*sizeof(float)); 

           for (j=0; j<m; j++)

           {

                 a2[j] = new float[n];

                 memcpy(a2[j],a[j],n*sizeof(float));

           } 
 

           for (j=0; j<m; j++)

           {

                 for (i=0; i<n; i++)

                 {

                       if (i == base_column)

                       {

                             a2[j][i] = (float) (j == base_row ? 1 : 0);

                       }

                       else

                       {

                             if (j == base_row)

                                   a2[j][i] = a[j][i]/a[base_row][base_column];

                             else

                                   a2[j][i] = a[j][i] - a[base_row][i]*a[j][base_column]/

                                         a[base_row][base_column];

                       }

                 } 

                 if (j == base_row)

                       b2[j] = b[j]/a[base_row][base_column];

                 else

                       b2[j] = b[j] - b[base_row]*a[j][base_column]/

                             a[base_row][base_column];

           } 
 
 

           memcpy(b,b2,m*sizeof(float));

           delete[] b2; 

           for (j=0; j<m; j++)

           {

                 memcpy(a[j],a2[j],n*sizeof(float));

                 delete[] a2[j];

           } 

           delete[] a2;

     } 

     // проверка: входит ли номер столбца  в число базисных переменных

     bool InBase (int num)

     {

           for (int j=0; j<m; j++)

                 if (num == base[j])

                       return true; 

           return false;

     } 

     // вывод линии символов

     void Rule (char c, int amount = full_table ? 5+(n+2)*8 : 5+(cnr+1)*8)

     {

           for (int i=0; i<amount; i++)

                 printf("%c", c);

           printf("\n");

     } 

     // вывод Симплекс-таблицы

     void ShowTable ()

     {

           int i,j; 

           static int iteration = 0;

           printf("[%i]\n", iteration++); 
 

           if (full_table) 

                 // полная таблица

           {

                 Rule('=');

                 printf("Баз.|       |       |");

                 for (i=0; i<cn; i++)