Постановка задачи нелинейного программирования и ее геометрическая интерпретация
Задача нелинейного программирования формулируется следующим образом:
определить минимальное значение функции
f(x) → min (7.1)
при условии, что её переменные удовлетворяют соотношениям
gi(x) = bi, i = 1:l, (7.2)
gi(x) £ bi, i = (l+1):m, (7.3)
где f(x), gi(x), i = 1:m − некоторые известные функции (необязательно линейные) n переменных, а bi − заданные числа. Считаем, что все функции fi(x), gi(x), i = 1:m определены на некотором открытом множестве X En. Для упрощения ограничимся случаем Х = Еn.
Условие неотрицательности переменных xj ³ 0, j = 1:n, входящее в постановки многих задач нелинейного программирования, можно записать в виде неравенств (7.3), положив gj(x) = -xj , bj = 0.
В евклидовом пространстве En система ограничений (7.2) … (7.3) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.
Cформулированная задача (7.1) … (7.3) представляет собой частный случай общей задачи математического программирования, заключающийся в определении наименьшего значения целевой функции f(x) на допустимом множестве
Х = {х Х | gi(х) = bi, i = 1:l, gi(х) ≤ bi, i = (l+1):m}.
Отметим, что если все функции gi(х) непрерывны в Еn, то множество Х замкнуто.
Большинство известных методов решения задачи нелинейного программирования позволяют найти лишь точки локального минимума целевой функции на заданном множестве. В этой связи важную роль играет априорная информация о существовании решения задачи, т.е. информация о том, достигает ли целевая функция наименьшего значения на допустимом множестве. В частности, если множество Х ограничено, а целевая функция непрерывна на Х, то задача нелинейного программирования имеет решение.
Однако проверить ограниченность множества Х не просто. Поэтому интересны другие условия, налагаемые на целевую функцию и ограничения и позволяющие делать заключение о существовании решения без использования ограниченности допустимого множества. В задаче выпуклого программирования, в которой целевая функция выпукла и допустимое множество Х выпукло, любая точка локального минимума целевой функции, согласно утверждения 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(х) = x2 − x12 + 6x1 (7.4)
при условиях
(7.5)
x1, x2 ³ 0. (7.6)
Решение.Так как целевая функция (7.4) нелинейная, то задача (7.4) … (7.6) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник 0АВС (рис. 7.4). Следовательно, для нахождения её решения нужно определить такую точку многоугольника 0АВС, в которой функция (7.4) принимает максимальное значение. Построим линию уровня f(х) = x2 − x12 + 6x1 = α , где α – некоторая постоянная, и исследуем её поведение при различных значениях α.. При каждом значении α получаем параболу, которая чем дальше отдалена от оси 0x1, тем больше значение α.. Значит, функция f принимает максимальное значение в точке касания одной из парабол с границей многоугольника 0АВС. В данном случае это точка D (рис. 7.4), в которой линия уравнения f = x2 − x12 + 6x1 = 13 касается стороны АВ многоугольника 0АВС.
Координаты точки D можно найти из системы уравнений
Решая эту систему, получим x1* = 3; x2* = 4. Итак, fmax = 13 при x* (3;4).
Рис. 7.4. Область допустимых решений
Для нахождения гиперплоскости наинизшего уровня можно руководствоваться следующими соотношениями: точка x* = (x1 min, x2 min) принадлежит прямой x2 = 0 и параболе fmin = x2 − x12 +6x1 , а потому обоим этим уравнениям, т. е. может быть определена как решение системы
(7.7)
Однако, так как нам не известно f* − оптимальное значение целевой функции f(x1, x2), то в этой системе оказывается три переменных и всего два уравнения, поэтому систему необходимо дополнить ещё одним уравнением, связывающим переменные x1, x2, fmin.
Нужное уравнение можно получить, если учесть, что угловой коэффициент касательной к параболе, по которой целевая функция достигает своего минимального значения, равен 1: касательной в этой точке является прямая x2 = 0. Как мы знаем, угловой коэффициент касательной к кривой x2 = f(x1) в точке x1 равен ∂x2 / ∂x1. Поэтому в нашем случае имеем
∂x2 / ∂x1 = 0. (7.8)
Вычислим теперь производную целевой функции fmin. Для этого продифференцируем левую и правую часть этого соотношения по x1. Получим:
0 = 0 − 2x1 + 6. (7.9)
Первое слагаемое дифференцируем, как сложную функцию от x2:
∂[x2]/∂x1 = ∂[x2]/∂x2·∂x2/∂x1 = 0.
Откуда из (7.9) следует 0 = 2x1 +6. Если учесть (7.8), то окончательно получим:
2x1 − 6 = 0, x1 = 3.
Дополняя этим последним соотношением систему (7.7), окончательно получим:
Откуда −9 + 18 = f*, f* = 9.
Для нахождения максимального значения функции поступаем аналогичным образом. Получаем систему:
Решая её, получим fmax = 13.
Рассмотрим задачу нелинейного программирования, в которой все ограничения заданы линейными функциями, на переменные x1,…, xn наложены условия неотрицательности, а целевая функция нелинейная.