Текст подпрограммы и версий ( Фортран )
mlogr.zip 		Тексты тестовых примеров ( Фортран )
tmlogr.zip
Текст подпрограммы и версий ( Си )
mlogr_c.zip 		Тексты тестовых примеров ( Си )
tmlogr_c.zip
Текст подпрограммы и версий ( Паскаль )
mlogr_p.zip 		Тексты тестовых примеров ( Паскаль )
tmlogr_p.zip

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

Назначение

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

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

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

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

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

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

Информация о задаче задается в следующем виде:

Матрица условий  A задается в трех массивах:

- в одномерном массиве  A последовательно помещаются ненулевые элементы матрицы по столбцам;
- в одномерном массиве NSA записываются номера строк соответствующих ненулевых элементов;
- в массиве NTAB указывается количество ненулевых элементов в каждом столбце матрицы.

Вектор  C содержит коэффициенты линейной формы.
Вектор ограничений  b задается в массиве  B.

Выходными параметрами подпрограммы являются:
вещественная переменная  F - оптимальное значение линейной формы;
вещественный вектор RM после окончания счета, содержащий в первых  N ячейках компоненты решения;
и целая переменная IERR, указывающая причину окончания счета.

Вводится в рассмотрение расширенный вектор ограничений  b длины  M = m + 2, у которого  b = bi  для  i = 1, ..., m,   bM - 1 = 0,   bM = - (b1 + ... + bm).

Точность вычислений характеризуется величиной невязки 

                            n
        r  =  bM  -   ∑  Sj x j ,    где    Sj = - ( ai j + ... + am j ) .
                           j =1

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

Г.Зойтендейк, Методы возможных направлений. Изд - во ИЛ, M., 1963.

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

    SUBROUTINE  MLOGR (M, N, PRP, A, NSA, NTAB, ALFA, NALFA,
                                              KV, B, C, LB, EPS, MNMX, F, IM, RM,
                                              IERR) 
   Параметры
M - число строк расширенной матрицы (тип: целый);
N - число столбцов в матрице условий (тип: целый);
PRP - целая переменная, задающая число итераций метода, через которое делается пересчет мультипликаторов (см. замечания по использованию);
A - вещественный вектор, задающий ненулевые элементы матрицы по столбцам;
NSA - массив индексов строк для соответствующих ненулевых элементов (тип: INTEGER * 2);
NTAB - вектор длины  N - таблица ненулевых элементов матрицы по столбцам (тип: INTEGER * 2);
ALFA - вещественный вектоp длины KV, содержащий отличные от + ∞, компоненты вектора верхних ограничений  α;
NALFA - массив номеров отличных от + ∞, компонент вектора верхних ограничений  α (тип: INTEGER * 2);
KV - количество отличных от + ∞ верхних ограничений на переменные (тип: целый);
B - вещественный вектор длины  M содержащий ограничения;
C - вещественный вектоp длины  N, содержащий коэффициенты линейной формы;
LB - целая переменная, задающая объем свободной оперативной памяти (см. замечания по использованию);
EPS - вещественная переменная, задающая точность вычисления оптимального плана;
MNMX - целая переменная, задающая признак оптимизации:
MNMX=0, если задача поставлена на минимум;
MNMX=1, если - на максимум,
F - вещественная переменная, содержащая оптимальное значение линейной формы;
IM - рабочий массив длины (1 + 6M + 2N + LB) (тип: INTEGER * 2);
RM - вещественный рабочий массив длины (1 + 4M + N + LB), после окончания счета в первых  N ячейках стоит решение;
IERR - целая переменная служащая для сообщения о причине окончания счета:
IERR= 0 - получено оптимальное решение;
IERR=65 - задача несовместна;
IERR=66 - линейная форма неограничена. 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

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

Вектор верхних ограничений на переменные   α не должен содержать нулевых компонент и хотя бы одна его компонента должна быть отлична от + ∞.

Процедура пересчета элементарных матриц предназначена для эффективного использования оперативной памяти. Обычно для хранения элементарных матриц используется вся свободная память (LB). Число PRP рекомендуется выбрать равным 3M/2, где  M - число ограничений задачи. Выбор момента пересчета элементарных матриц осуществляется программой. Пересчет производится при выполнении хотя бы одного из условий:
- выполнено PRP итераций метода,
- объем оперативной памяти, занимаемой элементарными матрицами превосходит LB.

При определении LB следует иметь ввиду, что программа использует (2 + 8 * M + 4,5 * N + 1,5 * Z) ячеек памяти без учета массива элементарных матриц, где  Z - количество ненулевых элементов в матрице условий.

Длина входных векторов  A и NSA должна быть не меньше  Z.

После работы подпрограммы изменяются:
вектор правых частей, вектор коэффициентов линейной формы и EPS.

Используются служебные подпрограммы: MLMPM, MLMVK1, MLMPK, MLMRN, MLMLP, MLMXI, MLML11, MLML21, MLMX1, MLMD, MLMUP2, MLMU, MLMXK2, MLMG11, MLMVX1, MLMBR.

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

    max  [(c, x)  =  x1  +  2x2  +  3x3 - x4 ] , 
      x1  +  2x2  +  3x3            =  15 , 
    2x1  +    x2  +  5x3            =  20 , 
      x1  +  2x2  +    x3  +  x4  =  10 , 
             0 ≤ x1 ≤ 2 , 
             0 ≤ x2 , 
             0 ≤ x3 ≤ 3 , 
             0 ≤ x4 .

       REAL  A(10) /1, 2., 1., 2., 1., 2., 3., 5., 1., 1./,
      *           B(5) /15., 20., 10., 0., 0./,  ALFA(2) /2., 3./,
      *           EPS /0.01/,   C(4) /1., 2., 3., - 1./,  RM /55/
       INTEGER*2  NSA(10) /1, 2, 3, 1, 2, 3, 1, 2, 3, 3/,  NTAB(4) /3*3, 1/,
      *                     NALFA(2) /1, 3/,  IM(69)
       INTEGER  M /5/,  N /4/, PRP /6/,  KV /2/,  MNMX /1/,  LB /30/
       CALL  MLOGR (M, N, PRP, A, NSA, NTAB, ALFA, NALFA, KV, B,
      *                           C, LB, EPS, MNMX, F, IM, RM, IERR)

Результаты:

       IERR = 0

       Значение линейной формы   F = 14.571

       Решение

       2.0000     2.42857     2.71428     0.42857