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

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

Назначение

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

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

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

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

где 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 

   где  ai j   ( i = 1, ... , m ;  j = 1, ... , n ) - элементы  матрицы  A ,
   am+2, j  =  - ( a1 j + a2 j + ... + am j )    для   j = 1, ... , n .

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

Точность вычислений характеризуется величиной невязки  

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

С.Гасс, Линейное программирование, Физматгиз, 1961.

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

    int ml01r_c (real *a, integer *m, real *u, integer *n, real *x,
             integer *nb, integer *p, real *eps, real *xk)

   Параметры
a - вещественный двумерный массив размерности  m + 2 на  n, содержащий элементы расширенной матрицы A1;
m - число стpок матрицы A1 (тип: целый);
u - рабочий массив размерности m на m (тип: вещественный);
n - число столбцов матрицы A1 (тип: целый);
x - вещественный вектоp длины m, при этом на входе x (i) = bi,  i = 1, ..., m,  на выходе для  i = 1, ... , m - 2 ;
x (i) - ненулевые компоненты решения, x (m - 1) - минимальное (или максимальное) значение линейной формы, x (m) - величина невязки  r;
nb - вектоp длины m, содержащий номеpа ненулевых компонент решения т.е.  xnb (i) = x (i)  для  i = 1, ... , m - 2 (тип: целый);
p - целая переменная, при обращении к подпрограмме задается равной 1, если требуется найти максимум линейной формы, и не равной 1, в противном случае; на выходе:
p = 1 - если найдено решение,
p = 2 - если задача несовместна,
p = 3 - если значение линейной формы неограничено;
eps - заданная абсолютная погрешность вычислений (тип: вещественный);
xk - вещественный рабочий вектоp длины m. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

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

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

Подпрограмма ml01r_c использует служебные подпрограммы mlu01_c, mlu02_c, mlu03_c, mlu04_c, mlu05_c, mlu06_c, mlu07_c, mlu08_c, mlu09_c, mlu10_c.

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

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 int nb[5] = { 0,0,0,0,0 };
    static int p = 1;
    static int m = 5;
    static int n = 4;
    static float eps = .01f;

    /* Local variables */
    extern int ml01r_c(float *, int *, float *, int *, float *, int *,
                       int *, float *, float *);
    static float u[25] /* was [5][5] */, xk[5];

    ml01r_c(a, &m, u, &n, x, nb, &p, &eps, xk);

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


Результаты:

       x  =  ( 2.5,  2.5,  2.5,  15.,  -0.00 )
       nb  =  ( 2,  3,  1 )
       p   =  1
 то есть решение    x  =  ( 2.5,  2.5,  2.5,  0. )
       (c, x)  =  15.0
       невязка  r  =  0.00