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.
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
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 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 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 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.
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 .
No hay comentarios:
Publicar un comentario