Текст подпрограммы и версий
mlogr_p.zip 		Тексты тестовых примеров
tmlogr_p.zip

Подпрограмма:  MLOGR (модуль MLOGR_p)

Назначение

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

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

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

      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.

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

procedure MLOGR(M :Integer; N :Integer; PRP :Integer;
                var A :Array of Real; var NSA :Array of Integer;
                var NTAB :Array of Integer; var ALFA :Array of Real;
                var NALFA :Array of Integer; var KV :Integer;
                var B :Array of Real; var C :Array of Real;
                LB :Integer; var EPS :Real; MNMX :Integer;
                var F :Real; var IM :Array of Integer;
                var RM :Array of Real; var IERR :Integer);


   Параметры
M - число строк расширенной матрицы (тип: целый);
N - число столбцов в матрице условий (тип: целый);
PRP - целая переменная, задающая число итераций метода, через которое делается пересчет мультипликаторов (см. замечания по использованию);
A - вещественный вектор, задающий ненулевые элементы матрицы по столбцам;
NSA - массив индексов строк для соответствующих ненулевых элементов;
NTAB - вектор длины  N - таблица ненулевых элементов матрицы по столбцам;
ALFA - вещественный вектоp длины KV, содержащий отличные от + ∞, компоненты вектора верхних ограничений  α;
NALFA - массив номеров отличных от + ∞, компонент вектора верхних ограничений  α;
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, MLMLZ, MLMXI, MLML11, MLML21, MLMX1, MLMD, MLMUZ2, 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 .


Unit TMLOGR_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, MLOGR_p;

function TMLOGR: String;

implementation

function TMLOGR: String;
var
I,IERR :Integer;
F :Real;
RM :Array [0..54] of Real;
IM :Array [0..68] of Integer;
const
A :Array [0..9] of Real = ( 1.0,2.0,1.0,2.0,1.0,2.0,3.0,5.0,1.0,1.0 );
ALFA :Array [0..1] of Real = ( 2.0,3.0 );
B :Array [0..4] of Real = ( 15.0,20.0,10.0,0.0,0.0 );
C :Array [0..3] of Real = ( 1.0,2.0,3.0,-1.0 );
NALFA :Array [0..1] of Integer = ( 1,3 );
NSA :Array [0..9] of Integer = ( 1,2,3,1,2,3,1,2,3,3 );
NТАВ :Array [0..3] of Integer = ( 3,3,3,1 );
M :Integer = 5;
N :Integer = 4;
PRP :Integer = 6;
KV :Integer = 2;
MNМХ :Integer = 1;
LB :Integer = 30;
EPS :Real = 0.01;
begin
Result := '';  { результат функции }
MLOGR(M,N,PRP,A,NSA,NTAB,ALFA,NALFA,KV,B,C,LB,EPS,MNMX,
     F,IM,RM,IERR);
Result := Result + #$0D#$0A;
for I:=1 to N do
 begin
  Result := Result + Format('%20.16f ',[RM[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMLOGR',Result);  { вывод результатов в файл TMLOGR.res }
exit;
end;

end.

Результаты:

       IERR = 0

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

       Решение

       2.0000     2.42857     2.71428     0.42857