El Método SIMPLEX.

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al ´optimo del problema de Programación Lineal en caso de existir esta ´ultima. La primera implementación computacional del Método Simplex es el año 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones. El Método Simplex hace uso de la propiedad de que la solución ´optima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto ´ultimo en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el ´optimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.

Forma estándar de un modelo de programación lineal

Consideremos un modelo de Programación Lineal en su forma estándar, que denotaremos en lo que sigue por:

Ejemplo 

Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 ≥ 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:

En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido “más negativo”. En este caso, X2. Luego, para escoger que variable básica deja la base debemos buscar el mínimo cociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes ¿ 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en mín.{70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. 

En la posición que se alcanza el mínimo cociente lo llamaremos “Pivote” (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones por filas, logrando la siguiente tabla al cabo de una iteración:  

El valor de la función objetivo luego de una iteración ha pasado de 0 a 1800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles. 

La actual tabla no corresponde a la solución ´optima del problema debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cociente calculamos la variable que debe dejar la base:

 mín.{40/(5/3), 10/(2/3), 30/(1/3)} = 15,

 asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:

Finalmente se alcanza la solución óptima del problema y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguales que cero). Nótese que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con “infinitas soluciones”. 

La solución alcanzada es X1∗ = 15, X2∗ = 25 con V(P∗) = 2100.

Solución mediante Excel Solver