Programación non linear

En matemáticas, programación non linear (PNL) é o proceso de resolución dun sistema de igualdades e desigualdades suxeitas a un conxunto de restricións sobre un conxunto de variables reais descoñecidas, cunha función obxectivo para maximizar (ou minimizar), cando algunha das restricións ou a función obxectivo non son lineares.

 Formulación matemática do problema 
O problema de programación non linear pode enunciarse dun xeito moi simple:
 maximizar unha función obxectivo
o
 minimizar unha función obxectivo (de custo)
onde

 Métodos de resolución do problema 
Se a función obxectivo f é linear e o espazo restrinxido é un politopo, o problema é de programación linear e pode resolverse utilizando algún dos algoritmos coñecidos de programación linear.

Se a función obxectivo é cóncava (problema de maximización), ou convexa (problema de minimización) e o conxunto de restricións é convexo, entón pode empregarse o método xeral de optimización convexa

Existen diversos métodos para resolver problemas non convexos. Un deles consiste en empregar formulacións especiais de problemas de programación linear. Outro método implica o uso de técnicas de ramificación e poda, cando o problema se divide en subdivisións para resolver mediante aproximacións que forman un límite inferior do custo total en cada subdivisión.

Mediante subdivisións sucesivas, obterase unha solución cun custo igual ou inferior que o mellor límite inferior obtido por algunha das solucións aproximadas. Esta solución é óptima, aínda que posiblemente non sexa única.

O algoritmo pode ser parado antes, coa garantía de que a mellor solución será mellor que a solución atopada nunha porcentaxe limitada. Iso emprégase en concreto en problemas importantes e especialmente difíciles e cando o problema conta con custos incertos ou valores onde a incerteza pode ser estimada nun grao de fiabilidade apropiado.

As condicións de Karush-Kuhn-Tucker proporcionan as condicións necesarias para que unha solución sexa óptima.

 Exemplos 
 Exemplo bidimensional 

miniatura|A intersección da liña co espazo de restricións representa a solución.
Un problema sinxelo pode definirse polas restricións:
x1 ≥ 0 
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2
cunha función obxectivo que se quere maximizar
f(x) = x1 + x2
onde x = (x1, x2)

 Exemplo tridimensional 
miniatura|A intersección da superficie superior co espazo de restricións no centro representa a solución.
Outro problema simple defínese pola restricións:x12 − x22 + x32 ≤ 2 
x12 + x22 + x32 ≤ 10
cunha función obxectivo que se quere maximizar
f(x) = x1x2 + x2x3
onde x = (x1, x2, x3)

 Notas 

 Véxase tamén 
 Bibliografía 
 Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
 Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
 Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
 Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.
 Outros artigos 
 Optimización
 Axuste de curvas
 Método de mínimos cadrados
 Programación linear
 Ligazóns externas 
 Programación non Linear
 Preguntas frecuentes de programación non linear 
 Glosario de programación matemática  
 Nonlinear Programming Survey OR/MS Today

Categoría:Estatística