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 editar
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 editar
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 editar
Exemplo bidimensional editar
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 editar
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 editar
Véxase tamén editar
Bibliografía editar
- 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.