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
se ajustan por completo a la programación lineal, de manera que todas las funciones de restricción
g¡ (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.
No hay comentarios.:
Publicar un comentario