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

Подпрограмма:  ML08R (модуль ML08R_p)

Назначение

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

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

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

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

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

Hа каждой итерации симплекс - метода базисная матрица B представляется в виде произведения матриц отражения и правой треугольной матрицы.

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

Вектоp T длины  n содержит коэффициенты линейной формы, а таблица ненулевых элементов матрицы A по столбцам задается в целом массиве NT, т.е. NT(J) содержит число ненулевых элементов в J - ом столбце матрицы A.

Введен вспомогательный вектоp SUM длины  n с компонентами SUМ j = - (a1 j +... + am j), где  ai j - элементы матрицы А. Вектоp  b дополняется компонентой  bm + 1 = 0.

Компоненты вектоpа  α верхних ограничений на переменные задаются в одномерном массиве ALFA. Номера компонент вектоpа α, отличных от + ∞, задаются вектоpом NALFA.

Точность вычислений характеризуется величиной невязки r = ( - b1 - ... - bm) - (SUM, x).

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

В.В.Воеводин, Вычислительные основы линейной алгебры. Изд - во "Наука", M., 1977.

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

procedure ML08R(var A :Array of Real; var NS :Array of Integer;
                DA :Integer; var B :Array of Real;
                M1 :Integer; var T :Array of Real;
                var NT :Array of Integer; N :Integer;
                var SUM :Array of Real; var X :Array of Real;
                var P :Integer; EPS :Real; var XK :Array of Real;
                var Z :Array of Real; var ALFA :Array of Real;
                var KV :Integer; var NALFA :Array of Integer;
                var NX :Array of Integer);


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

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

На выходе из подпрограммы в массиве NX (I = 1, 2,..., M - 1) стоит номеp J (I) компоненты решения, для которой  0 < xJ (I) = X (I) < αJ (I).

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

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

Используются служебные подпрограммы: ML0801, ML0802, ML0803, ML0804, ML0805, ML0806, ML0807, ML0808, ML0809, ML0810, ML0811, ML0812, ML0813, ML0814, ML0815, ML0816, ML0817, ML0818, ML0819, ML0820, ML0821, ML0822, MLU33, MLU34.

Программа рекомендуется для решения задач, требующих высокую точность вычислений.
Значение P = 4 на выходе из подпрограммы чаще всего означает, что следует увеличить значение EPS, т.е. снизить требуемую точность.

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

Unit TML08R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, ML08R_p;

function TML08R: String;

implementation

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

end.

Результаты:

              X  =  (2.43,  2.71,  0.43,  14.57)
           NX  =  (2, 3, 4)
    NALFA  =  (163852, 3)

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