Convergencia, degeneración y el "lado oscuro" del Símplex

El Algoritmo del Símplex es extremadamente eficiente en la práctica, pero para garantizar que siempre llegue a la solución óptima (convergencia), debemos entender qué sucede cuando el algoritmo se encuentra con obstáculos geométricos y matemáticos.

El Problema de la Degeneración

Una solución básica factible se considera degenerada si al menos una de las variables básicas tiene un valor igual a cero.

Causa geométrica: Ocurre cuando más restricciones de las necesarias intersectan en un vértice, haciendo que varias bases diferentes proporcionen el mismo punto. Esto provoca que el vértice tenga más de una representación como solución básica.
Consecuencia: El mayor peligro de la degeneración es el ciclado. Si se produce un empate en la variable de salida, una de las variables básicas tendrá valor 0. Esto puede provocar que el algoritmo entre en un bucle infinito, pasando por las mismas bases una y otra vez sin avanzar hacia el óptimo.

Los ciclos, por tanto, son un elemento a tener en cuenta en la resolución del problema de optimización lineal. El primer ejemplo fue propuesto por Alan Hoffman en (Hoffman, 1953) con un problema de 11 variables donde se alcanza un ciclo y, por tanto, el Símplex no converge. Poco después, Martin Beale propuso un ejemplo (Beale, 1955) con 7 variables que se muestra a continuación:

\[\begin{aligned} \min\;\; & z = -(3/4) x_4 + 20 x_5 -(1/2) x_6 + 6 x_7 \\ \textrm{s. a:}\;\; & x_1 + (1/4)x_4 - 8x_5 - x_6 + 9x_7 = 0 \\ & x_2 + (1/2)x_4 - 12x_5 - (1/2)x_6 + 3x_7 = 0 \\ & x_3 + x_6 = 1 \\ & x_1, x_2, x_3, x_4, x_5, x_6, x_7 \geqslant 0 \end{aligned}\]

La secuencia de tablas muestra que se alcanza la misma solución en todas ellas y que además el Algoritmo del Símplex entra en un ciclo infinito:

\[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 0 & 0 & 0 & 3/4 & -20 & 1/2 & -6 & 0 \\ \hline {\color{gray}0} & x_1 & 1 & 0 & 0 & {\color{#2698ba}1/4} & -8 & -1 & 9 & 0 \\ {\color{gray}0} & x_2 & 0 & 1 & 0 & 1/2 & -12 & -1/2 & 3 & 0 \\ {\color{gray}0} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & -3 & 0 & 0 & 0 & 4 & 7/2 & -33 & 0 \\ \hline {\color{gray}{-3/4}} & x_4 & 4 & 0 & 0 & 1 & -32 & -4 & 36 & 0 \\ {\color{gray}0} & x_2 & -2 & 1 & 0 & 0 & {\color{#2698ba}4} & 3/2 & -15 & 0 \\ {\color{gray}0} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & -1 & -1 & 0 & 0 & 0 & 2 & -18 & 0 \\ \hline {\color{gray}{-3/4}} & x_4 & -12 & 8 & 0 & 1 & 0 & {\color{#2698ba}8} & -84 & 0 \\ {\color{gray}{20}} & x_5 & -1/2 & 1/4 & 0 & 0 & 1 & 3/8 & -15/4 & 0 \\ {\color{gray}{0}} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 2 & -3 & 0 & -1/4 & 0 & 0 & 3 & 0 \\ \hline {\color{gray}{-1/2}} & x_6 & -3/2 & 1 & 0 & 1/8 & 0 & 1 & -21/2 & 0 \\ {\color{gray}{20}} & x_5 & 1/16 & -1/8 & 0 & -3/64 & 1 & 0 & {\color{#2698ba}3/16} & 0 \\ {\color{gray}{0}} & x_3 & 3/2 & -1 & 1 & -1/8 & 0 & 0 & 21/2 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 1 & -1 & 0 & 1/2 & -16 & 0 & 0 & 0 \\ \hline {\color{gray}{-1/2}} & x_6 & {\color{#2698ba}2} & -6 & 0 & -5/2 & 56 & 1 & 0 & 0 \\ {\color{gray}{6}} & x_7 & 1/3 & -2/3 & 0 & -1/4 & 16/3 & 0 & 1 & 0 \\ {\color{gray}{0}} & x_3 & -2 & 6 & 1 & 5/2 & -56 & 0 & 0 & 1 \\ \hline \end{array}\] \[\begin{array}{cc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}{-3/4}} & {\color{gray}{20}} & {\color{gray}{-1/2}} & {\color{gray}{6}} & \\ & & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline & z_j-c_j & 0 & 2 & 0 & 7/4 & -44 & -1/2 & 0 & 0 \\ \hline {\color{gray}{0}} & x_1 & 1 & -3 & 0 & -5/4 & 28 & 1/2 & 0 & 0 \\ {\color{gray}{6}} & x_7 & 0 & {\color{#2698ba}1/3} & 0 & 1/6 & -4 & -1/6 & 1 & 0 \\ {\color{gray}{0}} & x_3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline \end{array}\]

que, iterando de nuevo, se obtiene la primera tabla mostrada.

Garantizando la Convergencia: Reglas de Bland y Lexicográfica

Para evitar que el algoritmo se quede atrapado en un ciclo, se utilizan reglas de selección de variables:

Regla Lexicográfica: Fue propuesta por Abraham Charnes en (Charnes, 1952) y George Dantzig, Alexander Orden y Philip Wolfe en (Dantzig et al., 1955). Si hay un empate en la variable de salida, se dividen los elementos de las filas candidatas por el pivote y se comparan columna por columna (empezando por la primera) para romper el empate basándose en el menor cociente encontrado.

Regla de Bland: Fue propuesta por Robert Bland en (Bland, 1977). Es una regla más sencilla que consiste en seleccionar siempre la variable con el índice más bajo tanto para entrar como para salir de la base cuando existan múltiples candidatas. Esto garantiza matemáticamente que no habrá ciclos y que el algoritmo convergerá.

La secuencia de tablas aplicando la regla de Bland es la siguiente:

En esta tabla se aplica la regla de Bland, introduciendo $x_1$ en la base en lugar de $x_7$:

De nuevo se aplica la regla de Bland en la siguiente tabla entrando $x_2$ en lugar de $x_4$:

obteniendo, al igual que antes, la solución óptima del problema:

\[(\mathbf{x}^*)^\intercal = (3/4,0,0,1,0,1,0) \quad z^* = -5/4\]

Complejidad algorítmica y los cubos de Klee-Minty

Aunque el Símplex funciona muy rápido en problemas reales (normalmente entre $3m$ y $3m^2$ iteraciones), su complejidad teórica es exponencial.

El Ejemplo de Klee-Minty

En 1972, Victor Klee y George Minty diseñaron un ejemplo en (Klee & Minty, 1972) (conocido como “cubos de Klee-Minty”) para demostrar el peor escenario posible del Símplex. Este ejemplo ilustra cómo, en el peor de los casos, el Símplex puede recorrer literalmente cada vértice del poliedro antes de encontrar la solución óptima, algo que rara vez ocurre en problemas reales.

Formulación general:

\[\begin{array}{lrcrcrcrcrcr} \max & 2^{n-1} x_1 &+& 2^{n-2} x_2 &+& \ldots &+& 2 x_{n-1} &+& x_n \\ \textrm{s. a:} & x_1 & & & & & & & & & \leqslant & 5 \\ & 2^2 x_1 &+& x_2 & & & & & & & \leqslant & 5^2 \\ & 2^3 x_1 &+& 2^2 x_2 &+& x_3 & & & & & \leqslant & 5^3 \\ & \vdots & & & & & & & & & & \vdots \\ & 2^n x_1 &+& 2^{n-1} x_2 &+& \ldots &+& 2^2 x_{n-1} &+& x_n & \leqslant & 5^n \\ & x_1 &,& x_2 &,& \ldots &,& x_{n-1} &,& x_n & \geqslant & 0 \end{array}\]

¿Por qué es especial?

En este tipo de problemas, si se utiliza la regla de entrada estándar, el Algoritmo del Símplex se ve obligado a visitar todos los vértices del poliedro. Para un problema de $n$ variables, esto supone realizar $2^n - 1$ iteraciones.

Para $n=2$ (un cuadrado “deformado”), el algoritmo visitaría los puntos A(0,0) $\to$ B(5,0) $\to$ C(5,5) $\to$ D(0,25) antes de encontrar el óptimo, recorriendo cada esquina disponible en lugar de ir directo a la solución. Para $n=3$ (un cubo “deformado”), el algoritmo recorre todos los vértioces de forma análoga:

Recorrido del Símplex en el ejemplo de Klee-Minty con n=2

Recorrido del Símplex en el ejemplo de Klee-Minty con n=3

Resumen de la eficiencia del Símplex

Complejidad Teórica: Exponencial (por casos como Klee-Minty).
Complejidad Empírica: Muy eficiente (lineal/cuadrática respecto al número de restricciones $m$).
Alternativa: Los Métodos de Punto Interior introducidos por Narendra Karmarkar en (Karmarkar, 1984) son algoritmos que sí resuelven el problema de optimización lineal en tiempo polinomial, siendo una alternativa para problemas de grandes dimensiones donde el Símplex podría tener problemas de convergencia.