Método Simplex

El método gráfico para resolver problemas de programación lineal tiene una particularidad, solo aplica para resolver problemas con dos variables de decisión. Sin embargo, los problemas cotidianos de programación lineal que se enfrentan regularmente los especialistas en IO, involucran un número mayor de variables y a veces compuestos de cientos de restricciones por lo que es necesario auxiliarse de programas computacionales, basados en el algoritmo Símplex, para la solución de los mismos.

Para la aplicación del algoritmo Símplex se transforma el modelo de programación original, formado por restricciones funcionales de desigualdad,  en un modelo de forma estándar, integrado por restricciones de igualdad equivalentes. Esta conversión se logra con la introducción de variables de holguras y/o superávit.

Variables de holgura. Aplica para las restricciones del tipo (<=), donde el lado derecho de la desigualdad representa el limite sobre la disponibilidad de un recurso y el lado izquierdo representa la utilización de ese recurso limitado que hacen las variables del modelo. Esto quiere decir que una holgura representa la cantidad disponible del recurso que excede a la utilización que se le da. En la conversión de este tipo de desigualdad se añade una variable de ajuste (Xi o Hi) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: 3X1 + 2X2 <= 6, su equivalente seria, 3X1 + 2X2 + X3 = 6.

Variables de superávit. Aplica para las restricciones del tipo (>=), generalmente determinan los requerimientos mínimos de especificaciones. Es decir, un superávit representa el exceso minimo del lado izquierdo sobre el requerimiento mínimo de la restricción. En la conversión de este tipo de desigualdad se resta una variable de ajuste (Xi o Si) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restricción: X1 + 3X2 >= 5, su equivalente seria, X1 + 3X2 - X3 = 5.

La solución del algoritmo Símplex se puede realizar de forma algebraica o de forma tabular. Para los fines de este apartado se explicará el desarrollo del algoritmo en su forma tabular. Antes de iniciar, se deben plantear algunos conceptos importantes: variables básicas, variables no básicas, solución básica factible, variable de entrada, variable de salida, iteración, condición de optimalidad (criterio de entrada) y condición de factibilidad (criterio de salida).

La forma estándar de un problema de programación lineal se compone de m ecuaciones lineales simultaneas en n incógnitas o variables, donde m es menor que n (m < n). Este conjunto de variables se puede segmentar en dos grupos: (1) m - n variables, a las cuales se le asigna un valor cero y (2) las restantes m variables, cuyos valores se determinan resolviendo las m ecuaciones resultantes. Si la m ecuaciones conducen a una única solución, estas variables se denominan variables básicas y las n - m restantes variables se les llaman variables no básicas.

En el inicio de un algoritmo Símplex, se consideran todas las variables de holguras y ficticias adicionadas en la forma estándar, con valores cero, procedimiento que se denomina solución básica factible inicial.  Se denomina una solución básica factible si las m variables básicas son no negativas (>= 0). Si cualquiera de estas m variables es igual a cero se considera un solución BF degenerada. Después se trata de encontrar otra solución básica factible que mejorará el valor del objetivo, proceso denominado iteraciones. Para que una variable cero actual se convierta en positiva, debe eliminarse una de las variables basicas actuales, es decir, volver esta última no básica a nivel cero. Esto introduce dos conceptos, la variable cero seleccionada es la variable de entrada y la variable básica eliminada es la variable de salida.

Condición de optimalidad. La variable de entrada en un problema de maximización es la variable no basica que tiene el coeficiente más negativo en la fila Z o función objetivo. En el caso de minimización, la variable de entrada se define como la variable no básica que tiene que tiene el coeficiente más positivo en la fila Z.

Condición de factibilidad. Tanto para los problemas de maximización como de minimización, la variable de salida es la variable básica asociada con la razón no negativa más pequeña. En caso de empates se rompen arbitrariamente y se descartan las razones negativas o indefinidas. Cuando se refiere a razón se entiende por la división de los limites del lado derecho entre los coeficientes de la columna de la variable de entrada.

A continuación un vídeo donde muestra como resolver un problema del método simplex