Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://num-anal.srcc.msu.ru/lib_na/cat/mn/mnbbr.htm
Дата изменения: Thu Nov 26 13:17:39 2015 Дата индексирования: Sun Apr 10 01:27:01 2016 Кодировка: Windows-1251 |
Текст подпрограммы и версий ( Фортран ) mnbbr.zip |
Тексты тестовых примеров ( Фортран ) tmnbbr.zip |
Текст подпрограммы и версий ( Си ) mnbbr_c.zip |
Тексты тестовых примеров ( Си ) tmnbbr_c.zip |
Текст подпрограммы и версий ( Паскаль ) mnbbr_p.zip |
Тексты тестовых примеров ( Паскаль ) tmnbbr_p.zip |
Решение задачи минимизации функции многих переменных при наличии ограничений методом скользящего допуска.
Для решения задачи
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 составляются пользователем. 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