Текст подпрограммы и версий ( Фортран )
mnbbr.zip 		Тексты тестовых примеров ( Фортран )
tmnbbr.zip
Текст подпрограммы и версий ( Си )
mnbbr_c.zip 		Тексты тестовых примеров ( Си )
tmnbbr_c.zip
Текст подпрограммы и версий ( Паскаль )
mnbbr_p.zip 		Тексты тестовых примеров ( Паскаль )
tmnbbr_p.zip

Подпрограмма:  MNBBR

Назначение

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

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

Для решения задачи
     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.

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

    SUBROUTINE  MNBBR (N, NMP1, ITMAX, ITMT, ALFA, BETA,
                                              GAM, ACC, A, XYZ, XX, VEC, FF, MAXK,
                                              MAXT, FUN, FUNT, IERR) 
   Параметры
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) должен иметь вид: 

           SUBROUTINE  FUN (X, F, FE)

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

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

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

           SUBROUTINE  FUNT (X, F, FTE)

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

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

Имена подпрограмм вычисления функции  f (x) и функционала  T (x) должны быть определены в вызывающей программе опеpатоpом EXTERNAL.

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

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

       SUBROUTINE  F0 (X, F, FE)
       DIMENSION  X(1)
       F = 4.*X(1) - X(2)**2 -12.
       RETURN
       END

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

       SUBROUTINE  T (X, F, FE)
       DIMENSION  X(1)
       F =  25. - X(1)**2 - X(2)**2
       F = F**2
       R = (X(1) - 5.)**2 + (X(2) - 5.)**2 - 16.
       R = - R
       IF(R .LT. 0.) F = F + R**2
       IF(X(1) .LT. 0.) F = F + X(1)**2
       IF(X(2) .LT. 0.) F = F + X(2)**2
       F = SQRT(F)
       RETURN
       END

   Вызывающая программа

       DIMENSION  XYZ(3, 6), VEC(2, 8), XX(2)
       EXTERNAL  F0, T
       DATA  ALFA, BETA, GAM / 1., 0.5, 2./,
      *            N, ITMAX, MAXK /2, 50, 400/
       DATA  ACC, A /1.E - 6, 0.3/, XX(1), XX(2) /1., 1./
       DATA  NMP1, ITMT, MAXT /3, 200, 500/
       CALL  MNBBR (N, NMP1, ITMAX, ITMT, ALFA, BETA, GAM, ACC, 
      *                          A, XYZ, XX, VEC, FF, MAXK, MAXT, F0, T, IERR)

Результаты:

      IERR   =  65
      FF       =  -0.3199231 + 02

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