Minientrada archivos - Página 5 de 8 - Gestión de Operaciones

Problema de la Dieta en Programación Lineal resuelto con Solver de Excel

Una de las aplicaciones clásicas de la Programación Lineal es el Problema de la Dieta. El objetivo es seleccionar un conjunto de alimentos dados que permitan satisfacer ciertos requerimientos nutricionales y preferencias y que adicionalmente tenga un costo mínimo.

En este contexto en el Servidor NEOS se puede encontrar un conjunto de antecedentes que permiten comprender el contexto histórico del Problema de la Dieta y cómo se puede abordar de forma eficiente a través de modelos de optimización. Al igual que varias de las aplicaciones de la Investigación de Operaciones este problema tiene un origen militar.

Para efectos de este tutorial y con el objetivo de ilustrar esta aplicación consideremos el siguiente listado de alimentos con su perfil nutricional y costo monetario:

Se desea proponer una dieta que contenga al menos 2.000 (Kcal) , al menos 55 gramos de proteína y 800 (mg) de calcio. Adicionalmente para garantizar cierta variedad en la dieta se establece límites de porciones por día en los alimentos. Con esta información se requiere encontrar la dieta que tenga el menor costo asociado y permita satisfacer los requerimientos anteriores.

Para ello definimos el siguiente modelo de Programación Lineal:

1. Variables de Decisión: Xi : Porciones de alimentos a consumir durante el día del alimento i (Con i=1 ==> Avena, …. i=6 ==> Porotos).

2. Función Objetivo: Minimizar 30X1+240X2+130X3+90X4+200X5+60X6

3. Restricciones:

Mínimo de Calorias (KCal): 110X1+205X2+160X3+160X4+420X5+260X6 >= 2.000
Mínimo de Proteínas: 4X1+32X2+13X3+8X4+4X5+14X6 >= 55
Mínimo de Calcio: 2X1+12X2+54X3+285X4+22X5+80X6 >= 800
Variedad de la Dieta: X1<=4 X2<=3 X3<=2 X4<=8 X5<=2 X6<=2
No Negatividad: Xi>=0 Para todo i.

La implementación de este modelo en Solver de Excel para obtener su solución óptima y valor óptimo se muestra en el siguiente tutorial:

La Solución Óptima es X1=4, X2=0, X3=0, X4=2,08, X5=1,68, X6=2 y el Valor Óptimo (costo de la dieta) es $764,07.

Como el modelo es de Programación Lineal se permiten valores fraccionarios para las variables de decisión. Por tanto si buscamos solo valores enteros para las variables de decisión en ese caso debemos definir un modelo de Programación Entera el cual revisamos en el siguiente artículo: Problema de la Dieta en Programación Entera resuelto con Solver de Excel.

Cantidad Económica de Pedido (EOQ) con Descuentos por Cantidad

Uno de los supuestos del modelo de Cantidad Económica de Pedido (o EOQ según sus siglas en inglés) es que el costo de adquisición unitario es independiente del tamaño del pedido, sin embargo, este supuesto es factible de flexibilizar debido a que en muchos casos es razonable asumir que se puede acceder a un determinado descuento por unidad en la medida de pedidos de tamaño mayor.

Para determinados productos, los proveedores suelen ofrecer una escala de descuentos dependiendo del tamaño del pedido. Este tipo de estrategia de venta es frecuentemente utilizado por mayoristas y distribuidores que buscan con esto tener una mayor Rotación de Inventario y en consecuencia disminuir los Días de Inventario (con la correspondiente disminución de los costos de almacenamiento del inventario). Adicionalmente, la escala de descuentos suele estar previamente tabulada y accesible para el comprador.

Ejemplo EOQ con Descuentos por Cantidad

A continuación tomaremos nuevamente los datos del ejemplo de EOQ analizados en el tutorial del Cálculo de la Cantidad Económica de Pedido con WINQSB, sin embargo, en esta oportunidad consideraremos que el costo de almacenamiento anual se puede representar como un porcentaje del costo de adquisición.

D: Demanda Anual = 6.000 unidades
S: Costo de Emisión = $750
H: Costo de Almacenamiento Anual (unitario) = 10% del costo de adquisición (i)

El precio unitario a pagar dependerá del tamaño del pedido según muestra la siguiente tabla:

Para poder determinar el tamaño de pedido que minimiza los costos totales se debe evaluar cada uno de los tramos de precios.

Notar que H=i*C, es decir, se considera que el costo de almacenar un producto se puede representar como un porcentaje de su costo de adquisición (compra). De esta forma, al aumentar los descuentos (y en consecuencia disminuir el precio de compra) el costo unitario de almacenamiento representado por H=i*C disminuirá y generará un incentivo a pedidos de mayor tamaño (dado que el denominador de la formula a continuación disminuye en magnitud).

En el primer tramo (sin descuento) el tamaño de pedido recomendado es de 150 unidades.

En el segundo tramo el tamaño de pedido óptimo según EOQ es de 160,3 unidades, sin embargo, dicho pedido es insuficiente para acceder al precio descontado de $3.500 por tanto para el tramo 2 el pedido óptimo se aproxima a 200 unidades.

Finalmente para el tercer tramo el tamaño del pedido es también insuficiente para acceder al precio unitario de $3.200 por tanto se aproxima a 300 unidades.

En resumen, para el tramo 1 ==> Q=150[u/ped]; tramo 2 ==> Q=200[u/ped]; tramo 3 ==> Q=300[u/ped].

Los fórmula de Costos Totales del Modelo EOQ es: CT=C*D+(D/Q)*S+(Q/2)*H

Tramo 1: CT=$4.000*6.000+(6.000/150)*$750+(150/2)*10%*$4.000=$24.060.000
Tramo 2: CT=$3.500*6.000+(6.000/200)*$750+(200/2)*10%*$3.500=$21.057.500
Tramo 3: CT=$3.200*6000+(6.000/300)*$750+(300/2)*10%*$3.200=$19.263.000

El menor costo se alcanza en el tramo 3 y la cantidad de pedido que minimiza los costos totales será de 300 unidades. Es importante destacar que no necesariamente el tramo con el menor precio unitario será el que tenga el menor costo asociado y por tanto el resultado obtenido en este ejemplo no se puede extrapolar para cualquier caso.

Cómo calcular Gráficamente el Precio Sombra de una Restricción

El Precio Sombra de una restricción en Programación Lineal indica cuánto cambia el valor de la función objetivo (óptimo) ante una variación marginal del lado derecho de una restricción. Se asume que el resto de los parámetros del modelo permanecen constantes. De antemano es conveniente señalar que el Precio Sombra puede ser positivo, cero o negativo y en el Blog iremos discutiendo estos distintos escenarios.

Para obtener los Informes de Sensibilidad de un modelo de Programación Lineal se puede hacer uso de herramientas computacionales como Solver de Excel, sin embargo, en esta oportunidad nos enfocaremos en el cálculo del precio sombra de una restricción en forma gráfica, lo que nos ayudará más adelante a entender los conceptos que fundamentan los resultados de Solver.

Cálculo del Precio Sombra de una Restricción con el Método Gráfico

A continuación calcularemos el precio sombra de una restricción del siguiente modelo de Programación Lineal:

La solución óptima de este modelo es X=100 e Y=350 con valor óptimo V(P)=3.100 según su resolución gráfica con Geogebra o su resolución con Solver de Excel. El siguiente diagrama muestra la solución óptima obtenida gráficamente en el vértice C, que corresponde a la intersección de la restricción 1 (R1: color rojo) y la restricción 3 (R3: color gris), siendo ésta una solución básica factible óptima.

Supongamos que deseamos saber cuánto cambiará el valor óptimo (respecto a su valor actual) si aumenta en una unidad el lado derecho de la restricción 1 pero sin resolver nuevamente el problema. El precio sombra nos permite dar respuesta a dicha interrogante y permite anticipar el nuevo valor óptimo ante una variación marginal del lado derecho de una restricción.

Un variación marginal de un lado derecho implica que la nueva solución óptima se seguirá encontrando con las actuales restricciones activas, es decir, aquellas que se cumplen en igualdad en el óptimo (esto es se conserva la base óptima).

En el caso de la restricción 1 si aumentamos su lado derecho, ésta se desplazará en forma paralela hacia arriba. Si buscamos garantizar que la nueva solución óptima aún se encontrará con R1 y R3 activas llegaremos al vértice donde actualmente se interceptan la R2 y R3 que corresponde a la coordenada X=166,67 e Y=350 (ésta será la máxima variación).

En forma análoga si disminuimos el lado derecho de la restricción 1 y buscamos mantener R1 y R3 activas en el nuevo óptimo, el último punto donde se garantiza esto es el vértice B cuyas coordenadas son X=0 e Y=350 (ésta será la menor variación). Con esta información calculamos el precio sombra de la restricción 1:

Este precio sombra es válido si el lado derecho de la restricción 1 (actualmente b1=1.600) varía entre [1.400,1.733,33]. Por ejemplo, si el lado derecho de R1 aumenta de 1.600 a 1.700 el nuevo valor óptimo será V(P)=3.100+100*1,5=3.250. Análogamente si el lado derecho de R1 disminuye de 1.600 a 1.550 el nuevo valor óptimo será V(P)=3.100-50*1,5=3.025. (Se recomienda corroborar estos resultados gráficamente con TORA o IORTutorial). Notar que si la variación del lado derecho de la restricción 1 está por fuera del intervalo [1.400,1.733,33], no se puede utilizar el precio sombra para predecir cuál será el nuevo valor óptimo.

En un próximo análisis complementaremos el cálculo del precio sombra de las restricciones 2 y 3 en conjunto con otros Análisis de Sensibilidad en la resolución de modelos de programación lineal. Hasta entonces!

Preguntas Frecuentes (Procesos): Capacidad, Tiempo de Flujo, Tiempo de Ciclo

Para desarrollar un análisis cuantitativo de procesos productivos (proceso de transformación de insumos en productos o servicios) generalmente se hace referencia a indicadores de gestión que permiten evaluar el desempeño y eficiencia de dicho proceso en el tiempo. Algunos de los indicadores más utilizados son capacidad, tiempo de flujo y tiempo de ciclo. A continuación los definimos brevemente para luego aplicarlos a un ejemplo tipo:

Capacidad de un Proceso: corresponde a la tasa máxima de producción, es decir, cuántas unidades en un intervalo de tiempo un proceso (sistema) puede producir.
Tiempo de Flujo: es el tiempo de producción, es decir, es el tiempo mínimo total que una unidad se demora en pasar por el sistema.
Tiempo de Ciclo: es el tiempo promedio entre la producción de dos unidades consecutivas.

A continuación presentaremos un proceso de producción sencillo de fabricación de muebles.

La Capacidad del Proceso es de 10 [u/hora]
El Tiempo de Flujo (para la primera unidad) es de 19 [min] (5+8+6)
El Tiempo de Ciclo del proceso es de 6 [min] (si se producen 10[u/hora] en promedio se produce una cada 6[min])

Las siguientes preguntas frecuentes nos permitirán entender mejor los conceptos relacionados con los procesos productivos:

1. ¿Si se dobla la capacidad de la actividad cuello de botella entonces se doblará la capacidad del proceso?.

Falso. Esto no es cierto en todos los casos. En nuestro ejemplo la actividad cuello de botella es Pintar y su capacidad es de 10[u/hora] (recordar que la capacidad conjunto de las etapas Ensamblar es de 13,5[u/hora]). Si doblamos la capacidad de Pintar su nueva capacidad será ahora 20[u/hora] y ahora el cuello de botella es Pulir. La nueva capacidad del proceso es de 12[u/hora] lo que no es el doble de la capacidad original.

2. ¿En una hora de trabajo se producirán exactamente las unidades que indica la capacidad del proceso?.

Falso. De otra forma en la primera hora de trabajo no se alcanzan a producir las 10[u/hora] que indica la capacidad del proceso. ¿Por qué?. La razón es que la(s) primera(s) unidad(es) se demoran más que las unidades cuando el proceso se encuentra estabilizado. Por ejemplo, la primera unidad sale del sistema a los 19[min] (tiempo de flujo), la segunda unidad sale a los 26[min] (7 minutos después de la primera), la tercera, cuarta, quinta, etc, unidades salen cada 6[min] (tiempo de ciclo) lo que permite anticipar que las unidades que sigan saldrán en promedio cada 6[min]. La Carta Gantt a continuación permite visualizar el proceso en su primera hora donde queda de manifiesto que no se alcanzan a procesar en forma completa las 10 unidades.

3. ¿Cómo determinar entonces cuántas unidades completas se alcanzan a procesar en la primera hora de trabajo?.

Para ello utilizamos la siguiente fórmula:

T(N)=TF+(1/Cap)*(N-1)

En nuestro ejemplo: 60[min]=19[min]+6[min/u]*(N-1) ==> N=7,833[u] ~ 7[u]

Es decir, se alcanzan a producir en forma completa 7 unidades en la primera hora. Notar que esto no contradice la capacidad del proceso. Si tomamos un horizonte de tiempo más amplio (2 horas, 3 horas, etc) la cantidad de unidades que se puedan procesar en promedio en una hora convergerá a la capacidad del proceso que es de 10[u/hora]. El motivo de lo anterior es que cada vez el efecto de las primeras unidades (hasta la estabilización del proceso) es menor.

Regla de Johnson en la Programación de n Trabajos en 2 Máquinas

Una de las variantes de la Programación de Tareas es la asignación de 2 máquinas al procesamiento de n trabajos siguiendo un orden común. Una estrategia a aplicar es la Regla o Método de Johnson con el objetivo de minimizar el tiempo requerido para finalizar los n trabajos en el taller de trabajo (conocido también como makespan).

El Método de Johnson considera los siguientes pasos:

Se anota el tiempo de operación de cada trabajo en ambas máquinas.
Se elige el tiempo más breve.
Si el tiempo breve es para la primera máquina, se hace el primer trabajo; si es para la segunda máquina, se hace el trabajo al último. En caso de empate (igualdad de tiempo) se hace el trabajo en la primera máquina.
Repetir los pasos 2 y 3 con los restantes trabajos hasta completar la programación.

Ejemplo Método de Johnson

A continuación se presenta un ejemplo que considera 7 trabajos a programar en 2 máquinas. Para que un trabajo sea terminado debe pasar primero por la máquina A y luego por la máquina B. Nos interesa aplicar la Regla de Johnson para generar una asignación que tenga asociado el menor tiempo posible (en minutos) en procesar los 7 trabajos:

Paso 1: Listo. Tiempos de procesamiento disponibles en la tabla.

Paso 2, 3 y 4: Se elige el tiempo más breve (Trabajo 4 Máquina B). Como el tiempo más breve es en la segunda máquina, el Trabajo 4 se hace al final. El siguiente tiempo más breve es en el Trabajo 7 Máquina A y se programa en primer lugar. Luego el Trabajo 6 y 1 tienen el tiempo más breve que sigue (10), sin embargo, dado el empate se hace el trabajo en la Máquina A y por tanto se programa el Trabajo 6 en segundo lugar. Ahora tomamos el Trabajo 1 y siendo su menor tiempo en la Máquina B se programa en penúltimo lugar. Sigue el Trabajo 2 el cual se programa en tercer lugar. Posteriormente el Trabajo 3 en antepenúltimo lugar y finalmente el Trabajo 5 en cuarto lugar.

La secuencia óptima luego de aplicar la Regla de Johnson sería: 7-6-2-5-3-1-4. Luego, para determinar el tiempo requerido para completar los 7 trabajos se puede construir una Carta Gantt que muestre dicha planificación. El tiempo requerido es de 119 minutos (makespan).

El software WINQSB entre sus distintas aplicaciones nos permite generar una programación de los trabajos siguiendo el Método de Johnson según se muestra en el siguiente tutorial: