Текст подпрограммы и версий ( Фортран )
ml05r.zip 		Тексты тестовых примеров ( Фортран )
tml05r.zip
Текст подпрограммы и версий ( Си )
ml05r_c.zip 		Тексты тестовых примеров ( Си )
tml05r_c.zip
Текст подпрограммы и версий ( Паскаль )
ml05r_p.zip 		Тексты тестовых примеров ( Паскаль )
tml05r_p.zip

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

Назначение

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

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

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

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

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

Используется модифицированный симплекс - метод. Произвольный столбец A j матрицы A формируется подпрограммой пользователя, причем каждый столбец дополняется двумя компонентами  am + 1, j = cj ,  am + 2, j = - (a1 j + ... + am j).

Вектоp  b дополняется двумя компонентами  bm + 1 = 0,  bm + 2 = - (b1 + ... + bm). Точность вычислений характеризуется величиной невязки 

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

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

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

    SUBROUTINE  ML05R (ST, U, M, X, XK, N, NX, P, EPS, ALFA,
                                             NALFA, KV, F, NB) 
   Параметры
ST - вещественный рабочий массив размерности  m + 2;
U - вещественный двумерный рабочий массив размерности  m + 2 на  m + 2;
M - длина расширенного вектоpа  b, равная  m + 2 (тип: целый);
X - вещественный вектоp длины M, при этом на входе: X (I) = bI,  I = 1,..., M; на выходе:
X (I) - не равные граничным значениям компоненты решения в компактной форме при I = 1,..., M - 2 (см. замечания по использованию);
X (M - 1) - минимальное значение линейной формы;
X (M) - величина невязки r;
XK - вещественный рабочий массив размерности M;
N - число столбцов матрицы A (тип: целый);
NX - целый двухбайтовый вектоp длины  M, содержащий на выходе из подпрограммы номера компонент решения (см. замечания по использованию);
P - целая переменная, указывающая причину окончания счета:
P= 1 - если найдено решение,
P= 2 - если задача несовместна,
P= 3 - если линейная форма неограничена;
EPS - заданная абсолютная погрешность вычислений (тип: вещественный);
ALFA - вещественный массив размерности KV, содержащий отличные от  + ∞ компоненты вектоpа верхних ограничений  α (см. замечания по использованию);
NALFA - целый двухбайтовый вектоp длины  KV, на входе содержит номера компонент вектоpа  α, соответствующие элементам ALFA;
KV - размерность массива ALFA (тип: целый);
F - имя подпрограммы пользователя, формирующей pасширенный столбец матрицы условий A (см. замечания по использованию);
NB - вектоp длины M, первые M - 2 компоненты которого содержат на выходе из подпрограммы возрастающую последовательность номеpов компонент решения, не равных граничным значениям (тип: целый). 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

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

На выходе из подпрограммы компоненты вектоpа NB равны номеpам компонент решения не равных граничным значениям, так что  0 < xNB (I) = X (I) < αNB (I).

Hомеpа компонент, принимающих значения верхних ограничений, определены в массиве NALFA. Если на выходе элемент NALFA (J) = (K + 1600), то  xK = αK. Остальные компоненты решения равны нулю.

Первый оператор подпрограммы F, формирующей расширенный столбец матрицы A, должен иметь вид: 

      SUBROUTINE  F (K,ST,M)

Параметры:

K - номеp формируемого столбца матрицы A (тип: целый);

ST - вещественный вектоp длины M, содержащий на выходе компоненты расширенного К - го столбца матрицы A;

M - длина расширенного вектора - столбца (тип: целый).

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

Используются служебные подпрограммы MLU01, MLU07, MLU18, MLU19, MLU23, MLU24, MLU25, MLU32, MLU36, MLU37, MLU38, MLU39, MLU40, MLU41, MLU42.

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

       INTEGER*2  NALFA(2), NX(5)
       REAL  U(5, 5), X(5), XK(5), ALFA(2), EPS, ST(5)
       INTEGER  NB(5), P, KV
       EXTERNAL  F
       DATA  X /15., 20., 10., 0., -45./
       DATA  ALFA /2., 3./
       DATA  KV /2/, M /5/, N /4/, EPS /0.01/
       DATA  NALFA /1, 3/
       CALL  ML05R (ST, U, M, X, XK, N, NX, P, EPS, ALFA, NALFA, KV,
      *                          F, NB)

       SUBROUTINE  F(K, ST, M)
       REAL ST(M), A(5, 4)
       DATA  A /1., 2., 1., -1., -4., 2., 1., 2., -2., -5., 3., 5., 1., -3., 
      *                 -9., 0., 0., 1., 1., -1./
       DO 1  I = 1, M
   1 ST(I) = A(I, K)
       RETURN
       END

Результаты:

       P  =  1
       X  =  (2.43,  2.71,  0.43,  -14.57,  0.00)
       NX  =  (2, 3, 4, 8, 9)
       NALFA  =  (16001, 3)

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