Модуль 7. методы и модели нелинейного программирования

7.1. Постановка и геометрический смысл общей задачи нелинейного программирования

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

(7.1)

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

, (7.2)

где f и g_i – некоторые неизвестные функции n переменных, а b_i – заданные числа, а знак ( ) означает, что при различных i ограничения (7.2) могут выражаться со знаком или , или уравнениями. Здесь имеется в виду, что в результате решения задачи будет определена точка , координаты которой удовлетворяют соотношениям (7.2) и такая, что для всякой другой точки , удовлетворяющей условиям (7.2), выполняется в задаче на максимум (минимум) неравенство

Если f и g_i – линейные функции, то задача является задачей линейного программирования.

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

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

Если определена область допустимых решений, то нахождение решения задачи (7.1)-(7.2) сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня: . Указанная точка может находиться как на границе области допустимых решений, так и внутри нее.

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

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

2. Строят гиперповерхность .

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

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

Пример:

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

(7.3)

при условиях

(7.4)

x₁≥0, x₂ ≥ 0

Решение: Областью допустимых решений исходной задачи является многоугольник ABCDE (рис. 7.1), а линиями уровня – окружности с центром F(4, 3) и радиусом .

Рис.7.1 Геометрическая иллюстрация

Из рисунка. 7.1 видно, что целевая функция принимает минимальное значение в точке F(4, 3), а максимальное значение – в точке С (13, 21/2). Следовательно, F_min=0 , F_max=137,25.

7.2. Метод множителей Лагранжа

Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и и - функции, непрерывные вместе со своими частными производными

; (7.5)

(7.6)

В курсе математического анализа задачу (7.5) – (7.6) называют задачей на условный экстремум или классической задачей оптимизации.

Чтобы найти решение этой задачи, вводят набор переменных , называемых множителями Лагранжа, составляют функцию Лагранжа

(7.7)

Находят частные производные и и рассматривают систему n+m уравнений

(7.8)

с n+m неизвестными . Всякое решение системы уравнений (7.8) определяет точку , в которой может иметь место экстремум функции . Следовательно, решив систему уравнений (7.8), получают все точки, в которых функция (7.5) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума.

Таким образом, определение экстремальных точек задачи(7.5) – (7.6) методом множителей Лагранжа включает следующие этапы:

1. Составляют функцию Лагранжа.

2. Находят частные производные от функции Лагранжа по переменным x_j и λ_i и приравнивают их к нулю.

3. Решая систему уравнений (7.8), находят точки, в которых целевая функция задачи может иметь экстремум.

4. Среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значения функции (7.5) в этих точках.

Градиентные методы

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

Функция называется целевой функцией или функцией цели.

Если функция дифференцируема в точке , то градиентом в точке называется n-мерный вектор

.

Градиент в каждой точке , в которой он существует, направлен по нормали к линии уровня поверхности и показывает направление наискорейшего возрастания функции в данной точке (рис 7.2)

Рис. 7.2. Свойства вектора градиента

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

Вектор «- », противоположный градиенту, называется антиградиентом и указывает направление наискорейшего убывания функции .

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