Programación Lineal Archivos - Página 11 de 16

Cómo descargar e instalar Premium Solver en Excel 2010

Solver es sin duda junto a What’sBest! la herramienta más popular para resolver modelos de optimización utilizando Microsoft Excel como plataforma. En efecto la versión gratuita que utilizamos de Solver es desarrollada por Frontline Systems Inc, empresa que ofrece un importante número de herramientas y motores de resolución que son de gran utilidad para enfrentar problemas de naturaleza real aplicados en la industria.

En el siguiente artículo nos referiremos a cómo descargar e instalar la versión de prueba de Premium Solver que está disponible en forma gratuita por un período de 15 días y la cual nos permite enfrentar la resolución de modelos de Investigación Operativa significativamente mayores tanto en el número de variables de decisión como restricciones, que aquellos posibles de abordar con la versión tradicional de Solver.

Adicionalmente, al contar con algoritmos de resolución mejorados se favorece la confiabilidad de las soluciones encontradas y los tiempos de procesamiento.

A continuación presentamos el procedimiento detallado para descargar e instalar la versión de prueba de Premium Solver en un computador con Excel versión 2010.

Paso 1: Ingresar a Frontline Systems Inc, completando la información requerida en el formulario de suscripción.

Paso 2: Descargar la versión de prueba compatible con la versión de Excel que dispongamos. En este tutorial se muestra la instalación de la versión de 64 bits. Una vez que estamos seguros de nuestra elección seleccionamos “Download Now”.

Si tienes Excel 2010 y deseas saber de cuántos bits es la versión que utilizas ejecuta Excel y en el menú Archivo selecciona la opción Ayuda. En la esquina inferior derecha se mostrará la cantidad de bits de tu versión bajo el titulo “Acerca de Microsoft Excel”.

Paso 3: Revisa tu cuenta de correo electrónico (la que proporcionaste en el formulario de suscripción del Paso 1) y anota las 2 contraseñas que te han sido asignadas (en la imagen a continuación éstas han sido protegidas con color azul y rojo).

Paso 4: Una vez completada la descarga ejecuta el archivo “SolverSetup64.exe” (o el nombre que corresponda según la versión de Excel que estés utilizando).

A continuación se desplegará el asistente para la instalación del programa. (Seleccionar “Next”).

Ahora debemos ingresar los password que hemos recibido por correo electrónico (Paso 3) para continuar con la activación del programa:

Luego debemos aceptar los acuerdos de la licencia del programa y seleccionar “Next”.

En estos momentos la licencia del programa ya ha sido activada y continuamos el proceso de la instalación seleccionando “OK”.

Se debe seleccionar la carpeta donde se instalará el programa y podemos en este punto seleccionar simplemente aquella ubicación que el programa selecciona por defecto.

Es el momento de seleccionar el producto que deseamos activar. En este caso hemos seleccionado “Premium Solver Pro” que corresponde a la versión mejorada de la versión de Solver que se utiliza generalmente para fines académicos.

El asistente de instalación nos solicitará confirmar la instalación que hemos seleccionado (“Install”).

Finalmente hemos completado la instalación del programa Premium Solver Pro y ya estamos en condiciones de poder utilizarlo para resolver modelos de optimización utilizando Microsoft Excel como plataforma.

Cambio de Variables en un Modelo de Programación Lineal

Cuando se desea resolver un modelo de Programación Lineal es importante tener en cuenta que generalmente se dispone de varias alternativas las cuales difieren en dificultad y por tanto es necesario evaluar cada una en su mérito para luego decidir qué estrategia algorítmica utilizar.

Este concepto es válido tanto para la resolución de pequeños modelos de optimización lineales como los que usualmente se consideran para fines académicos, como también para modelos de mayor tamaño, donde seleccionar una estrategia adecuada favorece los tiempos y confiabilidad de la resolución computacional.

A continuación presentaremos un problema de Programación Lineal en 2 variables que resulta de interés su resolución:

Notar que existen distintas estrategias que nos permiten abordar el problema anterior. Por ejemplo, lo podríamos resolver gráficamente (Método Gráfico en Programación Lineal) o utilizar el Método Simplex de 2 Fases, agregando variables de holgura para las restricciones 1, 2 y 3 y variables de exceso y auxiliares para las restricciones 4 y 5. También por cierto se podría definir el Problema Dual del ejemplo anterior y luego intentar su resolución, lo que a primera vista no sería de mayor ayuda.

Ahora bien, si una variable de decisión x debe cumplir la restricción x≥a, para una constante a positiva, se puede imponer un cambio de variables y=x-a, que define una nueva variable y que tiene solo una restricción de no negatividad y simplifica imponer la primera como una restricción general en la aplicación del Método Simplex.

El concepto anterior nos permite hacer lo siguiente: Y1=X1-20>=0; Y2=X2-20>=0. Es decir X1=Y1+20 y X2=Y2+20. En consecuencia podemos reescribir el modelo original de la siguiente forma:

Reduciendo términos semejantes se obtiene:

Notar que este nuevo modelo de optimización se puede resolver de forma directa a través del Método Simplex, incorporando las variables no negativas Y3, Y4 e Y5 como holguras de las restricciones 1, 2 y 3, respectivamente. De esta forma el problema en su forma estándar proporciona la siguiente tabla inicial: (Notar que el valor de la función objetivo inicialmente es 1.100 debido a que dicha constante se obtiene luego de realizar el cambio de variables)

La variable Y1 entra a la base al ser la variable no básica con el costo reducido más negativo. Luego para determinar la variable básica que deja la base calculamos el mínimo cuociente: Min {420/6; 140/1; 160/2} = 70 ==>Y3 sale de la base. Se realiza una iteración del Método Simplex:

Ahora Y2 entra a la base al ser la única variable no básica con costo reducido negativo. A continuación la variable que deja la base se determina a través del criterio del mínimo cuociente: Min {70/1/2; 70/3/2; 20/1} = 20 ==>Y5 sale de la base. Se realiza una nueva iteración:

Se ha alcanzado la tabla óptima donde Y1=60 e Y2=20 con valor óptimo V(P)=3.400. Reemplazando en las variables originales se obtiene la solución óptima del problema original: X1=60+20=80 y X2=20+20=40. Se puede corroborar que esta solución óptima al ser evaluada en la función objetivo del problema inicial proporciona el valor óptimo del modelo de programación lineal: Max 30*(80)+25*(40)=3.400, lo que permite garantizar la equivalencia del procedimiento utilizado.

Incorporar Nueva Restricción (Análisis Postoptimal Programación Lineal)

Una vez resuelto un modelo de Programación Lineal puede resultar de interés si la actual solución óptima y valor óptimo se conservaran si se decide incorporar una nueva restricción al problema. Esta restricción generalmente representa una condición que en primera instancia se omite de forma voluntaria para dar una mayor flexibilidad a la resolución del modelo original o alternativamente su no inclusión en el modelo original puede también deberse a una simple omisión (involuntaria).

Consideremos el siguiente modelo de Programación Lineal que hemos resuelto en un artículo previo a través del Método Simplex:

La tabla final óptima que considera las variables s1, s2 y s3 como las respectivas holguras de las restricciones del problema es:

Por ejemplo, consideremos que se desea incorporar una nueva restricción definida por la siguiente expresión: 3X+Y<=600. ¿Cambia la actual solución óptima y valor óptimo?.

Para responder a lo anterior se recomienda evaluar la actual solución óptima en la nueva restricción; si ésta se cumple entonces el modelo conserva su solución óptima y valor óptimo; en caso contrario la solución óptima actual será infactible y se debe incorporar esta situación en el modelo original para encontrar la nueva solución del mismo. Notar que también puede suceder que al agregar una nueva restricción que no satisface la solución actual el problema podría resultar ser infactible al tener un dominio de soluciones factibles vacío.

En nuestro ejemplo al evaluar obtenemos: 3(100)+(350)<=600, es decir, la solución óptima actual es infactible al incorporar esta nueva restricción.

Para incorporar esta modificación en la tabla final del Método Simplex agregamos una nueva fila y una nueva columna asociada a una variable s4>=0 que será la holgura de la nueva restricción. La tabla queda de la siguiente forma:

Las variables básicas del problema original son x, s2 e y, respectivamente. Al incorporar la nueva restricción (fila) tanto x como y pierden la estructura de la identidad característica de las variables básicas. Por ello para formar la base podemos realizar operaciones fila multiplicando por -3 la fila 1 y sumando ésta a la fila 4. Posteriormente multiplicar por -1 la fila 3 y sumar a la fila 4:

Ahora las variables básicas son x, s2, y, s4 (enumeradas en el orden en el cual aparecen en la identidad), sin embargo, la variable s4 toma un valor de -50 lo cual no corresponde a una solución básica factible.

¿Cómo continuar con las iteraciones?. Utilizando el Método Simplex Dual se recomienda corroborar que la nueva solución óptima corresponde a x=250/3 e y=350.

Adicionalmente podemos utilizar un enfoque de Resolución Gráfica para el problema anterior. El siguiente gráfico representa la resolución del escenario inicial donde la solución básica factible óptima se alcanza en el vértice C con x=100 e y=350.

Al incorporar la nueva restricción (recta color rojo) el dominio de soluciones factibles se ve reducido, donde ahora ya no son factibles los puntos en el polígono con área achurada color verde (donde se puede verificar que el vértice C es infactible).

Si se resuelve gráficamente sobre el nuevo dominio (área achurada color naranjo) las curvas de nivel de la función objetivo (recta punteada color azul) pasa por última vez en el vértice F donde x=250/3 e y=350 como solución óptima del nuevo problema.

Relaciones de Dualidad en Programación Lineal (Pasar de Primal a Dual)

El modelo dual de un problema de Programación Lineal consiste en una instancia alternativa de modelamiento matemático que nos permite rescatar la información del problema original conocido comúnmente como modelo primal.

En consecuencia es suficiente con resolver uno de ellos (primal o dual) para poder obtener la solución óptima y valor óptimo del problema equivalente (primal o dual según sea el caso). Para ello se puede utilizar, por ejemplo, las condiciones establecidas en el Teorema de Holguras Complementarias.

Las relaciones de dualidad se pueden resumir en el siguiente cuadro:

La tabla anterior se puede interpretar tanto de izquierda a derecha como de derecha a izquierda.

Primal Minimización – Dual Maximización

Por ejemplo, leyendo la tabla desde izquierda a derecha, es decir, pasar de un problema primal de minimización a un problema dual de maximización, tenemos:

Si el problema primal es de minimización, entonces su correspondiente dual será uno de maximización.
Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser >=0.
Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser <=0.
Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser <=.
Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser >=.
Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Primal Maximización – Dual Minimización

De forma análoga, interpretando la tabla desde derecha a izquierda, es decir, pasar de un problema primal de maximización a un problema dual de minimización, tenemos:

Si el problema primal es de maximización, entonces su correspondiente dual será uno de minimización.
Si el problema primal tiene una restricción del tipo <=, la variable dual asociada a dicha restricción debe ser >=0.
Si el problema primal tiene una restricción del tipo >=, la variable dual asociada a dicha restricción debe ser <=0.
Si el problema primal tiene una restricción del tipo =, la variable dual asociada a dicha restricción debe ser irrestricta (libre de signo).
Si el problema primal tiene una variable >=0, la correspondiente restricción asociada en el dual debe ser >=.
Si el problema primal tiene una variable <=0, la correspondiente restricción asociada en el dual debe ser <=.
Si el problema primal tiene una variable irrestricta (libre de signo), la correspondiente restricción asociada en el dual debe ser =.

Ejemplo Relaciones de Dualidad en Programación Lineal

A continuación presentamos un modelo de optimización que consideraremos como el problema primal y que en un artículo previo fue resuelto a través del Método Simplex de 2 Fases.

Como en este caso el problema primal es de minimización, para definir su respectivo problema dual leeremos la tabla que resume las relaciones de dualidad desde izquierda a derecha. En consecuencia, el problema dual será uno de maximización.

Adicionalmente la primera y segunda restricción del problema primal definirán las variables de decisiones (variables duales) en el problema dual (Y1 e Y2, respectivamente), siendo los coeficientes en la función objetivo los actuales valores de los lados derechos de las restricciones del problema primal.

De esta forma la función objetivo del problema dual queda definida por la siguiente expresión:

Luego por cada variable en el problema primal vamos a tener la misma cantidad de restricciones en el problema dual. En este caso las variables X1, X2 y X3 definirán la estructura de las restricciones 1, 2 y 3 en nuestro problema dual. Por ejemplo la primera restricción del problema dual (asociada a la variable primal X1) sería 2Y1+2Y2<=160.

Notar que los coeficientes que ponderan a las variables duales son los parámetros asociados a la variable X1 en el primal en la primera y segunda restricción, respectivamente. La restricción en el dual es del tipo “<=” debido a que la variable X1 en el problema primal de minimización tiene la condición de no negatividad (“>=0”). Por último el lado derecho de la restricción es el coeficiente que tiene la variable X1 en la función objetivo del problema primal. Siguiendo el procedimiento las restricciones del problema dual serían:

Finalmente como las 2 primeras restricciones del problema primal son del tipo “>=” en el problema primal de minimización, las respectivas variables duales asociadas en el problema de maximización serán no negativas. De esta forma el problema dual es:

Ejercicio Propuesto: Utilizando las relaciones de dualidad en Programación Lineal, dado un problema primal P, demuestre que su correspondiente dual D queda definido de acuerdo a:

En lo que sigue, combinaremos las distintas restricciones del problema primal, ponderando por los valores no negativos $\pi_{1},\pi_{2}$ y $\pi_{3}$ cada una, respectivamente, de modo de obtener la mejor cota superior del valor óptimo del problema P). Vale decir:

De modo de garantizar que el lado derecho de esta última desigualdad sea una cota superior de la función objetivo del problema primal se debe cumplir que:

$2\pi_{1}+\pi_{2}+\pi_{3}\geq 40$

$\pi_{1}+\pi_{2}+3\pi_{3}\geq 60$

La mejor elección de esta cota se obtendría al resolver el siguiente problema de optimización:

Este problema se conoce como el problema “Dual” D) asociado al problema “Primal” P).

También resulta que al formular el problema dual de D) se obtiene el problema primal P) (o uno equivalente). Cualquiera de los dos entrega la misma información y el valor óptimo alcanzado es el mismo.

Modelo de Transporte con Transbordo resuelto con Solver de Excel

Una de las aplicaciones clásicas de la Investigación de Operaciones y en particular de la Programación Lineal es proponer alternativas óptimas para el proceso logístico o transporte de insumos o productos desde un conjunto de oferentes hasta un conjunto de destinatarios o demandantes.

Cuando consideramos que en este proceso de transporte pueden participar intermediarios estamos frente a una extensión del modelo básico de transporte el cual es comúnmente conocido como Modelo de Transporte con Transbordo. A continuación presentaremos un caso aplicado de dicho modelo.

Ejemplo Problema de Transporte con Transbordo

Se deben transportar 20 millones de barriles de petróleo desde Dhahran en Arabia Saudita a las ciudades de Rotterdam, Marsella y Nápoles en Europa. Las demandas de estas tres ciudades son 4, 12 y 4 millones de barriles, respectivamente. A continuación se presenta un diagrama con las posibles rutas:

Observe que para cada ciudad existe la posibilidad directa de envío, es decir, que los barriles sean transportados directamente desde Dhahran. Sin embargo, la ruta que une Dhahran y Marsella no puede transportar más de 3 millones de barriles debido a ciertos acuerdos comerciales.

Por otro lado, existe la posibilidad que se realice una detención, ya sea en el puerto de Alejandría o Suez, donde la capacidad de almacenamiento es de 8 y 10 millones respectivamente.

Por último, observe que es posible enviar barriles de petróleo desde Marsella a Nápoles. Sin embargo, le está prohibido a Nápoles recibir más petróleo de Marsella que directamente de Dhahran. Formule y resuelva un modelo de Programación Lineal que permita hallar la política óptima de transporte para cumplir con los requerimientos de demanda de los puertos.

Variables de Decisión:

X1: Barriles transportados desde Dhahran a Rotterdam
X2: Barriles transportados desde Dhahran a Marsella
X3: Barriles transportados desde Dhahran a Nápoles
X4: Barriles transportados desde Dhahran a Alejandría
X5: Barriles transportados desde Dhahran a Suez
X6: Barriles transportados desde Alejandría a Rotterdam
X7: Barriles transportados desde Alejandría a Marsella
X8: Barriles transportados desde Suez a Marsella
X9: Barriles transportados desde Suez a Nápoles
X10: Barriles transportados desde Marsella a Nápoles

Función Objetivo:

Minimizar los costos totales de transportes dados por la siguiente expresión: 7X1 + 8X2 + 15X3 + 6X4 + 5X5 + 8X6 + 7X7 + 2X8 + 6X9 + 1X10

Restricciones:

Satisfacer la Demanda en los Puertos:

X1 + X6 = 4.000.000 (Rotterdam)
X2 + X7 + X8 – X10 = 12.000.000 (Marsella)
X3 + X9 + X10 = 4.000.000 (Nápoles)

Notar que Marsella eventualmente podría recibir más de 12 millones de barriles de petróleo (su demanda) debido a que este Puerto tiene la posibilidad de abastecer a Nápoles.

Balance en el Transbordo:

X4 = X6 + X7 (Alejandría)
X5 = X8 + X9 (Suez)

La cantidad de barriles que recibe Alejandría y Suez debe ser igual a lo que cada uno de ellos despacha a los Puertos, es decir, los intermediarios no acumulan inventario al final del periodo de planificación. En este punto es importante destacar que si se considera un modelo extendido donde se busca satisfacer los requerimientos de demanda de varios periodos podría ser admisible almacenar inventario en Alejandría y Suez, cambiando en este caso la forma del modelo de optimización.

Capacidad de Procesamiento en el Transbordo:

X4 <= 8.000.000 (Alejandría)
X5 <= 10.000.000 (Suez)

Tanto Alejandría como Suez no pueden recibir una cantidad de barriles mayor a la que pueden procesar.

Capacidad Ruta entre Dhahran y Marsella:

X2 <= 3.000.000

La ruta que une Dhahran y Marsella no puede transportar más de 3 millones de barriles por acuerdos comerciales.

Cantidad Recibida por Nápoles:

X3 >= X10

Está prohibido a Nápoles recibir más petróleo de Marsella que directamente de Dhahran.

No Negatividad:

Xi >= 0 Para todo i

Al implementar el modelo anterior con Solver de Excel se obtienen los siguientes resultados:

Donde la solución alcanzada tiene la siguiente estructura (sobre los arcos se detalla el valor de la solución óptima):