Тема 10. Элементы нелинейного программирования

План лекции:

1. Постановка задачи нелинейного программирования (ЗНП)

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

3. Задача выпуклого программирования

4. Задача квадратического программирования

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

В общем виде ЗНП формулируется след образом:

где и (или) нелинейны.

Например,

Для ЗНП, в отличие от ЗЛП, нет единого метода решения. В зависимости от вида целевой функции и ограничений разработано несколько специальных методов решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод.

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

Пусть требуется решить ЗНП следующего вида

где и (или) непрерывны и дифференцируемы.

Для решения задачи вводят так называемую функцию Лагранжа L(x, l):

.

Метод функции Лагранжа сводит ЗНП на условный экстремум к задаче нахождения локального экстремума.

Алгоритм метода:

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

2) Находят стационарные точки функции Лагранжа из системы уравнений:

3) Из найденных стационарных точек выбирают те, в которых функция L(x, l) имеет локальные экстремумы. Функция L(x, l) имеет в стационарной точке локальный максимум, если в ней дифференциал второго порядка меньшего нуля (d²L<0), и локальный минимум, если дифференциал второго порядка больше нуля (d²L>0).

Множителям Лагранжа можно придать экономический смысл. Если F(x₁,x₂…x_n) – доход, соответствующий плану x=(x₁,x₂…x_n), – затраты некоторых ресурсов, тогда множители будут показывать как изменится максимальный доход, если количество ресурса i-го вида увеличится на единицу.

Задача. Найти условный минимум функции при ограничениях

Составим функцию Лагранжа:

.

Найдем стационарные точки функции Лагранжа из системы уравнений:

Решая систему, получаем .

Запишем дифференциал второго порядка функции Лагранжа. Поскольку все частные производные второго порядка, в записи которых присутствуют , равны нулю, то формула дифференциала второго порядка для функции Лагранжа примет вид:

.

Так как , , , , , , то

.

Следовательно, точка является точкой минимума функции . Найдем значение функции в данной точке:

.

Ответ: , .

3. Задача выпуклого программирования

Пусть дана система неравенств вида:

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

Определение 10.1. Точка (x*, λ*) называется седловой точкой функции Лагранжа, если n-мерная точка x* является точкой минимума функции L(x, λ*), а m-мерная точка λ* – точкой максимума функции L(x*, λ), так что x и λ выполняется неравенство:

.

Теорема 10.1. (Условие регулярности Слейтера) Множество Х допустимых решений ЗВП удовлетворяет условию регулярности Слейтера, если существует по крайне мере одно точка , такая что .

Теорема 10.2 (теорема Куна-Таккера). Чтобы точка x* была оптимальным решением ЗВП, множество допустимых решений которой обладают свойством регулярности Слейтера, необходимо и достаточно, чтобы существовала такая пара (x*, λ*), которая являлась бы седловой точкой функции Лагранжа данной ЗВП.

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

Для того чтобы найти седловые точки необходимо и достаточно составить систему: