What'sBest! Archivos - Gestión de Operaciones

Programación Lineal (Método Gráfico)

El Método Gráfico (resolución gráfica) constituye una excelente alternativa de representación y resolución de modelos de Programación Lineal que tienen 2 variables de decisión. Para estos efectos existen herramientas computacionales que facilitan la aplicación del método gráfico como los softwares TORA, IORTutorial y Geogebra, los cuales se pueden consultar en detalle en Cómo Resolver Gráficamente un Modelo de Programación Lineal con TORA, Cómo Resolver Gráficamente un Modelo de Programación Lineal con IORTutorial y Cómo Resolver Gráficamente un modelo de Programación Lineal con Geogebra, respectivamente. En este contexto a continuación presentamos un compendio de ejercicios de Programación Lineal resueltos a través del método gráfico.

Ejercicios Resueltos del Método Gráfico en Programación Lineal

Ejercicio N°1: Una empresa vitivinícola ha adquirido recientemente un terreno de 110 hectáreas. Debido a la calidad del sol y el excelente clima de la región, se puede vender toda la producción de uvas Sauvignon Blanc y Chardonay. Se desea conocer cuánto plantar de cada variedad en las 110 hectáreas, dado los costos, beneficios netos y requerimientos de mano de obra según los datos que se muestran a continuación:

Suponga que se posee un presupuesto de US$10.000 y una disponibilidad de 1.200 días hombre durante el horizonte de planificación. Formule y resuelva gráficamente un modelo de Programación Lineal para este problema. Detalle claramente el dominio de soluciones factibles y el procedimiento utilizado para encontrar la solución óptima y valor óptimo.

Variables de Decisión:

$X_{1}$ : Hectáreas destinadas al cultivo de de Sauvignon Blanc
$X_{2}$ : Hectáreas destinadas al cultivo de Chardonay

Función Objetivo:

Maximizar $50X_{1}+120X_{2}$

Restricciones:

$X_{1}+X_{2}\leq 110$
$100X_{1}+200X_{2}\leq 10.000$
$10X_{1}+30X_{2}\leq 1.200$
$X_{1},X_{2}\geq 0$

Donde las restricciones están asociadas a la disponibilidad máxima de hectáreas para la plantación, presupuesto disponible, horas hombre en el período de planificación y no negatividad, respectivamente.

El siguiente gráfico muestra la representación del problema de la empresa vitivinícola. El área achurada corresponde al dominio de soluciones factibles, donde la solución básica factible óptima se alcanza en el vértice C, donde se encuentran activas las restricciones de presupuestos y días hombre. De esta forma resolviendo dicho sistema de ecuaciones se encuentra la coordenada de la solución óptima donde $X_{1}=60$ y $X_{2}=20$ (hectáreas). El valor óptimo es $V(P)=50(60)+120(20)=5.400$ (dólares).

Ejercicio N°2: Un taller tiene tres (3) tipos de máquinas A, B y C; puede fabricar dos (2) productos 1 y 2, todos los productos tienen que ir a cada máquina y cada uno va en el mismo orden: Primero a la máquina A, luego a la B y luego a la C. La siguiente tabla muestra:

Las horas requeridas en cada máquina, por unidad de producto
Las horas totales disponibles para cada máquina, por semana
La ganancia por unidad vendida de cada producto

Formule y resuelva a través del método gráfico un modelo de Programación Lineal para la situación anterior que permite obtener la máxima ganancia para el taller.

Variables de Decisión:

$X_{1}$ : Unidades a producir del Producto 1 semanalmente
$X_{2}$ : Unidades a producir del Producto 2 semanalmente

Función Objetivo:

Maximizar $X_{1}+1,5X_{2}$

Restricciones:

$2X_{1}+2X_{2}\leq 16$
$X_{1}+2X_{2}\leq 12$
$4X_{1}+2X_{2}\leq 28$
$X_{1},X_{2}\geq 0$

Las restricciones representan la disponibilidad de horas semanales para las máquinas A, B y C, respectivamente, además de incorporar las condiciones de no negatividad.

Para la resolución gráfica de este modelo utilizaremos el software GLP cual abordamos en el artículo Problema de Planificación Forestal resuelto con Graphic Linear Optimizer (GLP). El área de color verde corresponde al conjunto de soluciones factibles y la curva de nivel de la función objetivo que pasa por el vértice óptimo se muestra con una línea punteada de color rojo.

La solución óptima es $X_{1}=4$ y $X_{2}=4$ con valor óptimo $V(P)=1(4)+1,5(4)=10$ que representa la ganancia para el taller.

Ejercicio N°3: Una compañía elabora dos productos diferentes. Uno de ellos requiere por unidad 1/4 de hora en labores de armado, 1/8 de hora en labores de control de calidad y US$1,2 en materias primas. El otro producto requiere por unidad 1/3 de hora en labores de armado, 1/3 de hora en labores de control de calidad y US$0,9 en materias primas. Dada las actuales disponibilidades de personal en la compañía, existe a lo más un total de 90 horas para armado y 80 horas para control de calidad, cada día. El primer producto descrito tiene un valor de mercado (precio de venta) de US$9,0 por unidad y para el segundo este valor corresponde a US$8,0 por unidad. Adicionalmente se ha estimado que el límite máximo de ventas diarias para el primer producto descrito es de 200 unidades, no existiendo un límite máximo de ventas diarias para el segundo producto.

Formule y resuelva gráficamente un modelo de Programación Lineal que permita maximizar las utilidades de la compañía.

Variables de Decisión:

$X_{1}$ : Unidades a producir diariamente del Producto 1
$X_{2}$ : Unidades a producir diariamente del Producto 2

Función Objetivo:

Maximizar $(9-1,2)X_{1}+(8-0,9)X_{2}=7,8X_{1}+7,1X_{2}$

Restricciones:

$\frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90$
$\frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80$
$X_{1}\leq 200$
$X_{1},X_{2}\geq 0$

La primera restricción representa las limitantes de horas de armado diariamente. La segunda restricción la disponibilidad de horas para labores de control de calidad (también diariamente). La tercera restricción establece una cota superior para la producción y ventas diarias del Producto 1. Adicionalmente se incluyen las condiciones de no negatividad para las variables de decisión.

El dominio de soluciones factibles tiene 5 vértices que corresponden a los candidatos a óptimos del problema. En particular el vértice óptimo es D de modo que la solución óptima es $X_{1}=200$ y $X_{2}=120$ con valor óptimo $V(P)=7,8(200)+7,1(120)=2.412$ que corresponde a la utilidad máxima para la empresa.

Importante: A la fecha de esta publicación disponemos de más de 70 artículos relativos a la Programación Lineal los cuales recomendamos revisar, donde se aborda la resolución gráfica de este tipo de modelos como también la resolución a través de algoritmos como el Método Simplex y la implementación computacional con herramientas como Solver, What’sBest! y OpenSolver, entre otras.

En el siguiente tutorial de nuestro canal de Youtube se explica un ejemplo adicional con todos los elementos del método gráfico en Programación Lineal:

Como resolver un modelo de Programación Lineal con LINGO 14.0

LINGO es un popular software de optimización matemática para uso tanto académico como empresarial desarrollado por LINDO Systems Inc (quienes desarrollaron What’sBest!) que provee una alternativa para enfrentar el problema de modelamiento matemático e implementación computacional en una plataforma distinta a Excel (en contraste a los complementos que han tenido un lugar preferente en nuestro sitio como Solver, Premium Solver Pro, What’sBest! y OpenSolver).

En el siguiente artículo detallaremos cómo descargar e instalar el programa LINGO para luego utilizar éste en la resolución de un modelo de Programación Lineal con 2 variables de decisión. Dado lo anterior consideremos el siguiente problema:

Paso 1: Descarga e instalar la última versión disponible de LINGO desde la sección de descargas del sitio web de LINDO Systems. Se debe tener especial atención en seleccionar de forma correcta la versión compatible con nuestro sistema operativo (Windows o Linux) y la cantidad de bits asociado a dicho sistema. Para verificar este último aspecto te recomendamos leer el artículo “Cómo descargar e instalar la versión de Prueba de What’sBest! 11.1 en Excel 2010”. En dicho artículo se detalla adicionalmente el procedimiento de registro y activación de la licencia.

Paso 2: Una vez instalado LINGO en nuestro computador ejecutamos el programa y luego implementamos el modelo de optimización. El software es compatible con distintos tipos de sintaxis las cuales iremos abordando en próximos artículos en el Blog). Por el momento a continuación detallamos una notación intuitiva que nos permite representar nuestro ejemplo:

Una vez incorporado definido el problema ejecutamos el botón “Solve”:

Paso 3: Se obtienen los resultados para el modelo. La ventana “Lingo 14.0 Solver Status” detalla las características del problema: LP (Programación Lineal) con Valor Óptimo de 2.025.

El detalle de los resultados se aprecia en el informe de respuestas que genera el programa de forma automática. La salida computacional se muestra a continuación:

La Solución Óptima es A=60 y C=27,5 con Valor Óptimo V(P)=2.025. Notar adicionalmente que los resultados son consistentes con los que obtendríamos de utilizar Solver para este ejemplo y haciendo uso del Informe de Confidencialidad (Sensibilidad).

Con color verde destacamos el precio sombra de cada una de las restricciones del problema. Estos valores se identifican en la columna etiquetada “Dual Price” en el informe de resultados de LINGO en las Filas (Row) 2, 3 y 4, respectivamente.

Una representación gráfica del problema anterior con Geogebra nos permite corroborar los resultados anteriores de forma intuitiva, por ejemplo la restricción C<=50 no está activa, en consecuencia su precio sombra es igual a cero.

Cómo descargar e instalar OpenSolver en Excel 2010

OpenSolver es una alternativa gratuita a Premium Solver Pro y What’sBest! que permite resolver modelos de optimización haciendo uso de Excel. Este complemento fue desarrollado y actualmente mantenido por Andrew Mason y estudiantes del departamento de ciencias de la ingeniería de la Universidad de Auckland (Nueva Zelanda). En el siguiente artículo mostraremos cómo descargar e instalar OpenSolver en un computador que utiliza Windows 7 Home Premium como sistema operativo y Microsoft Office Professional Plus 2010.

Paso 1: Descargar OpenSolver21 (~~A la fecha de este artículo la versión 2.1 del 6 de Septiembre de 2012 es la más reciente~~).

Actualización: La última versión disponible a Octubre de 2015 es la edición 2.7.1 con fecha de lanzamiento 28 de Junio de 2015. Para descargar dicha versión se puede acceder directamente a la Página de Descarga e Instalación de OpenSolver.

Paso 2: Descomprimir el archivo ZIP de preferencia en una carpeta o en un lugar a elección.

Paso 3: Abrir el archivo «OpenSolver.xlam» (es aquel con el icono de Excel y un pequeño cuadrado color rojo en la esquina superior derecha).

Paso 4: Es probable que Excel solicite tu autorización para ejecutar el programa. En este caso debes seleccionar «Habilitar macros».

Una vez concluidos los pasos anteriores OpenSolver debería estar disponible en la pestaña de Datos en Excel (esquina superior derecha) tal como se muestra a continuación. En efecto se podrá encontrar a la derecha del acceso a Solver.

El complemento estará disponible hasta cerrar Excel. Si se desea que OpenSolver este siempre disponible al ejecutar Excel se deben copiar todos los archivos que están incluidos en el archivo comprimido (ZIP) de la instalación (aquellos que se pueden observar en la imagen del Paso 3) en el directorio de «add-in» de Excel. La ruta típica suele ser: C:/Documents and Settings/»user name»/Application Data/Microsoft/Addins (se debe tener en cuenta que el acceso puede cambiar dependiendo de la versión de Windows que se este utilizando).

Fuerza Laboral Exacta aplicada a un Plan Maestro de la Producción (PMP)

En el desarrollo de un Plan Maestro de la Producción (PMP) resulta de interés el análisis de estrategias puras, es decir, enfoques en los cuales se utiliza una variable de ajuste de forma exclusiva para responder a la demanda pronosticada. Si bien en la práctica lo usual es utilizar una combinación de alternativas para lograr cumplir con los requerimientos (estrategia mixta), el estudio de las estrategias puras ayuda a comprender las ventajas y desventajas asociadas a la utilización de una determinada variable de ajuste.

En este artículo buscaremos mediante la fuerza laboral, en particular, mediante la contratación y despido de trabajadores responder de forma exacta a las necesidades proyectadas. Para ello es necesario recordar los siguientes antecedentes de operación detallados en la Formulación y Resolución de un Modelo de Programación Entera para un Plan Maestro de la Producción (Cabe destacar que en la resolución computacional de alcanza el mínimo costo de US$1.468.400 al utilizar What’sBest!)

Costo de Contratar un Trabajador: US$1.000
Costo de Despedir un Trabajador: US$1.800
Costo de Almacenamiento Unitario Mensual: US$10
Inventario Inicial: 500 unidades
Costo Remuneración (Sueldo) de un Trabajador al Mes: US$600
Número de Trabajadores al Inicio de la Planificación: 100
Unidades de Producto producidas por un Trabajador al Mes: 50

La utilización de la fuerza laboral o mano de obra exacta evita la acumulación de inventario contratando y despidiendo trabajadores para cumplir con la demanda estimada de cada período (mes). En este contexto al disponer de un inventario inicial de 500 unidades, sólo se necesitan fabricar 3.500 unidades en el mes de Enero. Para lograr este nivel de producción se necesitan 70 trabajadores (recordar que cada trabajador produce 50 unidades al mes) y por tanto se despiden 30 trabajadores.

Continuando con el procedimiento en el mes de Febrero se necesitan 4.500 unidades (ahora no se dispone de inventario que haya quedado a fines de Enero) y por tanto es necesario disponer de 90 trabajadores. Por ello contratamos 20 trabajadores.

En Marzo se necesitan 4o trabajadores adicionales de modo de contar con 130 en operación para lograr un nivel de producción de 6.500 unidades.

Así sucesivamente se continua con la evaluación hasta completar el período de planificación. La evaluación económica de esta estrategia pura se presenta a continuación:

El costo total asciende a US$1.627.200 lo cual es US$158.800 mayor al alcanzado mediante la resolución computacional. Sin embargo, no sólo el costo adicional es un factor en desmedro de esta alternativa, sino también se pueden mencionar los siguientes factores:

La alta rotación de personal puede crear un clima de inestabilidad laboral al interior de la empresa lo cual afecta la moral de los trabajadores y su productividad. Adicionalmente es una fuente potencial de conflictos con los sindicatos.
Si bien la evaluación económica no lo considera es importante tener en cuenta que un trabajador nuevo requerirá de un tiempo de aprendizaje luego del cual podrá lograr una productividad equivalente con un trabajador que lleva más tiempo en operación en la empresa.
Al no acumular inventarios el plan de fuerza laboral exacta es propenso a generar quiebres de stock cuando la demanda real supere en magnitud a la demanda pronosticada.

Formulación un modelo de Programación Entera para un Plan Maestro de la Producción (PMP)

La Planificación Agregada y el Plan Maestro de la Producción (PMP o MPS según sus siglas en inglés Master Production Schedule) son metodologías ampliamente utilizadas hoy en día en empresas de manufactura para planificar las necesidades de producción de una serie de productos, de modo de responder a un pronóstico de demanda a través de los recursos productivos que se disponen.

En este contexto, la evidencia empírica muestra que existen diversas estrategias que se pueden utilizar para enfrentar la demanda, cada una de las cuales se puede valorar en términos de costos pero también a través de una serie de criterios cualitativos que por su naturaleza son difíciles de estimar en una unidad monetaria.

A continuación se presenta un gráfico con el Pronóstico de Demanda de un producto para el cual propondremos un modelo de optimización que permita cumplir con dichos requerimientos, minimizando los costos asociados a la utilización de los recursos productivos:

Se puede apreciar que la demanda presenta una estacionalidad marcada donde al inicio y final del año los valores son menores a la demanda de un mes promedio (7.817 unidades).

En contraste con lo anterior en los meses de Junio, Julio y Agosto se presenta un peak de demanda, superando en magnitud claramente lo que correspondería a la demanda de un mes promedio. Adicionalmente consideremos los siguientes antecedentes de operación:

Costo de Contratar un Trabajador: US$1.000
Costo de Despedir un Trabajador: US$1.800
Costo de Almacenamiento Unitario Mensual: US$10
Inventario Inicial: 500 unidades
Costo Remuneración (Sueldo) de un Trabajador al Mes: US$600
Número de Trabajadores al Inicio de la Planificación: 100
Unidades de Producto producidas por un Trabajador al Mes: 50

La pregunta inmediata es: ¿Cómo responder a la demanda pronosticada durante el período de planificación al menor costo posible?. Algunas posibles respuestas son:

Fuerza Laboral Exacta: Esto es mediante contratación y despido de trabajadores para responder de forma exacta a las necesidades de cada mes. Con esta alternativa se busca evitar la acumulación de inventario.

Acumulación y Liquidación de Inventario: Producir en mayor volumen en los meses de menor demanda de modo de acumular inventario para enfrentar los requerimientos adicionales de los meses de mayor demanda. Si se considera adecuado se puede utilizar esta alternativa buscando no afectar el tamaño de la fuerza laboral.

Por cierto también se puede utilizar una estrategia mixta o híbrida que mezcle por ejemplo características de las 2 opciones presentadas anteriormente. Este enfoque generalmente es el que permite alcanzar menores costos.

Adicionalmente cabe destacar que en un Plan Maestro de la Producción (PMP) se podrían considerar otras alternativas o variables de ajuste no consideradas en este ejemplo como la utilización de trabajadores en tiempo extraordinario, la subcontratación parcial de la producción, la eventual postergación de demanda, entre otras opciones.

Luego, en relación a los antecedentes de operación previamente detallados, un modelo de Programación Entera para el Plan Maestro de la Producción es:

1. Variables de Decisión:

2. Función Objetivo:

3. Restricciones:

Satisfacer la Demanda (Balance de Inventario): Donde Dt corresponde a la demanda pronosticada para el mes t (parámetros).

Balance Mano de Obra: La cantidad de trabajadores en operación en cada período corresponde a los trabajadores disponibles al final del mes anterior, más los contratados y menos los despedidos en el mes en curso.

Capacidad de Producción: La producción de cada mes se ve limitada por la disponibilidad de trabajadores y el rendimiento mensual (en unidades de producto) que cada uno de éstos tiene.

No Negatividad e Integralidad: Todas las variables de decisión deben adoptar valores no negativos y adicionalmente ser enteras.

El modelo anterior se puede implementar con Solver y What’sBest! obteniendo los siguientes resultados:

Implementación Computacional en Solver: Se alcanza una solución factible con valor en la función objetivo de US$1.468.700.

El detalle de la resolución la puedes revisar en el siguiente tutorial de nuestro canal de Youtube:

Implementación Computacional con What’sBest!: Se alcanza una solución factible con valor en la función objetivo de US$1.468.400, la cual es ligeramente inferior en costos a la solución obtenida con Solver.

La carga del modelo en What’sBest! y la obtención de los resultados anteriores se puede revisar en el siguiente tutorial de nuestro canal de Youtube:

[sociallocker]Problema PMP www.gestiondeoperaciones.net[/sociallocker]