TIPOS DE PROGRAMACIÓN NO LINEAL

3.3. Tipos de problemas de programación no lineal.

Veamos las clases de problemas de PNL m´as importantes:

• Optimización no restringida: problema sin restricciones, es decir, el problema se reduce a

Max f(x).

Tipos de problemas de programación no lineal.

Si f(x) es diferenciable, la condición necesaria para que x = x* sea optima es

[pic 1]

La condición suficiente es que f(x) sea cóncava.

• Optimización restringida linealmente: si todas las funciones de restricciones son lineales pero la función objetivo es no lineal. Se han desarrollado extensiones del método simplex. Un caso particular, con m = 0 es aquel en que hay variables no negativas. Por ejemplo,

Max f(x)

s.a. xj ≥ 0

Entonces la condición necesaria cambiaria a :

[pic 2]

Programación cuadrática: problema restringido linealmente con función objetivo cuadrática (contiene cuadrados de variables o/y productos de variables.

[pic 3]

Se han desarrollado muchos algoritmos para f(x) cóncava, esta formulación surge de manera natural en muchas aplicaciones.

• Programación convexa: abarca una amplia clase de problemas, entre los cuales, como casos especiales, se puede mencionar todos los tipos anteriores cuando f(x) es una función cóncava que debe maximizarse. Los supuestos son: (i) f(x) es cóncava y (ii) cada g(x) es convexa. Estos supuestos aseguran que un máximo local es global.

• Programación separable: es un caso especial de programación convexa, en donde el supuesto adicional es: todas las funciones f(x) y g(x) son separables. Una función separable es una función en la que cada término incluye una sola variable, por lo que la función se puede separar en una función separable, se puede expresar como:

[pic 4]

Donde cada fj(xj) incluye sólo los términos de xj. Por ejemplo: [pic 5] es una función separable porque puede ser expresada como [pic 6], donde [pic 7] y [pic 8] son cada una funciones de una sola variable. Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método simplex.

...