El Algoritmo Símplex, el motor de la optimización matemática

Desde su introducción por George B. Dantzig en 1947, aunque fue publicado en 1951, (Dantzig, 1951), el Algoritmo Símplex ha sido calificado como uno de los avances más influyentes en el cálculo científico y la toma de decisiones estratégicas. Su importancia radica en su capacidad para resolver problemas de optimización lineal, permitiendo encontrar de forma eficiente el valor óptimo (máximo o mínimo) de una función sujeta a múltiples restricciones de recursos.

El Algoritmo del Símplex navega de forma inteligente por los vértices de la región factible, garantizando que, si existe una solución óptima, esta será alcanzada en un número finito de pasos.

Para seguir el procedimiento que se explica a continuación, conviene tener presente los conceptos básicos presentados en el post La anatomía del problema de optimización lineal.

El Sistema Explícito: La Base del Algoritmo

Para que el algoritmo pueda evaluar si una solución es óptima o cómo mejorarla, es necesario transformar el problema original en un sistema explícito asociado a una base $\mathbf{B}$. Partimos de la forma estándar:

\[\begin{aligned} \min \;\; & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s. a:}\;\; & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0}. \end{aligned}\]

Dividiendo las variables en básicas \(\mathbf{x}_\mathbf{B}\) y no básicas \(\mathbf{x}_{\mathbf{N}}\), y multiplicando por la inversa de la base \(\mathbf{B}^{-1}\), obtenemos los elementos fundamentales:

• Índices de componentes básicas:

  \[\mathcal{I} = \big\{s \in \{1,\ldots,n\}: \mathbf{a}_s \in \mathbf{B} \big\}\]

• Índices de componentes no básicas:

  \[\mathcal{J} = \big\{j \in \{1,\ldots,n\}: \mathbf{a}_j \in \mathbf{N} \big\}\]

• Ecuaciones de las variables básicas:

  \[\mathbf{x}_\mathbf{B} = \bar{\mathbf{x}}_\mathbf{B} - \displaystyle \sum_{j \in \mathcal{J}} \mathbf{y}_j x_j\]

  donde $\bar{\mathbf{x}}_\mathbf{B} = \mathbf{B}^{-1}\mathbf{b}$ es la solución básica actual e $\mathbf{y}_j = \mathbf{B}^{-1}\mathbf{a}_j$.

• Función Objetivo:

  \[z = \bar{z} - \displaystyle \sum_{j \in \mathcal{J}} (z_j - c_j)x_j\]

  donde $\bar{z}$ representa el valor actual de la función objetivo y la magnitud $(c_j - z_j)$ nos indica cuánto aumenta (o disminuye) la función por cada unidad que incrementamos la variable no básica $x_j$.

dando lugar al sistema explícito en su forma estándar para una base $\mathbf{B}$:

\[\begin{aligned} \min\;\;\; & \bar{z} - \sum_{j \in \mathcal{J}} (z_j - c_j) x_j \\ \textrm{s. a:}\;\;\; & \bar{x}_s - \sum_{j \in \mathcal{J}} y_{sj} x_j \geqslant 0 && \forall s \in \mathcal{I} \\ & x_j \geqslant 0 && \forall j \in \mathcal{J} \end{aligned}\]

Los Tres Teoremas del Símplex

El comportamiento y el criterio de parada del algoritmo se fundamentan en estos tres teoremas esenciales (planteados para un problema de minimización):

Primer Teorema del Símplex (Criterio de ptimalidad)

Una solución básica factible es óptima si para toda variable no básica se cumple que:

\[z_j - c_j \leqslant 0\]

Segundo Teorema del Símplex (Solución Óptima no Acotada):

Si existe una variable no básica $x_k$ tal que:

\[z_k - c_k > 0\]

y todos los elementos de su vector asociado son no positivos ($\mathbf{y}_k \leqslant 0$), entonces el problema tiene solución óptima no acotada.

Tercer Teorema (Condición de mejora de la solución):

Si para una solución básica factible existe una variable $x_k$ tal que:

\[z_k - c_k > 0\]

y al menos una componente de $\mathbf{y}_k$ es positiva ($\mathbf{y}_k \nleqslant 0$), existe una nueva base $\mathbf{B}’$ que proporciona una solución factible con un valor de la función objetivo menor o igual al actual.

Procedimiento en las iteraciones

El Algoritmo del Símplex trabaja sobre dos reglas: entrada, seleccionando la variable que entra en la base, y salida, seleccionando la variable que sale de la base.

• Regla de entrada:

  Entra la variable $x_k$ tal que:

  \[z_k - c_k = \max\{z_j-c_j>0 : j \in \mathcal{J}\}\]

  Si el problema es de maximización:

  \[z_k - c_k = \max\{z_j-c_j<0 : j \in \mathcal{J}\}\]

• Regla de salida:

  Sale la variable $x_l$ tal que:

  \[\frac{\bar{x}_l}{y_{lk}} \equiv \min \Bigg\{\frac{\bar{x}_s}{y_{sk}} : y_{sk} > 0\Bigg\}\]

• Cambio de base:

  Las fórmulas de cambio de base están basadas en el método de eliminación gaussiana.

Tablas del Símplex

Para la resolución manual de un problema de optimización lineal, se puede indexar toda la información en lo que se conocen como tablas del Símplex que se usaron por primera vez en (Charnes et al., 1953). Estas tablas permiten disponer del sistema explícito en función de una base $\mathbf{B}$ y tienen la siguiente forma:

\(\left. \begin{array}{cc|cccccccccc|c} & & {\color{gray}c_1} & {\color{gray}\ldots} & {\color{gray}c_l} & {\color{gray}\ldots} & {\color{gray}c_m} & {\color{gray}c_{m+1}} & {\color{gray}\ldots} & {\color{gray}c_k} & {\color{gray}\ldots} & {\color{gray}c_n} & \\ & & x_1 & \ldots & x_l & \ldots & x_m & x_{m+1} & \ldots & x_k & \ldots & x_n & \\ \hline & z_j-c_j & 0 & \ldots & 0 & \ldots & 0 & z_{m+1}-c_{m+1} & \ldots & z_k-c_k & \ldots & z_n-c_n & \bar{z} \\ \hline {\color{gray}c_1} & x_1 & 1 & \ldots & 0 & \ldots & 0 & y_{1m+1} & \ldots & y_{1k} & \ldots & y_{1n} & \bar{x}_1 \\ {\color{gray}\vdots} & \vdots & \vdots & & \vdots & & \vdots & \vdots & & \vdots & & \vdots & \vdots \\ {\color{gray}c_l} & x_l & 0 & \ldots & 1 & \ldots & 0 & y_{lm+1} & \ldots & y_{lk} & \ldots & y_{ln} & \bar{x}_l \\ {\color{gray}\vdots} & \vdots & \vdots & & \vdots & & \vdots & \vdots & & \vdots & & \vdots & \vdots \\ {\color{gray}c_m} & x_m & 0 & \ldots & 0 & \ldots & 1 & y_{mm+1} & \ldots & y_{mk} & \ldots & y_{mn} & \bar{x}_m \\ \hline \end{array} \right.\) donde las primeras $m$ variables son las variables básicas.

En la literatura pueden encontrarse las siguientes modificaciones:

• Fila $c_j-z_j$ en lugar de $z_j-c_j$. En cuyo caso, la regla de entrada debe adaptarse convenientemente.
• La fila $z_j-c_j$ puede aparecer al final de la tabla en lugar de arriba.
• La columna con la solución y el valor de la función objetivo puede aparecer antes de comenzar las variables.

Ejemplos numéricos

Sea el siguiente problema de optimización lineal:

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

La forma estándar de este problema (introduciendo 3 variables de holgura) viene dada por:

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

La primera tabla del Símplex viene dada por:

\[\begin{array}{rc|rrrrr|r} & & {\color{gray}6} & {\color{gray}3} & {\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 & -6 & -3 & 0 & 0 & 0 & 0 \\ \hline {\color{gray}0} & x_3^h & 2 & 4 & 1 & 0 & 0 & 8 \\ {\color{gray}0} & x_4^h & -1 & 4 & 0 & 1 & 0 & 4 \\ {\color{gray}0} & x_5^h & {\color{#2698ba}1} & -1 & 0 & 0 & 1 & 2 \\ \hline \end{array}\]

donde el elemento marcado en azul es el elemento pivote, es decir, el que indica la variable que sale ($x_5^h$) y la variable que entra ($x_1$) ya que nos encontramos en las condiciones del tercer teorema del Símplex.

La segunda tabla del Símplex viene dada por:

\[\begin{array}{rc|rrrrr|r} & & {\color{gray}6} & {\color{gray}3} & {\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 & -9 & 0 & 0 & 6 & 12 \\ \hline {\color{gray}0} & x_3^h & 0 & {\color{#2698ba}6} & 1 & 0 & -2 & 4 \\ {\color{gray}0} & x_4^h & 0 & 3 & 0 & 1 & 1 & 6 \\ {\color{gray}6} & x_1 & 1 & -1 & 0 & 0 & 1 & 2 \\ \hline \end{array}\]

Al seguir satisfaciendo las condiciones del tercer teorema del Símplex, se aplican la regla de entrada y salida para determinar el elemento pivote (en azul).

La tercera tabla del Símplex es:

\[\begin{array}{rc|rrrrr|r} & & {\color{gray}6} & {\color{gray}3} & {\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 & 3/2 & 0 & 3 & 18 \\ \hline {\color{gray}3} & x_2 & 0 & 1 & 1/6 & 0 & -1/3 & 2/3 \\ {\color{gray}0} & x_4^h & 0 & 0 & -1/2 & 1 & 2 & 4 \\ {\color{gray}6} & x_1 & 1 & 0 & 1/6 & 0 & 2/3 & 8/3 \\ \hline \end{array}\]

que ya cumple con las condiciones del primer teorema del Símplex, por tanto, se ha alcanzado la solución óptima:

\[(\mathbf{x}^*)^\intercal = (8/3, 2/3,0,4,0) \quad z^* = 18\]

Gráficamente, el recorrido seguido por el Símplex se muestra en la siguiente figura:

Con el Algoritmo Símplex, lo abstracto de la matemática se convierte en una herramienta práctica, demostrando que la elegancia de las matemáticas puede tener un impacto real en la vida diaria.