Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Метод барьерных функций

Этот метод был предложен Фиакко и Мак-Кормиком и назван ими методом последовательной безусловной минимизации. Этот метод предназначен для решения задач нелинейного программирования в форме неравенств:

¦(x) ® min; x Î X Ì E ⁿ, (8.32)

g_i (x) < 0, i = 1: m. (8.33)

Неравенство (8.33) запрещает присутствие в задании множества X ограничений-равенств. На множестве Х определим функцию B (x), которая называется барьерной функцией. Барьерные функции могут быть двух типов.

В первом типе используется так называемая обратная функция:

B (x) = - [ g_i (x)]^-1, (8.34)

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

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

B (x) = - ln [- g_i (x)], (8.35)

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

Составим функцию

¦(x, k) = ¦(x) + B (x).

Штрафная добавка B (x) к целевой функции ¦(x) образует как бы барьер, препятствующий выходу из допустимой области в процессе оптимизационного поиска.

Метод заключается в следующем. Выбирается последовательность постоянных { k_i }, k_i ® ¥. Решается соответствующая последовательность задач минимизации без ограничений, в результате чего определяется последовательность минимальных точек { x ^{( k )*}}. При определенных условиях такая последовательность { x ^{( k )*}} существует и точка минимума x ^* задачи с ограничениями получается в виде предела.

, ¦^*» ¦(x ^{( k )}).

Поскольку все точки последовательности { x ^{( k )}} лежат в допустимой области, метод барьерных функций называют методом внутренней то чки.

Пример 8.7. Решить задачу

¦(x) = x ® min,

- x + 2 £ 0

методом барьерных функций, используя в качестве В (x) = - 1/ g_i (x).

Решение. Обобщенная функция будет иметь вид

¦(x, k) = x + . (8.36)

Y

¦₁(x)

A₁

5

4

¦₁₀₀(x)

3

A₂

8 A

1

x^* x⁽¹⁰⁰⁾ x⁽¹⁾

1 2 3 4 5 X

Рис. 8.8. Графическая иллюстрация задачи

Область ограничений лежит справа от вертикальной прямой x = 2 (рис. 8.8). Начиная из произвольной точки допустимого множества, например x ⁽⁰⁾ = 5, найдем решение ¦ (x, k) при различных k. Вычислим производную

d ¦(x, k)/ dx = 1 – 1/(k (x -2)²) = 0.

Откуда

k (x -2)² – 1 = 0, (x -2)² = , x = 2 + . (8.37)

Решая (8.37) при k=1; 9; 100, получим соответственно x ^(1)* = 3, x ^(9)* = 2,3, x ^(100)* = 2,1 (табл. 8.2).

Таблица 8.2.

Оптимальные значения функции (8.36)

Нетрудно видеть, что последовательность точек A ₁, A ₂, A ₃ стремится к A - минимуму функции при наличии ограничений.

d ²¦(х, k)/ dx ² = 2 /[ k (x -2)³] и минимум достигается при x = 2 + . Тогда A ₁ есть точка с координатами (3; 4), A ₂ – точка с координатами (2,3;2,67), A ₃ – точка с координатами (2,1;2,2). Ясно, что при k ® ¥ x ^{( k )*} = 2.