Programación NO Lineal (PNL)
Optimización sin restricciones
Ejemplos de los problemas que se aplica la programación NO Lineal:
Problema de transporte con descuentos por cantidad: El precio unitario de transporte entre un
origen y un destino es decreciente en función de la cantidad a transportar.
Problema de flujo de cargas en un sistema eléctrico: Las pérdidas son no lineales.
Problema de producción con elasticidad en el precio y/o en el coste: Consideremos que los
precios unitarios disminuyen cuando vendemos un número importante de productos, esto nos
indica que la renta marginal disminuye cuando aumentan las ventas. Es el caso de reducir el
precio de venta a partir de cierta cantidad vendida: cuando llevo vendido una cantidad
importante le reduzco el precio de venta.
Extremos de la función: Los valores donde alcanza el máximo o el mínimo se llaman extremos de la
función.
Extremo global
La función objetivo f(x1;x2; xn) tiene un extremo global; por ejemplo, un
máximo global, si es mayor o igual que cualquier otro valor de la función dentro del dominio de esta.
Análogamente para mínimo si es menor o igual.
Extremo local
En este caso el extremo que alcanza la función es dentro de un entorno de un punto. Con el signo ≤ ; ó ≥ según
corresponda a mínimo o máximo.
Podemos definir entonces que para Programación No Lineal un punto factible
X= (x1,x2, ,xn) es un máximo (mínimo) local si para un ε suficientemente pequeño,
cualquier punto factible X’= (x1’,x2’,...,xn’) tal que |xi-xi’| <ε satisface f(X) ≥ (≤) f(X’)
Un punto que es un máximo o mínimo local se llama extremo local o relativo.
Funciones cóncavas y convexas
Función convexa:
Si hablamos de la función objetivo f(x1,x2,...xn) podemos definir si se trata de una función Cóncava (cóncava
hacia abajo) ó Convexa (cóncava hacia arriba) Para interpretar la definición se puede pensar en una función de 2
variables que podemos representar en el plano.
f(x,y) es convexa si las cuerdas entre dos puntos de la función están por arriba de la curva que representa la
función
f(x,y) es convexa
Otra definición es que: las derivadas primeras son rectas que quedan por debajo de la función (rectas en verde)
f(x,y) es cóncava si las cuerdas entre dos puntos de la función están por debajo de la curva que representa la
función
f(x,y) es cóncava
En este caso las derivadas primeras son las rectas que permanecen por encima de la función (rectas en verde)
Esta condición la podemos anotar: f es convexa si
f λ x1 + (1 – λ) x2 ≤ λ f(x1) +(1 – λ) f(x2);
si el signo es < es estrictamente convexa donde λ es un número real entre 0 y 1 ; 0 ≤ λ ≤1 análogamente f es
cóncava si
f λ x1 + (1 – λ) x2 ≥ λ f(x1) +(1 – λ) f(x2)
si el signo es > es estrictamente cóncava
Teorema 1
Se considera un PNL con región factible S convexa.
Entonces si el problema es de maximización (minimización) y la función f es estrictamente cóncava (convexa)
en S, entonces cualquier máximo (mínimo) local del PNL es una solución óptima de este problema; es decir es
un máximo global.
Teorema 2
Si f’’(X) existe para cualquier X en un conjunto convexo S, entonces f(X)
es una función cóncava (convexa) en S si y sólo si f’’(X) ≤ 0 ( ≥ 0) para todo X de S.
Teorema 3
Si f (x1,x2,...,xn) tiene derivadas parciales de segundo orden continuas para cada punto X= (x1,x2,...,xn) de un
conjunto convexo S, entonces f(X)es una función estrictamente cóncava (convexa) en S si y sólo si su matriz
Hessiana es definida negativa (positiva).
Conclusiones:
El máximo (mínimo) global es difícil de encontrar. Muchos métodos son locales.
Sólo bajo supuestos adicionales concavidad (convexidad) se puede garantizar que es global.
Dentro de un espacio solución (conjunto de inecuaciones) lineal convexo, si f(X) es cóncava, el máximo
obtenido es global es decir es el óptimo de f(x), pues no existe otro mayor dentro del espacio solución.
Dentro de un espacio lineal convexo (conjunto de inecuaciones), si f(X) es convexa el máximo obtenido es un
máximo local. Es el mayor dentro de un subespacio del espacio solución, pero No podemos asegurar que es el
óptimo de f(X).
Bibliografía:
[Link]
Michael German Posada Torres
