Programacion no lineal

Universidad de Chile

Facultad de Ciencias Forestales
Depto: Manejo de Recursos Forestales
Curso: "Investigación de Operaciones - II"
Programación NO Lineal

Prof. J. Barrios M. -- Noviembre del 2002.

En la programación no lineal (PNL) lo que se quiere es encontrar el óptimo de una función objetivo f(x) de n variables, no lineal, sujeto o no sujeto a restricciones arbitrarias de las nvariables del problema. Dicho de otra manera la PNL pretende encontrar el máximo y/o el mínimo de una función no lineal f(x) de n variables en que se puede tener o no variadas restricciones para las n variables.

Recordemos que una función real f(x) de n variables es función lineal si ella es una suma ponderada de las n variables de f(x). Es decir, f(x) es función lineal si tiene la forma:a1x1 + a2x2 + ......... + anxn ; con ai ( IR , (i . O bien, f(x) es función lineal si satisface la condición de linealidad: f((u + (v ) = (f(u) + (f(v); ((,(( IR ; (u,v ( IRn .

Lo anterior permite entender o decir que una función no lineal es aquella que no es función lineal en el sentido establecido en el párrafo anterior.

|Máx f(x);|Máx f(x); |
|s.a: g1(x) (< ( = > ( () b1, |s.a: g1(x) (< ( = > ( () b1, |
|.... gm(x) (< ( = > ( () bm |.... gm(x) (< ( = > ( () bm |
|con x ( IRn , f(x) ( IR , m(0, n(1,|con x ( IRn , f(x) ( IR , m(0, n(1, |
|f función real no lineal |f función real no lineal |

No hay un método general que permita resolver siempre un problema de programación no lineal, por lo que la PNL se estudia a través de casos. Y, los principales 3 casos son:i)Sin restricciones, ii)Con restricciones en igualdad, iii)Con restricciones en desigualdad. Dentro de cada uno de los casos se pueden distinguir subcasos.

Caso 1: Sin restricciones.

Los extremos de una función de n variables con valores reales pueden ser la solución de un modelo de programación no lineal. Su forma es:

|Máx (f(x)) |Min(f(x)) |
|x ( IRn |x ( IRn |

Para ubicar sus extremos relativos se plantea la condición de primer orden: [pic] Sistema de n ecuaciones que resulta de igualar a cero las n derivadas parciales de f, cuyas soluciones dan elpunto crítico, o los puntos críticos, si es que existen, entre los que están las soluciones posibles del problema. (En un extremo relativo de f(x) se cumple que todas sus derivadas parciales valen cero; condición necesaria pero no suficiente, como Ud. sabe).
Luego, se obtiene el Hessiano [pic] y se evalúa en cada punto crítico que se obtuvo. Por ejemplo: x0

Si H(x0) es definida, f tiene extremoen x0;
y, Si H(x0) es definida positiva, f tiene MINIMO en x0.
Si H(x0) es definida negativa, f tiene MAXIMO en x0.
Si H(x0) no es definida, entonces f(x) no tiene extremo en x0.

Una matriz A = (aij)nxn es definida si todos los valores propios (i de ella son de un mismo signo; ya sea todos positivos o todos negativos.

Una matriz A se dice definida positiva si (i > 0; (i.Una matriz A se dice definida negativa si (i < 0; (i.

Una matriz A se dice semi definida positiva si (i ( 0; (i.

Una matriz A se dice semi definida negativa si (i ( 0; (i.

Ejemplo - 1 Determinar extremos de [pic]

|fx = |x2 + y2 + 2x - 15 = 0 |Si y = 0, x2 + 2x - 15 = 0 | Si x = 0, y2 - 15 = 0 |
|fy = |2xy = 0...