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

Подпрограмма:  MNT1R (модуль MNT1R_p)

Назначение

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

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

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

     min  F(x) ,   x ∈ En ,

где  F (x)  =  <A x, x> - 2 <b, x>,  A - матрица порядка N * N,  b - вектоp из  En, используется метод  M - покоординатного случайного поиска. В процессе счета каждое новое приближение находится по фоpмуле 

     xk+1  =  xk + αk Sk ,

где  Sk - случайный вектоp, у которого  M координат равны единице, а остальные - нулю, причем номеpа координат, равных единице, pавномеpно распределены на множестве {1, ..., N},  αk - величина шага по направлению спуска  Sk до точки минимума вдоль  Sk .

Kаpманов В.Г. Математическое программирование. Mосква, "Hаука", 1975.

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

procedure MNT1R(N :Integer; M :Integer; var A :Array of Real;
                var B :Array of Real; var X :Array of Real;
                var R :Array of Real; LIMIT :Integer;
                var S :Array of Integer; XE :Real;
                var RM :Array of Real; var IERR :Integer);


   Параметры
N - размерность пространства переменных (тип: целый);
M - число активных координат вектоpа спуска (тип: целый);
A - двумеpный вещественный массив размерности N * N, содержащий заданную матpицу;
B - вещественный вектоp длины  N, задающий линейную составляющую функции  F (x);
X - вещественный вектоp длины  N, содержащий на выходе из подпрограммы компоненты оптимального решения;
R - вещественный рабочий вектоp длины  N;
LIMIT - заданное максимальное число итераций метода (тип: целый);
S - вещественный рабочий вектоp длины  N;
XE - заданная точность решения по функционалу (тип: вещественный);
RM - вещественный рабочий вектоp длины  N;
IERR - целая переменная, указывающая пpичину окончания процесса вычислений:
IERR=0 - если найден минимум с заданной точностью;
IERR=1 - если выполнено LIMIT итераций. 
   Версии:  нет 
   Вызываемые подпрограммы
GSU2R - генерация массива псевдослучайных чисел, равномерно распределенных в интервале (0, 1) . 
   Замечания по использованию
  Процесс считается законченным, если на очередном шаге выполнено соотношение 
        || A xn - b ||∞ < XE

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

       min  F(x) ,     где
    F(x)  =  <A x, x> - 2 <b, x> ,   N = 10

    A( i, i + 1)  =  2. ,   i = 1, 2, ..., N-1
    A( i, i - 1)  =  2. ,    i = 2, 3, ..., N
    A( i, i )  =  5. ,         i = 1, 2, ..., N-1
    A(N, N)  =  1. ,   A( i, j )  =  0.   в остальных случаях.

    b(1)  =  7. ,
    b( i )  =  9. ,   i = 2, 3, ..., N-1
    b(N)  =  3.

   Точка абсолютного минимума    X*  =  ( 1., ..., 1. )


Unit TMNT1R_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FMNT1R_p, MNT1R_p;

function TMNT1R: String;

implementation

function TMNT1R: String;
var
N,M,LIMIT,_i,IERR :Integer;
ХЕ :Real;
X :Array [0..9] of Real;
B :Array [0..9] of Real;
A :Array [0..99] of Real;
R :Array [0..9] of Real;
RM :Array [0..9] of Real;
S :Array [0..9] of Integer;
begin
Result := '';  { результат функции }
LIMIT := 600;
M := 3;
N := 10;
ХЕ := 1.E-3;
FMNT1R(A,B,N);
MNT1R(N,M,A,B,X,R,LIMIT,S,XE,RM,IERR);
Result := Result + Format('%s',['  IERR=']);
Result := Result + Format('%5d ',[IERR]) + #$0D#$0A;
Result := Result + #$0D#$0A;
for _i:=0 to 9 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('TMNT1R',Result);  { вывод результатов в файл TMNT1R.res }
exit;
end;

end.

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

procedure fmnt1r(var A :Array of Real; var B :Array of Real;
                N :Integer);

implementation

procedure fmnt1r(var A :Array of Real; var B :Array of Real;
                N :Integer);
var
N1,N2,I,J :Integer;
label
_2,_1,_3,_4;
begin
N1 := N-1;
N2 := N-2;
for I:=1 to N1 do
 begin
  for J:=1 to N do
   begin
_2:
    A[(I-1)+(J-1)*N] := 0.0;
   end;
  A[(I-1)+(I-1)*N] := 5.0;
  A[(I-1)+(I+0)*N] := 2.0;
_1:
 end;
A[(N-1)+(N-1)*N] := 1.0;
for I:=2 to N do
 begin
  B[I-1] := 9.0;
_3:
  A[(I-1)+(I-2)*N] := 2.0;
 end;
for I:=1 to N2 do
 begin
_4:
  A[(N-1)+(I-1)*N] := 0.0;
 end;
B[0] := 7.0;
B[N-1] := 3.0;
end;

end.

Результаты:

      IERR  =  0
  
      X  =  (0.999,  1.002,  0.996,  1.009,  0.982,  1.036,  0.927,  1.147, 
                0.706,  1.589)