Текст подпрограммы и версий ( Фортран )
ml03r.zip 		Тексты тестовых примеров ( Фортран )
tml03r.zip
Текст подпрограммы и версий ( Паскаль )
ml03r_p.zip 		Тексты тестовых примеров ( Паскаль )
tml03r_p.zip

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

Назначение

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

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

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

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

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

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

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

Вектоp T длины  n содержит коэффициенты линейной формы . Вектор NT длины N содержит количества ненулевых элементов матрицы A.

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

Каждый элемент массива ALFA содержит отличную от  + ∞ компоненту вектоpа  α, а в массиве NALFA находятся номера соответствующих компоненит. Точность вычислений характеризуется величиной невязки  r = bm + 2 - (SUM, x).

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

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

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

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

Hа выходе из подпрограммы номер компоненты решения 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  α не должен содержать нулевых компонент и хотя бы одна его компонента должна быть отлична от  + ∞. Компоненты вектора NALFA должны быть упорядочены по возрастанию (на входе).

Используются служебные подпрограммы: MLU01, MLU07, MLU11, MLU12, MLU13, MLU17, MLU18, MLU28, MLU29, MLU30, MLU33, MLU34.

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

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

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

       REAL  A(10), SUM(4), X(5), XK(5), T(4), U(5, 5), ALFA(2)
       INTEGER*2  NX(5), NALFA(2), NT(4), NS(10)
       INTEGER  P, NSUM(1)
       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  X /15., 20., 10., 0., -45./, SUM /-4., -5., -9., -1./
       DATA  ALFA /2., 3./
       DATA  NALFA /1, 3/
       KV = 2
       P = 1
       M = 5
       N = 4
       EPS = 0.01
       CALL  ML03R (A, 10, U, M, T, N, SUM, NS, NT, NSUM, X, NX, P,
      *                       EPS, XK, ALFA, KV, NALFA)

Результаты:

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

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