Задачи нелинейного программирования

Лекция 16

1:

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

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

F(х)→min (max) (1)

при условии

g(x)≤ 0, (2)

 

где х – вектор искомых переменных; F(х) - целевая числовая функция; g(x) – вектор-функция системы ограничений.

2:

При этом могут быть разные случаи:

1) целевая функция – нелинейная, а ограничения – линейны;

2) целевая функция – линейная, а ограничения (хотя бы одно из них) – нелинейные;

3) целевая функция и ограничения нелинейные.

Задачи условной оптимизации нелинейного программирования бывают двух типов: когда в ограничениях (2) имеют место:

а) знаки равенства;

б) знаки неравенства.

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

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

3:

Среди большого числа вычислительных алгоритмов нелинейного программирования значительное место занимают:

- различные варианты градиентных методов (метод проекции градиента, метод условного градиента и т. п.);

- методы штрафных функций;

- методы барьерных функций;

- метод модифицированных функций Лагранжа и др.

4:

Нелинейные задачи с ограничениями в форме равенств нередко решаются с помощью введения функции Лагранжа:

 

 

 

где L(x, λ) — лагранжиан; φ(x) — целевая функция; λ_i (i = 1, 2, ..., k) – множители Лагранжа; k — число ограничений g_i(x).

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

Задачи нелинейного программирования на практике возникают довольно часто, например, когда затраты растут непропорционально количеству закупленных или произведенных товаров. Хорошо известно, что чем больше партия закупаемого товара, тем меньше стоимость единицы продукта. Каждому знакомо понятие розничных и оптовых цен.

Рассмотрим частный случай общей задачи нелинейного программирования (1), предполагая, что система ограничений (2) содержит только уравнения, отсутствуют условия неотрицательности переменных, F(х) и g(x) – функции, непрерывные вместе со своими частными производными. Ограничения в задаче заданы уравнениями, поэтому для ее решения можно воспользоваться классическим методом отыскания условного экстремума функций нескольких переменных. Вводят набор переменных, называемых множителями Лагранжа, и составляют функцию Лагранжа:

5:

 

 

находят частные производные

 

 

 

и рассматривают систему n + m уравнений:

 

(3)

с n + m неизвестными , . Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений.

6:

Пример. Найти точку условного экстремума функции при ограничениях:

 

 

7:

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

 

 

 

Продифференцируем ее по переменным . Приравнивая полученные выражения к нулю, получим следующую систему уравнений:

 

 

8:

Из второго и третьего уравнений следует, что ; тогда

 

 

 

Решив данную систему, получим:

 

и