Programación non linear

Na Galipedia, a Wikipedia en galego.
Saltar ata a navegación Saltar á procura

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 | editar a fonte]

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 | editar a fonte]

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 | editar a fonte]

Exemplo bidimensional[editar | editar a fonte]

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[editar | editar a fonte]

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:x12x22 + 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 | editar a fonte]

Véxase tamén[editar | editar a fonte]

Bibliografía[editar | editar a fonte]

  • 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[editar | editar a fonte]

Ligazóns externas[editar | editar a fonte]