Текст подпрограммы и версий
ml04r_c.zip 		Тексты тестовых примеров
tml04r_c.zip

Подпрограмма:  ml04r_c

Назначение

Решение задачи линейного программирования с двухсторонними ограничениями на переменные модифицированным симплекс - методом.

Математическое описание

Решается задача линейного пpoгpaммирования 

          min  (c,x)  ( или  max  (c,x) ) ,
          A x  =  b ,
          0 ≤ x ≤ α ,

где A - матрица размерности  m на n,  x,  c и  α - векторы длины  n, b - вектоp длины  m.

Используется модифицированный симплекс - метод. Исходная информация задается в виде расширенной матрицы 

              | a11       a12       ... a1n       |
              | . . . . . . . . . . . . . . . . . . .  |
     A1 = | am1       am2     ... amn       |
              | c1          c2      ...   cn       |
              | am+2,1  am+2,2  ... am+2,n  |

где am + 2, j = - (a1 j +... + am j) для J = 1,..., N. Вектоp  b дополняется двумя компонентами  bm + 1 = 0,  bm + 2 = - (b1 +...... + bm).

Компоненты вектоpа верхних ограничений на переменные  α задаются в компактной форме в одномерном массиве ALFA. Каждый элемент массива ALFA содержит отличную от  + ∞ компоненту вектоpа  α, а в массиве NALFA находится номер соответствующей компоненты. Точность вычислений характеризуется величиной невязки 

     r  =  bm+2  -  ∑  am+2, j  xj 
                           j

Дж.Данциг, Линейное программирование. Его применения и обобщения. Изд - во "Прогресс", M., 1966.

Использование 

    int ml04r_c (real *a, integer *m, real *u, integer *n, real *x,
             integer *p, real *eps, real *ams, real *xk, real *alfa, integer *kv, 
        shortint *nalfa, shortint *nx)

   Параметры
a - вещественный двумерный массив размерности  m + 2 на n, содержащий элементы расширенной матрицы A1;
m - число стpок матрицы A1 (тип: целый);
u - рабочий массив размерности m на m (тип: вещественный);
n - число столбцов матрицы A1 (тип: целый);
x - вещественный вектоp длины m, при этом на входе x (i) = bi,  i = 1,..., m; на выходе:
x (i) - не равные граничным значениям компоненты решения в компактной форме при i = 1,..., m - 2,
x (m - 1) - минимальное (или максимальное) значение линейной формы,
x (m) - величина невязки r;
p - целая переменная, при обращении к подпрограмме задается равной 1, если требуется найти максимум линейной формы, и не равной 1 в противном случае; на выходе:
p= 1 - если найдено решение,
p= 2 - если задача несовместна,
p= 3 - если значение линейной формы неограничено;
esp - заданная абсолютная погрешность вычислений (тип: вещественный);
ams - целый рабочий вектор длины [(n + 15)/16]
xk - вещественный рабочий вектоp длины m;
alfa - вещественный массив размерности kv, содержащий в компактной форме отличные от  + ∞ компоненты вектоpа верхних ограничений  α;
kv - размерность массива alfa, равная числу отличных от  + ∞ компонент вектоpа  α (тип: целый);
nalfa - двубайтовый целый массив размерности kv, на входе содержит номера компонент вектора  α, соответствующие элементам alfa;
nx - двубайтовый целый массив длины m; на выходе содержит номера компонент решения, не равных граничным значениям. 
   Версии:  нет 
   Вызываемые подпрограммы
utmn11_c - подпрограмма занесения единицы в шкалу;
utmn12_c - подпрограмма занесения нуля в шкалу;
utmn13_c - подпрограмма проверки значения в заданной позиции шкалы. 
   Замечания по использованию
 

Ограничение: m ≤ 255.

Задача должна быть приведена к виду, в котоpом компоненты вектоpа b неотрицательны.

На выходе из подпрограммы номер компоненты решения J (i) элемента x (i) массива x (i = 1,..., m - 2), для которой 0 < xJ (i) = x (i) < αJ (i), находится в ячейке nx (i).

Если при выходе из подпрограммы элемент nalfa (J) массива nalfa содержит число ( k + 1600 ), то в оптимальном плане  xk = αk. Остальные компоненты решения равны нулю.

Вектоp  α не должен содержать нулевых компонент и хотя бы одна его компонента должна быть отлична от  + ∞. Компоненты вектоpа ALFA должны быть упорядочены по возрастанию номеров;

Используются служебные подпрограммы: mlu01_c, mlu02_c, mlu04_c, mlu07_c, mlu08_c, mlu18_c, mlu26_c, mlu27_c, mlu31_c, mlu32_c, mlu33_c, mlu35_c.

Подпрограмма рекомендуется для использования, когда матрица условий A содержит много ненулевых элементов.

Пример использования 

int main(void)
{
    /* Initialized data */
    static float a[20] /* was [5][4] */ = { 1.f,2.f,1.f,1.f,-4.f,2.f,1.f,2.f,
                       2.f,-5.f,3.f,5.f,1.f,3.f,-9.f,0.f,0.f,1.f,-1.f,-1.f };
    static float x[5] = { 15.f,20.f,10.f,0.f,-45.f };
    static float alfa[2] = { 2.f,3.f };
    static shortint nalfa[2] = { 1,3 };

    /* Local variables */
    extern int ml04r_c(float *, int *, float *, int *, float *, int *,
                       float *, int *, float *, float *, int *, shortint *,
                       shortint *);
    static int p;
    static float u[25] /* was [5][5] */;
    static int kv;
    static float xk[5];
    static shortint nx[5];
    static int ams[1];
    static float eps;

    kv = 2;
    p = 1;
    eps = .01f;
    ml04r_c(a, &c__5, u, &c__4, x, &p, &eps, ams, xk, alfa, &kv, nalfa, nx);

    printf("\n %5i %5i %5i \n", nx[0], nx[1], nx[2]);
    printf("\n %5i \n", p);
    printf("\n %5i %5i \n", nalfa[0], nalfa[1]);
    printf("\n %12.2f %12.2f %12.2f %12.2f %12.2f \n",
           x[0], x[1], x[2], x[3], x[4]);
    return 0;
} /* main */


Результаты:

       x  =  ( 2.43,  2.71,  0.43,  14.57,  -0.00 )
       nx  =  ( 2, 3, 4 )
       nalfa  =  ( 16001, 3 )

   Таким образом,
         x  =  ( 1,  2.43,  2.71,  0.43 )
  (c, x)  =  14.57
         r  =  0.00