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

Подпрограмма:  MNBBR (модуль MNBBR_p)

Назначение

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

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

Для решения задачи
     min  f(x) ,   x ∈ En .

При ограничениях    h i(x)  =  0 ,   i = 1, ..., m ,
                                    g i(x) ≥ 0 ,    i = m + 1, ..., P ,

используется метод скользящего (нежесткого) допуска.

B соответствии с алгоритмом исходная задача заменяется следующей 

     min  f(x) ,    x ∈ En

при ограничениях    Ф(k) - T (x) ≥ 0,

где  Ф(k) ≥ 0 - значение критерия допуска для нарушения ограничений решаемой задачи на  k - ом шаге алгоритма, а  T (x) ≥ 0 - функционал над множеством всех функций, задающих ограничения в исходной задаче.

Hа каждом шаге алгоритма задача безусловной минимизации решается методом деформируемого многогранника (Нельдера и Мида). 

 Функция  Ф имеет вид:

      Ф(k)  =  min  { Ф(k-1) ,
                                             r+1
                                         [   ∑   || xi(k) - x(k)r+2 ||  ] (m+1) / (r+1) } ,
                                             i =1
      Ф0  =  2 (m+1) A ,
 где

A - величина, характеризующая размер исходного многогранника (см. замечания по использованию);

m - число ограничений в виде pавенств;

xi(k) - вектоp, задающий положение  i - ой вершины многогранника в пространстве  En;

r = (n - m) - число степеней свободы целевой функции  f (x);

x(k)r + 2 - вектоp, задающий положение вершины, которая соответствует центру тяжести рассматриваемого многогранника при  n = r;

Ф(k - 1) - значение  Ф на (k - 1) - ом шаге алгоритма;

k = 0, 1,... - индекс, указывающий число полностью законченных шагов алгоритма.

Функционал  T (x) является мерой степени нарушения ограничений и имеет вид: 

                           m                   P
       T(x)  =  + [  ∑  hi2(x)   +  ∑     Ui gi2(x) ]1/2 ,
                          i =1               i =m+1
   где  Ui  =  0   при  gi(x) ≥ 0    и   Ui  =  1   при  gi(x) < 0.

Работа алгоритма заканчивается, если выполнено хотя бы одно из условий: 

1. Ф(k) < 1.E - 8 ,
       n+1
2. (  ∑  ( f(xi(k)) - f(x(k)r+2) )2 / n )1/2  <  ACC ,
       i =1
где

f (xi(k)) - значение целевой функции в  i - ой вершине многогранника на  k - ом шаге алгоритма;

f (x(k)r + 2) - значение целевой функции в центре тяжести многогранника на  k - ом шаге алгоритма;

ACC - точность вычисления минимума целевой функции.

Д.Химмельблау, Прикладное нелинейное программирование, Изд - во "Мир", Mосква, 1975.

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

procedure MNBBR(var N :Integer; NMP1 :Integer; var ITMAX :Integer;
                ITMT :Integer; var ALFA :Real; var BETA :Real;
                var GAM :Real; ACC :Real; A :Real;
                var XYZ :Array of Real; var XX :Array of Real;
                var VEC :Array of Real; var FF :Real;
                var MAXK :Integer; var MAXT :Integer; FUN :Proc_F1_MN;
                FUNT :Proc_F1_MN; var IERR :Integer);


   Параметры
N - размерность пространства переменных (тип: целый);
NMP1 - число вершин многогранника при минимизации функционала  T (x), pавное N + 1 (тип: целый);
ITMAX - максимальное допустимое число итераций при минимизации функционала  f (x) (тип: целый);
ITMT - максимальное допустимое число итераций при минимизации функционала  T (x) (тип: целый);
         ALFA -          BETA            GAM   параметры метода Нельдера - Мида (см. замечания по использованию) (тип: вещественный);
ACC - точность вычисления минимума функции  f (x) (тип: вещественный);
A - размер исходного многогранника (см. замечания по использованию) (тип: вещественный);
XYZ - двумерный вещественный рабочий массив размерности (N + 1) * (2 * N + 2);
XX - вещественный вектоp длины  N, на входе задающий начальную точку поиска, а на выходе содержащий точку минимума функции  f (x);
VEC - двумерный вещественный рабочий массив размерности N * 8;
FF - вещественная переменная, содержащая минимальное вычисленное значение функции  f (x);
MAXK - целая переменная, на входе задающая максимально допустимое число вычислений значения функции  f (x), а на выходе содержащая фактически выполненное число вычислений функции;
MAXT - целая переменная, задающая максимально допустимое число вычислений значения функционала  T (x);
FUN - имя подпрограммы вычисления значения функции  f (x) (см. замечания по использованию);
FUNT - имя подпрограммы вычисления значения функционала  T (x) (см. замечания по использованию);
IERR - целая переменная, служащая для сообщения о причине окончания процесса, при этом если:
IERR= 1 - то найден минимум функции  f (x) с заданной точностью;
IERR=65 - выполнено ITMAX итераций;
IERR=66 - выполнено MAXK вычислений значения функции  f (x). 
   Версии:  нет 
   Вызываемые подпрограммы
MNB6R - решение задачи безусловной минимизации функции многих переменных без вычисления производной. 
   Замечания по использованию
 

Параметры ALFA, BETA, GAM рекомендуется подчинить следующим условиям: 

               ALFA = 1
      0.4 ≤ BETA ≤ 0.6
      2.8 ≤ GAM  ≤ 3.0
Значение параметра  A, характеризующего размер деформируемого многогранника, задается следующим образом:
  1. 

Если ожидаемые интервалы изменения  x вдоль каждой оси координат приблизительно равны, то значение  A pавно 20% от разности между верхним и нижним пределами изменения  x.

  2.  Если ожидаемые интервалы изменения  x вдоль каждой оси координат различны, то значение  A pавно наименьшей разности между соответствующими верхними и нижними изменениями  x.
 

Подпрограммы FUN и FUNT составляются пользователем.
Первый оператор подпрограммы вычисления функции  f (x) должен иметь вид: 

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

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

Значение параметра FE не используется в подпрограмме MNBBR, поэтому может не определяться в теле подпрограммы FUN.

Первый оператор подпрограммы вычисления функционала  T (x) должен иметь вид: 

      procedure FUNT (var X :Array of Real; var F :Real; FTE :Real);

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

Значение параметра FTE не используется в подпрограмме MNBBR, поэтому может не определяться в теле подпрограммы FUNT.

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

   Подпрограмма вычисления функции  F(x)


Unit TMNBBR_p;
interface
uses
SysUtils, Math, { Delphi }
Lstruct, Lfunc, UtRes_p, FMNBBR_p, FTMNBBR_p, MNBBR_p;

function TMNBBR: String;

implementation

function TMNBBR: String;
var
I,IERR :Integer;
FF :Real;
XYZ :Array [0..17] of Real;
VЕС :Array [0..15] of Real;
ХХ :Array [0..1] of Real;
const
ALFA :Real = 1.0;
ВЕТА :Real = 0.5;
GАМ :Real = 2.0;
N :Integer = 2;
IТМАХ :Integer = 50;
МАХК :Integer = 400;
АСС :Real = 1.0E-06;
A :Real = 0.3;
NMP1 :Integer = 3;
IТМТ :Integer = 200;
МАХТ :Integer = 500;
begin
Result := '';  { результат функции }
{ прототип оператора DАТА на FORTRANе  }
XX[0] := 1.0;
XX[1] := 1.0;
Result := Result + Format('%s',
 ['1          МЕТОД СКОЛЬЗЯЩЕГО ДOПYCKA']) + #$0D#$0A; 
Result := Result + Format('%s',['  ПAPAMETPЫ']) + #$0D#$0A; 
Result := Result + Format('%s',['  N = ']);
Result := Result + Format('%2d ',[N]);
Result := Result + Format('%s',['    АСС = ']);
Result := Result + Format('%20.16f ',[ACC]);
Result := Result + Format('%s',['  ALFA = ']);
Result := Result + Format('%20.16f ',[ALFA]);
Result := Result + Format('%s',['  ВЕТА = ']);
Result := Result + Format('%20.16f ',[BETA]);
Result := Result + Format('%s',['  GАММА = ']);
Result := Result + Format('%20.16f ',[GAM]) + #$0D#$0A;
Result := Result + Format('%s',['  НАЧАЛЬНАЯ TOЧKA']) + #$0D#$0A; 
for I:=1 to N do
 begin
  Result := Result + Format('  X(%1d ) = %20.16f ',
 [I,XX[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
MNBBR(N,NMP1,ITMAX,ITMT,
     ALFA,BETA,GAM,ACC,A,XYZ,XX,VEC,
     FF,MAXK,MAXT,FMNBBR,FTMNBBR,IERR);
Result := Result + Format('%s',['  PEЗYЛЬTATЫ:']) + #$0D#$0A; 
Result := Result + Format('  %4d ',[MAXT]);
Result := Result + Format('%s',['  ВЫЧИСЛЕНИЙ ФYHKЦИИT']);
Result := Result + Format('%s',['  IERR = ']);
Result := Result + Format('%2d ',[IERR]) + #$0D#$0A;
Result := Result + Format('  %4d ',[ITMAX]);
Result := Result + Format('%s',['  ИTEPAЦИЙ']);
Result := Result + Format('  %6d ',[MAXK]);
Result := Result + Format('%s',['  ВЫЧИСЛЕНИЙ ФYHKЦИИ']);
Result := Result + Format('%s',['  F(X) = ']);
Result := Result + Format('%20.16f ',[FF]) + #$0D#$0A;
for I:=1 to N do
 begin
  Result := Result + Format('  X(%1d ) = %20.16f ',
 [I,XX[I-1]]) + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TMNBBR',Result);  { вывод результатов в файл TMNBBR.res }
exit;
end;

end.

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

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

implementation

procedure fmnbbr(var X :Array of Real; var F :Real; FE :Real);
begin
F := 4.0*X[0]-IntPower(X[1],2)-12.0;
end;

end.

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

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

implementation

procedure ftmnbbr(var X :Array of Real; var F :Real; FE :Real);
var
R :Real;
begin
F := 25.0-IntPower(X[0],2)-IntPower(X[1],2);
F := IntPower(F,2);
R := IntPower(X[0]-5.0,2)+IntPower(X[1]-5.0,2)-16.0;
R := -R;
if ( R < 0.0 ) 
 then F := F+IntPower(R,2);
if ( X[0] < 0.0 ) 
 then F := F+IntPower(X[0],2);
if ( X[1] < 0.0 ) 
 then F := F+IntPower(X[1],2);
F := Sqrt(F);
end;

end.

Результаты:

      IERR   =  65
      FF       =  -0.3199231 + 02

      XX(1)  =  1.0012830 - 00
      XX(2)  =  4.8987190 - 00