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 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:
Para cada solución factible
De esta forma definimos
En resumen, para cada selección de valores de las variables
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
En el contexto del objetivo planteado anteriormente, debemos buscar una solución factible que permita alcanzar un mayor valor para
Sin embargo, si asumimos
Por tanto la pregunta relevante es: ¿cuánto se puede incrementar el valor de
(manteniendo al mismo tiempo) y seguir conservando la factibilidad ( )?.
La condición
Que claramente constituye una mejora para el valor de la función objetivo en comparación al valor inicial
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
De esta forma y luego de cierta manipulación algebraica podemos reescribir
Luego, con el objetivo de expresar
De esta forma nuestro sistema de ecuaciones (diccionario) queda definido por:
Como lo hicimos en la primera iteración debemos intentar incrementar 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
es seleccionar la variable .
¿Cuánto debemos incrementar el valor de
La nueva solución corresponde a:
El valor de
A continuación actualizamos el sistema de ecuaciones donde las variables que adoptan valores positivos
Notar que no es posible seguir aumentando el valor de la función objetivo
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:
A continuación incorporamos las variables de holgura (no negativas)
(*). Para nuestros efectos consideraremos que la forma estándar de un modelo de Programación Lineal esta dada por
, 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.
![Minimizar[c^{t}x, Ax=b,x\geq 0]](https://s0.wp.com/latex.php?latex=Minimizar%5Bc%5E%7Bt%7Dx%2C+Ax%3Db%2Cx%5Cgeq+0%5D&bg=ffffff&fg=000000&s=0 "Minimizar[c^{t}x, Ax=b,x\geq 0]")
Retomando nuestro ejemplo, el tableau inicial queda definido por:
Las variables de holgura definen una Solución Básica Factible Inicial, con
¿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
La variable que deja la base para dar lugar a
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}](https://s0.wp.com/latex.php?latex=Min%5B%5Cfrac%7B5%7D%7B2%7D%2C%5Cfrac%7B11%7D%7B4%7D%2C%5Cfrac%7B8%7D%7B3%7D%5D%3D%5Cfrac%7B5%7D%7B2%7D&bg=ffffff&fg=000000&s=0 "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
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
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 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:
La solución básica factible actual corresponde a:
con valor en la función objetivo . 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
![Min[\frac{5/2}{1/2},\frac{1/2}{1/2}]=1](https://s0.wp.com/latex.php?latex=Min%5B%5Cfrac%7B5%2F2%7D%7B1%2F2%7D%2C%5Cfrac%7B1%2F2%7D%7B1%2F2%7D%5D%3D1&bg=ffffff&fg=000000&s=0 "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
Actualizamos el tableau del Método Simplex obteniendo los siguientes resultados:
Los valores que adoptan las variables básicas correspondientes a esta nueva iteración es
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 (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:
- Si el problema no tiene solución óptima entonces es no-acotado o infactible.
- Si tiene una solución factible, tiene una solución básica factible.
- 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.
