Подпрограмма:  MNR5R (модуль MNR5R_p)

Назначение

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

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

   Для решения задачи:

       min  f(x) ,    x∈Q ,
        x
где     Q = { x:  A1*x = B1 ,   A ≤ x ≤ B } ,
       x, A, B - векторы из  En ,
             B1 - вектор из  Em ,
             A1 - вещественная матрица  m * n . 

Используется модификация метода условного градиета. В процессе счета каждое новое приближение определяется по формуле:

     xk+1  =  xk + αk(yk - xk) , 

где    y_k - минимум линейной функции  < f ' (x_k), x - x_k > при  x ∈ Q;
   f ' (x_k) - градиент функции  f точке  x_k;
        α_k - величина шага по направлению спуска  p_k = y_k - x_k .

B программе предусмотрены четыре критерия останова: по времени, по числу итераций, по величине сдвига в пространстве аргумента и по изменению функции.

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

procedure MNR5R(var N :Integer; var M :Integer; var X :Array of Real;
                var XE :Array of Real; var I0 :Array of Integer;
                var A :Array of Real; var B :Array of Real;
                var B1 :Array of Real; var LA :Integer;
                var A1 :Array of Real; var NS :Array of Integer;
                var T :Array of Real; FUNC :Proc_F1_MN; var F :Real;
                var FE :Real; GRAD :Proc_F2_MN; var G :Array of Real;
                var GE :Array of Real; var UP :Array of Real;
                var RM :Array of Real; var IRM :Array of Integer;
                var IRM1 :Array of Integer; var IERR :Integer);

   Параметры 

   Версии:  нет 

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

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

      procedure FUNC (var X :Array of Real; var F :Real; FE :Real);

       Параметры
       X   - вещественный вектор длины  N, задающий
               точку пространства, в которой вычисляется
               значение функции;
       F   - вещественная переменная, содержащая
               вычисленное значение функции в точке  X;
       FE - заданная точность вычисления функции в
               точке  X (тип: вещественный).  

      procedure GRAD (var X :Array of Real; var G :Array of Real;
                var GE :Array of Real; var I0 :Array of Integer);

       Параметры
       X   - вещественный вектор длины  N, задающий 
               точку пространства, в которой вычисляется градиент;
       G   - вещественный вектоp длины  N, содержащий
               вычисленный градиент функции в точке  X;
       GE - вещественный вектоp длины  N, содержащий
               абсолютные точности, с которыми требуется
               вычислить компоненты градиента;
       I0  - целый вектоp длины  N, используемый при
               вычислении градиента:  если  I0(J) = 1,
               то в  G(J) засылается значение  J-ой
               компоненты градиента, если  I0(J) = 0,
               то в  G(J) засылается 0. 

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

     min  F(x)  =  4x12 + 3x22

                  x1 + 3x2 - x3  =  5
             0.5x1 + 2x2 - x4  =  2

             10-6 ≤ x1 ≤ 5
             10-6 ≤ x2 ≤ 5
             10-6 ≤ x3 ≤ 5
             10-6 ≤ x4 ≤ 5

Unit TMNR5R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FGMNR5R_p, FMNR5R_p, MNR5R_p;

function TMNR5R: String;

implementation

function TMNR5R: String;
var
N,M,DA,IERR,LA,_i :Integer;
F :Real;
IRM1 :Array [0..7] of Integer;
IRM :Array [0..15] of Integer;
G :Array [0..3] of Real;
RM :Array [0..57] of Real;
const
IO :Array [0..3] of Integer = ( 1,1,1,1 );
X :Array [0..3] of Real = ( 5.0,0.1,1.0,1.0 );
GE :Array [0..3] of Real = ( 1.E-6,1.E-6,1.E-6,1.E-6 );
ХЕ :Array [0..3] of Real = ( 0.1E-10,0.1E-10,0.1E-10,0.1E-10 );
A :Array [0..3] of Real = ( 1.E-6,1.E-6,1.E-6,1.E-6 );
B :Array [0..3] of Real = ( 5.0,5.0,5.0,5.0 );
B1 :Array [0..3] of Real = ( 5.0,2.0,0.0,0.0 );
T :Array [0..3] of Real = ( 2.0,2.0,1.0,1.0 );
FE :Real = 0.1E-6;
UP :Array [0..3] of Real = ( 100.0,3.0,2.0,1.0E-12 );
A1 :Array [0..5] of Real = ( 1.0,0.5,3.0,2.0,-1.0,-1.0 );
NS :Array [0..5] of Integer = ( 1,2,1,2,1,2 );
begin
Result := '';  { результат функции }
LA := 6;
M := 4;
N := 4;
RM[0] := 20;
MNR5R(N,M,X,XE,IO,A,B,B1,LA,A1,NS,T,FMNR5R,F,FE,FGMNR5R,
     G,GE,UP,RM,IRM,IRM1,IERR);
Result := Result + Format('%s',[' IERR=']);
Result := Result + Format('%2d ',[IERR]);
Result := Result + Format('%s',['  RM(2)=']);
Result := Result + Format('%20.16f ',[RM[1]]);
Result := Result + Format('%s',['  RM(3)=']);
Result := Result + Format('%20.16f ',[RM[2]]);
Result := Result + Format('%s',[' F=']);
Result := Result + Format('%20.16f ',[F]);
Result := Result + Format('%s',[' МАССИВ X  ']);
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 + Format('%s',['  RM(1)=']);
Result := Result + Format('%20.16f ',[RM[0]]) + #$0D#$0A;
UtRes('TMNR5R',Result);  { вывод результатов в файл TMNR5R.res }
exit;
end;

end.

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

procedure fmnr5r(var X :Array of Real; var F :Real; FE :Real);

implementation

procedure fmnr5r(var X :Array of Real; var F :Real; FE :Real);
begin
F := 4*X[0]*X[0]+3*X[1]*X[1];
end;

end.

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

procedure fgmnr5r(var X :Array of Real; var G :Array of Real;
                var GE :Array of Real; var IO :Array of Integer);

implementation

procedure fgmnr5r(var X :Array of Real; var G :Array of Real;
                var GE :Array of Real; var IO :Array of Integer);
var
I :Integer;
label
_3,_1,_2;
begin
for I:=1 to 4 do
 begin
_3:
  G[I-1] := 0.0;
 end;
if ( IO[0] = 0 ) 
 then goto _1;
G[0] := 8*X[0];
_1:
if ( IO[1] = 0 ) 
 then goto _2;
G[1] := 6*X[1];
_2:
end;

end.

Результаты:

      IERR = 2 ;  KOЛИЧECTBO ИTEPAЦИЙ  = 7 ;
      NF (KOЛИЧECTBO BЫЧИCЛEHИЙ ФУHKЦИИ)  = 8 ;
      NG (KOЛИЧECTBO BЫЧИCЛEHИЙ ГPAДИEHTA)  = 22 ;
      F  =  7.692 ;
      X  =  (0.3846,  1.538,  10-6,  1.269) .