Formulación de un Problema de Aleaciones de Metales resuelto con Solver de Excel

Los modelos de Programación Lineal constituyen una excelente herramienta para representar Problemas de Mezcla de Productos en los cuales se asume que la calidad de la mezcla final en términos de los atributos propios de sus componentes, será proporcional a la participación de los insumos. En este contexto, el siguiente problema representa la situación de una empresa metalúrgica que debe determinar la combinación óptima de distintas aleaciones de metales que le permita configurar una nueva aleación a un costo mínimo. Por cierto se asume que el supuesto básico de la Programación Lineal asociado a la proporcionalidad es admisible.

Problema de Aleaciones de Metales

Una empresa metalúrgica desea fabricar 100 kilos de una nueva aleación que contenga no más de un 45% de Cobre, no menos de un 30% de Acero y un 20% de Estaño a partir de cuatro aleaciones que tienen las siguientes propiedades:

tabla-aleaciones

Formule y resuelva un modelo de Programación Lineal que permita determinar el porcentaje de cada una de las aleaciones debe contener la nueva aleación, de forma que resulte a un mínimo costo.

metales-aleacion

Variables de Decisión: Se propone definir la cantidad de kilogramos que representará cada una de las 4 aleaciones originales en la nueva aleación. Análogamente se puede definir como variables de decisión el porcentaje que representa cada aleación (original) respecto a la nueva aleación.

variables-decision-aleacion

Función Objetivo: Se desea minimizar el costo asociado a la utilización de las distintas utilizaciones.

funcion-objetivo-aleacion

Restricciones: El valor que adopten las variables de decisión previamente definidas deben satisfacer las condiciones que establecen las siguientes restricciones.

Kilogramos a Producir de la Nueva Aleación: Se deben producir 100 kilogramos de la nueva aleación.

fabricar-100-kilos-de-la-al

Máximo Porcentaje de Cobre: La nueva aleación debe contener como máximo un 45% de cobre.

maximo-porcentaje-de-cobre

Mínimo Porcentaje de Acero: La nueva aleación debe contenemos como mínimo un 30% de acero.

minimo-porcentaje-acero

Porcentaje de Estaño: La nueva aleación debe tener exactamente un 20% de estaño.

porcentaje-estaño

No Negatividad: Naturalmente las variables de decisión deben adoptar valores mayores o iguales a cero.

no-negatividad-aleacion

A continuación se muestra un extracto de los resultados computacionales luego de hacer uso de Solver de Excel.

solucion-optima-solver-alea

La solución óptima consiste en X_{1}=25, X_{2}=0, X_{3}=25, X_{4}=50, con valor óptimo V(P)=1.375.000. Dicha solución representa 100 kilogramos de la nueva aleación (que en efecto corresponde a la sumatoria de la cantidad de kilos que representa cada variable) donde la nueva aleación tiene un 45% de cobre, un 35% de acero y un 20% de estaño.

¿Quieres tener el archivo Excel con la resolución en Solver del Problema de Aleaciones de Metales presentado en este artículo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP)

El software Graphic Linear Optimizer (GLP) es una excelente herramienta que permite resolver gráficamente modelos de Programación Lineal. GLP fue desarrollado bajo la supervisión del profesor Jeffrey Moore (Ph. D) perteneciente a la Universidad de Stanford en Estados Unidos. En el siguiente artículo se muestra la utilización de Graphic LP Optimizer o GLP versión 2.6 en la resolución de un modelo de Programación Lineal en 2 variables que aborda una problemática de planificación forestal.

Una compañía forestal tiene un predio de 100 hectáreas de bosques para explotar. Talar y dejar el suelo para uso agrícola tiene un costo inmediato de M$10 por hectárea y un retorno posterior de M$50 por hectárea. Una alternativa es talar y plantar pino que tiene un costo inmediato de M$50 por hectárea y un retorno posterior de M$120 por hectárea. De aquí que los beneficios netos de ambos planes sean de M$40 y M$70 por hectárea, respectivamente. Desafortunadamente, el segundo plan no puede ser aplicado a todo el terreno ya que sólo se dispone de recursos inmediatos por M$4000. Formule y resuelva gráficamente utilizando el software Graphic Linear Optimizer (GLP) un modelo de Programación Lineal que provea el plan más eficiente de explotación, indicando claramente la solución óptima y valor óptimo.

El modelo de Programación Lineal para la situación anterior es:

modelo-planificacion-forest

Donde x_{1} representa las hectáreas para talar y dejar para uso agrícola y x_{2} las hectáreas para talar y plantar pino. En la siguiente imagen se muestra un extracto de la interfaz del programa GLP donde al pie de la misma se observa la solución óptima del problema con x_{1}=25x_{2}=75. El valor óptimo es 6.250 el cual se encuentra en la fila con la etiqueta PAYOFF.

GLP

El software GLP permite ajustar tanto la escala del gráfico como un zoom personalizado en cualquiera de los ejes de coordenadas. No obstante recomendamos hacer uso de la funcionalidad Auto Zoom que ajusta automáticamente la representación gráfica a una escala adecuada en relación a la magnitud de los datos de origen.

autozoom-glp

A continuación dejamos a nuestros usuarios un enlace de descarga del software Graphic Linear Optimizer o GLP para que puedan probar sus distintas funcionalidades.

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Problema de Inversión y Selección de Proyectos

Los modelos de Programación Entera constituyen una alternativa eficiente para apoyar la toma de decisiones en aquellos problemas donde se debe implementar (o no) una alternativa o curso de acción que no admite soluciones intermedias. Tal es el caso del Problema de Selección de Cartera de Proyectos donde no es razonable, por ejemplo, si se destina la mitad de los fondos requeridos para un proyecto, asumir que de éste se obtendrá la mitad de sus beneficios o Valor Presente Neto (VPN). Dicho de otro modo, el cumplimiento del supuesto de la proporcionalidad de la Programación Lineal no es adecuado.

El problema que se presenta a continuación aborda estos aspectos y adicionalmente se busca proponer distintas alternativas al momento de establecer las restricciones o condiciones del problema.

Problema de Inversión y Selección de Proyectos

Una empresa está pensando invertir en cuatro proyectos diferentes, cada proyecto se finaliza a lo más en 3 años. Los flujos de caja requeridos en cada año junto con el Valor Presente Neto (VPN) de cada proyecto, concluidos los años de ejecución, y las disponibilidades de recursos financieros se resumen en la siguiente tabla:

tabla-inversion-y-vpn-proye

Interesa determinar en cuáles proyectos invertir de modo de conseguir el mayor VPN de la inversión.

Variables de Decisión: Se desea determina en cuáles proyectos invertir de las 4 alternativas posibles.

variables-decision-inversio

Función Objetivo: Maximizar la sumatoria del Valor Presente Neto (VPN) de los proyectos en los cuales se decida invertir.

maximizar-vpn-inversion

Restricciones: Se proponen 3 escenarios para definir las restricciones del problema.

Alternativa 1: Reinvirtiendo el dinero no utilizado en un período, es decir, el dinero que eventualmente quede disponible al final del año 1 y año 2 se puede considerar como parte del presupuesto disponible para el año siguiente. Lo anterior se representa a través de las variables s_{1} y s_{2}, respectivamente.

alternativa-1-inversion-pro

La implementación computacional del problema haciendo uso de Solver de Excel nos entrega los siguientes resultados:

solucion-optima-inversion-1

Se debe invertir en los proyectos 1 y 4. El VPN total es de $51.

Alternativa 2: Sin invertir el dinero no utilizado en un período, pero utilizando el retorno de los proyectos concluidos.

alternativa-2-inversion

En este caso se debe invertir en los proyectos 1, 2 y 4, alcanzando un VPN total de $69.

solucion-optima-inversion-2

Alternativa 3: Reinvirtiendo el dinero no utilizado en un período y también el retorno de los proyectos concluidos.

alternativa-3-inversion

En este caso la solución óptima y valor óptimo es equivalente al escenario planteado en la Alternativa 3.

solucion-optima-inversion-3

Cabe destacar que la Alternativa 3 es la que provee mayor flexibilidad (en cuanto a los presupuestos para inversión) en comparación a las Alternativas 1 y 2, en consecuencia era razonable esperar en este caso que el VPN total de la Alternativa 3 sea mayor o igual que los VPN de las Alternativas 1 y 2.

Notar que el conjunto de las soluciones factibles es finito. Esto ocurrirá generalmente con los problemas de Programación Entera (puros). En el ejemplo, el número de soluciones factibles no supera el número de las soluciones binarias del problema (variables restringidas sólo a valores 0 o 1) que son 2^{4}=16, dado el número de variables utilizadas, de hecho las soluciones factibles son menos de 16 pues en particular x_{i}=1 para i=1,2,3,4 no satisface las disponibilidades de capital en cualquiera de las tres alternativas.

Criterios para la Rapidez de Convergencia del Método Simplex

En un artículo previo respecto a Cómo resolver un modelo de Programación Lineal con el Método Simplex de 2 Fases, se consideró en una iteración intermedia (es decir, en un tableau que representa una solución básica factible no óptima) la entrada a la base de una variable no básica que no era aquella con el costo reducido más negativo. Dicha situación por cierto no tuvo incidencia respecto a alcanzar los resultados del modelo en cuanto a su solución óptima y valor óptimo, no obstante, dicha situación afecto la rapidez de convergencia del Método Simplex.

Entendemos por rapidez de convergencia en este caso, el número de iteraciones necesarias en la aplicación del Método Simplex para, comenzando en una solución básica factible inicial llegar a una solución básica factible óptima.

Se debe destacar que si bien es frecuente que en la bibliografía básica asociada a cursos de Investigación de Operaciones se considere como criterio privilegiar la entrada a la base de aquella variable no básica con el costo reducido más negativo esto NO garantiza un menor número de iteraciones en el Método Simplex.

Ejemplo Criterio Costo Reducido Más Negativo en el Método Simplex

Como forma de corroborar lo anterior retomaremos el modelo de Programación Lineal que fue presentado en el artículo mencionado anteriormente:

ejemplo-simplex-dual

La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando X_{4} y X_{5} como variables de excesoX_{6} y X_{7} como variables auxiliares, de las restricciones 1 y 2, respectivamente. Esto da origen al siguiente problema de la Fase 1.

fase-1

Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:

tabla-3-fase-1

A continuación podríamos seleccionar como variable que ingresa a la base tanto a X_{1}, X_{2}  o X_{4}, al tener cada una de estas variables no básicas un costo reducido negativo.

Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable X_{2} que tiene el costo reducido más negativo. En consecuencia el mínimo cuociente se calcula en la columna de la variable X_{2}, siendo éste: Min\begin{Bmatrix}\frac{1/4}{1/4};\frac{1}{3/2}\end{Bmatrix}=2/3, por tanto X_{1} deja la base. Se actualiza la tabla con esta nueva información obteniendo lo siguiente que representa el fin de la Fase I:

rapidez-de-convergencia-fas

Eliminamos las columnas de las variables auxiliares X_{6} y X_{7} y adicionalmente actualizamos el vector de costos reducidos considerando la función objetivo original.

inicio-fase-2-convergencia

Luego llevamos a cero los costos reducidos de las variables X_{3} y X_{2}:

fase-2-rapidez-convergencia

Ahora entra la variable X_{1} a la base. El criterio de factibilidad o mínimo cuociente determina que Min\begin{Bmatrix}\frac{1/12}{1/3};\frac{2/3}{2/3}\end{Bmatrix}=1/4 la variable X_{3} deja la base. Se actualiza la tabla:

tabla-final-fase-2-rapidez-

Que corresponde a la tabla final de la Fase II donde X_{1}=1/4X_{2}=1/2X_{3}=0 y que por cierto demuestra la equivalencia en los resultados obtenidos cuando en la tabla  intermedia de la Fase I se ingresa a la base a la variable X_{1}. Cabe destacar que una forma alternativa de resolver el problema anterior que evita la aplicación de las 2 Fases del Método Simplex es a través del Método Simplex Dual.

Ejemplo Criterio Costo Reducido Negativo en el Método Simplex

Consideremos el siguiente problema de Programación Lineal:

ejemplo costo reducido negativo método simplex

El lector puede corroborar que luego de llevar a la forma estándar el problema anterior, pasando a minimización la función objetivo y agregando como variables de holgura las variables x_{3}x_{4} se dispone de una solución básica factible inicial en el origen (vértice A de la siguiente gráfica).

gráfico costo reducido negativo

Si se privilegia la entrada a la base de aquella variable no básica con el costo reducido más negativo se debería seleccionar inicialmente la variable x_{2} la cual permite concluir con las iteraciones del Método Simplex y alcanzar la solución óptima al cabo de 3 iteraciones (vértice D). Por el contrario si inicialmente se ingresa a la base la variable x_{1} se alcanza la solución óptima al cabo de 1 iteración. Se recomienda al lector verificar estos resultados.

Este sencillo ejemplo demuestra que NO necesariamente garantiza una mayor rapidez de convergencia del Método Simplex el considerar como criterio de entrada a la base aquella variable no básica con el costo reducido más negativo.

Cambio de Variables como alternativa al Método Simplex de 2 Fases

Una empresa que fabrica tres artículos A, B y C, desea encontrar un Plan de Producción semanal que le permita maximizar sus beneficios netos totales. Los productos son procesados en tres máquinas siendo la producción mínima semanal de 100, 60 y 60 unidades respectivamente. El beneficio neto por unidad vendida de estos artículos son 2, 2 y 4 mil pesos para los artículos A, B y C, respectivamente. Las horas que se necesitan por unidad y máquina son:

maquinas-tiempos-de-producc

Siendo el número de horas disponibles de cada máquina 240, 400 y 360 respectivamente. Formule un modelo de Programación Lineal para abordar el problema propuesto. Resuelva a través del Método Simplex dicho modelo, indicando cuántas unidades de A, B y C se deben fabricar semanalmente y el beneficio final de este plan.

Variables de Decisión: Se debe definir cuántas unidades de cada uno de los 3 productos se fabricarán durante el período de evaluación.

variables-produccion-abc

Función Objetivo: Consiste en maximizar el beneficio neto asociado al plan de producción.

funcion-objetivo-abc

Restricciones: Se debe garantizar que se fabrique los mínimos semanales exigidos para cada producto como también que se respete la disponibilidad de horas máquinas.

restricciones-abc

El problema anterior se puede resolver por el Método Simplex de 2 Fases agregando variables de exceso y auxiliares para cada una de las restricciones que establecen los mínimos semanales de producción. Además se debe agregar variables de holguras para cada una de las restricciones de disponibilidad de horas máquinas. En consecuencia el problema de la Fase 1 tendría 3 variables auxiliares (cuya sumatoria se minimiza en la función objetivo) lo cual genera una instancia de resolución al menos tediosa para este problema (en caso se ser abordada manualmente).

Una alternativa más eficiente de resolución se alcanza al imponer un cambio de variables, lo que permite simplificar las restricciones de mínimos de producción semanal. Sea X=A-100\geq 0, Y=B-60\geq 0Z=C-60\geq 0. Luego A=X+100B=Y+60C=Z+60, obteniendo la siguiente instancia de modelamiento equivalente:

modelo-lineal-con-cambio-de

A continuación llevamos a la forma estándar el modelo anterior, transformando la función objetivo a minimización y agregando s_{1},s_{2},s_{3} como variables de holgura de las restricciones 1, 2 y 3, respectivamente:

forma-estandar-cambio-de-va

Lo que da origen a la siguiente tabla inicial del Método Simplex:

tabla-inicial-forma-estanda

A continuación incorporamos a la base a la variable Z considerando el criterio que favorece la rapidez de convergencia del algoritmo. Luego calculamos el criterio de factibilidad o mínimo cuociente en la columna de la variable Z: Min\begin{Bmatrix}\frac{60}{2}; \frac{180}{1}; \frac{40}{1}\end{Bmatrix}=30, lo que determina que la variable s_{1} deja la base. Se actualiza la tabla realizando una iteración del Método Simplex:

iteracion-1-cambio-de-varia

Se procede a incorporar a la variable X a la base y s_{3} abandona la base dado que Min\begin{Bmatrix}\frac{150}{1}; \frac{10}{2}\end{Bmatrix}=5. Se realiza una iteración adicional que permite alcanzar la siguiente solución básica factible óptima:

solucion-optima-cambio-de-v

La solución óptima es X=5Y=0Z=30 que al remplazar en las variables originales permite obtener A=X+100=5+100=105B=Y+60=0+60=60C=Z+60=30+60=90. Notar que el valor óptimo es V(P)=130+560=690 luego de sumar el valor de la constante 560 al valor obtenido para la función objetivo del problema auxiliar. Se propone al lector corroborar los resultados anterior a través de la aplicación del Método Simplex de 2 Fases que por cierto permite alcanzar idénticos resultados pero con una mayor esfuerzo en la resolución.