Подпрограмма:  ML03R (модуль ML03R_p)

Назначение

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

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

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

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

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

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

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

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

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

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

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

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

procedure ML03R(var A :Array of Real; DA :Integer;
                var U :Array of Real; M :Integer;
                var T :Array of Real; N :Integer;
                var SUM :Array of Real; var NS :Array of Integer;
                var NT :Array of Integer; var NSUM :Array of Integer;
                var X :Array of Real; var NX :Array of Integer;
                var P :Integer; EPS :Real; var XK :Array of Real;
                var ALFA :Array of Real; KV :Integer;
                var NALFA :Array of Integer);

   Параметры 

   Версии:  нет 

   Вызываемые подпрограммы 

   Замечания по использованию  

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

Unit TML03R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, ML03R_p;

function TML03R: String;

implementation

function TML03R: String;
var
P,KV,M,N,_i :Integer;
EPS :Real;
NSUM :Array [0..0] of Integer;
NX :Array [0..4] of Integer;
ХК :Array [0..4] of Real;
U :Array [0..24] of Real;
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 );
NS :Array [0..9] of Integer = ( 1,2,3,1,2,3,1,2,3,3 );
T :Array [0..3] of Real = ( 1.0,2.0,3.0,-1.0 );
NT :Array [0..3] of Integer = ( 3,3,3,1 );
SUM :Array [0..3] of Real = ( -4.0,-5.0,-9.0,-1.0 );
X :Array [0..4] of Real = ( 15.0,20.0,10.0,0.0,-45.0 );
ALFA :Array [0..1] of Real = ( 2.0,3.0 );
NALFA :Array [0..1] of Integer = ( 1,3 );
begin
Result := '';  { результат функции }
KV := 2;
P := 1;
M := 5;
N := 4;
EPS := 0.01;
ML03R(A,10,U,M,T,N,SUM,NS,NT,NSUM,X,NX,P,EPS,XK,
     ALFA,KV,NALFA);
Result := Result + Format('%s',[' P=']);
Result := Result + Format('%1d ',[P]);
Result := Result + Format('%s',[#$0D#$0A + ' X=']);
Result := Result + #$0D#$0A;
for _i:=0 to 4 do
 begin
  Result := Result + Format('%20.16f ',[X[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[#$0D#$0A + ' NX=']);
Result := Result + #$0D#$0A;
for _i:=0 to 4 do
 begin
  Result := Result + Format('%5d ',[NX[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[' NALFA=  ']);
Result := Result + #$0D#$0A;
for _i:=0 to 1 do
 begin
  Result := Result + Format('%5d ',[NALFA[_i]]);
  if ( ((_i+1) mod 2)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[#$0D#$0A + ' ALFA=']);
Result := Result + #$0D#$0A;
for _i:=0 to 1 do
 begin
  Result := Result + Format('%20.16f ',[ALFA[_i]]);
  if ( ((_i+1) mod 2)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TML03R',Result);  { вывод результатов в файл TML03R.res }
exit;
end;

end.

Результаты:

       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