El Símplex al revés, entendiendo el algoritmo dual del Símplex

El Algoritmo Dual del Símplex, desarrollado por Carlton E. Lemke (Lemke, 1954), ofrece una forma diferente de abordar los problemas de optimización lineal. Mientras que el Símplex clásico mantiene la factibilidad primal y mejora la función objetivo hasta alcanzar el óptimo, el Símplex Dual sigue la estrategia opuesta: conserva la factibilidad dual y va eliminando las violaciones de factibilidad primal mediante sucesivos pivotajes.

Este cambio de enfoque, que a primera vista puede parecer contraintuitivo, resulta especialmente útil en muchos problemas reales donde es difícil encontrar una solución inicial factible. Entender cómo funciona no sólo amplía nuestras herramientas de cálculo, sino que también ayuda a desarrollar una intuición más profunda sobre cómo se comportan estos modelos.

Es especialmente potente en situaciones como:

• Análisis de Sensibilidad: Cuando se añaden nuevas restricciones o se cambia el vector de recursos a un problema ya resuelto y la solución óptima actual se vuelve infactible.

• Problemas con Restricciones $\geqslant$: A menudo es más rápido que el método de las Dos Fases o el método de las penalizaciones.

• Optimización Entera: Se utiliza habitualmente en algoritmos de planos de corte.

Antes de estudiar el algoritmo, resulta útil compararlo con el método clásico del Símplex:

	Símplex Primal	Símplex Dual
Mantiene durante las iteraciones	Factibilidad primal	Factibilidad dual
Objetivo de cada pivotaje	Mejorar la función objetivo	Recuperar la factibilidad primal
Requiere para comenzar	Solución primal factible	Solución dualmente factible
Finaliza cuando	No existen costes reducidos mejorables	Todas las variables básicas son no negativas

Pasos del Algoritmo Dual del Símplex

El algoritmo únicamente puede iniciarse cuando la tabla inicial es dualmente factible, es decir, cuando los costes reducidos satisfacen la condición de optimalidad, aunque alguna variable básica sea negativa.

Los pasos del algoritmo son:

1. Inicialización: Seleccionar una base $\mathbf{B} = \mathbf{I}$ formada por las variables de holgura de modo que se garantice la factibilidad dual inicial.
2. Criterio de Parada: - Si todas las variables básicas son no negativas ($\mathbf{x}_\mathbf{B} \geqslant \mathbf{0}$), se ha alcanzado la solución óptima.

3. Si existe alguna variable básica con valor negativo ($x_{\mathbf{B}_i} < 0$), la solución actual no es factible primal y puede ser mejorada:

   • Regla de Salida (Variable que deja la base): Se selecciona la variable básica con el valor más negativo, ya que es la que presenta la mayor violación de la factibilidad primal. La variable que sale de la base, $x_l$, es aquella que presenta el valor más negativo en la columna de soluciones:

     \[\bar{x}_l = \min\{\bar{x}_s : \bar{x}_s < 0, \forall s \in \mathcal{I}\}\]

   • Regla de Entrada (Variable que entra en la base): Para determinar la variable que entra $x_k$, se calcula el mínimo de los cocientes entre los valores $z_j - c_j$ y los elementos negativos de la fila de la variable saliente ($y_{lj} < 0$):

     \[\frac{z_k - c_k}{y_{lk}} = \min \left\{ \frac{z_j - c_j}{y_{lj}} : y_{lj} < 0, \forall j \in \mathcal{J} \right\}\]

   • Pivotaje: Se realiza la operación de pivotaje sobre el elemento $y_{lk}$ de la misma forma que en el Símplex Primal clásico para actualizar la tabla, regresando al paso 2.

A continuación se ilustra el funcionamiento del algoritmo mediante un ejemplo completo.

Ejemplo numérico

Sea el problema de optimización lineal:

\[\begin{aligned} \max\;\; & z = 2x_1 + 6x_2 + 4x_3 \\ \textrm{s. a:}\;\; & - x_1 - 2x_2 - x_3 \leqslant -4 \\ & -2x_1 + x_2 - 3x_3 \leqslant -1 \\ & 4x_1 - 3x_2 + 2x_3 \leqslant -2 \\ & x_1, x_2, x_3 \geqslant 0 \end{aligned}\]

y su forma estándar

\[\begin{aligned} \max\;\; & z = 2x_1 + 6x_2 + 4x_3 \\ \textrm{s. a:}\;\; & - x_1 - 2x_2 - x_3 + x_4^h = -4 \\ & -2x_1 + x_2 - 3x_3 + x_5^h = -1 \\ & 4x_1 - 3x_2 + 2x_3 + x_6^h = -2 \\ & x_1, x_2, x_3, x_4^h, x_5^h, x_6^h \geqslant 0 \end{aligned}\]

La tabla final del Símplex es:

\[\begin{array}{cc|rrrrrr|r} & & {\color{gray}2} & {\color{gray}6} & {\color{gray}4} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & x_6^h & \\ \hline & z_j-c_j & 0 & 0 & 0 & -18/7 & -6/7 & -4/7 & 86/7 \\ \hline {\color{gray}2} & x_1 & 1 & 0 & 0 & -1/3 & 1/3 & 1/3 & 1/3 \\ {\color{gray}4} & x_3 & 0 & 0 & 1 & 2/21 & -11/21 & -5/21 & 13/21 \\ {\color{gray}6} & x_2 & 0 & 1 & 0 & -8/21 & 2/21 & -1/21 & 32/21 \\ \hline \end{array}\]

Tras tres iteraciones, todas las variables básicas son no negativas, por lo que se ha alcanzado la factibilidad primal. Como la factibilidad dual se ha mantenido durante todo el proceso, la solución obtenida es óptima:

\[(\mathbf{x}^*)^\intercal = (1/3,32/21,13/21,0,0,0) \quad z^* = 86/7\]

El método de la Restricción Artificial

Hasta ahora se ha supuesto que la tabla inicial era dualmente factible. Sin embargo, esto no siempre ocurre. En esos casos es necesario construir artificialmente una base que satisfaga esta condición antes de aplicar el algoritmo.

Cuando esto ocurre, se recurre al Método de la Restricción Artificial. La idea consiste en crear temporalmente una nueva restricción que obligue al algoritmo a construir una base dualmente factible. Una vez recuperada dicha factibilidad, la restricción artificial deja de tener utilidad y el algoritmo continúa sobre el problema original. La restricción artificial es la siguiente:

\[\sum_{j \in \mathcal{N}} x_j \leqslant M\]

donde:

• $\mathcal{N}$ es el conjunto de variables que incumplen la factibilidad dual (es decir, aquellas con $z_j-c_j > 0$ en un problema de minimización (equivalentemente $z_j-c_j < 0$ en un problema de maximización).
• $M$ representa un número real positivo lo suficientemente grande (un parámetro artificial).

Una vez añadida la restricción, se introduce su correspondiente variable de holgura y se realiza un pivotaje forzado para que dicha variable de holgura salga de la base inmediatamente. Tras el pivotaje, se restablece la factibilidad dual. A partir de este momento, se continúa iterando con el Símplex Dual clásico. Al llegar al final, podemos encontrarnos tres escenarios posibles:

• Solución Óptima: Si todas las variables básicas son mayores o iguales que cero ($x_s \geqslant 0$) y la variable de holgura de la restricción artificial permanece en la base con un valor estrictamente positivo. El problema original tiene una solución óptima única o múltiples óptimos.
• Solución Óptima No Acotada: Si todas las variables básicas son no negativas ($x_s \geqslant 0$), pero la variable de holgura de la restricción artificial no está en la base o está en ella con un valor igual a 0. El problema original tiene solución óptima no acotada.
• Problema infactible: Si existe alguna variable básica con un valor negativo ($x_s < 0$) y su fila $\mathbf{y}_s \geqslant \mathbf{0}$, significa que el problema dual tiene solución óptima no acotada y, por tanto, el problema inicial es infactible.

Ejemplos numéricos

Dependiendo del comportamiento de la variable asociada a la restricción artificial, el algoritmo puede terminar en distintos escenarios. A continuación se presentan diferentes ejemplos numéricos para distintos tipos de problema.

Solución óptima única

El caso más habitual es aquel en el que el problema tiene una única solución óptima.

Sea el problema de optimización lineal:

\[\begin{aligned} \max\;\; & z = x_1 + 6x_2 \\ \textrm{s. a:}\;\; & x_1 + 2x_2 \leqslant 20 \\ & x_1 + 1/2x_2 \geqslant 1/2 \\ & x_1, x_2 \geqslant 0 \end{aligned}\]

y su forma estándar

\[\begin{aligned} \max\;\; & z = x_1 + 6x_2 \\ \textrm{s. a:}\;\; & x_1 + 2x_2 + x_3^h = 20 \\ & -x_1 - 1/2x_2 + x_4^h = -1/2 \\ & x_1, x_2, x_3^h, x_4^h \geqslant 0 \end{aligned}\]

donde su primera tabla del Símplex es:

\[\begin{array}{cc|rrrr|r} & & {\color{gray}1} & {\color{gray}6} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & \\ \hline & z_j-c_j & -1 & -6 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^h & 1 & 2 & 1 & 0 & 20 \\ {\color{gray}0} & x_4^h & -1 & -1/2 & 0 & 1 & -1/2 \\ \hline \end{array}\]

observándose que la tabla inicial no es dual factible. Por tanto, se debe incluir la restricción artificial:

\[x_1 + x_2 \leqslant M\]

La tabla final viene dada por:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\color{gray}6} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^h & \\ \hline & z_j-c_j & 2 & 0 & 3 & 0 & 0 & 60 \\ \hline {\color{gray}0} & x_5^h & 1/2 & 0 & -1/2 & 0 & 1 & M-10 \\ {\color{gray}0} & x_4^h & -3/4 & 0 & 1/4 & 1 & 0 & 9/2 \\ {\color{gray}6} & x_2 & 1/2 & 1 & 1/2 & 0 & 0 & 10 \\ \hline \end{array}\]

donde se observa que se ha obtenido la solución óptima del problema al estar la variable de holgura de la restricción artificial ($x_5^h$) dentro de la base:

\[(\mathbf{x}^*)^\intercal = (0,10,0,9/2) \quad z^* = 60\]

Solución óptima no acotada

Sea el problema de optimización lineal:

\[\begin{aligned} \max\;\; & z = -4x_1 + 5x_2 \\ \textrm{s. a:}\;\; & 2x_1 + 2x_2 \geqslant 4 \\ & x_1 - x_2 \geqslant 3 \\ & x_1, x_2 \geqslant 0 \end{aligned}\]

y su forma estándar

\[\begin{aligned} \max\;\; & z = -4x_1 + 5x_2 \\ \textrm{s. a:}\;\; & -2x_1 - 2x_2 + x_3^h = -4 \\ & - x_1 + x_2 + x_4^h = -3 \\ & x_1, x_2, x_3^h, x_4^h \geqslant 0 \end{aligned}\]

donde su primera tabla del Símplex es:

\[\begin{array}{cc|rrrr|r} & & {\color{gray}-4} & {\color{gray}5} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & \\ \hline & z_j-c_j & 4 & -5 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^h & -2 & -2 & 1 & 0 & -4 \\ {\color{gray}0} & x_4^h & -1 & 1 & 0 & 1 & -3 \\ \hline \end{array}\]

observándose que la tabla inicial no es dual factible. Por tanto, se debe incluir la restricción artificial:

\[x_2 \leqslant M\]

Nota: Se podría obtener el mismo resultado con la restricción $x_1 + x_2 \leqslant M$

La tabla final viene dada por:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}-4} & {\color{gray}5} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & 0 & 0 & 4 & 1 & M-12 \\ \hline {\color{gray}0} & x_3^h & 0 & 0 & 1 & -2 & 4 & 4M+2 \\ {\color{gray}-4} & x_1 & 1 & 0 & 0 & -1 & 1 & M+3 \\ {\color{gray}5} & x_2 & 0 & 1 & 0 & 0 & 1 & M \\ \hline \end{array}\]

donde se observa que la variable de holgura de la restricción artificial ($x_5^h$) no está en la base y que se ha alcanzado factibilidad primal. Por tanto, este problema tiene solución óptima no acotada.

Problema infactible

Sea el problema de optimización lineal:

\[\begin{aligned} \max\;\; & z = 2x_1 + x_2 \\ \textrm{s. a:}\;\; & x_1 + x_2 \leqslant 2 \\ & -3x_1 + x_2 \geqslant 3 \\ & x_1, x_2 \geqslant 0 \end{aligned}\]

y su forma estándar

\[\begin{aligned} \max\;\; & z = 2x_1 + x_2 \\ \textrm{s. a:}\;\; & x_1 + x_2 + x_3^h = 2 \\ & 3x_1 - x_2 + x_4^h = -3 \\ & x_1, x_2, x_3^h, x_4^h \geqslant 0 \end{aligned}\]

donde su primera tabla del Símplex es:

\[\begin{array}{cc|rrrr|r} & & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & \\ \hline & z_j-c_j & -2 & -1 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^h & 1 & 1 & 1 & 0 & 2 \\ {\color{gray}0} & x_4^h & 3 & -1 & 0 & 1 & -3 \\ \hline \end{array}\]

observándose que la tabla inicial no es dual factible. Por tanto, se debe incluir la restricción artificial:

\[x_1 + x_2 \leqslant M\]

La tabla final viene dada por:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & 0 & 5/4 & 1/4 & 0 & 7/4 \\ \hline {\color{gray}0} & x_5^h & 0 & 0 & -1 & 0 & 1 & M-2 \\ {\color{gray}1} & x_2 & 0 & 1 & 3/4 & -1/4 & 0 & 9/4 \\ {\color{gray}2} & x_1 & 1 & 0 & 1/4 & 1/4 & 0 & -1/4 \\ \hline \end{array}\]

La siguiente iteración no puede realizarse porque la variable candidata a entrar no dispone de un pivote válido. Esto implica que el problema dual tiene solución óptima no acotada y, por dualidad, el problema primal resulta infactible.

El algoritmo Dual del Símplex constituye una alternativa natural al método clásico cuando se dispone de una solución dualmente factible, pero no primalmente factible. Además de ser una herramienta muy eficiente para resolver determinados problemas de optimización lineal, desempeña un papel fundamental en procedimientos más avanzados, como el análisis de sensibilidad, la optimización entera o los algoritmos de generación de columnas. Comprender su funcionamiento no sólo amplía el conjunto de técnicas disponibles para resolver problemas de optimización, sino que también proporciona una visión más completa de la estrecha relación existente entre un problema primal y su correspondiente problema dual.