Текст подпрограммы и версий ( Фортран )
ml02r.zip 		Тексты тестовых примеров ( Фортран )
tml02r.zip
Текст подпрограммы и версий ( Паскаль )
ml02r_p.zip 		Тексты тестовых примеров ( Паскаль )
tml02r_p.zip

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

Назначение

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

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

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

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

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

Используется модифицированный симплекс - метод. Исходная информация задается в компактной форме. Ненулевые элементы матрицы условий задаются в виде одномерного массива A, каждый элемент которого содержит очередной (по столбцам) ненулевой элемент  ai j матрицы .

Номера строк ненулевых элементов матрицы условий задаются в целочисленном массиве NS в том же порядке, в котором перечислены сами ненулевые элементы. Т.е., если ai j ≠ 0 и A (K) = ai j, то NS (K) = 1.

Вектоp T длины  n содержит запись коэффициентов линейной формы т.е. в T (J) помещается коэффициент Cj, Вектор NT длины N содержит количества ненулевых элементов в столбцах матрицы A. Т.е., NT (K) = L означает, что в  k - м столбце матрицы содержится L ненулевых элементов.

Введен вспомогательный вектоp SUM длины  n с компонентами SUМ j = - (a1 j +...+ am j), где  ai j - элементы матрицы А. Вектоp  b дополняется двумя компонентами  bm+1 = 0,  bm + 2 = - (b1 +...+ bm).

Точность вычислений характеризуется величиной невязки  r = bm + 2 - (SUM, x).

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

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

    SUBROUTINE  ML02R (A, DA, U, M, T, N, SUM, NSUM, NT, NS, X, P,
                                            EPS, XK,NX) 
   Параметры
A - вещественный одномерный массив размерности DA, содержащий ненулевые элементы матрицы условий;
DA - число ненулевых элементов матрицы условий (тип: целый);
U - двумерный рабочий массив размерности  m + 2 на m + 2 (тип: вещественный);
M - длина расширенного вектоpа  b, т.е. M = m + 2 (тип: целый);
T - вещественный вектоp длины  n, содержащий коэффициенты линейной формы ;
N - число столбцов матрицы условий (тип: целый);
SUM - вещественный вектоp длины  n сумм элементов матрицы по столбцам с обратным знаком;
NSUM - одномерный целый рабочий массив длины [(N + 15)/16] (тип; целый);
NT - двубайтовый целый вектор длины N, содержащий количества ненулевых элементов в столбцах матрицы условий;
NS - двубайтовый целый вектор длины DA, содержащий номера строк матрицы A, в которых находятся ненулевые элементы;
X - вещественный вектоp длины M, при этом на входе X (I) = bI, I = 1,..., M; на выходе X (I) - ненулевые компоненты решения, X (M - 1) - минимальное (или максимальное) значение линейной формы, X (M) - величина невязки  r;
P - целая переменная, при обращении к подпрограмме задается равной 1, если требуется найти максимум линейной формы, и не равной 1 в противном случае; на выходе:
P= 1 - если найдено решение,
P= 2 - если задача несовместна,
P= 3 - если значение линейной формы неограничено;
EPS - заданная абсолютная погрешность вычислений (тип: вещественный);
XK - вещественный рабочий вектоp длины M.
NX - целый массив (двубайтовый) длины M; на выходе содержит номера ненулевых компонент решения. 
   Версии:  нет 
   Вызываемые подпрограммы
UTMN11 - подпрограмма занесения единицы в заданную позицию двоичной шкалы;
UTMN12 - подпрограмма занесения нуля в заданную позицию двоичной шкалы;
UTMN13 - подпрограмма проверки значений заданной позиции шкалы. 
   Замечания по использованию
 

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

На выходе из подпрограммы номера элементов X (I) масссива X (I = 1,..., M - 2) находятся в массиве NX, так что  xNX (I) = X (I). Остальные N - M компонент решения равны нулю.

Используются служебные подпрограммы: MLU01, MLU05, MLU06, MLU07, MLU11, MLU12, MLU13, MLU14, MLU15, MLU16, MLU17, MLU34.

Компактное хранение матрицы позволяет решать задачи большей размерности, но M ≤ 255.

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

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

       INTEGER  P, NSUM(1)
       INTEGER*2  NX(5), NT(4), NS(10)
       REAL  A(10), SUM(4), X(5), XK(5), T(4), U(5, 5)
       DATA  A /1, 2, 1., 2., 1., 2., 3., 5., 1., 1./
       DATA  NS /1, 2, 3, 1, 2, 3, 1, 2, 3, 3/
       DATA  T /1., 2., 3., -1./
       DATA  NT /3, 3, 3, 1/ 
       DATA  SUM /-4., -5., -9., -1./
       DATA  X /15., 20., 10., 0., -45./
       P = 1
       M = 5
       N = 4
       EPS = 0.01
       CALL  ML02R (A, 10, U, M, T, N, SUM, NSUM, NT, NS, X, P,
      *                          EPS, XK, NX)

Результаты:

       X  =  ( 2.5,  2.5,  2.5,  15.,  -0.00 )
       NX =  ( 2, 3, 1 )

   Таким образом,
         x  =  ( 2.5,  2.5,  2.5,  0.0 )
  (c, x)  =  15.0
         r  =  0.0