Текст подпрограммы и версий ( Фортран )
ml04r.zip 		Тексты тестовых примеров ( Фортран )
tml04r.zip
Текст подпрограммы и версий ( Си )
ml04r_c.zip 		Тексты тестовых примеров ( Си )
tml04r_c.zip
Текст подпрограммы и версий ( Паскаль )
ml04r_p.zip 		Тексты тестовых примеров ( Паскаль )
tml04r_p.zip

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

Назначение

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

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

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

          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.

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

    SUBROUTINE  ML04R (A, M, U, N, X, P, EPS, AMS, XK, ALFA, KV,
                                           NALFA, 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 - подпрограмма занесения единицы в шкалу;
UTMN12 - подпрограмма занесения нуля в шкалу;
UTMN13 - подпрограмма проверки значения в заданной позиции шкалы. 
   Замечания по использованию
 

Ограничение: 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, MLU02, MLU04, MLU07, MLU08, MLU18, MLU26, MLU27, MLU31, MLU32, MLU33, MLU35.

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

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

       REAL  A(5, 4), U(5, 5), X(5), XK(5)
       INTEGER*2  NX(5), NALFA(2)
       REAL ALFA(2)
       INTEGER  P, AMS(1)
       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./
       DATA  ALFA /2., 3./, KV /2/, P /1/, M /5/, N /4/, EPS /0.01/
       DATA  NALFA /1, 3/
       CALL  ML04R (A, M, U, N, X, P, EPS, AMS, XK, ALFA, KV,
      *                         NALFA, NX)

Результаты:

       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