El Algoritmo Símplex, el Motor de la Optimización Matemática

Desde su introducción por George B. Dantzig en 1947, 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.

A diferencia de otros métodos, el 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.

1. 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: \(\min z = \mathbf{c}^\intercal x\) sujeto a \(\mathbf{Ax} = \mathbf{b}\), \(\mathbf{x} \geqslant \mathbf{0}\)

Dividiendo las variables en básicas ($x_B$) y no básicas ($x_N$), y multiplicando por la inversa de la base ($B^{-1}$), obtenemos las ecuaciones clave [5, 6]:

• Ecuaciones de las variables básicas: \(x_B = \bar{x}_B - \sum_{j \in J} y_j x_j\) Donde $\bar{x}_B = B^{-1}b$ es la solución básica actual y $y_j = B^{-1}a_j$ [4].

• Ecuación de costes (Función Objetivo): \(z = \bar{z} - \sum_{j \in J} (z_j - c_j)x_j\) Aquí, $\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$ [7, 8].

2. Los Tres Teoremas del Símplex

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

1. Primer Teorema (Optimalidad): Una solución básica factible es óptima si para toda variable no básica se cumple que $z_j - c_j \leq 0$ [9, 10].
2. Segundo Teorema (Solución No Acotada): Si existe una variable no básica $k$ tal que $z_k - c_k > 0$ y todos los elementos de su vector asociado son no positivos ($y_k \leq 0$), entonces el problema tiene una solución óptima no acotada [11, 12].
3. Tercer Teorema (Mejora de la Solución): Si para una solución básica factible existe un índice $k$ tal que $z_k - c_k > 0$ y al menos un componente de $y_k$ es positivo ($y_k \not\leq 0$), existe una nueva base $B’$ que proporciona una solución factible con un valor de la función objetivo menor o igual al actual [13, 14].

3. Ejemplos Numéricos

Para ilustrar estos teoremas, veamos casos extraídos de situaciones reales de cálculo:

Caso A: Solución Óptima Alcanzada

En un problema de minimización con base $B_1$, obtenemos los siguientes valores [11, 15]:

• $\bar{z} = 6$
• $z_4 - c_4 = 0$
• $z_5 - c_5 = -6$ Al ser todos los $z_j - c_j \leq 0$, el Primer Teorema garantiza que la solución $(\bar{x}_1=1, \bar{x}_2=1, \bar{x}_3=1, \bar{x}_4=0, \bar{x}_5=0)$ es óptima [9, 11].

Caso B: Problema No Acotado

Consideremos un sistema donde identificamos una variable $x_2$ tal que [16]:

• $z_2 - c_2 = 2$ (Indica que el valor puede seguir bajando).
• $y_2 = \begin{pmatrix} 0 \ -1 \end{pmatrix}$ (No hay restricciones que detengan el crecimiento de $x_2$). Bajo el Segundo Teorema, concluimos que el valor de la función objetivo puede decrecer indefinidamente [16, 17].

Caso C: Mejora mediante Cambio de Base

Si partimos de una base $B_2$ donde $z_2 - c_2 = 6 > 0$ y el vector $y_2$ tiene componentes positivos como $\begin{pmatrix} 1 \ 0 \ 1 \end{pmatrix}$ [18, 19]: El Tercer Teorema nos indica que debemos realizar un “pivoteo”. Al introducir $x_2$ en la base y sacar la variable correspondiente (regla del cociente mínimo), logramos una nueva solución factible que mejora (o mantiene) el valor de la función objetivo [13, 20, 21].