Programación non llinial

En matemátiques, programación non llinial (PNL) ye'l procesu de resolución d'un sistema d'igualdaes y desigualdaes suxetes a un conxuntu de restricciones sobre un conxuntu de variables reales desconocíes, con una función oxetivu a maximizar (o embrivir), cuando dalguna de les restricciones o la función oxetivu nun son lliniales.

Formulación matemática del problema

El problema de programación non llinial puede enunciase d'una forma bien simple:

$\max _{x\in X}f(x)$ maximizar una función oxetivu o :$\min _{x\in X}f(x)$ embrivir una función oxetivu (de costu)

onde :$f:R^{n}\to R$

$X\subseteq R^{n}.$

Métodos de resolución del problema

Si la función oxetivu f ye llinial y l'espaciu acutáu ye un politopo, el problema ye de programación llinial y puede resolvese utilizando dalgunu de los bien conocíos algoritmos de programación llinial.

Si la función oxetivu ye cóncavu (problema de maximización), o convexa (problema de minimización) y el conxuntu de restricciones ye convexu, entós puede utilizase el métodu xeneral d'optimización convexa.

Esiste una variedá de métodos pa resolver problemes non convexos. Unu d'ellos consiste n'utilizar formulaciones especiales de problemes de programación llinial. Otru métodu implica l'usu de téuniques de Ramificación y fradadura, cuando'l problema estremar en subdivisiones a resolver por aciu aproximamientos que formen una llende inferior del costu total en cada subdivisión. Por aciu subdivisiones socesives, va llograse una solución que'l so costu ye igual o inferior que'l meyor llende inferior llográu por dalguna de les soluciones averaes. Esta solución ye óptima, anque posiblemente nun sía única. L'algoritmu puede ser paráu antes, cola garantía de que la meyor solución va ser meyor que la solución atopada nun porcentaxe acutáu. Ello utilízase en concretu en problemes importantes y especialmente difíciles y cuando'l problema cunta con costos inciertos o valores onde la incertidume puede ser envalorada nun grau de fiabilidá apropiáu.

Les condiciones de Karush-Kuhn-Tucker apurren les condiciones necesaries por que una solución sía óptima.

Ejemplo

Ejemplo bidimensional

La interseición de la llinia col espaciu de restricciones representa la solución.

Un problema senciellu puede definise poles restricciones:

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

con una función oxetivu a ser maximizada

f(x) = x₁ + x₂

onde x = (x₁, x₂)

Exemplu tridimensional

La interseición de la superficie cimera col espaciu de restricciones nel centru representa la solución.

Otru problema simple definir pola restricciones:x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

con una función oxetivu a ser maximizada

f(x) = x₁x₂ + x₂x₃

onde x = (x₁, x₂, x₃)

Ver tamién

• Optimización
• Axuste de curves
• Métodu de mínimos cuadraos
• Programación llinial

Referencies

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.

Enllaces esternos

• Programación Non Llinial (enllaz rotu disponible n'Internet Archive; ver l'historial y la última versión).
• Entrugues frecuentes de programación non llinial (n'inglés)
• Glosariu de programación matemática (n'inglés) Archiváu 2010-03-28 en Wayback Machine
• Nonlinear Programming Survey OR/MS Today Archiváu 2009-07-24 en Wayback Machine

Software

• AIMMS Optimization Modeling AIMMS — Inclúi programación non llinial en soluciones sectoriales (prueba gratis, llicencia de prueba disponible);
• AMPL solver software - De baldre pa estudiantes
• GAMS – Versión gratis disponible pa estudiantes