Tipos de problemas de programación no lineal.

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,…,

About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: