Задачи условной оптимизации и методы их решений

В общем случае задача условной оптимизации имеет вид:

F= f(x_j) →min;

g_i (x_j) = 0;

a_j ≤ x_j ≤ b_j.

Рассмотрим один из способов решения подобных задач, называемый методом штрафных функций, суть которого заключается в следующем. От задачи целевой оптимизации переходят к такой задаче, минимизируется новая целевая функция, включающая, кроме заданной целевой функции f(xj), заданные ограничения gi (xj). Новая целевая функция записывается следующим образом

Ф(x_j) = f(x_j)+ ψ[gi(x_j)]→min, где ψ[g_i(x_j)] –штрафная функция.

Вводимая штрафная функция ψ[g_i(x_j)] должна удовлетворять следующим требованиям:

ψ[g_i(x_j)] = 0, если x_j находится в области допустимых значений.

ψ[g_i(x_j)] > 0, если x_j находится в области допустимых решений.

Штрафная функция может иметь следующий вид:

_m

ψ[g_i(x_j)] = M ∑ g_i² (x_j), где M – большое число

ⁱ⁼¹

(например, если ожидаемое оптимальное значение целевой функции порядка единицы, то можно принять М=1000).

Если x_j находится в области допустимых решений, то выполняются все ограничения, значит,

g_i(x_j) = 0. При этом штрафная функция равняется нулю, и новая целевая функция оказывается равной заданной, т.е Ф(x_j) = f (x_j)→min.

Если x_j не находится в области допустимых решений, то ограничения не выполняются, т.е. g_i(x_j)≠ 0. Значит, g_i² (x_j)> 0, а большое число M приводит к тому, что в новой целевой функции штрафная функция оказывается существенно больше заданной целевой функции f (xj). Поэтому в ходе минимизации сначала уменьшается до нуля штрафная функция, а затем уже и сама целевая функция.

Примеp: решить задачу условной оптимизации вида: F =X₂→min;

X² = 2(x₁-2)²+1;

(x₁-3)²+(x₂-0,5)² ≥ 4;

0 ≤ x1 ≤ 4; 0 ≤ x2 ≤3.

Решение: Первое ограничение представляет собой параболу с координатами вершины A(2;1), второе – часть плоскости, находящуюся вне окружности радиуса R=2, центр которой имеет координаты O (3; 0.5). Без наложения второго ограничения минимум находился бы в вершине параболы и имел бы значение F₁=1. Наложение привело к тому, что минимум переместился в точку B с координатой х₁=1.4. При этом F₂= x₂= 1.8, то есть его значение ухудшилось.

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

1. Записывается условие задачи в виде системы

F= x₂ – min;

x₂ – 2(x₁-2)²-1=0;

(x₁-3)² + (x₂-0.5)² – y₁ – 4=0;

0 ≤ x₁≤ 4; 0 ≤ x₂ ≤ 3;

y₁≥0

2. Составляется новая целевая функция, включающая штрафную функцию с число M=1000. Получим F=x₂+100 [x₂-2(x₁-2)²+1+(x₁-3)²+(x₂-0.5)² –y₁-4] →min; 0 ≤ x₁≤ 4; 0 ≤ x₂ ≤ 3;

y₁≥0.

3. Далее проводится решение полученной системы.

Вопросы для самоконтроля по главе

1. Указать на разницу между понятиями экстремум и оптимум функции.

2. Дайте определение задачи безусловной оптимизации.

3. Дайте определение задачи условной оптимизации.

4. Каков алгоритм нахождения экстремума функций двух переменных.

5. В чем заключается суть метода штрафных функций.