Método Simplex

 

El método Simplex es un procedimiento general para resolver problemas de programación lineal. Desarrollado por George Dantzig en 1947, esta comprobada su extraordinaria eficiencia, y se usa en forma rutinaria para resolver problemas grandes en computadoras actuales. 

También se usan extensiones y variaciones del método Simplex para realizar análisis posoptimo (que incluye el análisis de sensibilidad)  sobre el modelo.

El método Simplex es un proceso algebraico, pero sus conceptos básicos son geométricos, por lo que entender estos conceptos geométricos nos da una fuerte intuición sobre cómo funciona el método Simplex y por qué es tan eficiente.

Este método se utiliza en conjunto con procedimientos interactivos, es decir, se utilizan las mismas rutinas básicas de cálculo una tras otra, dando como resultado una serie de soluciones sucesivas hasta encontrar la mejor solución. Una característica básica del método simplex es que en el problema de maximización, la contribución de la última solución es igual o mayor que la solución anterior, lo que brinda la seguridad de obtener la mejor respuesta al final.

Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en buscar otro punto que mejore el valor anterior. Como se verá en el método Gráfico, dichos puntos son los vértices del polígono (o poliedro o polícoro, si el número de variables es mayor de 2) que constituye la región determinada por las restricciones a las que se encuentra sujeto el problema (llamada región factible). La búsqueda se realiza mediante desplazamientos por las aristas del polígono, desde el vértice actual hasta uno adyacente que mejore el valor de la función objetivo. Siempre que exista región factible, como su número de vértices y de aristas es finito, será posible encontrar la solución

Se basa en la siguiente propiedad: Si la función objetivo Z no toma su valor máximo en el vértice A, entonces existe una arista que parte de A y a lo largo de la cual el valor de Z aumenta.

Será necesario tener en cuenta que el método Simplex únicamente trabaja con restricciones del problema cuyas inecuaciones sean del tipo "≤" (menor o igual) y sus coeficientes independientes sean mayores o iguales a 0. Por tanto habrá que estandarizar las restricciones para que cumplan estos requisitos antes de iniciar el algoritmo del Simplex. En caso de que después de éste proceso aparezcan restricciones del tipo "≥" (mayor o igual) o "=" (igualdad), o no se puedan cambiar, será necesario emplear otros métodos de resolución, siendo el más común el método de las Dos Fases.