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

Подпрограмма:  ML04R (модуль ML04R_p)

Назначение

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

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

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

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

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

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

              | a11       a12       ... a1n       |
              | . . . . . . . . . . . . . . . . . . .  |
     A1 = | am1       am2     ... amn       |
              | c1          c2      ...   cn       |
              | am+2,1  am+2,2  ... am+2,n  |

где am + 2, j = - (a1 j +... + am j) для J = 1,..., N. Вектоp  b дополняется двумя компонентами  bm + 1 = 0,  bm + 2 = - (b1 +...... + bm).

Компоненты вектоpа верхних ограничений на переменные  α задаются в компактной форме в одномерном массиве ALFA. Каждый элемент массива ALFA содержит отличную от  + ∞ компоненту вектоpа  α, а в массиве NALFA находится номер соответствующей компоненты. Точность вычислений характеризуется величиной невязки 

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

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

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

procedure ML04R(var A :Array of Real; M :Integer;
                var U :Array of Real; N :Integer;
                var X :Array of Real; var P :Integer; EPS :Real;
                var AMS :Array of Integer; var XK :Array of Real;
                var ALFA :Array of Real; KV :Integer;
                var NALFA :Array of Integer;
                var NX :Array of Integer);


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

Ограничение: M ≤ 255.

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

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

Используются служебные подпрограммы: MLU01, MLU02, MLU04, MLU07, MLU08, MLU18, MLU26, MLU27, MLU31, MLU32, MLU33, MLU35.

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

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

Unit TML04R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, ML04R_p;

function TML04R: String;

implementation

function TML04R: String;
var
P,KV,_i :Integer;
EPS :Real;
AMS :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..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 );
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;
EPS := 0.01;
ML04R(A,5,U,4,X,P,EPS,AMS,XK,
     ALFA,KV,NALFA,NX);
Result := Result + Format('%s',[' NX(1)=']);
Result := Result + Format('%1d ',[NX[0]]);
Result := Result + Format('%s',['  NX(2)=']);
Result := Result + Format('%1d ',[NX[1]]);
Result := Result + Format('%s',['  NX(3)=']);
Result := Result + Format('%1d ',[NX[2]]);
Result := Result + Format('%s',[' P=']);
Result := Result + Format('%1d ',[P]);
Result := Result + Format('%s',['   NALFA(1)=']);
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 + #$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;
UtRes('TML04R',Result);  { вывод результатов в файл TML04R.res }
exit;
end;

end.

Результаты:

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

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