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.

Rating: 4.6. From 12 votes.
Please wait...

, , , , , , , , , ,

3 Comentarios para Ejemplo del Método Simplex (Tutorial y Cómo Funciona)

  1. Augusto García Grass 10/09/2016 en 13:18 #

    Excelente explicación, muy claro y de invaluable ayuda. Mil gracias.

  2. David Navas 06/04/2017 en 10:37 #

    Hola, muy buena la información, gracias por compartirla. Tengo una duda ingenieros, he buscado pero no encuentro respuesta alguna. Cuando una restricción tiene como termino independiente el valor de 0, en el caso de maximización y debe ser mayor o igual, ¿Qué debo hacer en ese caso?, ¿Lo multiplico por -1 o lo dejo así?
    Ejemplo: 2X – 3Z >= 0
    La duda me surgió por un problema que ya se que no tiene solución pero que en un programa para verificar el ejercicio me apareció que debía multiplicarlo por -1. En otros libros y páginas solo dice que se multiplica por -1 cuando es menor a 0, no igual. ¿Qué debo hacer realmente?. Gracias de antemano por su colaboración.

    • GEO Tutoriales 09/04/2017 en 20:56 #

      @David. En rigor multiplicar por -1 una restricción no tiene efectos en la definición del conjunto de soluciones factibles de un modelo de optimización y sólo podría ser requerido para llevar el modelo a una estructura deseada que, por ejemplo, facilite su implementación computacional en una determinada herramienta. Por ejemplo, si la restricción que propones fuese 2X-3Z>=-2 al multiplicar ésta por -1 quedaría -2X+3Z<=2 y que siguiendo la estructura que hemos detallado en este artículo sólo requeriría de una variable de holgura para llevar transforma ésta en una ecuación.

Deja un comentario