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:

descomposición de benders

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:

master y subproblema benders

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:

dual subproblema benders

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

  1. 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
  2. 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:

problema maestro relajado benders

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:

  1. 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.
  2. 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:

ejemplo benders programación lineal

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.

iteración 1 benders

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

cotas benders

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:

corte benders

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

cota 2 benders

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:

corte 2 benders

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:

cota 3 benders
convergencia descomposición de benders

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 del Método Simplex (Tutorial y Cómo Funciona)

En el siguiente artículo detallaremos cómo funciona el Método Simplex a través de un ejemplo sencillo correspondiente a un modelo de Programación Lineal que considera 3 variables de decisión.

El Método Simplex corresponde a un algoritmo iterativo publicado por George Bernard Dantzig en el año 1947 en donde se busca alcanzar el máximo (o mínimo) de una función lineal compuesta por un conjunto de variables que deben satisfacer condiciones impuestas por restricciones lineales en forma de inecuaciones.

En este contexto, el objetivo de este artículo es definir en detalle distintas aproximaciones para la resolución de un modelo de Programación Lineal utilizando el Método Simplex, además de discutir sobre sus principales características.

Con tal propósito en perspectiva consideremos el siguiente modelo de optimización lineal:

ejemplo método simplex

Ejemplo del Método Simplex (Utilizando Diccionarios)

Un paso preliminar consiste en incorporar las denominadas variables de holgura. De modo de comprender este concepto consideremos la primera restricción:

2x_{1}+3x_{2}+x_{3}\leq 5

Para cada solución factible x_{1},x_{2},x_{3}, el valor del lado izquierdo será a lo más el valor del lado derecho; o eventualmente existirá una diferencia (holgura) entre estos 2 valores.

De esta forma definimos x_{4} como variable de holgura de dicha restricción, la cual se puede denotar por x_{4}=5-2x_{1}-3x_{2}-x_{3}, donde x_{4}\geq 0. De forma análoga se pueden definir las variables de holgura (no negativas) x_{5}x_{6} para las restricciones 2 y 3, respectivamente. Finalmente podemos describir la función objetivo 5x_{1}+4x_{2}+3x_{3} utilizando z de forma compacta.

En resumen, para cada selección de valores de las variables x_{1},x_{2}x_{3} podemos definir valores para las variables x_{4},x_{5},x_{6}, y z utilizando las siguientes fórmulas (conocido comúnmente como diccionarios según la terminología utilizada en el libro Linear Programming de Vasek Chvátal):

  • x_{4}=5-2x_{1}-3x_{2}-x_{3}
  • x_{5}=11-4x_{1}-x_{2}-2x_{3}
  • x_{6}=8-3x_{1}-4x_{2}-2x_{3}
  • z=5x_{1}+4x_{2}+3x_{3}

El objetivo del Método Simplex es lograr sucesivas mejoras para el valor de la función objetivo asociada a la selección de alguna solución factible. Repetir dicho procedimiento un numero finito de veces debería permitir eventualmente alcanzar la solución óptima del problema lineal en estudio.

Para inicializar el Método Simplex necesitamos una solución factible. En nuestro ejemplo esto es sencillo y se puede alcanzar simplemente fijando las variables x_{1},x_{2},x_{3} en cero. De esta forma se alcanzan los siguientes resultados:

x_{1}=0,x_{2}=0,x_{3}=0,x_{4}=5,x_{5}=11,x_{6}=8,z=0

En el contexto del objetivo planteado anteriormente, debemos buscar una solución factible que permita alcanzar un mayor valor para z. Si, por ejemplo, mantenemos x_{2}=x_{3}=0 e incrementamos el valor de x_{1} obtenemos z=5x_{1}>0, de modo que si x_{1}=1 se obtiene z=5 (y x_{4}=3,x_{5}=7,x_{6}=5). Mejor aún, si x_{1}=2 (manteniendo x_{2}=x_{3}=0), se obtiene z=10 (y x_{4}=1,x_{5}=3,x_{6}=2).

Sin embargo, si asumimos x_{1}=3 (conservando x_{2}=x_{3}=0) el valor de la función objetivo ahora es z=15, pero x_{4}=-1,x_{5}=-1,x_{6}=-1 que claramente no satisface las condiciones de no negatividad para las variables.

Por tanto la pregunta relevante es: ¿cuánto se puede incrementar el valor de x_{1} (manteniendo x_{2}=x_{3}=0 al mismo tiempo) y seguir conservando la factibilidad (x_{4},x_{5},x_{6}\geq 0)?.

La condición x_{4}=5-2x_{1}-3x_{2}-x_{3}\geq 0 implica x_{1}\leq \frac{5}{2}; de forma similar x_{5}\geq 0 implica x_{1}\leq \frac{11}{4}x_{6}\geq 0 implica x_{1}\leq \frac{8}{3}. Claramente de estas 3 cotas para la variable x_{1} la más restrictiva es x_{1}\leq \frac{5}{2}, de modo que incrementamos el valor de x_{1} hasta ese valor de modo de obtener una nueva solución:

x_{1}=\frac{5}{2},x_{2}=0,x_{3}=0,x_{4}=0,x_{5}=1,x_{6}=1/2,z=\frac{25}{2}

Que claramente constituye una mejora para el valor de la función objetivo en comparación al valor inicial z=0.

A continuación debemos buscar una nueva solución factible que sea aún mejor que la que acabamos de encontrar. Para ello la variable x_{1} que cambió su valor desde cero a un número positivo (12,5), debe cambiar su lugar desde el lado derecho al lado izquierdo del sistema de ecuaciones. De forma análoga, la variable x_{4} que cambio su valor de un número positivo a cero debe cambiar de lugar desde el lado derecho al lado izquierdo.

De esta forma y luego de cierta manipulación algebraica podemos reescribir x_{1} en términos de x_{2},x_{3},x_{4} según se observa a continuación:

x_{1}=\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4}

Luego, con el objetivo de expresar x_{5},x_{6}z en términos de x_{2},x_{3},x_{4}, simplemente substituimos el resultado anterior en las filas correspondientes:

  • x_{5}=11-4(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})-x_{2}-2x_{3}
  • x_{5}=1+5x_{2}+2x_{4}
  • x_{6}=8-3(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})-4x_{2}-2x_{3}
  • x_{6}=\frac{1}{2}+\frac{1}{2}x_{2}-\frac{1}{2}x_{3}+\frac{3}{2}x_{4}
  • z=5(\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4})+4x_{2}+3x_{3}
  • z=\frac{25}{2}-\frac{7}{2}x_{2}+\frac{1}{2}x_{3}-\frac{5}{2}x_{4}

De esta forma nuestro sistema de ecuaciones (diccionario) queda definido por:

  • x_{1}=\frac{5}{2}-\frac{3}{2}x_{2}-\frac{1}{2}x_{3}-\frac{1}{2}x_{4}
  • x_{5}=1+5x_{2}+2x_{4}
  • x_{6}=\frac{1}{2}+\frac{1}{2}x_{2}-\frac{1}{2}x_{3}+\frac{3}{2}x_{4}
  • z=\frac{25}{2}-\frac{7}{2}x_{2}+\frac{1}{2}x_{3}-\frac{5}{2}x_{4}

Como lo hicimos en la primera iteración debemos intentar incrementar el valor de la función objetivo (z) seleccionando una variable adecuada en el lado derecho, mientras que al mismo tiempo mantenemos las restantes variables del lado derecho en cero. En este sentido se puede observar que aumentar el valor de las variables x_{2}x_{4} generaría una disminución en el valor de z que va en sentido contrario a nuestro objetivo de maximizar el valor de la función objetivo.

Por tanto, la única selección de una variable en el lado derecho que permitirá aumentar el valor de z es seleccionar la variable x_{3}.

¿Cuánto debemos incrementar el valor de x_{3}?. La respuesta se puede obtener directamente del sistema de ecuaciones anterior, considerando x_{2}=x_{4}=0, la restricción x_{1}\geq 0 implica que x_{3}\leq 5; la restricción x_{5}\geq 0 no impone condiciones adicionales y la restricción x_{6}\geq 0 implica x_{3}\leq 1. En consecuencia x_{3}=1 es el mejor valor que puede adoptar dicha variable.

La nueva solución corresponde a:

x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0,z=13

El valor de z paso de 12,5 a 13 al cabo de una iteración del Método Simplex.

A continuación actualizamos el sistema de ecuaciones donde las variables que adoptan valores positivos x_{1},x_{3},x_{5} se encontraran en el lado izquierdo, mientras las variables igual a cero estarán en el lado derecho. De este modo pasamos la variable x_{3} al lado izquierdo, donde x_{3}=1+x_{2}+3x_{4}-2x_{6} que permite substituir en el resto de las ecuaciones:

  • x_{3}=1+x_{2}+3x_{4}-2x_{6}
  • x_{1}=2-2x_{2}-2x_{4}+x_{6}
  • x_{5}=1+5x_{2}+2x_{4}
  • z=13-3x_{2}-x_{4}-x_{6}

Notar que no es posible seguir aumentando el valor de la función objetivo z mediante un incremento de las variables del lado derecho x_{2},x_{4},x_{6} (en efecto, el valor de z decrecería). En consecuencia estamos en presencia de la solución óptima del problema: x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0 con valor óptimo z=13.

El procedimiento anterior basado en diccionarios favorece una mejor comprensión conceptual de los fundamentos sobre los que se basa el Método Simplex. De forma complementaria a continuación presentaremos a modo de contraste las iteraciones del Método Simplex utilizando tablas (o tableau) que comúnmente corresponde a la forma en la cual se presenta el algoritmo en cursos de pregrado.

Ejemplo del Método Simplex (Utilizando Tableau)

Consideremos nuevamente nuestro problema de Programación Lineal:

ejemplo método simplex

A continuación incorporamos las variables de holgura (no negativas) x_{4},x_{5},x_{6} que por definición tienen coeficiente nulo (cero) en la función objetivo. De esta forma obtenemos la forma estándar (*):

forma estándar ejemplo método simplex

(*). Para nuestros efectos consideraremos que la forma estándar de un modelo de Programación Lineal esta dada por Minimizar[c^{t}x, Ax=b,x\geq 0], siendo este formato el que preferentemente hemos utilizado para desarrollar las iteraciones del Método Simplex en otros artículos relacionados en nuestro sitio. En consecuencia la selección de dicho formato es meramente convencional.

Retomando nuestro ejemplo, el tableau inicial queda definido por:

tableau inicial método simplex

Las variables de holgura definen una Solución Básica Factible Inicial, con x_{4}=5,x_{5}=11,x_{6}=8 (las variables no básicas inicialmente corresponden a las variables originales del modelo, es decir, x_{1},x_{2},x_{3} que por definición adoptan un valor igual a cero.

¿Cómo verificar que el tableau inicial representa una solución básica factible óptima para el problema?.

Criterio de Optimalidad: Si en una iteración del Método Simplex se dispone de una solución básica factible y adicionalmente todos los costos reducidos son mayores o iguales que cero, parar ya que la actual solución básica factible es óptima.

En el ejemplo propuesto si bien nos encontramos frente a una solución básica factible el costo reducido de las variables no básicas son negativos, por tanto no se cumple el criterio de optimalidad, es decir, se puede seguir mejorando el valor de la función objetivo.

En este sentido consideraremos arbitrariamente x_{1} como la variable que ingresa a la base, aun cuando no hay certeza que la selección de la variable no básica con el costo reducido más negativo contribuya necesariamente a la Rapidez de Convergencia del Método Simplex.

La variable que deja la base para dar lugar a x_{1} se obtiene del criterio de factibilidad:

Criterio de Factibilidad: Para decidir que variable básica deja la base, es necesario calcular el mayor valor que puede tomar la variable no básica que entra a la base que garantice la factibilidad de la nueva solución básica. Para ello se considera un cuociente entre el valor de la solución básica factible actual y los coeficientes mayores a cero en la columna de la variable entrante. Si todos los cuocientes son negativos el Problema es No Acotado y por tanto no existe solución óptima.

En el ejemplo el criterio de factibilidad para la presente iteración esta dado por:

Min[\frac{5}{2},\frac{11}{4},\frac{8}{3}]=\frac{5}{2}

El menor cuociente se alcanza en la primera fila (restricción) que determina la variable que debe abandonar la base, en este caso, la variable x_{4}. Luego se actualiza la tabla realizando operaciones filas considerando el denominador del mínimo cuociente como pivote. El objetivo es alcanzar en la columna de la variable x_{1} lo que actualmente disponemos en la columna de la variable x_{4}.

Por ejemplo, podemos dividir la fila 1 por 2 de modo de obtener un 1 en la posición del pivote. Luego sobre esta nueva fila 1 podemos multiplicarla por -4 y sumarla a la fila 2. También se puede alcanzar un cero para la variable x_{1} en la fila 3 multiplicando por -3 la nueva fila 1 y sumándola a la fila 3. Finalmente para lograr un cero en el costo reducido de x_{1} se multiplica por 5 la nueva fila 1 y se suma a la fila 4.

De este modo el tableau del Método Simplex al cabo de una iteración queda de la siguiente forma:

segundo tableau método simplex

La solución básica factible actual corresponde a: x_{1}=\frac{5}{2},x_{2}=0,x_{3}=0,x_{4}=0,x_{5}=1,x_{6}=1/2 con valor en la función objetivo z=\frac{25}{2}. Se puede apreciar que dicho resultado es consistente con el enfoque de diccionarios utilizado inicialmente.

Claramente no se satisface el criterio de optimalidad dado que la variable no básica x_{3} tiene costo reducido negativo. Por ello x_{3} ingresa a la base y por tanto debemos calcular nuevamente el criterio de factibilidad para determinar la variable que deberá dejar la base:

Min[\frac{5/2}{1/2},\frac{1/2}{1/2}]=1

El pivote ahora se encuentra en la fila 3 y en consecuencia la variable básica x_{6} debe dejar la base. Notar que no se ha considerado para el cálculo del criterio de factibilidad el coeficiente de la variable x_{3} correspondiente a la fila 2 del tableau anterior (cuyo valor es cero y por tanto el cuociente se indefine).

Actualizamos el tableau del Método Simplex obteniendo los siguientes resultados:

tableau óptimo método simplex

Los valores que adoptan las variables básicas correspondientes a esta nueva iteración es x_{1}=2,x_{2}=0,x_{3}=1,x_{4}=0,x_{5}=1,x_{6}=0 que además representa la solución óptima del modelo de Programación Lineal (dado el cumplimiento del criterio de optimalidad). Luego el valor óptimo corresponde a z=13.

Importante: Existen herramientas computacionales y aplicaciones que permiten resolver online un problema de Programación Lineal mediante el Método Simplex. A continuación se presenta un extracto de los resultados alcanzados para nuestro ejemplo utilizando la aplicación disponible en http://www.programacionlineal.net/simplex.html.

método simplex online ejemplo

Método Simplex (Conclusiones)

El ejemplo que hemos desarrollado en este artículo busca presentar de forma sencilla y didáctica los principales fundamentos asociados al Método Simplex. Cabe destacar que ha sido necesario para la aplicación del algoritmo llevar el modelo original a su forma estándar que como se discutió anteriormente puede tener distintas representaciones según la bibliografía que se consulte.

En este contexto, cada problema de Programación Lineal en su forma estándar cumple con las siguientes propiedades establecidas en el Teorema Fundamental de la Programación Lineal:

  1. Si el problema no tiene solución óptima entonces es no-acotado o infactible.
  2. Si tiene una solución factible, tiene una solución básica factible.
  3. Si el problema tiene solución óptima, tiene una solución básica factible óptima.

Cabe destacar que no siempre se dispone de una solución básica factible en las variables originales del modelo (luego de llevar el problema a su forma estándar). Si bien existen diversas estrategias algorítmicas para enfrentar esta dificultad, se propone al lector revisar los tutoriales que hemos desarrollado sobre esta problemática, en particular respecto al Método Simplex de 2 Fases, Método de la M Grande y Método Simplex Dual.

Adicionalmente con el objetivo de resumir algunas ideas principales del algoritmo hemos preparado una infografía que hemos llamado 10 Cosas que Necesitas saber sobre el Método Simplex.

Finalmente quisiéramos recordar a nuestros usuarios que en el Blog de Gestión de Operaciones se pueden encontrar a la fecha más de 80 publicaciones relativas a la Programación Lineal y la Investigación de Operaciones. De modo de favorecer una rápida búsqueda ingresa al menú Cómo Comenzar. Por último agradeceríamos compartir y difundir este material en la medida que haya sido considerado útil y evaluar este tutorial utilizando las estrellas al final de esta publicación.

Criterios para la Rapidez de Convergencia del Método Simplex

En un artículo previo respecto a Cómo resolver un modelo de Programación Lineal con el Método Simplex de 2 Fases, se consideró en una iteración intermedia (es decir, en un tableau que representa una solución básica factible no óptima) la entrada a la base de una variable no básica que no era aquella con el costo reducido más negativo. Dicha situación por cierto no tuvo incidencia respecto a alcanzar los resultados del modelo en cuanto a su solución óptima y valor óptimo, no obstante, dicha situación afecto la rapidez de convergencia del Método Simplex.

Entendemos por rapidez de convergencia en este caso, el número de iteraciones necesarias en la aplicación del Método Simplex para, comenzando en una solución básica factible inicial llegar a una solución básica factible óptima.

Se debe destacar que si bien es frecuente que en la bibliografía básica asociada a cursos de Investigación de Operaciones se considere como criterio privilegiar la entrada a la base de aquella variable no básica con el costo reducido más negativo esto NO garantiza un menor número de iteraciones en el Método Simplex.

Ejemplo Criterio Costo Reducido Más Negativo en el Método Simplex

Como forma de corroborar lo anterior retomaremos el modelo de Programación Lineal que fue presentado en el artículo mencionado anteriormente:

ejemplo-simplex-dual

La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando X_{4} y X_{5} como variables de excesoX_{6} y X_{7} como variables auxiliares, de las restricciones 1 y 2, respectivamente. Esto da origen al siguiente problema de la Fase 1.

fase-1

Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:

tabla-3-fase-1

A continuación podríamos seleccionar como variable que ingresa a la base tanto a X_{1}, X_{2}  o X_{4}, al tener cada una de estas variables no básicas un costo reducido negativo.

Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable X_{2} que tiene el costo reducido más negativo. En consecuencia el mínimo cuociente se calcula en la columna de la variable X_{2}, siendo éste: Min\begin{Bmatrix}\frac{1/4}{1/4};\frac{1}{3/2}\end{Bmatrix}=2/3, por tanto X_{1} deja la base. Se actualiza la tabla con esta nueva información obteniendo lo siguiente que representa el fin de la Fase I:

rapidez-de-convergencia-fas

Eliminamos las columnas de las variables auxiliares X_{6} y X_{7} y adicionalmente actualizamos el vector de costos reducidos considerando la función objetivo original.

inicio-fase-2-convergencia

Luego llevamos a cero los costos reducidos de las variables X_{3} y X_{2}:

fase-2-rapidez-convergencia

Ahora entra la variable X_{1} a la base. El criterio de factibilidad o mínimo cuociente determina que Min\begin{Bmatrix}\frac{1/12}{1/3};\frac{2/3}{2/3}\end{Bmatrix}=1/4 la variable X_{3} deja la base. Se actualiza la tabla:

tabla-final-fase-2-rapidez-

Que corresponde a la tabla final de la Fase II donde X_{1}=1/4X_{2}=1/2X_{3}=0 y que por cierto demuestra la equivalencia en los resultados obtenidos cuando en la tabla  intermedia de la Fase I se ingresa a la base a la variable X_{1}. Cabe destacar que una forma alternativa de resolver el problema anterior que evita la aplicación de las 2 Fases del Método Simplex es a través del Método Simplex Dual.

Ejemplo Criterio Costo Reducido Negativo en el Método Simplex

Consideremos el siguiente problema de Programación Lineal:

ejemplo costo reducido negativo método simplex

El lector puede corroborar que luego de llevar a la forma estándar el problema anterior, pasando a minimización la función objetivo y agregando como variables de holgura las variables x_{3}x_{4} se dispone de una solución básica factible inicial en el origen (vértice A de la siguiente gráfica).

gráfico costo reducido negativo

Si se privilegia la entrada a la base de aquella variable no básica con el costo reducido más negativo se debería seleccionar inicialmente la variable x_{2} la cual permite concluir con las iteraciones del Método Simplex y alcanzar la solución óptima al cabo de 3 iteraciones (vértice D). Por el contrario si inicialmente se ingresa a la base la variable x_{1} se alcanza la solución óptima al cabo de 1 iteración. Se recomienda al lector verificar estos resultados.

Este sencillo ejemplo demuestra que NO necesariamente garantiza una mayor rapidez de convergencia del Método Simplex el considerar como criterio de entrada a la base aquella variable no básica con el costo reducido más negativo.




Cambio de Variables como alternativa al Método Simplex de 2 Fases

Una empresa que fabrica tres artículos A, B y C, desea encontrar un Plan de Producción semanal que le permita maximizar sus beneficios netos totales. Los productos son procesados en tres máquinas siendo la producción mínima semanal de 100, 60 y 60 unidades respectivamente. El beneficio neto por unidad vendida de estos artículos son 2, 2 y 4 mil pesos para los artículos A, B y C, respectivamente. Las horas que se necesitan por unidad y máquina son:

maquinas-tiempos-de-producc

Siendo el número de horas disponibles de cada máquina 240, 400 y 360 respectivamente. Formule un modelo de Programación Lineal para abordar el problema propuesto. Resuelva a través del Método Simplex dicho modelo, indicando cuántas unidades de A, B y C se deben fabricar semanalmente y el beneficio final de este plan.

Variables de Decisión: Se debe definir cuántas unidades de cada uno de los 3 productos se fabricarán durante el período de evaluación.

variables-produccion-abc

Función Objetivo: Consiste en maximizar el beneficio neto asociado al plan de producción.

funcion-objetivo-abc

Restricciones: Se debe garantizar que se fabrique los mínimos semanales exigidos para cada producto como también que se respete la disponibilidad de horas máquinas.

restricciones-abc

El problema anterior se puede resolver por el Método Simplex de 2 Fases agregando variables de exceso y auxiliares para cada una de las restricciones que establecen los mínimos semanales de producción. Además se debe agregar variables de holguras para cada una de las restricciones de disponibilidad de horas máquinas. En consecuencia el problema de la Fase 1 tendría 3 variables auxiliares (cuya sumatoria se minimiza en la función objetivo) lo cual genera una instancia de resolución al menos tediosa para este problema (en caso se ser abordada manualmente).

Una alternativa más eficiente de resolución se alcanza al imponer un cambio de variables, lo que permite simplificar las restricciones de mínimos de producción semanal. Sea X=A-100\geq 0, Y=B-60\geq 0Z=C-60\geq 0. Luego A=X+100B=Y+60C=Z+60, obteniendo la siguiente instancia de modelamiento equivalente:

modelo-lineal-con-cambio-de

A continuación llevamos a la forma estándar el modelo anterior, transformando la función objetivo a minimización y agregando s_{1},s_{2},s_{3} como variables de holgura de las restricciones 1, 2 y 3, respectivamente:

forma-estandar-cambio-de-va

Lo que da origen a la siguiente tabla inicial del Método Simplex:

tabla-inicial-forma-estanda

A continuación incorporamos a la base a la variable Z considerando el criterio que favorece la rapidez de convergencia del algoritmo. Luego calculamos el criterio de factibilidad o mínimo cuociente en la columna de la variable Z: Min\begin{Bmatrix}\frac{60}{2}; \frac{180}{1}; \frac{40}{1}\end{Bmatrix}=30, lo que determina que la variable s_{1} deja la base. Se actualiza la tabla realizando una iteración del Método Simplex:

iteracion-1-cambio-de-varia

Se procede a incorporar a la variable X a la base y s_{3} abandona la base dado que Min\begin{Bmatrix}\frac{150}{1}; \frac{10}{2}\end{Bmatrix}=5. Se realiza una iteración adicional que permite alcanzar la siguiente solución básica factible óptima:

solucion-optima-cambio-de-v

La solución óptima es X=5Y=0Z=30 que al remplazar en las variables originales permite obtener A=X+100=5+100=105B=Y+60=0+60=60C=Z+60=30+60=90. Notar que el valor óptimo es V(P)=130+560=690 luego de sumar el valor de la constante 560 al valor obtenido para la función objetivo del problema auxiliar. Se propone al lector corroborar los resultados anterior a través de la aplicación del Método Simplex de 2 Fases que por cierto permite alcanzar idénticos resultados pero con una mayor esfuerzo en la resolución.




Casos Especiales en la Programación Lineal detectados con el Método Simplex

En la resolución de un modelo de Programación Lineal se pueden enfrentar ciertos casos especiales que merecen particular atención. Estos casos (infinitas soluciones óptimas, problema no acotado sin solución óptima, problema infactible, solución óptima degenerada) se pueden detectar a través de la aplicación del Método Simplex según hemos tratado previamente en el Blog. A continuación un resumen de dichos escenarios:

Infinitas Soluciones Óptimas: Se detecta cuando luego de alcanzar una solución básica factible óptima, al menos una variable no básica tiene costo reducido igual a cero. La siguiente imagen representa esta situación donde la solución óptima (infinitas) se alcanza en el tramo entre los vértices B y C. En efecto se puede representar de forma general las soluciones óptimas como: (x,y)=\lambda (0,3)+(1-\lambda )(2,2) con 0\leq \lambda\leq 1.

Grafico Infinitas Soluciones Optimas

Problema No Acotado: En las iteraciones del Método Simplex un problema no acotado se detecta cuando al calcular el criterio de factibilidad o mínimo cuociente que determina la variable que deja la base, todas las entradas en la columna de la variable no básica entrante son negativas o cero, por tanto no existe denominador válido (mayor a cero) que permita determinar el pivote. En la siguiente representación gráfica se puede apreciar que las curvas de nivel de la función objetivo crecen en la dirección del vector gradiente, donde en particular el dominio de soluciones factibles es no acotado para los valores que puede adoptar la variable x_{2}.

problema no acotado

Es importante destacar que el hecho que un dominio de soluciones factibles sea no acotado no implica necesariamente que el problema de Programación Lineal no tiene solución.

Problema Infactible: Si al finalizar la Fase I del Método Simplex de 2 Fases el valor de la función objetivo es distinto a cero, entonces el problema lineal es infactible, es decir, el dominio de soluciones factibles es vacío al existir restricciones incompatibles (por ejemplo en el gráfico a continuación el área azul no se intersecta con el área color rojo).

dominio-infactible-problema

Solución Óptima Degenerada: Cuando se presenta un empate el el cálculo de la condición de factibilidad del Método Simplex, al menos una variable básica será cero en la siguiente iteración, caso en el cual se dice que la nueva solución es degenerada. Esto implica que el modelo tiene al menos una restricción redundante.

solucion-optima-degenerada-