Постановка задачи нелинейного программирования и ее геометрическая интерпретация

 

Задача нелинейного программирования формулируется следующим образом:

определить минимальное значение функции

 

f(x) → min (7.1)

 

при условии, что её переменные удовлетворяют соотношениям

 

g_i(x) = b_i, i = 1:l, (7.2)

g_i(x) £ b_i, i = (l+1):m, (7.3)

 

где f(x), g_i(x), i = 1:m − некоторые известные функции (необязательно линейные) n переменных, а b_i − заданные числа. Считаем, что все функции f_i(x), g_i(x), i = 1:m определены на некотором открытом множестве X Eⁿ. Для упрощения ограничимся случаем Х = Еⁿ.

Условие неотрицательности переменных x_j ³ 0, j = 1:n, входящее в постановки многих задач нелинейного программирования, можно записать в виде неравенств (7.3), положив g_j(x) = -x_j , b_j = 0.

В евклидовом пространстве Eⁿ система ограничений (7.2) … (7.3) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Cформулированная задача (7.1) … (7.3) представляет собой частный случай общей задачи математического программирования, заключающийся в определении наименьшего значения целевой функции f(x) на допустимом множестве

Х = {х Х | g_i(х) = b_i, i = 1:l, g_i(х) ≤ b_i, i = (l+1):m}.

Отметим, что если все функции g_i(х) непрерывны в Еⁿ, то множество Х замкнуто.

Большинство известных методов решения задачи нелинейного программирования позволяют найти лишь точки локального минимума целевой функции на заданном множестве. В этой связи важную роль играет априорная информация о существовании решения задачи, т.е. информация о том, достигает ли целевая функция наименьшего значения на допустимом множестве. В частности, если множество Х ограничено, а целевая функция непрерывна на Х, то задача нелинейного программирования имеет решение.

Однако проверить ограниченность множества Х не просто. Поэтому интересны другие условия, налагаемые на целевую функцию и ограничения и позволяющие делать заключение о существовании решения без использования ограниченности допустимого множества. В задаче выпуклого программирования, в которой целевая функция выпукла и допустимое множество Х выпукло, любая точка локального минимума целевой функции, согласно утверждения 3.1, является решением этой задачи.

Если определена область допустимых решений, то нахождение решения задачи (7.1) … (7.3) сводится к определению такой точки этой области, через которую проходит гиперплоскость наинизшего уровня: f(x) = α , где α − произвольное число.

Процесс нахождения решения задач нелинейного программирования (7.1)…(7.3) с использованием её геометрической интерпретации включает следующие этапы:

1. Находят область допустимых решений задачи, определяемую соотношениями (7.2) … (7.3).

2. Строят гиперплоскость f(x) = α.

3. Определяют гиперплоскость наинизшего уровня или устанавливают неразрешимость задачи из-за неограниченности функции (7.1) снизу на множестве допустимых решений.

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

 

Пример 7.1.Найти максимальное значение функции

 

f(х) = x₂ − x₁² + 6x₁ (7.4)

 

при условиях

(7.5)

x₁, x₂ ³ 0. (7.6)

 

Решение.Так как целевая функция (7.4) нелинейная, то задача (7.4) … (7.6) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник 0АВС (рис. 7.4). Следовательно, для нахождения её решения нужно определить такую точку многоугольника 0АВС, в которой функция (7.4) принимает максимальное значение. Построим линию уровня f(х) = x₂ − x₁² + 6x₁ = α , где α – некоторая постоянная, и исследуем её поведение при различных значениях α.. При каждом значении α получаем параболу, которая чем дальше отдалена от оси 0x₁, тем больше значение α.. Значит, функция f принимает максимальное значение в точке касания одной из парабол с границей многоугольника 0АВС. В данном случае это точка D (рис. 7.4), в которой линия уравнения f = x₂ − x₁² + 6x₁ = 13 касается стороны АВ многоугольника 0АВС.

Координаты точки D можно найти из системы уравнений

Решая эту систему, получим x₁^* = 3; x₂^* = 4. Итак, f_max = 13 при x^* (3;4).

 

 

Рис. 7.4. Область допустимых решений

 

Для нахождения гиперплоскости наинизшего уровня можно руководствоваться следующими соотношениями: точка x^* = (x_{1 min}, x_{2 min}) принадлежит прямой x₂ = 0 и параболе f_min = x₂ − x₁² +6x₁ , а потому обоим этим уравнениям, т. е. может быть определена как решение системы

 

(7.7)

 

Однако, так как нам не известно f* − оптимальное значение целевой функции f(x₁, x₂), то в этой системе оказывается три переменных и всего два уравнения, поэтому систему необходимо дополнить ещё одним уравнением, связывающим переменные x₁, x₂, f_min.

Нужное уравнение можно получить, если учесть, что угловой коэффициент касательной к параболе, по которой целевая функция достигает своего минимального значения, равен 1: касательной в этой точке является прямая x₂ = 0. Как мы знаем, угловой коэффициент касательной к кривой x₂ = f(x₁) в точке x₁ равен ∂x₂ / ∂x₁. Поэтому в нашем случае имеем

 

∂x₂ / ∂x₁ = 0. (7.8)

 

Вычислим теперь производную целевой функции f_min. Для этого продифференцируем левую и правую часть этого соотношения по x₁. Получим:

 

0 = 0 − 2x₁ + 6. (7.9)

 

Первое слагаемое дифференцируем, как сложную функцию от x₂:

 

∂[x₂]/∂x₁ = ∂[x₂]/∂x₂·∂x₂/∂x₁ = 0.

 

Откуда из (7.9) следует 0 = 2x₁ +6. Если учесть (7.8), то окончательно получим:

2x₁ − 6 = 0, x₁ = 3.

Дополняя этим последним соотношением систему (7.7), окончательно получим:

Откуда −9 + 18 = f*, f* = 9.

Для нахождения максимального значения функции поступаем аналогичным образом. Получаем систему:

Решая её, получим f_max = 13.

Рассмотрим задачу нелинейного программирования, в которой все ограничения заданы линейными функциями, на переменные x₁,…, x_n наложены условия неотрицательности, а целевая функция нелинейная.