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 la condición necesaria para que una solución específica X=X* sea óptima cuando f(X) es una función diferenciable es:
∂f = 0 en X=X*, para j=1,2,…, n.
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 este caso?
Cuando una variable Xj tiene una restricción de no negatividad, xj=>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 siguiente, donde la solución óptima de un problema con una 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 a 0 en X=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 gi(X) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho si solo se tiene que tomar en cuenta una función no lineal junto con una región factible de programación lineal.
Programación cuadrática
De nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la función objetivo f(x) debe ser cuadrática. Entonces, la única diferencia entre estos 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.
Se han desarrollado muchos algoritmos para este caso, con la suposición adicional de que f(X) es cóncava. La programación cuadrática es muy importante, en parte porque las formulaciones de este tipo surgen de manera natural en muchas aplicaciones. Sin embargo, otra razón por la que es importante es que al resolver problemas generales de optimización linealmente restringida se puede obtener la solución de una sucesión de aproximaciones de programación cuadrática.
Programación convexa
La programación convexa abarca una amplia clase de problemas, entre ellos como casos especiales, están los tipos anteriores cuando f(x) es cóncava. Las suposiciones son:
1. F(X) es cóncava.
2. Cada una de las gi(X) es convexa.
Programación separable
La programación separable es un caso especial de programación convexa, en donde las suposiciones adicionales es:
3.- Todas las funciones f(X) y gj(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:
F(X)= Σ fj (Xj)
En donde cada fj(Xj) incluye solo los términos con Xj. en la terminología de programación lineal, los problemas de programación separable satisfacen las suposiciones de auditividad pero no las de proporcionalidad (para funciones no lineales). Para ilustrar, la función objetivo considerada en la siguiente figura:
F(X1, X2)=126X1 – 9x21 + 182X2 – 13X22
Es una función separable porque puede ser expresada como:
F(X1, X2)= F(X1) + F(X2)
Donde F1(X1)= 126X1 – 9x21 y F(X2)= 182X2 – 13X22 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 siguiente, 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.
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 si existen algunos algoritmos bastantes 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:
No hay comentarios:
Publicar un comentario