Gestión de Operaciones

Método de Descomposición aplicado para un Pronóstico de Demanda

El Método de Descomposición corresponde a una metodología para la Proyección de la Demanda que como el nombre lo sugiere “descompone” el comportamiento de una Serie de Tiempo en tendencia, estacionalidad y ciclo, relacionando dichos componentes a través de la siguiente fórmula (multiplicativa):

Donde:

S= Valor pronosticado
T= Factor de tendencia
C= Componente cíclico
Y= Componente estacional
μ= Variación no sistemática

A continuación aplicaremos el Método de Descomposición para el pronóstico de la demanda de un producto sobre el cual tenemos información histórica para un período de 4 años (48 meses).

Paso 1: Se debe calcular el factor de estacionalidad, realizando un cuociente entre el valor pronosticado según el Promedio o Media Móvil Simple con n=12 y el valor real de la demanda. En la imagen a continuación se observa que el promedio móvil para Enero de 2010 corresponde al promedio simple de la demanda real desde Enero de 2009 a Diciembre de 2009. (Los resultados han sido aproximados a un decimal)

Paso 2: Se calcula el factor de estacionalidad promedio para cada período. Este procedimiento se facilita al trabajar con Tablas Dinámicas (Selecciona las columnas de los datos de la planilla según muestra la imagen a continuación, luego en el Menú de Excel ir a “Insertar” y en la esquina superior izquierda seleccionar Tabla Dinámica).

Al desplegarse el menú “Lista de campos de tabla dinámica” arrastramos el campo de Mes a Etiquetas de columnas y el campo Año a Etiquetas de fila. Por último arrastrar el campo (a/b)*100 a Valores seleccionando en la configuración de dicho campo “Promedio“.

La Tabla Dinámica tiene la siguiente forma donde se obtiene el factor de estacionalidad promedio:

Paso 3: Se ajusta cada factor promedio, multiplicándolo por el factor de estacionalidad K, calculado de:

En el ejemplo: K=(12*100)/(1.235,8)=0,971 (aproximado). Notar que los valores de la fila Indice Estacionalidad corresponde a la ponderación del Factor de Estacionalidad Promedio por el parámetro K.

Paso 4: Calcular la tendencia de la serie de tiempo ajustando los datos a una regresión lineal, donde la variable dependiente corresponde a la demanda (Y) y la variable independiente a los períodos (X).

Para este propósito se puede aplicar el procedimiento de forma muy sencilla en Excel a través de las siguientes alternativas:

1. Hacer un Gráfico de Línea con los valores de la demanda real como se muestra en la imagen a continuación:

Luego sobre el gráfico de línea con el mouse o teclado seleccionar con el botón derecho la opción “Agregar línea de tendencia”. Por defecto se ofrece la alternativa de tendencia lineal (no modificar) y debemos seleccionar las siguientes opciones:

Una vez realizado lo anterior obtendremos el gráfico que muestra el ajuste de la regresión y su ecuación. En nuestro ejemplo la regresión es: Y=98,038*X+15.157.

2. En la pestaña de “Datos” de Excel en la esquina superior derecha observaremos la opción “Análisis de datos” la cual debemos seleccionar, ingresando en el “Rango Y de entrada” los valores en la columna de la demanda real y en “Rango X de entrada” los valores de los períodos.

Luego presionar “Aceptar“, luego de lo cual se generará una nueva hoja en la planilla de cálculo con los resultados de la Regresión Lineal: (hemos marcado con color amarillo los resultados más relevantes en la aplicación del método de descomposición que son por supuesto coherentes con los que se obtienen al desarrollar el procedimiento del gráfico de línea).

Paso 5: Se calcula el factor cíclico de la serie histórica a partir de la siguiente expresión:

Por ejemplo para Enero de 2010 (dato 13) el Factor Cíclico es 0,973 (se obtiene dividiendo 15.994,4 en 98,038*13+15.157). En la imagen a continuación se muestra la fórmula en Excel que hemos utilizado considerando una aproximación de los resultados a 3 decimales.

Paso 6: Determinar el factor cíclico promedio para cada período. En este paso al igual que en el Paso 2 una Tabla Dinámica resulta de bastante ayuda:

Una vez completado el Paso 6 estamos en condiciones de realizar un pronóstico de demanda utilizando la fórmula presentada al inicio del artículo. Por ejemplo si queremos pronosticar la demanda de Enero de 2013 (período 49) el resultado sería el siguiente:

T(49) = 98,038*49+15157 = 19.960,862
C(Ene) = 0,966
Y(Ene) = 90,8/100
S(49) = 19.960,862 * (90,8/100) * 0,966 = 17.508,231

¿Te pareció interesante este artículo? ¿Desearías tener la planilla de cálculo Excel con los resultados y detalle de los procedimientos?

[sociallocker]https://www.dropbox.com/s/0wch166wbgki6pq/Plantilla%20M%C3%A9todo%20Descomposici%C3%B3n.xlsx?dl=0[/sociallocker]

Reglas de Prioridad para la Programación de n Trabajos en una Máquina

En la Programación de Trabajos en una máquina se pueden implementar distintas políticas o reglas de prioridad que en particular buscan mejorar el desempeño de la programación en un indicador en particular (minimizar la cantidad de trabajos atrasados, minimizar el atraso promedio, minimizar el atraso máximo, minimizar el tiempo de flujo promedio, etc), sin embargo, el makespan o tiempo requerido para completar los trabajos será idéntico independiente de la regla de prioridad.

A continuación mediante un ejemplo mostraremos la aplicación de las reglas de prioridad más comunes en la programación de 5 trabajos. Asumiremos para efectos prácticos que los tiempos de proceso y fechas de entrega se expresan en días y son fijos, es decir, no existe incertidumbre en cuanto a su duración:

FIFO (First In First Out)

Es una de las reglas de prioridad más utilizada y considera atender los trabajos según orden de llegada. En nuestro ejemplo consideraremos que los trabajos fueron recibidos en el siguiente orden: A, B, C, D, E.

Tiempo de Flujo Promedio = 245[días]/5[trabajos]=49[días/trabajo]
Tiempo de Atraso Promedio = 108[días]/5[trabajos]=21,6[días/trabajo]
Atraso Máximo = 40[días]
Número de Trabajos Atrasados = 3[trabajos]

LIFO (Last In First Out)

Se atienden los trabajos en orden inverso al orden de llegado. En este caso E, D, C, B y finalmente A.

Tiempo de Flujo Promedio = 235[días]/5[trabajos]=47[días/trabajo]
Tiempo de Atraso Promedio = 73[días]/5[trabajos]=14,6[días/trabajo]
Atraso Máximo = 30[días]
Número de Trabajos Atrasados = 4[trabajos]

SPT (Shortest Processing Time)

Los trabajos se procesan en orden creciente de tiempo de proceso.

Tiempo de Flujo Promedio = 180[días]/5[trabajos]=36[días/trabajo]
Tiempo de Atraso Promedio = 50[días]/5[trabajos]=10[días/trabajo]
Atraso Máximo = 35[días]
Número de Trabajos Atrasados = 3[trabajos]

LPT (Largest Processing Time)

Los trabajos se procesan en orden decreciente de tiempo de proceso.

Tiempo de Flujo Promedio = 300[días]/5[trabajos]=60[días/trabajo]
Tiempo de Atraso Promedio = 133[días]/5[trabajos]=26,6[días/trabajo]
Atraso Máximo = 58[días]
Número de Trabajos Atrasados = 4[trabajos]

EDD (Earliest Due Date)

Los trabajos se atienden por fecha de entrega.

Tiempo de Flujo Promedio = 215[días]/5[trabajos]=43[días/trabajo]
Tiempo de Atraso Promedio = 55[días]/5[trabajos]=11[días/trabajo]
Atraso Máximo = 30[días]
Número de Trabajos Atrasados = 2[trabajos]

Por supuesto existen otros criterios que permiten secuenciar “n“ trabajos en una máquina y cada uno de ellos se debe evaluar en su merito. En nuestro ejemplo podemos apreciar lo que generalmente ocurre en este tipo de procedimientos respecto a que es difícil encontrar una regla de prioridad que en términos comparativos sea mejor que las restantes en todos los indicadores.

En consecuencia, el tomador de decisiones deberá privilegiar aquel indicador que en su caso en particular resulte ser más crítico. Por ejemplo, si se busca la menor cantidad de trabajos atrasados podría seleccionar EDD, sin embargo, si lo más importante es el tiempo de flujo promedio podría seleccionar SPT. Notar finalmente que independiente de la regla de prioridad utilizada el makespan es de 80[días].

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):