Текст подпрограммы и версий ( Фортран )
ml01r.zip 		Тексты тестовых примеров ( Фортран )
tml01r.zip
Текст подпрограммы и версий ( Си )
ml01r_c.zip 		Тексты тестовых примеров ( Си )
tml01r_c.zip
Текст подпрограммы и версий ( Паскаль )
ml01r_p.zip 		Тексты тестовых примеров ( Паскаль )
tml01r_p.zip

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

Назначение

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

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

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

           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.

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

    SUBROUTINE  ML01R (A, M1, U, N, X1, NB, P, EPS, 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 использует служебные подпрограммы MLU01, MLU02, MLU03, MLU04, MLU05, MLU06, MLU07, MLU08, MLU09, MLU10.

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

       REAL  A(5, 4), U(5, 5), X(5), XK(5)
       INTEGER  P, NB(5)
       DATA  A /1., 2., 1., 1., -4., 2., 1., 2., 2., -5., 3., 5., 1., 3., -9., 
      *            0., 0., 1., -1., -1./
       DATA  X /15., 20., 10., 0., -45./
       P = 1
       M = 5
       N = 4
       EPS = 0.01
       CALL  ML01R (A, M, U, N, X, NB, P, EPS, XK)

Результаты:

       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