La programación no lineal forma parte de la investigación de operaciones y también, como la programación lineal, tiene como finalidad proporcionar los elementos para encontrar los puntos óptimos para una función objetivo. En este planteamiento, tanto la función objetivo como las restricciones son no lineales.
Ejemplos de Programación No Lineal
Existen múltiples aplicaciones típicas para modelos no lineales. A continuación se resumen algunas:
Localización de Instalaciones: Considere que una empresa distribuidora de productos farmacéuticos requiere determinar la localización de una bodega que funcionará como centro de distribución y abastecimiento para sus locales en el país. En especial se busca estar a la menor distancia de los 3 principales locales de venta al público denominados A, B y C, respectivamente. Las coordenadas geográficas de dichos locales se presentan en el siguiente gráfico:
Formule y resuelva un modelo de optimización que permita determinar la localización óptima de la bodega y que minimize la distancia a los distintos locales de la empresa. Asuma que la bodega puede ser ubicada en cualquier coordenada o punto del mapa.
Respuesta: Si consideramos como variables de decisión X e Y que correspondan a las respectivas coordenadas de la bodega a instalar, se puede definir el siguiente modelo de optimización no lineal sin restricciones, donde la siguiente función objetivo de minimización de distancia (Min f(x,y)).
Generalidades De La programacion No Lineal
Generalidades De La programacion No Lineal
Muchas aplicaciones industriales de optimización
implican una modelización que se aproxima más a la física. En optimización del
diseño por ejemplo, se optimizan meta-modelos o espacios de respuesta que
provienen de un modelo estadístico, que no son lineales. Así mismo, la
optimización topológica o la optimización de forma recurren a modelos no
lineales y además de tamaño muy grande, como en este ejemplo.
Formalmente, un programa matemático no lineal se enuncia:
Min f(x)
gj(x) <=0 j = 1,…,m
x vector de números reales que representan las variables de decisión
Las técnicas para resolver los problemas
matemáticos y los resultados de los algoritmos de optimización dependen de la
naturaleza de la función objetivo y de las restricciones.
- La programacion lineal trata los casos en los que f(x) y gj(x) son lineales. El algoritmo del Simplex o los métodos del punto interior permiten resolver problemas de gran tamaño (algunos con miles o millones de variables y decenas de miles de restricciones).
- La programación cuadrática trata el problema en el que la función objetivo f(x) es cuadrática, y las restricciones gj(x) son lineales. Existen algoritmos eficaces para tratar este caso particular, por ejemplo en las problemáticas de optimización de carteras financieras.
- La programación estocástica y la optimización robusta tratan situaciones en las que algunos parámetros son variables aleatorias o imprecisas (marco de la optimización robusta).
- La programación dinámica es un método útil para los casos en los que una solución óptima se divide en sub-soluciones optimales (propiedad utilizada por ejemplo para buscar los caminos más cortos en los gráficos) y de caminos más cortos con restricciones (algoritmos utilizados en los métodos de generación de columnas para resolver sub-problemas asociados en componentes como LP-ShiftPlanner).
- La programación no lineal analiza la problemática general en la que el objetivo f(x) o las restricciones gj(x) (o los dos) son funciones no lineales.
- optimizacion no restringida
- optimizacion linealmente restringida
- programacion cuadratica
- programacion convexa
- programacion separable
- programacion no convexa
- programacion geometrica
- programacion fraccional
- problema de complementariedad.
Diferencias entre la Programación No Lineal y la Programación Lineal
El supuesto de la proporcionalidad de la
programación lineal no siempre es adecuado para representar de buena forma
situaciones de naturaleza real que requieren de un modelo de optimización como
apoyo para el proceso de toma de decisiones. Cabe señalar que un modelo de programación
no lineal es aquel donde la función objetivo y/o las restricciones son
funciones no lineales de las variables de decisión.
En este sentido la programación no lineal permite
enfrentar una serie de aplicaciones prácticas que requieren una representación
a través de funciones no lineales. Algunos casos característicos de la
programación no lineal son los problemas de minimización de distancia,
economías o deseconomías de escala, carteras de inversión, ajuste de curva,
entre otros.
En general cuando formulamos un modelo de
optimización no lineal esperamos que éste sea más representativo de una
situación real en comparación a un modelo lineal, sin embargo, a la vez
asumimos que es probable que la complejidad de la resolución aumente. Por ello
quien formule un modelo debe equilibrar la representatividad del mismo con la
dificultad de la resolución
A continuación
presentaremos dos modelos de optimización que comparten las mismas
restricciones (que asumiremos por simplicidad que son funciones lineales) y se
diferencian por la naturaleza de la función objetivo (lineal y no lineal,
respectivamente). Estos ejemplos nos ayudarán a explicar algunas diferencias
entre la programación lineal y programación no lineal:
Si
resolvemos gráficamente el modelo de programación lineal obtenemos la solución
óptima en el vértice C (X=14/5 Y=8/5 y valor óptimo V(P)=20,8).
En efecto, una de las propiedades básicas de la programación lineal es que
cuando un modelo admite solución, ésta se encontrará en un vértice (o tramo
frontera) del dominio de soluciones factibles.
En
cuanto a la resolución del modelo de programación no lineal, la función
objetivo no lineal tiene la forma de circunsferencias concéntricas desde la
coordenada (X,Y)=(2,4). Como la función objetivo es de minimización, buscamos
la circunsferencia de menor radio que intersecte por primera vez el dominio de
soluciones factibles. Esto se alcanza en (X,Y)=(1,2,2,4).
Conclusión: Si un modelo de
programación no lineal admite solución óptima, ésta se puede encontrar en
cualquier punto del dominio de soluciones factibles.
Por ejemplo, si nuestra función objetivo
estuviese centrada en (X,Y)=(2,1) ésta ya sería la solución óptima del
problema. Notar que esta situación (solución en un punto interno del dominio
factible) no sería posible en la resolución de un modelo de programación
lineal.
En próximos artículos en la categoría de
programación no lineal analizaremos algunos algoritmos especializados para la
resolución de modelos no lineales como también herramientas computacionales
para enfrentar este tipo de problemas.
