Tipos de problemas de programación no lineal.

abril 16, 2010

Los problemas de programación no lineal se presentan de muchas formas distintas. Al contrario

del método símplex para programación lineal, no se dispone de un algoritmo que resuelva

todos estos tipos especiales de problemas. En su lugar, se han desarrollado algoritmos

para algunas clases de problemas de programación no lineal.

Optimización no restringida

Los problemas de optimización no restringida no tienen restricciones, por lo que la función

objetivo es sencillamente

Maximizar /(x)

sobre todos los valores x= (jíj, x2,…,xn). Según el repaso del apéndice 3 , la condición necesaria

para que una solución específica x = x* sea óptima cuando /(x) es una función diferenciable

es

Cuando f (x) es cóncava, esta condición también es suficiente, con lo que la obtención de x* se

reduce a resolver el sistema de las n ecuaciones obtenidas al establecer las n derivadas parciales

iguales a cero. Por desgracia, cuando se trata de funciones no lineales f (x), estas ecuaciones

suelen ser no lineales también, en cuyo caso es poco probable que se pueda obtener una solución

analítica simultánea.

Cuando una variable Xj tiene una restricción de no negatividad, x- > 0, la condición necesaria

(y tal vez) suficiente anterior cambia ligeramente a  para cada j de este tipo.

Optimización linealmente restringida

Los problemas de optimización linealmente restringida se caracterizan por restricciones que

se ajustan por completo a la programación lineal, de manera que todas las funciones de restricción

(x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho

si sólo se tiene que tomar en cuenta una función no lineal junto con una región factible de

programación lineal. Se han desarrollado varios algoritmos especiales basados en una extensión

del método símplex para analizar la función objetivo no lineal.

Un caso especial importante descrito a continuación es la programación cuadrática.

Programación cuadrática

De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora

la función objetivo /(x) debe ser cuadrática. Entonces, la única diferencia entre éstos y un problema de programación lineal es que algunos términos de la función objetivo incluyen el

cuadrado de una variable o el producto de dos variables.

Programación convexa

La programación convexa abarca una amplia clase de problemas, entre ellos como casos especiales,

están todos los tipos anteriores cuando /(x) es cóncava. Las suposiciones son

1. /(x) es cóncava.

2. Cada una de las g¿(x) es convexa.

Programación separable

La programación separable es un caso especial de programación convexa, en donde la suposición

adicional es

3. Todas las funciones / ( x ) y g¡(x) son funciones 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 suma de funciones de variables individuales. Por ejemplo,

si /(x) es una función separable, se puede expresar como

en donde cada / • (Xj) incluye sólo los términos con Xj.En la terminología de programación

lineal los problemas de programación separable satisfacen las suposiciones

de aditividad pero no las de proporcionalidad (para funciones no lineales).

Programación no convexa

La programación no convexa incluye todos los problemas de programación no lineal que no satisfacen

las suposiciones de programación convexa. 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 tiene un algoritmo que garantice encontrar una solución óptima para todos estos

problemas; pero sí 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 supusieron para programación convexa.

Programación geométrica

Cuando se aplica programación no lineal a problemas de diseño de ingeniería, muchas veces

la función objetivo y las funciones de restricción toman la forma

En tales casos, las ci y a ty representan las constantes físicas y las x} son las variables de diseño.

Estas funciones por lo general no son ni cóncavas ni convexas, por lo que las técnicas de programación

convexa no se pueden aplicar directamente a estos problemas deprogramacióngeométrica.

Sin embargo, existe un caso importante en el que el problema se puede transformar

en un problema de programación convexa equivalente. Este caso es aquel en el que todos los

coeficientes c¿ en cada función son estrictamente positivos, es decir, las funciones son polinomios

positivos generalizados (ahora llamados posinomiales), y la función objetivo se tiene que

minimizar. El problema equivalente de programación convexa con variables de decisión yx,

y2,…, yn se obtiene entonces al establecer

Xj = ey\ para;’ = l , 2 , . . . ,n

en todo el modelo original. Ahora se puede aplicar un algoritmo de programación convexa.

Se ha desarrollado otro procedimiento de solución para resolver estos problemas ác.programación

posinomial, al igual que para problemas de programación geométrica de otros tipos.

Problema de complementariedad

Cuando se estudie la programación cuadrática en la sección 13.7, se verá un ejemplo de cómo

la solución de ciertos problemas de programación no lineal se puede reducir a resolver el problema

de complementariedad. Dadas las variables wy,w2,…,wp y el problema

de complementariedad encuentra una s o l u c i o n a r á para el conjunto de restricciones

que también satisface la restricción de complementariedad,

wr z = 0 .

Aquí, w y z son vectores columna, F es una función con valores vectoriales dada y el superíndice

T denota la traspuesta . El problema no tiene función objetivo, de manera

que técnicamente no es un problema de,programación no lineal completo. Se llama

problema de complementariedad por las relaciones complementarias que establecen que una

de las dos

wi = Ó o zi = 0 (o ambas) para cada i = 1, 2,…,

Ilustración grafica de problemas de programación no lineal

abril 16, 2010

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar

Gráficamente, una representación gráfica de este tipo proporciona una visión global de las propiedades de las soluciones óptimas de programación lineal y no lineal.

La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que se hacen

al modelo de la sección 3.1 son que la segunda y tercera restricciones funcionales se sustituyen

por la restricción no lineal 9x{ + 5x2 < 216.

La solución

óptima sigue siendo (x1 , x2) = (2,6). Todavía se encuentra sobre la frontera de la región

factible, pero no es una solución factible en un vértice (FEV). La solución óptima pudo haber

sido una solución FEV con una función objetivo diferente, pero que

no necesite serlo significa que ya no se puede aprovechar la gran simplificación utilizada

en programación lineal que permite limitar la búsqueda de una solución óptima para las soluciones

FEV.

si

Z= 126X1-9X1^2 +182X2-13X2^2,

entonces la representación gráfica en la figura 3.1 indica que la solución óptima es x1=8/3

x2 = 5, que de nuevo se encuentra en la frontera de la región factible. (El valor óptimo de Z es

Z = 857; así, la figura 13.6 muestra el hecho de que el lugar geométrico de todos los puntos

para los que Z = 857 tiene en común con la región factible sólo este punto, mientras que el lugar

geométrico de los puntos con Z más grande no toca la región factible en ningún punto.)

Por otro lado, si

Z= 5 4 x1 – 9×1^2 + 78X2 – 1 3 x2^2

entonces la figura 3.3 ilustra que la solución óptima es (x1,x2 ) = (3,3), que se encuentra

dentro de la frontera de la región factible. (Se puede comprobar que esta solución es óptima si

se usa cálculo para derivarla como un máximo global no restringido; como también satisface

las restricciones, debe ser óptima para el problema restringido.) Por lo tanto, es necesario que

un algoritmo general para resolver problemas de este tipo tome en cuenta todas las soluciones

en la región factible, y no sólo aquellas que están sobre la frontera.

Otra complicación que surge en programación no lineal es que un máximo local no necesariamente

es un máximoglobal (la solución óptima global). Por ejemplo, considere la función

de una sola variable graficada en la figura 3.3. En el intervalo 0 < x < 5, esta función

tiene tres máximos locales — x=0^x=2,x=4—pero sólo uno de éstos—x – 4—es un ximo

global. (De igual manera, existen mínimos locales en x = 1,3 y 5, pero sólo x = 5 es un mínimo

global.)

. Recuerde que en cálculo, cuando se maximiza una función

ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta garantía

está dada cuando

d^2f/ dx^2f≤0 para toda x.

Una función de este tipo cuya curvatura siempre es “hacia abajo” (o que no tiene curvatura)

se llama función cóncava.De igual manera, si se sustituye ≤ por ≥, de manera que la función

tiene siempre una curvatura “hacia arriba” (o no tiene curvatura), se llama función convexa.

(Así, una función lineal es tanto cóncava como convexa.)

Las funciones de variables múltiples también se pueden caracterizar como cóncavas o

convexas si su curvatura es siempre hacia abajo o hacia arriba. Estas definiciones intuitivas se

fundamentan en términos precisos que, junto con cierta profundización en los conceptos,

se presentan en el apéndice 2. El apéndice 2 proporciona una prueba conveniente para verificar

si una función de dos variables es cóncava, convexa o ninguna de las dos.

Las funciones de variables múltiples también se pueden caracterizar como cóncavas o

convexas si su curvatura es siempre hacia abajo o hacia arriba. Estas definiciones intuitivas se

fundamentan en términos precisos que, junto con cierta profundización en los conceptos,

se presentan en el apéndice 2. El apéndice 2 proporciona una prueba conveniente para verificar

si una función de dos variables es cóncava, convexa o ninguna de las dos.

Conceptos básicos de problemas de programación no lineal

abril 16, 2010

Una suposición

importante de programación lineal es que todas sus funciones (función objetivo y funciones

de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para

muchos problemas prácticos, con frecuencia no es así. De hecho, muchos economistas han

encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas

de planeación económica,1 por lo cual, muchas veces es necesario manejar problemas de programación

no linealDe una manera general, el problema de programación no lineal consiste en encontrar

x=(*!,*2 , . . . , * „ ) para

Maximizar f(x),

sujeta a

gi(x)≤ bi, paraí= 1, 2,…, m,

y

x ≥0

donde f( x ) y las g¡ (x) son funciones dadas de n variables de decisión.

No se dispone de un algoritmo que resuelva todos los problemas específicos que se ajustan

a este formato. Sin embargo, se han hecho grandes logros en lo que se refiere a algunos casos

especiales importantes de este problema, haciendo algunas suposiciones sobre las funciones,

y la investigación sigue muy activa. Esta área es amplia y aquí no se cuenta con el espacio suficiente

para un estudio completo. Se presentarán algunos ejemplos de aplicación y después se

introducirán algunas ideas básicas para resolver ciertos tipos importantes de problemas de

programación no lineal.