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

Подпрограмма:  ML05R (модуль ML05R_p)

Назначение

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

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

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

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

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

Используется модифицированный симплекс - метод. Произвольный столбец A j матрицы A формируется подпрограммой пользователя, причем каждый столбец дополняется двумя компонентами  am + 1, j = cj ,  am + 2, j = - (a1 j + ... + am j).

Вектоp  b дополняется двумя компонентами  bm + 1 = 0,  bm + 2 = - (b1 + ... + bm). Точность вычислений характеризуется величиной невязки 

   r  =  bm+2  -  ∑  am+2, j x j .
                        j

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

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

procedure ML05R(var ST :Array of Real; var U :Array of Real;
                M :Integer; var X :Array of Real;
                var XK :Array of Real; N :Integer;
                var NX :Array of Integer; var P :Integer;
                EPS :Real; var ALFA :Array of Real;
                var NALFA :Array of Integer; var KV :Integer;
                F :Proc_F3AI; var NB :Array of Integer);


   Параметры
ST - вещественный рабочий массив размерности  m + 2;
U - вещественный двумерный рабочий массив размерности  m + 2 на  m + 2;
M - длина расширенного вектоpа  b, равная  m + 2 (тип: целый);
X - вещественный вектоp длины M, при этом на входе: X (I) = bI,  I = 1,..., M; на выходе:
X (I) - не равные граничным значениям компоненты решения в компактной форме при I = 1,..., M - 2 (см. замечания по использованию);
X (M - 1) - минимальное значение линейной формы;
X (M) - величина невязки r;
XK - вещественный рабочий массив размерности M;
N - число столбцов матрицы A (тип: целый);
NX - целый двухбайтовый вектоp длины  M, содержащий на выходе из подпрограммы номера компонент решения (см. замечания по использованию);
P - целая переменная, указывающая причину окончания счета:
P= 1 - если найдено решение,
P= 2 - если задача несовместна,
P= 3 - если линейная форма неограничена;
EPS - заданная абсолютная погрешность вычислений (тип: вещественный);
ALFA - вещественный массив размерности KV, содержащий отличные от  + ∞ компоненты вектоpа верхних ограничений  α (см. замечания по использованию);
NALFA - целый двухбайтовый вектоp длины  KV, на входе содержит номера компонент вектоpа  α, соответствующие элементам ALFA;
KV - размерность массива ALFA (тип: целый);
F - имя подпрограммы пользователя, формирующей pасширенный столбец матрицы условий A (см. замечания по использованию);
NB - вектоp длины M, первые M - 2 компоненты которого содержат на выходе из подпрограммы возрастающую последовательность номеpов компонент решения, не равных граничным значениям (тип: целый). 
   Версии:  нет 
   Вызываемые подпрограммы:  нет 
   Замечания по использованию
 

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

На выходе из подпрограммы компоненты вектоpа NB равны номеpам компонент решения не равных граничным значениям, так что  0 < xNB (I) = X (I) < αNB (I).

Hомеpа компонент, принимающих значения верхних ограничений, определены в массиве NALFA. Если на выходе элемент NALFA (J) = (K + 1600), то  xK = αK. Остальные компоненты решения равны нулю.

Первый оператор подпрограммы F, формирующей расширенный столбец матрицы A, должен иметь вид: 

      
      procedure F (K :Integer; var ST :Array of Real; M :Integer);

Параметры:

K - номеp формируемого столбца матрицы A (тип: целый);

ST - вещественный вектоp длины M, содержащий на выходе компоненты расширенного К - го столбца матрицы A;

M - длина расширенного вектора - столбца (тип: целый).

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

Используются служебные подпрограммы MLU01, MLU07, MLU18, MLU19, MLU23, MLU24, MLU25, MLU32, MLU36, MLU37, MLU38, MLU39, MLU40, MLU41, MLU42.

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

Unit TML05R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FML05R_p, ML05R_p;

function TML05R: String;

implementation

function TML05R: String;
var
P,N,KV,_i :Integer;
EPS :Real;
NB :Array [0..4] of Integer;
NX :Array [0..4] of Integer;
ХК :Array [0..4] of Real;
U :Array [0..24] of Real;
ST :Array [0..4] of Real;
const
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 := '';  { результат функции }
N := 4;
KV := 2;
P := 1;
EPS := 0.01;
ML05R(ST,U,5,X,XK,N,NX,P,EPS,
     ALFA,NALFA,KV,FML05R,NB);
Result := Result + Format('%s',[' NALFA=  ']);
Result := Result + #$0D#$0A;
for _i:=0 to 1 do
 begin
  Result := Result + Format('%6d ',[NALFA[_i]]);
  if ( ((_i+1) mod 2)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
Result := Result + Format('%s',[' P=']);
Result := Result + Format('%3d ',[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('%6d ',[NX[_i]]);
  if ( ((_i+1) mod 4)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TML05R',Result);  { вывод результатов в файл TML05R.res }
exit;
end;

end.

Unit FML05R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc;

procedure FML05R(J :Integer; var ST :Array of Real; M :Integer);

implementation

procedure FML05R(J :Integer; var ST :Array of Real; M :Integer);
var
I :Integer;
const
A :Array [0..19] of Real = ( 1.0,2.0,1.0,-1.0,-4.0,2.0,1.0,2.0,-2.0,-5.0,3.0,
5.0,1.0,-3.0,-9.0,0.0,0.0,1.0,+1.0,-1.0 );
label
_1;
begin
for I:=1 to M do
 begin
_1:
  ST[I-1] := A[(I-1)+(J-1)*5];
 end;
end;

end.

Результаты:

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

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