Условие Куна – Таккера

Пусть дана задача нелинейного программирования: найти максимальное значение функции Z=f(x₁, x₂, …., x_n) 0, I=

Составим функцию Лагранжа для данной задачи

F(x, )=f(x)+ q_i(x) (14)

Если выполняется условие регулярности (т.е. существует по крайней мере одна точка Х, для которой q_i(x)>0,то имеет место следующая теорема:

x⁰ 0; x_j⁰ x⁰ =0 , x_j 0, j= (21)

x⁰ 0 ; x⁰, =0 , x_i 0, I=

Вектор Х₀ тогда и только тогда является оптимальным решением задачи, когда, когда существует такой вектор , что при x⁰ 0 и 0 для всех х 0 и 0.

F(x, ⁰) F(x⁰, ) F(x⁰, ). (15)

Если f(x) и g(x) – дифференцируемые функции, то условие(2) эквивалентно следующим локальным условиям Куна-Танкера:

Выражение означает, что значение частной производной функции Лагранжа берется в точке x⁰, , где x⁰=(x₁⁰, x₂⁰, …,x_n⁰) и =( ).

Покажем применение условий Куна-Такера на следующем примере. Найти максимум функцию Z=-x₁²- x₂² при ограничениях:

2x₁+x₂ 2

x₁+x₂ 6

2x₁+x₂ 8 x₁ 0, x₂ 0 .

Решение:

1.Аналитически или с помощью графического метода можно определить x₁=0,8, x₂=0,4, Z=-0,8.

2.Покажем, что существует 0, при которой в точке максимума выполняется условие Куна-Таккера.

Для функции F(x, ):

F(x, )=-x₁²-x₂²+ (2x₁+x₂-2)+ (-2x₁-x₂+8)+ (6-x₁-x₂)

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

=-2x₁+2 -2 - ; =2x₁+x₂-Z

=-2x₂+ - - ;

=8-2x₁-x₂; =6-x₁-x₂.

Согласно условиям (3) и ₃ должны принимать нулевые значения т.к. подставляя x₁=0,8 , x₂=0,4 в выражение и , имеет значение больше нуля, но с условием x⁰, =0.

В соответствии с условием (2) производная x⁰, (j=1,2) должна принимать нулевое значение т.к. координаты вектора х⁰ отличны от нуля. Находим =0,8. Следовательно, в точке (х⁰, ) выполняются условия Куна - Таккера и она действительно является точкой экстремума.

Дата добавления: 2015-07-26; просмотров: 466; Нарушение авторских прав

Мы поможем в написании ваших работ!