OpenSolver es una excelente complemento de Excel que permite resolver modelos de optimización. En el siguiente artículo se describe cómo resolver un modelo de Programación Lineal con esta herramienta (previa descarga e instalación de OpenSolver en Excel 2010). Para fines académicos consideraremos un modelo lineal con 2 variables de decisión, no obstante se puede extender su aplicación a problemas de mayor tamaño sin inconvenientes.
A continuación necesitamos preparar una planilla Excel que considere los parámetros y variables del modelo (este paso es similar a la carga de un modelo en Solver de Frontline). Se puede apreciar que las celdas B2 y C2 (color amarillo) han sido asignadas a las variables de decisión y la función objetivo (celda azul) corresponde a la celda E2 que es una fórmula que vincula las variables de decisión y los respectivos parámetros que ponderan a éstas. Finalmente las celdas D5 y D6 son fórmulas que representan el “lado izquierdo” de las restricciones del problema (por ejemplo la celda D5 corresponde a B2*B5+C2*C5 o equivalentemente SUMAPRODUCTO(B2:C2;B5:C5)).
Una vez completado el paso anterior se debe ejecutar OpenSolver cuyo menú esta disponible en la pestaña de “Datos” de Excel. Luego se selecciona “Model…” según se muestra a continuación:
La interfaz para implementar el modelo es bastante similar a la versión tradicional de Solver (Frontline). Se define la celda objetivo (E2) en maximización; a continuación se selecciona el rango de variables de decisión (según se muestra en la siguiente imagen) y las restricciones. Si intentas replicar la estructura del ejemplo que desarrollamos en este artículo se debería ver así:
Luego seleccionamos “Save Model” (cambiará la estructura de la planilla la cual adoptará colores lo cual es una de las características de OpenSolver que hacen de este complemento una herramienta intuitiva para el usuario).
Finalmente seleccionamos “Solve”:
El programa se ejecutará y proporcionará (de existir) la solución óptima (X=0 e Y=60) y valor óptimo (V(P)=1.200) del problema de optimización:
A continuación puedes descargar el archivo con la resolución en OpenSolver de este problema de modo de que puedas familiarizarte con este complemento de Excel: Modelo de Programación Lineal resuelto con OpenSolver
Un supuesto básico asociado a la Programación Lineal es que los parámetros o constantes son valores conocidos con exactitud al momento de resolver el modelo de optimización. Este supuesto de asumir que no existe incertidumbre claramente implica una simplificación en el modelamiento de problemas de naturaleza real y es conocido como el supuesto de modelo determinista.
La optimización también permite incorporar explícitamente la incertidumbre en los parámetros en el modelamiento, asumiendo que la totalidad o un conjunto de éstos se distribuyen aleatoriamente, lo cual se puede representar a través de una función de probabilidad conocida o una distribución empírica que modela distintos escenarios para los parámetros, asociando una probabilidad de ocurrencia en cada caso. Esta categoría de modelos de optimización (por cierto más complejos en comparación al caso determinista) se llaman modelos estocásticos, los cuales en rara oportunidad se analizan en cursos introductorios de Investigación de Operaciones, de modo que forman parte del programa de estudios en cursos de Magíster y Doctorado asociado al área de optimización matemática.
En relación a lo anterior, si bien un modelo determinista considera valores fijos para los parámetros, aún podemos analizar los cambios en los resultados del modelo (solución óptima y valor óptimo principalmente) en comparación a lo obtenido en una instancia de resolución original o escenario base. Esto se conoce como análisis de sensibilidad o análisis postoptimal.
Recordemos que la estructura de la tabla final del Método Simplex se puede representar de la siguiente forma:
Donde:
I: Matriz Identidad (Diagonal de “1”)
0: Vector de costos reducidos asociados a las variables básicas
B: Matriz de variables básicas
D: Matriz de variables no básicas
b: Vector de “lado derecho”
Cb: Coeficientes en la función objetivo asociados a las variables básicas
Cd: Coeficientes en la función objetivo asociados a las variables no básicas
A continuación presentamos los Análisis de Sensibilidad más recurrentes asociados a los modelos de Programación Lineal y utilizando como fuente de información la tabla final del Método Simplex. El siguiente es un listado de los artículos que hemos desarrollado para cada uno de estos temas los cuales te recomendamos visitar:
En el contexto de las relaciones de dualidad en Programación Lineal, los teoremas de dualidad fuerte y dualidad débil constituyen importantes resultados teóricos que contribuye a la comprensión y resolución de modelos de optimización lineales. En el siguiente artículo ilustraremos su utilización haciendo uso de un ejemplo sencillo para fines académicos que por supuesto puede ser extendido a problemas de mayor tamaño.
Consideremos los siguientes problemas Primal (P) y Dual (D) en su formato matricial:
Lo anterior no constituye una pérdida de generalidad dado que el problema primal puede ser de maximización o de minimización con la consecuente incidencia en la interpretación de los resultados.
Teorema de Dualidad Débil
El Teorema de Dualidad Débil establece que si x є IRn, es una solución factible del problema Primal P) y ∏ є IRm, una solución factible del problema Dual D), entonces:
Es decir, en el formato descrito anteriormente, el valor que reporta una solución factible del problema dual de minimización al ser evaluada en su respectiva función objetivo, representa una cota superior del valor óptimo del problema primal de maximización.
Análogamente, una solución factible del problema primal de maximización al ser evaluada en dicha función objetivo representa una cota inferior del valor óptimo del problema dual de minimización. En conclusión: V(P)<=V(D).
En general si el problema primal tiene un dominio de soluciones factibles no acotado sin solución óptima (es decir, es un problema no acotado) el respectivo problema dual resultará ser infactible (y viceversa).
Para corroborar el Teorema de Dualidad Débil consideraremos un problema primal y su respectivo dual: (si tienes dudas respecto a las relaciones de dualidad te recomendamos leer previamente el artículo Cómo pasar de Primal a Dual y viceversa).
Una representación gráfica realizada con Geogebra del problema primal permite apreciar que el dominio de factibilidad es no acotado y su solución óptima se encuentra en el vértice C donde X1=2/5 y X2=6/5 con valor óptimo V(P)=16/5.
Notar adicionalmente que cualquier par ordenado que pertenece al área achurada es factible, por ejemplo X1=2 y X2=2 es una Solución Básica Factible para el problema primal con V(P)=8 (cota superior del valor óptimo del problema dual de maximización).
En cuanto al problema dual su dominio de factibilidad es acotado y su solución óptima se encuentra en el vértice C con Y1=2/5 e Y2=2/5 y valor óptimo V(D)=16/5. Adicionalmente existen otros puntos factibles como el origen (Y1=0 e Y2=0) con V(D)=0 lo cual permite corroborar que cualquier solución factible del problema dual al ser evaluada en la función objetivo (de minimización) genera una cota inferior del valor óptimo del problema primal de minimización.
Teorema de Dualidad Fuerte
Si un problema (Primal) de Programación Lineal tiene una solución óptima, entonces el correspondiente problema Dual también tiene una solución óptima, y los respectivos valores en la función objetivo son idénticos.
En consecuencia, del Teorema de Dualidad Fuerte se deduce que ambos problemas (primal y dual) al ser evaluados en sus respectivas soluciones óptimas (en caso de existir) proveen idéntico valor óptimo, es decir, V(P)=V(D). Es más, resulta suficiente resolver uno de ellos y luego utilizar las propiedades del Teorema de Holguras Complementarias para encontrar la solución óptima (y valor óptimo) de su problema equivalente. En nuestro ejemplo V(P)=16/5=V(D).
En la Gestión de Proyectos uno de los aspectos claves es determinar los costos asociados a terminar el proyecto en un tiempo determinado. Del mismo modo, resulta de particular interés poder enfrentar de forma eficiente el problema de cómo reducir la duración del mismo de la forma más económica posible, partiendo de la premisa que ciertas actividades eventualmente se podrían desarrollar en un tiempo menor al estimado inicialmente luego de asignar una mayor cantidad de recursos. En este contexto el siguiente artículo aborda la problemática anterior a través de la formulación y resolución computacional de un modelo de optimización lineal.
Consideremos el siguiente proyecto que consta de 12 tareas estrictamente necesarias, donde la relación de predecesores, tiempos (en semanas) y costos se resume en la tabla a continuación:
Por ejemplo la actividad I tiene puede comenzar una vez completadas las actividades F y H y su tiempo estimado es de 1,5 semanas con un costo normal de $75. Sin embargo la actividad I se puede apurar (lo que comúnmente se conoce como “crash” o “crashing”) de modo que su duración pueda ser de 0,5 semanas pero con un costo mayor de $135. En consecuencia la máxima reducción permisible para dicha tarea es de 1 semana (1,5 – 0,5 semanas) con un costo adicional de $60. Asumiremos adicionalmente que existe proporcionalidad entre el tiempo de reducción y el costo adicional, por ejemplo, si quisiéramos reducir la actividad I en 0,5 semanas (es decir, pasar de 1,5 a 1,0 semanas) el costo de la actividad sería $105 ($75+0,5*$60) y el costo adicional (sobre el costo normal) es de $30.
A continuación determinamos la duración del proyecto utilizando el Método de Ruta Crítica (CPM), considerando los tiempos normales estimados para cada actividad.
El proyecto tiene una duración estimada de 15,5 semanas y existe una única ruta crítica: A-B-D-G-H-I-K-L (notar que todas las actividades en esta ruta tienen holgura igual a cero). El costo del proyecto es de $2.620 y se obtiene simplemente sumando los costos normales de cada una de las actividades. La notación que hemos utilizado es:
Donde IC: Inicio más Cercano; TC: Término más Cercano; IL: Inicio más Lejano; TL: Término más Lejano; TN: Tiempo Normal, HOLG: Holgura. De esta forma, por ejemplo, la actividad I tiene un tiempo normal de 1,5 semanas y holgura igual a cero, es decir, si se retrasa esta actividad el proyecto también se retrasará.
En este contexto, el siguiente modelo de Programación Lineal permite abordar de forma óptima el problema de cómo reducir la duración del proyecto de la forma más económica posible, mediante la reducción del tiempo de las actividades (en particular de las actividades pertenecientes a la(s) ruta(s) crítica(s)). Cabe destacar que en la actualidad existen softwares que facilita este tipo de procedimientos (Crashing) como por ejemplo WINQSB.
Variables de Decisión:
Parámetros:
Función Objetivo: Se buscar minimizar el costo adicional asociado al proyecto luego de hacer el “crashing” necesario para completar el proyecto en un tiempo determinado. Notar que podríamos agregar en la función objetivo como constante el costo normal del proyecto ($2.620) en donde en dicho caso la interpretación del valor óptimo sería el costo total del proyecto que tiene duración de K semanas.
Restricciones:
Cada actividad se puede reducir (de ser posible) dentro del límite máximo de reducción permisible:
Relaciones de predecesores entre las actividades y el tiempo de inicio y reducción:
Por ejemplo en conjunto las inecuaciones (3) y (4) representan que la semana de inicio para la actividad D será mayor o igual a la semana de término (luego de una eventual reducción) de la que termine más tarde entre sus actividades predecesoras (B y C). Adicionalmente hemos definido una actividad “ficticia” o de término llamada “M” la cual tiene como predecesoras a aquellas actividades que terminan una ruta para el proyecto (no necesariamente crítica) y nos permitirá estimar la duración del proyecto.
Definición del tiempo objetivo para el proyecto:
En la resolución computacional con Solver de Excel se puede simular para distintos valores del parámetro K de modo de ver cómo cambian los resultados. La mínima duración del proyecto estará dada por el menor valor de K que permite generar una instancia factible para el modelo de optimización.
No negatividad de las variables de decisión:
Los resultados se muestran en la tabla a continuación donde la mínima duración del proyecto corresponde a 8,5 semanas con un costo total de $3.295 ($675 adicional al costo normal del proyecto). En las celdas color amarillo (variables de decisión) se puede apreciar la solución óptima donde queda explícito cuándo comienza la actividad y cuánto se reduce respecto a su tiempo normal. Por ejemplo la actividad G comienza al cabo de 2,5 semanas (a contar del inicio del proyecto) y su duración normal se reduce en 1,5 semanas (es decir pasamos de un tiempo normal de 3 a 1,5 semanas).
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?
Una de las aplicaciones clásicas de los modelos de Programación Lineal son los problemas de mezcla de productos. Si la calidad de un producto que se procesa mediante la mezcla de determinados insumos se puede aproximar de forma razonable a través de una proporción, entonces un modelo de optimización lineal puede resultar de utilidad. El ejemplo a continuación muestra dicha situación para el caso de una refinería:
Problema de Mezcla de Productos en Programación Lineal
Una refinería de petróleos produce dos tipos de gasolina sin plomo: regular y extra, las cuales vende a los distribuidores en US$12 y US$14 por barril, respectivamente. Ambos tipos se preparan a partir del inventario de petróleo nacional refinado y de petróleo importado refinado que tiene la empresa (es decir mediante mezcla), las que deben cumplir las especificaciones que se presentan en la siguiente tabla:
Las características del inventario de petróleos refinados son las siguientes:
Se requiere formular y resolver un modelo de Programación Lineal que permita maximizar el ingreso semanal de la refinería, satisfaciendo los requerimientos previamente detallados.
Variables de Decisión:
Xnr: Barriles de petróleo nacional utilizados en la producción de gasolina regular
Xne: Barriles de petróleo nacional utilizados en la producción de gasolina extra
Xir: Barriles de petróleo importado utilizados en la producción de gasolina regular
Xie: Barriles de petróleo importado utilizados en la producción de gasolina extra
Función Objetivo: Se busca maximizar los ingresos semanales que percibe la refinería en la producción de gasolina regular y extra.
Max 12*(Xnr + Xir) + 14*(Xne + Xie)
Restricciones:
Presión de Vapor: El promedio ponderado de la presión de vapor de los distintos tipos de petróleos que participan de la mezcla no debe superar las 23 unidades (para cada tipo de gasolina).
(25Xnr + 15Xir ) / (Xnr + Xir) <= 23
(25Xne + 15Xie ) / (Xne + Xie) <= 23
Octanaje Mínimo: El promedio ponderado del octanaje de los distintos tipos de petróleos que participan de la mezcla debe ser al menos 88 y 93 unidades para la gasolina regular y extra, respectivamente.
(87Xnr + 98Xir ) / (Xnr + Xir) >= 88
(87Xne + 98Xie ) / (Xne + Xie) >= 93
Demanda Mínima y Máxima: Para cada gasolina se debe producir semanalmente una cantidad de barriles entre el mínimo y el máximo permitido.
50.000 <= Xnr + Xir <= 100.000
5.000 <= Xne + Xie <= 20.000
Inventario: Para la producción de gasolina regular y extra se debe respetar la disponibilidad de barriles de petróleo nacional e importado.
Xnr + Xne <= 40.000
Xir + Xie <= 60.000
No Negatividad: Las variables de decisión naturalmente deben adoptar valores mayores o iguales a cero.
Xnr, Xne, Xir, Xie >= 0
Al implementar el modelo de optimización anterior en Solver se alcanza la siguiente solución óptima y valor óptimo:
Se deben destinar 30.909,09 barriles de petróleo nacional para la producción de gasolina regular, 9.090,91 barriles de petróleo nacional para la producción de gasolina extra, 49.090,91 barriles de petróleo importado para la producción de gasolina regular y 10.909,09 barriles de petróleo importado para la producción de gasolina extra. La política de producción anterior permite generar un ingreso semanal de US$1.240.000.
Una recomendación en la carga computacional es rescribir las restricciones que incluyan proporciones de forma equivalente, de modo de evitar divisiones entre celdas cambiantes (variables de decisión) y adicionalmente denominadores que adopten inicialmente un valor igual a cero. Por ejemplo la restricción: (25Xnr + 15Xir ) / (Xnr + Xir) <= 23 se puede representar de forma análoga de la siguiente forma: (25Xnr + 15Xir ) -23 (Xnr + Xir) <= 0. De esta forma se puede corrobar, por ejemplo, que en la solución óptima la presión de vapor que alcanza la producción de barriles de gasolina regular es de: (25*30.909,09 + 15*49.090,91 ) / (30.909,09 + 49.090,91)=18,8636 (aprox) que es menor o igual al límite de 23 unidades.
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.
