Programación No Lineal

Prof. Ing. Claudio L. R. Sturla

REPÚBLICA ARGENTINA

PROGRAMACIÓN NO LINEAL
Puede reproducirse libremente. Se agradecerá citar la fuente.

Claudio L. R. Sturla
  Bibliografía: • Winston, Wayne L., Investigación de Operaciones, Grupo Editorial Iberoamérica, S. A. De C. V., México, 1.994, ISBN 970-625-029-8. • Chiang, Alpha C., Métodos Fundamentales de Economía Matemática, McGrawHill/Interamericana de México, S. A. De C. V., 1.998, ISBN 968-422-193-2.

Conceptos introductorios
DEFINICIÓN Se puede expresar un problema de programación no lineal (PNL)de la siguiente manera: Encuentre los valores de las variables x1 , x2 , , xn que z = f ( x1 , x2 , , xn ) máximo (o mínimo) sujeto a: g 2 ( x1 , x2 , , xn ) { ≤ ; = ; ≥ } b2 …………………………. …………………………. g n ( x1 , x2 , , xn ) { ≤ ;= ; ≥ } bn Como en la programación lineal z es el funcional del problema de programación no lineal y g1 ( x1 , x2 , , xn ) { ≤ ; = ; ≥ } b1 ; g 2 ( x1 , x2 , , xn ) { ≤ ; = ; ≥ } b2 ;… ; g n ( x1 , x2 , , xn ) { ≤ ; = ; ≥ } bn son las restricciones del problema de programación no lineal. Un problema de programación no lineal es un problema de programación no lineal no restringido. El conjuntode puntos ( x1 , x2 , , xn ) , tal que xi es un número real, es R n R1 , entonces, es el conjunto de los números reales. Los siguientes subconjuntos de R1 (llamados intervalos) serán de particular interés: g1 ( x1 , x2 , , xn ) { ≤ ; = ; ≥ } b1 (1)

[ a , b] las x que satisfacen a ≤ x ≤ b [ a, b) las x que satisfacen a ≤ x 〈 b
pnl-1.doc 238

Prof. Ing. Claudio L. R. Sturla (a, b] las x quesatisfacen a 〈 x ≤ b ( a, b ) las x que satisfacen a 〈 x 〈 b [ a, ∞ ) = las x que satisfacen x ≥ a (− ∞ , b] = las x que satisfacen x ≤ b Y en forma análoga a las definiciones de la programación lineal. DEFINICIÓN La región factible para el problema de programación no lineal es el conjunto de puntos ( x1 , x2 , , xn ) que satisfacen las m restricciones de (1). Supóngase que (1) es un problema demaximización. DEFINICIÓN Cualquier punto X en la región factible, para el cual se tiene que f ( X ) ≥ f ( X ) para todos los puntos X de la región factible, es una solución óptima para el problema de programación no lineal. (Para un problema de minimización, X es la solución óptima si f ( X ) ≤ f ( X ) para toda X factible. Por supuesto, si z , g 1 , g 2 ,  , g n son funciones lineales, entonces(1) será un problema de programación lineal y puede resolverse mediante el algoritmo simplex. Ejemplos de Programación No Lineal Ejemplo N° 1 A una compañía le cuesta c UM por unidad fabricar un producto. Si la compañía cobra p UM por unidad de producto, los clientes pedirán D( p ) unidades. Para maximizar las ganancias, ¿qué precio tendría que poner la compañía? Solución La variable de decisiónde la empresa es p Dado que la ganancia de la empresa es ( p − c ) D( p ) , la empresa querrá resolver el siguiente problema de maximización sin restricción:

( p − c ) D( p )

→

máximo

Ejemplo N° 2 Si se utilizan K unidades de capital y L unidades de trabajo, una compañía puede producir KL unidades de un bien manufacturado. Se puede conseguir el capital a 4 UM/unidad y el trabajo a 1UM/unidad. Se dispone de un total de 8 UM para contratar capital y trabajo. ¿Cómo puede la compañía maximizar la cantidad de bienes que se pueden fabricar? Solución Sea K = unidades de capital contratadas y L = unidades de trabajo compradas entonces K y L deben satisfacer 4 K + L ≤ 8 ; K ≥ 0 ; L ≥ 0 Por lo tanto, la compañía quiere resolver el siguiente problema de maximización restringido: pnl-1.doc239

Prof. Ing. Claudio L. R. Sturla z = KL → máximo sujeto a 4K + L ≤ 8 K ,L ≥ 0 Diferencias entre Programación No Lineal y Programación Lineal La solución para el problema de programación lineal es un conjunto convexo. También sabemos que la solución de programación lineal se encuentra en un punto extremo de un conjunto convexo. Pronto veremos, sin embargo, que aunque la región factible...