método de descomposición Archivos - Gestión de Operaciones

Método de Descomposición de Benders

La Descomposición de Benders es, como su nombre lo dice, un Método de Descomposición. La idea de este método es bastante simple: dividir para conquistar. El objetivo es literalmente descomponer el problema en dos partes: El Master Problem (Problema Maestro) y el Subproblem (Subproblema) (también llamado Slave Problem o Problema Esclavo). En el siguiente artículo revisaremos de qué se trata el Método de Descomposición de Benders, en conjunto con la presentación de su uso en un pequeño ejemplo.

Esta metodología fue propuesta por J.F. Benders en 1962, su nombre original es Partitioning procedures for solving mixed-variables programming problems, y como su nombre bien lo dice el método está pensado originalmente para problemas de Programación Entera Mixta. Sin embargo, también se puede aplicar en problemas de Programación Lineal.

El Método de Descomposición de Benders trabaja bajo el concepto de las “variables complicadas”, es decir las variables que hacen que nuestro problema se «complique». Si estas variables no existieran (o más bien, conociéramos su valor de forma anticipada) entonces el problema resultante se supone que es considerablemente más fácil de resolver.

En Programación Entera Mixta, se espera que estas variables “complicadas” sean las enteras, las cuales al fijar su valor, dejan un problema resultante que cumple con una característica muy conveniente: es lineal. Y como cumple con esto, entonces podemos hacer uso de todo lo que conocemos sobre Programación Lineal para realizar la optimización de las variables que (en un principio) fijamos.

Veamos entonces brevemente de que se trata el Método de Descomposición de Benders. Supongamos que tenemos un problema que tiene la siguiente estructura:

Como mencionamos al principio, entonces podemos separar este problema en dos partes. A continuación se muestra el Master Problem (Problema Maestro) a la izquierda y el Subproblem (Subproblema) a la derecha:

Como se puede ver, el Master Problem contiene las variables que son enteras, y el Subproblem contiene las variables continuas, por lo que este último cumple con ser un problema de Programación Lineal.

Notar que el lado derecho de las restricciones del problema esclavo son números, ya que los valores de las variables enteras están fijos.

Iniciamos este artículo diciendo que el concepto central es dividir para conquistar: en este caso lo que se hace es resolver el Problema Maestro para obtener los valores de y; con esto, podemos resolver entonces el Subproblema. Se puede observar que el valor de la función objetivo del Subproblema se encuentra en la función objetivo del Problema Maestro, lo anterior se reformulará más adelante.

Una nota relevante: Si te das cuenta, el Problema Maestro para esta formulación no tiene ninguna restricción más que las de dominio. Nada impide que el Problema Maestro también tenga restricciones. Esto estará dado por la estructura del problema que estemos estudiando.

Recuerda siempre: ambos problemas están conectados, por lo que el resultado de uno influye directamente en el resultado del otro. Con esto en consideración, se cumple la siguiente propiedad:

Si el Subproblema es no acotado, entonces el Problema Maestro también lo es, resultando en que el problema original es no acotado.

Si tenemos un problema de Programación Lineal, entonces tenemos que aprovecharlo. ¿Qué es lo primero que se nos viene a la mente con un problema lineal? La respuesta es dualidad. Cada problema lineal (primal) tiene su problema dual asociado, el cual para el caso del problema esclavo enunciado anteriormente, tiene la siguiente estructura:

¿Qué es lo que podemos ver en este problema dual?: Que la región factible (es decir el sub-espacio definido por las restricciones y el dominio del problema) no depende del valor que tomen las variables enteras, y sólo influye en el valor de la función objetivo (notar que están en ella).

Lo anterior entonces nos lleva a la siguiente pregunta: ¿Qué sucede cuando la región factible del problema es vacía? (recuerda que al ser vacía estamos diciendo que nuestro problema dual es infactible). Dos cosas pueden ocurrir:

Al ser el problema dual infactible, entonces su primal es no acotado para algún valor de las variables enteras, en cuyo caso el problema original también es no acotado, o bien
La región factible del problema primal es también infactible para todo valor de las variables enteras, llevando a la conclusión de que el problema original es infactible.

¿Por qué revisamos todo esto?: Porque es importante tenerlo en consideración, ya que como mencionamos anteriormente, al tener un problema esclavo lineal, entonces podemos hacer el uso de los conceptos de dualidad.

¿Para qué la usaremos?: Para reformular nuestro Problema Maestro, y transformarlo en lo que usualmente se conoce como Relaxed Master Problem (RMP). Esta reformulación utiliza las variables duales asociadas a las restricciones del Slave Problem primal.

El Relaxed Master Problem (Problema Maestro Relajado) se puede escribir de la siguiente forma:

A las restricciones (1) y (2) se les conoce como restricciones de factibilidad y optimalidad, respectivamente. Además, existe una variable auxiliar z, la cual permite es la responsable de hacer la “conexión” entre el Problema Maestro y el Subproblema (esto se puede ver en las restricciones del tipo (1) y (2)).

Al resolver el RMP vamos a obtener los valores de las variables enteras, las cuales utilizaremos para resolver el Subproblema, como resultado podemos obtener dos cosas:

El sub-problema es infactible, lo cual implica que el problema dual es no acotado. Si esto ocurre, debemos agregar un corte de factibilidad al RMP.
El sub-problema tiene una solución óptima, lo cual implica que el problema dual también la tiene. Si esto ocurre, entonces hay que agregar un corte de optimalidad al RMP.

La última pregunta que nos queda por responder es: ¿Cuántas veces iterar?. Para responder lo anterior debemos definir la cota superior e inferior.

La cota superior corresponde al valor de la función objetivo original de nuestro problema; la cota inferior corresponde a la función objetivo del Master Problem, por lo tanto, debemos continuar hasta que ambos valores sean iguales.

Como la teoría de esta descomposición puede ser un poco compleja, veamos un ejemplo.

Ejemplo Método de Descomposición de Benders (Programación Lineal)

El ejemplo que veremos a continuación corresponde a un problema de Programación Lineal. La aplicación es similar para los problemas de Programación Entera Mixta.

Supongamos que tenemos que resolver el siguiente problema:

La solución óptima para este problema es: $x_{1}=0$ , $x_{2}=0,714$ e $y=1,571$ con un valor para la función objetivo (valor óptimo) de 5,285. La solución óptima del problema anterior se puede alcanzar de forma sencilla a través del Método Simplex Dual o el Método Simplex de 2 Fases (y por cierto a través de otros procedimientos y herramientas computacionales como Solver de Excel).

Vamos a descomponer el problema de la siguiente forma: recuerda que utilizaremos el RMP (Problema Maestro Relajado). Sea esta la primera iteración, K=1.

Al resolver el RMP de la primera iteración, obtenemos como solución óptima $y=0$ y $z=0$ ; lo cual utilizaremos para resolver el Subproblema. Con $y=0$ , el resultado del Subproblema es: $x_{1}=2,2$ y $x_{2}=0,4$ con un valor en la función objetivo de 5,6.

Ahora debemos calcular la cota superior (UB) y cota inferior (LB):

Como difieren el valor de las cotas, debemos continuar. Gracias a la herramienta “Análisis de Sensibilidad” del Solver en Excel, podemos obtener el valor de las variables duales asociadas a las restricciones del Subproblema (también podríamos obtener el valor de las variables duales óptimas al utilizar el Teorema de Holguras Complementarias). Esos valores son: $\lambda_{1}=-1,6$ y $\lambda_{2}=-0,2$ .

Estos valores nos permiten crear el siguiente corte de optimalidad: $-1,6(-3+y)-0,2(-4+3y)\leq z$ , el cual agregamos al Problema Maestro:

Hacemos K=2 (contador de iteraciones) y resolvemos el Problema Maestro nuevamente. Este corte nos permite encontrar una nueva solución óptima: $y=2,545$ y $z=0$ . Con este valor de y, el resultado del Subproblema es: $x_{1}=0$ y $x_{2}=0,227$ con un valor en la función objetivo de 0,68.

Ahora debemos calcular la cota superior (UB) y cota inferior (LB):

Al ver las variables duales para las restricciones del Subproblema tenemos que: $\lambda_{1}=-1,5$ y $\lambda_{2}=0$ , lo cual permite crear el siguiente corte de optimalidad el cual agregamos al Problema Maestro:

Hacemos K=3 y resolvemos el Problema Maestro nuevamente. La nueva solución óptima para el Problema Maestro es $y=1,571$ y $z=2,142$ con un valor óptimo de 5,285. Con $y=1,571$ la solución del Subproblema es: $x_{1}=0$ y $x_{2}=0,714$ con un valor en la función objetivo de 2,148.

Ahora debemos calcular la cota superior e inferior:

Como ambas cotas (superior e inferior) son iguales, podemos detenernos. Hemos encontrado la solución óptima para nuestro problema de Programación Lineal. (Mis sinceros agradecimientos a mi amigo Javier Maturana Ross por su contribución con este detallado tutorial y los créditos correspondientes al profesor Yuping Huang por el ejemplo presentado en este artículo).

Ejemplo de Relajación Lagrangeana en Programación Entera

El método de Relajación Lagrangeana (o Relajación Lagrangiana) consiste básicamente en un Método de Descomposición cuya idea se basa en descomponer un problema original restringido, en principio complejo de resolver, de modo de reemplazarlo por otro problema que permita simplificar la resolución. Esto se logra incorporando aquellas restricciones que se consideran difíciles (las que hacen compleja la resolución directa del problema) a la función objetivo, donde cada una de éstas tendrá asociada un Multiplicador de Lagrange $\lambda$ que permitirá (iterativamente) penalizar el incumplimiento de las mismas al ser establecidos distintos valores para los multiplicadores. De esta forma se espera que las restantes restricciones (las que no se incorporan mediante penalizaciones en la función objetivo) permitan verificar un problema cuya resolución sea fácil (o al menos más sencilla que el problema en su estructura original).

El problema asociado a encontrar los valores de $\lambda$ que permitan minimizar la función $LR(\lambda)$ (que en sí es un problema de maximización) se conoce como el Problema Dual Lagrangeano. En general puede resultar un problema tedioso de resolver, no obstante, a continuación se enumeran una serie de pasos que permiten una aproximación a la implementación del método de Relajación Lagrangeana.

Supongamos que el problema original es de Maximización y que la o las restricciones relajadas son inecuaciones del tipo $\leqslant$ :

Comenzar con cada $\lambda$ igual a cero. Definir inicialmente (y de forma arbitraria) un Paso de magnitud k.
Resolver $LR(\lambda)$ de modo de alcanzar la solución óptima en términos de x.
Para cada restricción violada por x, incrementar el correspondiente $\lambda$ por k.
Si han transcurrido m iteraciones desde que se alcanzo la última relajación para el problema dual lagrangeano, disminuir k a la mitad.
Ir al Paso 2.

Para ilustrar el procedimiento anterior consideremos un Problema de la Mochila como el que se describe a continuación:

Luego de resolver el problema de Programación Entera propuesto haciendo uso de Solver de Excel se alcanza la Solución Óptima: $x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1$ con Valor Óptimo: $V(PE)=13$ .

Relajaremos las Restricciones 1 y 2 incorporando éstas a la función objetivo y dejando exclusivamente las condiciones de binarios para las variables de decisión. Esto da origen a nuestro problema de Relajación Lagrangeana $LR(\lambda)$ :

Consideraremos inicialmente $\lambda_{1}=0$ y $\lambda_{2}=0$ . La resolución de dicha instancia es trivial obteniéndose como Solución Óptima: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ y Valor Óptimo: $LR(\lambda)=22$ . Notar que la solución alcanzada no satisface la Restricción 1 (sin embargo, se satisface la Restricción 2).

Penalizaremos la Restricción 1 al considerar $\lambda_{1}=0,5$ (penalización arbitrariamente definida como punto de partida) y manteniendo $\lambda_{2}=0$ (dado que la Restricción 2 se satisface). La Solución Óptima es $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo de $LR(\lambda)=20$ . En consecuencia, la penalización establecida resulto ser insuficiente para que se evitara la violación (incumplimiento) de la Restricción 1.

Sea $\lambda_{1}=1$ (aumentamos nuevamente en 0,5 la penalización de la Restricción 1) y $\lambda_{2}=0$ . La Solución Óptima se mantiene: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo: $LR(\lambda)=18$ .

Sea $\lambda_{1}=1,5$ y $\lambda_{2}=0$ . La Solución Óptima se mantiene: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo: $LR(\lambda)=16$ . Se sigue violando la Restricción 1.

Sea $\lambda_{1}=2$ y $\lambda_{2}=0$ . La Solución Óptima ahora es: $x_{1}=0, x_{2}=1, x_{3}=0, x_{4}=0$ con Valor Óptimo: $LR(\lambda )=15$ . Ahora se satisfacen las Restricciones 1 y 2, teniendo éstas holguras de 5 y 1, respectivamente. Luego si se decide disminuir la penalización de la Restricción 1 a $\lambda_{1}=1,5$ se vuelve al mismo punto de la iteración anterior. En consecuencia se disminuye la magnitud del paso (penalización) a 0,25 de modo que $\lambda_{1}=1,75$ y $\lambda_{2}=0$ . La Solución Óptima es: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=0$ con Valor Óptimo: $LR(\lambda)=15$ .

No obstante, la Restricción 2 no se satisface para esta nueva solución y de esta forma se establecen nuevas penalizaciones: $\lambda_{1}=1,75$ y $\lambda_{2}=0,25$ y que dan origen a la Solución Óptima: $x_{1}=1, x_{2}=1, x_{3}=1, x_{4}=1$ con Valor Óptimo: $LR(\lambda)=15$ .

El procedimiento continua de esta forma disminuyendo la magnitud del paso (penalización) cuando resulta necesario. Notar que de esta forma las respectivas penalizaciones pueden aumentar o disminuir al cabo de una iteración. El detalle de las iteraciones realizadas se muestra a continuación:

Para cada iteración k se muestra la penalización aplicada para la Restricción 1 y 2 respectivamente, el criterio para la actualización del Paso, el valor de la función objetivo de la Relajación Lagrangeana $LR(\lambda )$ , la Solución Óptima alcanzada para el problema (destacado con color amarillo), el valor que representa dicha solución óptima al ser evaluada en la función objetivo original V(PE), la holgura de la Restricción 1 (2) (con color rojo se destaca cuando se viola la restricción en una determinada magnitud) y si la solución óptima alcanzada en la iteración k-ésima es factible en el problema original PE).

Según se señala en un tutorial por Michael A. Trick (donde se ha tomado este ejemplo y se ha extendido a un número mayor de iteraciones con ciertas variaciones en la aplicación de las mismas) las penalizaciones “óptimas” (luego de seguir iterando) corresponderán aproximadamente a $\lambda_{1}=1,83$ y $\lambda_{2}=0,33$ , alcanzando $LR(\lambda )=14,67$ que constituye una cota superior del valor óptimo del problema original. La Solución Óptima asociada a este escenario es $x_{1}=0, x_{2}=1, x_{3}=1, x_{4}=0$ que es factible en el problema original y reporta un valor en la función objetivo de 11. Notar que la Solución Óptima del PE) es $x_{1}=0, x_{2}=0, x_{3}=1, x_{4}=1$ con Valor Óptimo de 13.

Ejemplo Pronóstico de Demanda utilizando Variación Estacional

Si el comportamiento histórico de la demanda de un producto tiene un marcado comportamiento estacional una alternativa de pronóstico a evaluar es aquel que utiliza de forma exclusiva los índices estacionales (también conocido como factores estacionales o variación estacional). Dicho procedimiento por cierto es más acotado que el Método de Descomposición y reduce el número de pasos necesarios para realizar un pronóstico. Bloqueadores solares, helados, estufas, sistemas de aire acondicionado, etc, son buenos ejemplos de productos que tienen un comportamiento de la demanda claramente influido por la época del año y ante la necesidad de extrapolar dichos patrones a futuro resulta necesario considerar la estacionalidad en el método de pronóstico.

Pronóstico de Demanda utilizando Variación Estacional

A continuación un ejemplo que permite observar su utilización: La empresa de softwares Megasoft tiene disponibles los datos de ventas de notebooks de los últimos 2 años, divididos en 8 trimestres. Si la demanda esperada para el próximo año es de 2.000 notebooks, estime la demanda para los próximos 4 trimestres llevando en cuenta el factor estacionalidad.

En primer lugar debemos calcular el promedio de la demanda trimestral. Por ejemplo, el Trimestre 1 y 5 corresponden al primer trimestre del año 1 y 2, respectivamente y el promedio es (300+416)/2=358. Luego continuando el procedimiento se obtiene el promedio trimestral de los próximos períodos. El total de 2.716 unidades corresponde a la sumatoria de los promedios trimestrales (358+650+1.038+670). Si dicha sumatoria la dividimos por 4 períodos (2.716/4=679) se obtiene lo que correspondería a la demanda de un trimestre promedio sin estacionalidad. A continuación se calcula el factor de estacionalidad o índice de estacionalidad dividiendo el promedio trimestral por la demanda promedio trimestral sin estacionalidad.

Si la demanda para los próximos 4 trimestres es de 2.000 unidades entonces se espera que la demanda trimestral sin estacionalidad sea simplemente asumir que la demanda anual se divide en 4 trimestres (es decir 500 unidades) y luego se ajusta dicho resultado por los factores de estacionalidad estimados anteriormente.

Notar que la sumatoria de los pronósticos de demanda son 2.000 unidades (263,5+478,5+764,5+493,5) y la demanda proyectada considera las características estacionales de la demanda. El siguiente gráfico muestra el comportamiento de la demanda histórica (lineas azul y roja) y la demanda pronosticada (línea verde).

Una forma alternativa de representar la misma información es en un gráfico de línea donde con color rojo, amarillo, verde y azul, se muestra el comportamiento de la demanda de los Trimestres 1, 2, 3 y 4, respectivamente, quedando de manifiesto que el método utilizado logra rescatar el comportamiento estacional de la demanda.

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]