Las características de Solver han evolucionado en las distintas versiones de Office y en esta oportunidad mostraremos cómo activar este complemento en la versión del año 2003 y 2007. Para ello se deben seguir los siguientes pasos:
Paso 1: Abrir el programa Excel y en el menú de Herramientas seleccionar Complementos.
Paso 2: Seleccionar la opción Solver y luego Aceptar.
Paso 3: Puede ser necesario aprobar la ejecución del complemento como muestra la imagen a continuación. En este caso se debe seleccionar Sí
Paso 4: Una vez completada la activación de Solver el complemento estará disponible en el menú de Herramientas de Excel.
Una alternativa a Solver es el complemento de Excel OpenSolver el cual se puede descargar gratuitamente desde www.opensolver.org. En el artículo Cómo resolver un modelo de Programación Lineal con OpenSolver mostramos su utilización en un problema sencillo. Adicionalmente What’sBest! resulta ser otra excelente alternativa para Solver y desarrollado para Excel. En el siguiente tutorial detallamos cómo descargar e instalar What’sBest!.
Uno de los teoremas principales en la Teoría de Dualidad en Programación Lineal es el Teorema de Holguras Complementarias.
El Teorema de Holguras Complementarias nos permite encontrar la solución óptima del Problema Dual cuando conocemos la solución óptima del Problema Primal (y viceversa) a través de la resolución de un sistema de ecuaciones conformado por las variables de decisión (primales y duales) y las restricciones (del modelo primal y dual).
La importancia de este teorema radica en que facilita la resolución de los modelos de optimización lineal, permitiendo a quién los resuelve buscar el modelo más sencillo para abordar (desde el punto de vista algorítmico) dado que de cualquier forma podrá obtener los resultados del modelo equivalente asociado (sea éste el modelo primal o dual).
Ejemplo Teorema de Holguras Complementarias
Consideremos el siguiente modelo de Programación Lineal (en adelante Primal) en 2 variables cuya solución óptima obtenida por el Método Gráfico es X=14/5 e Y=8/5 con valor óptimo V(P)=20,8.
Luego, el Teorema de Holguras Complementarias plantea las siguientes relaciones:
Como sabemos X=14/5 e Y=8/5 (Solución Básica Factible Óptima del modelo primal). Si reemplazamos estos valores de X e Y en la tercera y cuarta ecuación generamos un sistema de ecuaciones de 2×2 en términos de A y B cuya solución corresponde a A=6/5 y B=2/5 (solución óptima del modelo dual). Si posteriormente evaluamos en la función objetivo del problema dual dicha solución obtenemos: V(D)=12(6/5)+16(2/5)=20,8 que es similar al valor óptimo del problema primal (Teorema de Dualidad Fuerte).
Siendo A=6/5 y B=2/5 una solución factible para el problema dual, ésta es la solución optima de dicho problema.
Observaciones: Notar que la restricción 1 y 2 del problema primal son activas en el óptimo, es decir, se cumplen en igualdad. Esto permite descartar que A y B (variables duales asociadas a dichas restricciones) son iguales a cero. Si por ejemplo, la restricción 1 del modelo primal no fuese activa en el óptimo se podría afirmar que A es igual a cero en el dual.
Ejercicio Teorema de Holguras Complementarias en Programación Lineal
Una empresa que fabrica muebles desea estudiar la producción de varios tipos de mesas de madera. Las mesas a fabricar son mesas de comedor, de centro y de arrimo, las que deben ser procesadas por 3 tipos de máquinas, una cortadora, una ensambladora y una pulidora. Se dispone de a lo mas de 80 horas de trabajo en cada una de las máquinas y 2.000 unidades de madera. La siguiente tabla muestra los tiempos y la madera necesaria para la fabricación de cada mesa, así como la utilidad que reporta cada una de ellas.
Dadas las siguientes soluciones del Problema PrimalS1=(900,100,0), S2=(176,496,656), S3=(200,400,550) y S4=(800,0,400). Determine mediante el Teorema de Holguras Complementarias si alguna de estas soluciones es óptima para el Problema Primal planteado.
MIN W = 4.800 Y1 + 4.800 Y2 + 4.800 Y3 + 2.000 Y4
S.A.
5 Y1 + 2 Y2 + 3 Y3 + 2 Y4 >= 3
3 Y1 + 5 Y2 + 2 Y3 + 2 Y4 >= 3
2 Y1 + 3 Y2 + 5 Y3 + 1 Y4 >= 2
Y1>= 0, Y2>=0, Y3>=0, Y4>=0
A continuación verificamos la factibilidad de las soluciones propuestas para el Problema Primal:
S1=(900,100,0), V(S1)=3.000 Satisface todas las restricciones S2=(176,496,656) V(S2)=3.328 Satisface todas las restricciones S3=(200,400,550) V(S3)=2.900 Satisface todas las restricciones S4=(800,0,400) V(S4)=3.200 Satisface todas las restricciones
Todas las soluciones satisfacen todas las restricciones por lo que son todas soluciones factibles. De ellas se escoge S2 ya que entrega la mayor utilidad para verificar si es solución óptima: X1=176, X2=496, X3=656.
En restricción (1) holgura X4 = 1.120
En restricción (2) holgura X5 = 0
En restricción (3) holgura X6 = 0
En restricción (4) holgura X7 = 0
De esta forma el Teorema de Holguras Complementarias permite obtener lo siguiente:
Que al ser reducido permite obtener un sistema de ecuaciones de 3×3:
2 Y2 + 3 Y3 + 2 Y4 = 3
5 Y2 + 2 Y3 + 2 Y4 = 3
3 Y2 + 5 Y3 + 1 Y4 = 2
Solución Problema Dual : Y1=0, Y2=1/25, Y3=3/25, Y4=32/25. Al evaluar la solución alcanzada en la función objetivo del dual se obtiene: W=4.800*0+4.800*1/25+4.800*3/25+2.000*32/25=3.328. Por el Teorema de Dualidad FuerteW=Z por lo tanto S2 es solución óptima del Problema Dual.
Por ejemplo, la versión de Solver disponible con Office 365 ofrece la siguiente interfaz para obtener el Informe de Sensibilidad (luego de alcanzar la solución óptima del problema en su escenario base).
En el caso de la versión de Solver compatible con Office 2007 y Office 2003, la interfaz es la siguiente:
De modo de ilustrar su correcta interpretación, a continuación consideraremos nuevamente nuestro ejemplo de Programación Lineal:
Con solución óptima X=14/5 Y=8/5 y valor óptimo V(P)=20,8. El Informe de Restricciones de Solver corresponde a:
Las filas del Informe de Restricciones corresponden a las restricciones 1 y 2, respectivamente.
En el caso de la restricción 1 el Precio Sombra es de 1,2 y el valor de la restricción (lado derecho) es igual a 12. Para dicho parámetro (lado derecho) se permite un aumento de de 9,33 y una disminución de 4, es decir, el lado derecho de la restricción 1 puede variar entre [8, 21,33] (12-4, 12+9,33) y el Precio Sombra de magnitud 1,2 seguirá siendo válido (es decir, se conserva la base óptima).
Esto significa que si, por ejemplo, el lado derecho de la restricción 1 aumenta en 1 unidad y el resto de los parámetros del modelo permanecen constantes, el nuevo valor óptimo será: V(P)=20,8+1*1,2=22.
Ahora bien, si por ejemplo, el lado derecho de la restricción 1 disminuye a 10 el nuevo valor óptimo será: V(P)=20,8-2*1,2=18,4.
Finalmente si la variación del lado derecho esta fuera del intervalo [8, 21,33]NO se puede utilizar el Precio Sombra para poder predecir cuál será el nuevo valor óptimo. Esto se debe a que la nueva solución óptima ya no se encontrará con las mismas restricciones activas, es decir, cambia la base óptima.
De forma análoga, para la restricción 2 el Precio Sombra es de 0,4 y este valor es válido si su lado derecho varía entre [9, 24] (16-7, 16+8). Por ejemplo, si el lado derecho de la restricción 2 aumenta en 3 unidades (y el resto de los parámetros permanece constante) el nuevo valor óptimo será: V(P)=20,8+3*0,4=22.
Cuando Resolvemos un modelo de Programación Lineal con Solver de Excel utilizamos una estimación de los parámetros (constantes) los cuales generalmente hacen referencia a disponibilidad de recursos, precios, costos, etc. En este contexto nos interesa simular el impacto en los resultados ante variaciones marginales de dichos parámetros sin la necesidad de resolver un nuevo modelo de optimización.
Este objetivo se puede alcanzar a través de los Informes de Sensibilidad de Solver los cuales se pueden generar una vez resuelto un escenario base para un modelo de optimización lineal, seleccionando la opción “Sensibilidad” (o Confidencialidad en versiones recientes de Office) según se muestra a continuación:
El siguiente análisis explica cómo interpretar el Informe de Sensibilidad de Celdas Cambiantes de Solver para el siguiente modelo de Programación Lineal:
Con solución óptima X=14/5 Y=8/5 y valor óptimo V(P)=20,8. El Informe de Celdas Cambiantes corresponde a:
Notar que en la última columna se ha marcado con color rojo la palabra Aumento que debiese decir Disminución (este tipo de error se observa generalmente en las versiones más antiguas de Office).
El Informe de Sensibilidad de Celdas Cambiantes nos indica el intervalo de variación para cada parámetro de la función objetivo que permite mantener la actual solución óptima (asumiendo que el resto de los parámetros permanece constante).
Por ejemplo, el coeficiente que actualmente pondera a la variable X en la función objetivo de maximización es 4. El aumento permisible de 4 nos indica que el actual parámetro podría aumentar en dicha magnitud y la solución óptima actual se mantendría.
Análogamente se podría disminuir en 1 unidad (disminución permisible) y se conserva la solución actual.
En conclusión, el Intervalo de Variación para el parámetro que pondera a la variable X en la función objetivo que conserva la actual solución óptima es entre [3,8].
Siguiendo un procedimiento similar se puede demostrar que el intervalo de variación para el parámetro asociado a la variable Y en la función objetivo que conserva la actual solución óptima es entre [3,8] (sólo es una coincidencia que sean los mismos intervalos para cada parámetro).
Por ejemplo, un cambio en uno de los parámetros de la función objetivo afecta la pendiente de ésta (curvas de nivel) que en la medida que se encuentre en el intervalo de variación previamente determinado mantendrá al vértice C como solución óptima del problema.
Una forma sencilla de corroborar estos resultados es mediante el Método Gráfico en Programación Lineal. Adicionalmente en el artículo Análisis de Sensibilidad Método Gráficose detalla el procedimiento para obtener los intervalos de variación para los parámetros tanto en la función objetivo como en las restricciones del problema. Recomendamos revisar ambos artículos de modo de favorecer la comprensión de este tipo de análisis.
Una de las posibilidades a las que nos podemos enfrentar cuando resolvemos un modelo de Programación Lineal a través del Método Simplex es el caso de múltiples o infinitas soluciones óptimas.
Esto significa que existe un tramo de soluciones factibles que reportan idéntico valor para la función objetivo y que no es posible mejorar.
En este contexto si luego de aplicar las iteraciones que resulten necesarias por el Método Simplex a un modelo de Programación Lineal (tabla óptima o tableau óptimo) se verifica que una variable no básica óptima tiene costo reducido igual a cero, esto permitirá afirmar que estamos ante el caso de infinitas soluciones.
Consideremos el siguiente modelo de Programación Lineal:
Llevamos el modelo a su forma estándar para proceder con la aplicación del Método Simplex, con S1 y S2 como variables de holgura de la restricción 1 y 2, respectivamente.
La tabla inicial con S1 y S2 como variables básicas iniciales es:
Y entra a la base. Luego para determinar la variable que deja la base utilizamos el criterio del mínimo cuociente: Min {12/4 ; 16/3} = 3 ==> S1 deja la base. Con esta información actualizamos la tabla realizando operaciones fila:
Luego de una iteración encontramos la solución óptima, donde Y y S2 son variables básicas. La solución básica factible óptima es X=0 Y=3 S1=0 S2=7. El valor óptimo es V(P)=6.
Notar que X (variable no básica) tiene costo reducido igual a cero lo que determina la existencia de múltiples o infinitas soluciones óptimas, de modo que la solución actual es uno de los vértices óptimos.
El siguiente diagrama muestra la Resolución Gráfica del problema con el software Geogebra donde la solución óptima que hemos encontrado en la aplicación del Método Simplex corresponde al vértice B.
Notar que la línea punteada de color azul corresponde a una curva de nivel de la función objetivo que tiene la misma pendiente que la restricción 1 (pendiente -1/2).
¿Cómo podemos obtener el vértice C que es solución óptima a través del Método Simplex? Una alternativa sería forzando la entrada a la base de la variable X en la tabla óptima. Luego calculamos cuál de las actuales variables básicas deja la base según el criterio del mínimo cuociente: Min {3/1/2 ; 7/5/2} = 14/5 ==> S2 deja la base. Actualizando la tabla obtenemos:
La nueva solución óptima (con idéntico valor óptimo) es X=14/5 Y=8/5 S1=0 S2=0, que corresponde al vértice C en el gráfico anterior. Ahora la variable no básica S2 tiene costo reducido igual a cero en la tabla óptima que señala el caso de múltiples soluciones óptimas (en este ejemplo el tramo BC).
