10 Cosas que Necesitas Saber sobre el Método Simplex

El Método Simplex desarrollado por George B. Dantzig en 1947 es sin duda el algoritmo más popular a la hora de enfrentar la resolución de un modelo de Programación Lineal y ocupa un lugar destacado en los cursos introductorios a la Investigación de Operaciones.

En esta oportunidad hemos buscado resumir 10 conceptos principales sobre el uso y la aplicación del Método Simplex con el objetivo de que nuestros usuarios puedan tener una primera aproximación al método observando algunos aspectos característicos. Esta recopilación se basa sobre nuestra experiencia docente dictando cursos de Investigación Operativa y las preguntas que frecuentemente recibimos por parte de los alumnos de pregrado.

10 Cosas que Necesitas Saber sobre el Método Simplex

método simplex

Te invitamos a revisar y compartir esta infografía en las redes sociales. Adicionalmente si consideras si un elemento importante quedo fuera de la lista anterior utiliza la herramienta de comentarios al pie de la página para hacernos saber tu opinión. De esta forma podremos ir actualizando periódicamente el artículo con las características principales del Método Simplex.

Planificación de la Producción Multiproducto

El siguiente problema consiste en la formulación de un modelo de Programación Entera y posterior resolución computacional haciendo uso del complemento OpenSolver de Excel, específicamente en lo que se refiere a un modelo que permita encontrar la estrategia óptima para la Planificación de la Producción Multiproducto (es decir, 2 o más productos) y multiperiodo (2 o más períodos en el horizonte de evaluación). Referencias adicionales sobre esta clase de problemáticas pueden ser consultadas en la categoría Plan Maestro de la Producción (PMP) donde se presentan un importante volumen de ejercicios resueltos de planificación agregada. Dicho lo anterior a continuación presentamos el ejemplo objeto de nuestro análisis:

Una empresa desea optimizar la planificación de la producción de sus cinco productos principales para los primeros 6 meses del año 2016. Para el desarrollo de la tarea encomendada la empresa recolecta los siguientes antecedentes:

demanda-multiproducto-multi

  1. El proceso de fabricación es intensivo en mano de obra donde cada trabajador percibe un salario bruto de US$1.200 por una jornada de 160 horas de trabajo al mes.

  2. El costo unitario de materiales y gastos generales, excluyendo el trabajo es de US$12 para A, US$14 para B, US$9 para C, US$13 para D y US$8 para E.

  3. El costo de mano de obra de producción en tiempo extra se paga con un recargo de un 50% respecto a la hora trabajada en horario normal. No obstante por política de la empresa se establece un máximo de 200 horas hombre en tiempo extraordinario para cada mes, exceptuando Enero y Febrero donde el límite corresponde a 100 horas (por acuerdos con el sindicato).

  4. El costo mensual de almacenar una unidad de cualquier producto en inventario es de US$4 por unidad. La bodega tiene una capacidad de almacenamiento de 250 unidades.

  5. El tiempo de producción por unidad es de 5 horas para A, 6 horas para B, 8 horas para C, 4 horas para D y 3 horas para E.

  6. La contratación de personal de producción considera un costo único de US$1.500 (adicional al sueldo) por concepto de capacitación y entrenamiento.

  7. Para la reducción de horas de trabajo o despido considere en promedio: un sueldo de US$1.200 y una antigüedad de 2 años. Por política de estabilidad laboral se establece un máximo de despido de 6 trabajadores durante el primer semestre.

  8. El inventario inicial corresponde a 120 y 80 unidades para los productos B y C respectivamente. No se dispone de inventario inicial para el producto A, D y E.

  9. La planilla de trabajadores al 31 de Diciembre de 2015 es de 55 trabajadores.

  10. Es posible dejar demanda pendiente del producto A y D asumiendo un costo unitario de US$25 en cada caso, la cual no expira y sólo se posterga para un próximo mes. No obstante la empresa requiere que como máximo queden 500 unidades de demanda pendiente (en total para la suma de ambos productos) a fines de Junio de 2016.

  11. En cuanto al producto B, éste se puede comprar adicionalmente a un proveedor a un costo unitario de US$75. Adicionalmente el costo fijo de gestionar un pedido al proveedor del producto B (independiente del tamaño del pedido) es de US$200.

  12. En cuanto al producto E, éste se puede comprar adicionalmente a un proveedor a un costo unitario de US$35. Adicionalmente el costo fijo de gestionar un pedido al proveedor del producto E (independiente del tamaño del pedido) es de US$150.

Formule y resuelva un modelo de optimización matemática que permita determinar la política operacional que minimice los costos totales en el horizonte de planificación y cumpla con las condiciones expuestas.

Planificación de la Producción Multiproducto

Variables de Decisión:

variables-de-decision-multi

Notar que se dispone de 5 productos y 6 períodos. En este contexto y con el objetivo de lograr una notación más compacta se utilizan los índices i y t para representar los productos y períodos (meses), respectivamente.

Parámetros:

parametros-pmp-multiproduct

La definición de parámetros no es estrictamente necesaria y se realiza de modo de establecer un caso más general para el problema que facilita (compacta) la notación requerida para definir el modelo. Se puede apreciar que no todos los datos factibles de poder representar con parámetros ha sido llevado a cabo, lo cual corresponde a una decisión arbitraria la que sin embargo no afecta los resultados.

Función Objetivo:

funcion-objetivo-multiprodu

Se busca minimizar los costos totales de la planificación multiproducto y multiperiodo. Los costos involucrados son (en orden): producción, inventario, mano de obra en tiempo normal, mano de obra en sobretiempo, contratación, despido, demanda pendiente, compra del producto B y compra del producto E.

Restricciones:

Balance de Inventario: Para el caso del producto A y D se puede utilizar demanda pendiente y para los productos B y E se pueden realizar compras. En este caso sólo los requerimientos del producto C deben ser satisfechos de forma exclusiva a través de la producción e inventario.

balance-de-inventario-multi

Balance de Trabajadores: La cantidad de trabajadores disponibles en un mes para funciones de producción será igual a los disponibles en el mes anterior, más los contratados en el mes y menos los despedidos en dicho mes.

balance-de-trabajadores-mul

Capacidad de Producción: El lado izquierdo de la restricción representa la cantidad de horas requeridas en un mes para la producción de los 5 productos, lo cual no podrá superar las horas disponibles (siendo éstas las horas en tiempo normal más las horas que eventualmente se utilicen en sobretiempo).

capacidad-de-produccion-mul

Capacidad de la Bodega: Para cada mes del horizonte de planificación la cantidad de productos almacenados en inventario (suma de todos los productos) no podrá superar la capacidad de almacenamiento de la bodega de 250 unidades.

capacidad-bodega-multiprodu

Máximo de Compras B y E: La cantidad máxima de compra para el producto B y E dependerá si se adopta la decisión de realizar una compra en el mes respectivo. En dicho caso la cantidad máxima a comprar corresponderá a los parámetros o constantes grandes M_{B}M_{E}, respectivamente. Por ejemplo un valor para M_{B} podría ser 3.152 que corresponde a la suma de la demanda del producto B del mes 1 al mes 6.

maximo-compras-b-y-e

Máxima Cantidad de Despidos: Durante el horizonte de planificación no se pueden despedir más de 6 trabajadores.

maximo-despidos-pmp

Máximo Demanda Pendiente Mes 6: Al final del mes 6 no debe quedar más de 500 unidades de demanda pendiente para el producto A y D (en conjunto).

maximo-demanda-pendiente

No Negatividad y Enteros: Las variables de decisión deben adoptar no negativos y enteros (exceptuando las variables binarias).

La implementación computacional con OpenSolver del modelo de optimización anterior entrega los siguientes resultados. Las celdas en color amarillo corresponden a las variables de decisión del problema definidas inicialmente que satisfacen las restricciones impuestas (solución factible).

solucion-optima-pmp-multipr

El valor óptimo corresponde a US$599.770 que corresponde al costo mínimo asociado al plan de producción. A continuación se desglosa dicho costo total en los distintos ítems de costos según lo detallado anteriormente.

valor-optimo-multiperiodo

¿Quieres tener la planilla Excel con la resolución en OpenSolver de este problema?.

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Problema de Producción y Mezcla de Café en Programación Lineal

Como hemos abordado anteriormente en el Blog, los modelos de Programación Lineal constituyen una alternativa metodológica para enfrentar Problemas de Mezcla de Productos. En este contexto a continuación presentamos la formulación de un modelo de optimización lineal junto a su implementación computacional haciendo uso de Solver de Excel el cual fue enviado por uno de nuestros usuarios de Costa Rica.

Problema de Producción y Mezcla

Una firma de café produce dos tipos de mezclas: suave y suavísimo. En la planta se cuenta con:

disponibilidad-y-caracteris

Por ejemplo, el costo por libra del café colombiano es $52, el cual contiene 2,5% de cafeína y se dispone de 20.000 libras para la producción de mezclas. Adicionalmente los productos que se comercializan en el mercado son:

precio-venta-y-demanda-cafe

Es decir, la mezcla suave se vende a $72 la libra, con una demanda de 35.000 libras y puede contener como máximo un 2,2% de cafeína.

Variables de Decisión:

variables-cafe

Donde i=1,2,3 representa los países de origen Colombia, Brasil y México, respectivamente y j=1,2 la mezcla Suave y Suavísimo, respectivamente.

Función Objetivo:

funcion-objetivo-ganancia-c

Se busca maximizar la ganancia (diferencia entre los ingresos menos los costos) asociada al plan de producción y venta de las mezclas de café. Con color amarillo se destaca los ingresos por venta correspondientes a las variedades Suave y Suavísimo y en color verde los costos asociados a la utilización de libras de café colombiano, brasileño y mexicano.

Restricciones:

Disponibilidad de Café: para cada país de origen la cantidad de libras utilizadas para el proceso de mezcla no debe superar la disponibilidad.

disponibilidad-cafe

Demanda de Mezclas: se debe satisfacer la demanda de cada mezcla de café a través de la asignación de las variedades provenientes de los 3 países de origen.

demanda-mezcla-cafe

Porcentaje Máximo de Cafeína: cada mezcla no debe superar un porcentaje máximo de cafeína admitido.

porcentaje-maximo-cafeina

No Negatividad: naturalmente las variables de decisión deben satisfacer las condiciones de no negatividad y se permiten valores fraccionarios: X_{ij}\geqslant 0.

Al implementar el modelo de Programación Lineal anterior haciendo uso de Solver de Excel se alcanza la siguiente solución óptima y valor óptimo:

solucion-solver-mezcla-cafe

La ganancia total (valor óptimo) es de $1.385.000, la cual se obtiene al asignar 20.000 libras de café Colombiano para la producción de la variedad Suave, 25.000 libras de café Brasileño para la producción de la mezcla Suavísimo y 15.000 libras de café Mexicano para la producción de la variedad Suave (solución óptima).

¿Quieres tener el archivo Excel con la resolución en Solver de este problema?.

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Cambio en el Lado Izquierdo de las Restricciones en Programación Lineal

El el contexto del Análisis de Sensibilidad en Programación Lineal es usual analizar el impacto que tiene la modificación en la disponibilidad de los recursos en la solución óptima alcanzada originalmente. Esto corresponde al Cambio en el Lado Derecho de las Restricciones (Análisis de Sensibilidad en Programación Lineal). En el siguiente artículo abordaremos el caso cuando cambia un coeficiente o parámetro en el lado izquierdo de las restricciones, generalmente asociado a un coeficiente tecnológico o factor de productividad (por ejemplo, la cantidad de horas hombre que puede requerir la fabricación de un producto, la cantidad de dinero requerido por unidad a producir dada una restricción presupuestaria, entre otras). En relación a lo anterior consideremos el caso de una empresa la cual tiene un plan de producción representado por:

modelo-lado-izquierdo

Donde x_{j} es la cantidad a producir del bien j, z la utilidad de la empresa (en unidades monetarias u.m) y los coeficientes a_{ij} de las restricciones, la cantidad de recurso i por unidad del producto j. Al aplicar el Método Simplex al modelo anterior incorporando x_{4} y x_{5} como variables de holgura de las restricciones del recurso 1 y 2 respectivamente, resulta la siguiente tabla final:

tabla-simplex-lado-izquierd

Si el requerimiento del primer recurso por parte del producto j=2 cambia de 5 a 2 debido a la incorporación de una nueva tecnología ¿Cambia la actual solución óptima? (x_{1}=\frac{20}{3}, x_{2}=\frac{4}{3} y x_{3}=0). Sabemos que:

formula-matriz-inversa

Luego al cambiar un coeficiente en el lado izquierdo asociado a la variable básica x_{2}, es necesario actualizar la matriz de base inversa o B^{-1}. Lo anterior se deduce del cálculo de la matriz inversa asociada a la matriz B donde los elementos en la columna correspondiente a los coeficientes en el lado izquierdo (forma estándar del Método Simplex) asociadas a las variables básicas x_{1}x_{2}, respectivamente. Finalmente obtenemos la nueva solución básica y verificamos si es factible, esto es si el valor que adopta cada una de las variables básicas satisface las condiciones de no negatividad (en caso que una de las variables básicas alcance un valor negativo se puede continuar las iteraciones con el Método Simplex Dual luego de actualizar el valor de la función objetivo).

calculo-xb-cambio-lado-izqu

En nuestro ejemplo x_{1}=\frac{28}{3}x_{2}=\frac{2}{3} y x_{3}=0 lo cual implica que se modifica la solución óptima original pero se conserva la actual base óptima (las mismas variables básicas originales). El nuevo valor óptimo será:

valor-optimo-cambio-lado-iz

Formulación de un Problema de Programación de Explotación Forestal resuelto con Solver de Excel

En el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP) describimos un problema de explotación forestal reducido en términos de la complejidad de un caso de esta naturaleza (de modo de representarlo gráficamente), el cual a continuación extenderemos a través de la incorporación de una serie de decisiones en el tiempo respecto a la actividad de producción, planificación de personal, gestión de inventarios, compra, entre otros.  En este contexto considere el caso de una compañía forestal que cosecha (tala) árboles los primeros meses del año. La compañía tiene una serie de pedidos que debe satisfacer cada mes. Estos datos se resumen a continuación:

demanda-arboles

Al 1 de Enero hay un total de 40 trabajadores y no hay árboles en inventario. La jornada laboral es de 40 horas semanales y 4 semanas laborales al mes. Para cosechar un árbol se requiere 4 horas hombre. Independiente de lo anterior la forestal tiene una capacidad de cosecha de 3.000 árboles mensuales lo cual está dado por la maquinaria disponible.

El sueldo mensual de cada trabajador es de M$400 (el sueldo se paga de forma íntegra ante todo evento, es decir, trabajando la totalidad de horas al mes o menos). La política de la gerencia es no utilizar horas extraordinarias pero si podría comprar árboles a otra forestal cercana a un costo unitario de M$18. Adicionalmente se ha convenido no contratar trabajadores por una fracción de una jornada de trabajo normal (160[horas/mes]). Esto implica que si se contrata un trabajador debe ser por 160[horas/mes] a un costo de M$400 pero no es válido, por ejemplo, contratar un trabajador por 80[horas/mes] a un costo de M$200. El costo de contratar un trabajador es de M$200 y el costo de despedir un trabajador se estima en M$600.

Almacenar un árbol en bodega tiene un costo de M$10 de un mes a otro. Sin embargo, en la bodega no hay espacio para almacenar más de 500 árboles.

Formule y resuelva un modelo de Programación Entera para este problema que permita hallar una política óptima de explotación para la forestal. Indique claramente las variables de decisión del modelo y detalle explícitamente la función objetivo y cada una de las restricciones del modelo.

Variables de Decisión:

variables-forestal

Donde t=1,…,6 con t=1 Enero y t=6 Junio.

Función Objetivo: Minimizar los costos durante el período de planificación asociado a las remuneraciones, contratación, despido, compra y mantenimiento de inventario (respectivamente).

objetivo-forestal

Restricciones:

Balance de Trabajadores: Por ejemplo la cantidad de trabajadores disponibles al final del mes de Marzo para labores de cosecha son aquellos que terminaron trabajando al final del mes de Febrero, más los contratados en el mes de Marzo y menos los despedidos en Marzo.

balance-trabajadores

Satisfacer Demanda de Árboles: Donde D_{t} representa la demanda (parámetros) de árboles para el mes t.

demanda-arboles-restriccion

Capacidad Tala (Mano de Obra): Talar cada árbol requiere 4 horas hombre y un trabajador aporte 160 horas hombre en un mes. Luego, cada trabajador puede talar como máximo 40 árboles mensuales.

capacidad-personal-forestal

Capacidad Tala (Máquinas): Se puede talar como máximo 3.000 árboles mensuales dada la capacidad de las máquinas.

capacidad-tala-maquina

Capacidad Bodega: La bodega tiene una capacidad máxima de almacenamiento de 500 árboles.

capacidad-bodega-forestal

No Negatividad y Enteros: Se deben satisfacer las condiciones de enteros para las variables de decisión no negativas.

no-negatividad-forestal

Al implementar en Solver de Excel el modelo anterior se alcanza la solución óptima (celdas en color amarillo) con un valor óptimo de M$152.360.

solver-explotacion-forestal

Se recomienda al lector verificar que la solución alcanzada satisface las restricciones anteriormente expuestas. Notar adicionalmente que el plan óptimo actual no despide trabajadores durante la planificación y contrata trabajadores en Febrero y Abril (11 y 19, respectivamente), los mismos meses donde adicionalmente compra árboles (10 y 110) a la forestal cercana. Naturalmente al final de la planificación no existen incentivos para mantener árboles en bodega.

¿Quieres tener el archivo Excel con la implementación computacional de este ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]