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 simplex
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 (tipos especiales) de problemas de
programación no lineal. Se introducirán las clases más importantes y después
se describirá cómo se pueden resolver algunos de estos problemas.
Si la función
objetivo f es lineal y el espacio restringido es un poli topo, el
problema es de Programación lineal y puede resolverse utilizando alguno de los
bien conocidos algoritmos de programación lineal.
Si la función objetivo es cóncava
(problema de maximización), o convexa (problema de minimización) y el conjunto
de restricciones es convexo, entonces se puede utilizar el método general de
Optimización convexa
Existe una variedad de métodos para
resolver problemas no convexos. Uno de ellos consiste en utilizar formulaciones
especiales de problemas de programación lineal. Otro método implica el uso de
técnicas de Ramificación y poda, cuando el problema se divide en subdivisiones
a resolver mediante aproximaciones que forman un límite inferior del coste
total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una
solución cuyo coste es igual o inferior que el mejor límite inferior obtenido
por alguna de las soluciones aproximadas. Esta solución es óptima, aunque
posiblemente no sea única. El algoritmo puede ser parado antes, con la garantía
de que la mejor solución será mejor que la solución encontrada en un porcentaje
acotado. Ello se utiliza en concreto en problemas importantes y especialmente
difíciles y cuando el problema cuenta con costes inciertos o valores donde la
incertidumbre puede ser estimada en un grado de fiabilidad
apropiado.
Las condiciones de Karush-Kuhn-Tucker
proporcionan las condiciones necesarias para que una solución sea
óptima.
Los
tipos de problemas de programación no lineal son:
-
Optimización no restringida.
-
Optimización linealmente restringida.
-
Programación cuadrática
-
Programación convexa.
-
Programación separable.
-
Programación no convexa.
-
Programación geométrica.
-
Programación fraccional.
-
Problema de complementariedad.
Algoritmos
sin restricción
En esta sección se presentarán dos
algoritmos para el problema no restringido: el algoritmo de búsqueda
directa y el algoritmo de gradiente.
Método
de búsqueda directa
Los métodos de búsqueda directa se
aplican principalmente a funciones estrictamente unimodales de una variable.
Aunque puede parecer trivial el caso, la cual muestra que la optimización de
funciones de una variable juega un papel clave en el desarrollo de los algoritmos
de varias variables, más generales.
La idea de los métodos de búsqueda
directa es identificar el intervalo de incertidumbre que comprenda
al punto de solución óptima. El procedimiento localiza el óptimo estrechando
en forma progresiva el intervalo de incertidumbre hasta cualquier grado de
exactitud que se desee.
En
esta sección se presentan dos algoritmos estrechamente
relacionados: los métodos de búsqueda dicótomo y de sección dorada (o
áurea). Ambos buscan la maximización de una función unimodal/(x) en el
intervalo a ^ x < b, que se sabe que incluye el punto
óptimo x*. Los dos métodos comienzan con /0 = (a,
b) que representa el intervalo inicial de incertidumbre.
Paso general i. Sea /, _,
= (xD xR) el intervalo actual de incertidumbre (en la iteración
0, xL = a y xR = b). A continuación se
definen xx y x2 tales que
xj^ ^ ^ x2 ^ xr
El siguiente intervalo de
incertidumbre, /z, se define como sigue:
Si f (xx) > /(x2),
entonces xL < x* < x2. Se definen xR = x2 e
/, = (xL, x2).
Si f (xx) < f (x2\ entonces xx <
x* < xR. Se definen xL = xx e I¡= (xh xR).
Si f {x\) = / (jc2),
entonces xx < x* < x2. Se definen xL = x2 e
/, = (xb x2).
La manera en que se
determinan xx y x2 garantiza que /, < /, _ p como
se demostrará en breve. El algoritmo termina en la
iteración ksilk< A, donde A es un grado de
exactitud definido por el usuario
La diferencia entre los métodos
dicótomos y de sección dorada estriba en la forma en que se
calculan xx y x2. La tabla siguiente presenta las
fórmulas.
En el método dicótomo los
valores jc, y x2 se encuentran simétricos
respecto del punto medio del actual intervalo de incertidumbre. Esto significa
que
La aplicación repetida
del algoritmo garantiza que la longitud del intervalo de incertidumbre se
acercará al nivel de exactitud deseado, A.
En el método de la
sección dorada la idea es de mayor involucramiento. Se puede apreciar que cada
iteración del método dicótomo requiere calcular los dos valores/(jc,) y f(x2), Pe” ro termina por
descartar alguno de ellos. Lo que propone el método de la sección dorada es
ahorrar cálculos mediante el reúso del valor descartado en la iteración
inmediata siguiente. Para definir 0 < a < 1
Cuando el intervalo de
incertidumbre /, en la iteración i es igual a (jc, x2) o a (xu xR). Considere el caso en que /, =
(jcl, x2), lo cual significa que xx está incluido en /,. En la
iteración /+1, seleccione x2 igual a jc, de la iteración /,
lo cual lleva a la siguiente ecuación:
x2(iteración i+l) = x{(iteración i)
Comparado con el método dicótomo,
el método de la sección dorada converge más rápidamente hacia el nivel deseado
de exactitud. Adicionalmente, cada iteración en el método de la sección dorada
requiere la mitad de los cálculos, en virtud de que recicla siempre un conjunto
de los cálculos correspondientes a la iteración inmediata anterior.
Ejemplo
El máximo valor de f(x) ocurre
en x = 2. La siguiente tabla muestra los cálculos para las
iteraciones 1 y 2, usando el método dicótomo y el de la sección dorada.
Supondremos que A = 0.1.
Al continuar de la misma forma, el
intervalo de incertidumbre terminará por estrecharse hasta la
tolerancia A deseada.
La plantilla
ch21DichotomousGoldenSection.xls de Excel está diseñada para manejar cualquiera
de estos dos métodos en forma automática. Los datos son / (*), a,b y
A. La función f {x) se captura en la celda E3 como sigue:
= IF (C3< = 2,3*C3,
(-C3+20)/3)
Optimización no restringida
Los problemas de optimización no
restringida no tienen restricciones, por lo que la función objetivo
es sencillamente
Maximizar f(x)
Sobre todos los valores x= (x1, 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 f(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. ¿Qué se puede hacer en ese caso?
Las secciones 13.4 y 13.5 describen procedimientos algorítmicos de
búsqueda para encontrar x* primero para n = 1 y luego
para n > 1. Estos procedimientos también tienen un papel
importante en la solución de varios tipos de problemas con restricciones, que
se describirán en seguida. La razón es que muchos algoritmos para
problemas restringidos están construidos de forma que se adaptan a
versiones no restringidas del problema en una parte de cada
iteración.
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. Esta condición se ilustra
en la figura, donde la solución óptima de un problema con una sola variable
es x = 0 aun cuando la derivada ahí es negativa y no cero. Como este
ejemplo tiene una función cóncava para maximizar sujeta a una restricción de no
negatividad, el que su derivada sea menor o igual a 0 en # = 0, es una
condición necesaria y suficiente para que x= 0 sea óptima.
Un problema que tiene algunas
restricciones de no negatividad y que no tiene restricciones funcionales es un
caso especial (m = 0) de la siguiente clase de problemas.
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 simplex 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. f(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
Todas las funciones f(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 f(x) es una función separable, se puede
expresar como
Son cada una funciones de una sola
variable x1 y x2, respectivamente. Usando el mismo razonamiento, se puede
verificar que la función considerada en la figura también es una función separable.
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
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.
Ciertos tipos específicos de
problemas de programación no convexa se pueden resolver sin mucha dificultad
mediante métodos especiales. Dos de ellos, de gran importancia, se presentarán
más adelante.
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 de programación geomé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
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 de programación
posinomial, al igual que para problemas de programación geométrica de
otros tipos.
Programación
fraccional
Suponga que la función objetivo se
encuentra en la forma de una fracción, esto es, la razón o cociente
de dos funciones,
Estos problemas de programación
fraccional surgen, por ejemplo, cuando se maximiza la razón de la
producción entre las horas-hombre empleadas (productividad), o la ganancia
entre el capital invertido (tasa de rendimiento), o el valor esperado dividido
entre la desviación estándar de alguna medida de desempeño para una cartera de
inversiones (rendimiento/riesgo). Se han formulado algunos procedimientos de
solución especiales1 para ciertas formas de f1(x) y f2 (x)
Cuando se puede hacer, el
enfoque más directo para resolver un problema de programación fraccional es
transformarlo en un problema equivalente de algún tipo estándar que disponga
de un procedimiento eficiente. Para ilustrar esto, suponga
que f(x) es de la forma de programación fraccional lineal
Donde c y d son
vectores renglón, x es un vector columna
y c0 y dQ son escalares. También suponga que las funciones
de restricción g ¡(x) son lineales, es decir, las restricciones en
forma matricial son Ax < b y x > 0.
Con algunas suposiciones débiles
adicionales, el problema se puede transformar en un problema equivalente
de programación lineal si se establece
Que se puede resolver con el método
simplex. En términos generales, se puede usar el mismo tipo de transformación
para convertir un problema de programación fraccional con / ¡(x) cóncava, f2 (x) convexa
y g¡ (x) convexas, en un problema equivalente de programación
convexa.
Conclusión
de los métodos de programación no lineal
La programación lineal es una técnica
poderosa para tratar problemas de asignación de recursos escasos entre
actividades que compiten, al igual que otros problemas cuya formulación
matemática es parecida. Se ha convertido en una herramienta estándar de gran
importancia para muchas organizaciones industriales y de negocios. Aún
más, casi cualquier organización social tiene el problema de asignar recursos
en algún contexto y cada vez mayor el reconocimiento de la aplicabilidad tan
amplia de esta técnica.
Sin embargo, no todos los problemas de
asignación de recursos limitados se pueden formular de manera que se ajusten a
un modelo de programación lineal, ni siquiera como una aproximación razonable.
Cuando no se cumplen una o más de las suposiciones de programación lineal, tal
vez sea posible aplicar otro tipo de modelos matemáticos, por ejemplo, los
modelos de programación entera o de programación no lineal.
La mayoría de los métodos de programación no lineales
utilizan el concepto de gradiente de las funciones f (x) y g (x) para calcular
direcciones de descenso es decir de mejora de la función objetivo. Cuando las
funciones son convexas (caso por ejemplo de la programación lineal continua),
Los algoritmos de descensos convergen hacia un óptimo global.
En general estos algoritmos y el software
correspondientes convergen solamente hacia un óptimo local. Siempre que sea
posible, Es importante ejecutar estos algoritmos a partir de varias soluciones
iniciales diferentes con el fin de seleccionar la mejor solución entre todas
las mencionadas.
No hay comentarios:
Publicar un comentario