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.

• Programación no convexa: incluye todos los problemas de PNL que no satisfacen los supuestos de programación onvexa. En este caso, aun cuando se tenga éxito en encontrar un máximo local, no hay garantía de que sea también un máximo global. Por lo tanto, no se cuenta con un algoritmo que garantice encontrar una solución óptima para todos estos problemas; sin embargo, existen algunos algoritmos bastante adecuados para encontrar máximos locales, en especial cuando las formas de las funciones no lineales no se desvían demasiado de aquellas que se supuso para programación convexa. Ciertos tipos específicos de problemas de programación no convexa se pueden resolver sin mucha dificultad mediante métodos especiales.

• Programación geométrica: cuando se aplica PNL a problemas de diseño de ingeniería, muchas veces la función objetivo y las funciones de restricción toman la forma:

[pic 9]

Donde:

[pic 10] [pic 11]

• Programación fraccional: si la función objetivo se encuentra en la forma de una fracción, esto es, como razón o cociente de dos funciones:

[pic 12]

...