El arranque del Símplex, cómo comenzar cuando no hay solución básica evidente

En optimización lineal, el Algoritmo Símplex es uno de los métodos más utilizados para encontrar soluciones óptimas. Sin embargo, para empezar a “caminar”, el algoritmo necesita un punto de partida: una solución básica factible inicial.

¿Por qué necesitamos variables artificiales?

Cuando todas las restricciones de un problema son del tipo “menor o igual” ($\leqslant$) con recursos positivos, las variables de holgura crean de forma natural la matriz identidad, que sirve como base inicial.

El problema surge cuando aparecen restricciones de igualdad ($=$) o de tipo “mayor o igual” ($\geqslant$). En estos casos, no disponemos de la matriz identidad de forma inmediata. Para solucionarlo, introducimos variables artificiales ($x^a \geqslant 0$). Estas variables no tienen significado en el problema original: son simplemente un recurso matemático para construir una base inicial. El objetivo es que estas variables abandonen la base y tomen valor cero en la solución final, ya que si una variable artificial es positiva en la solución final, el problema original se considera infactible (no tiene ninguna solución que cumpla todas las restricciones).

Existen dos métodos principales para gestionar estas variables: el método de las penalizaciones o gran M, introducido en (Charnes et al., 1953) y el método de las dos fases, introducido en (Wagner, 1956).

El Método de las Penalizaciones o Gran M

Este método consiste en penalizar las variables artificiales en la función objetivo utilizando un valor M extremadamente grande.

• Si el objetivo es minimizar, se suma $M \cdot x^a$ por cada variable artificial.
• Si el objetivo es maximizar, se resta $M \cdot x^a$ por cada variable artificial.

Esta penalización tan alta obliga al algoritmo a intentar reducir el valor de las variables artificiales a cero para mejorar el valor de la función objetivo.

Consideremos el siguiente problema de optimización lineal:

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

Al aplicar el método de las penalizaciones, el modelo estándar introduce variables de holgura ($x_4^h$ y $x_5^h$). Como la primera restricción es de tipo $\geqslant$ y la tercera es una igualdad, no podemos obtener directamente una base identidad. Por ello es necesario introducir variables artificiales ($x_6^a, x_7^a$) quedando la forma estándar:

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

La segunda tabla proporciona la tabla final: \(\begin{array}{rc|rrrrrrr|r} & & {\color{gray}-5} & {\color{gray}6} & {\color{gray}7} & {\color{gray}0} & {\color{gray}0} & {\color{gray}-M} & {\color{gray}-M} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^a & x_7^a & \\ \hline & z_j - c_j & 8M+11 & 0 & 16M-1 & M & 0 & 0 & 6M+3 & -5M+15 \\ \hline {\color{gray}-M} & x_6^a & -8 & 0 & -16 & -1 & 0 & 1 & -5 & 5 \\ {\color{gray}0} & x_5^s & 6 & 0 & 8 & 0 & 1 & 0 & 3/2 & 35/2 \\ {\color{gray}6} & x_2 & 1 & 1 & 1 & 0 & 0 & 0 & 1/2 & 5/2 \\ \hline \end{array}\)

Como el valor de la función objetivo es $-5M+15 \neq 0$, al menos una variable artificial permanece en la base. Por tanto, el problema original es infactible.

El Método de las Dos Fases

Este enfoque separa el proceso en dos etapas claramente diferenciadas:

• Fase 1: Se olvida temporalmente la función objetivo original. En su lugar, se busca minimizar la suma de todas las variables artificiales ($w = \sum x^a$).
  • Si el valor mínimo de $w$ es 0, significa que hemos encontrado una solución factible para el problema original y podemos pasar a la siguiente fase.
  • Si es mayor que 0, el problema es infactible.
• Fase 2: Se descarta la función objetivo auxiliar de la Fase 1 y las columnas de las variables artificiales. Se recupera la función objetivo original y se continúa el Símplex desde la solución que se encontró en la Fase 1.

En el ejemplo anterior, el modelo auxiliar que se resuelve en la Fase 1, en forma estándar, es:

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

La segunda tabla proporciona la tabla final:

\[\begin{array}{rc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}1} & {\color{gray}1} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^a & x_7^a & \\ \hline & w_j - c_j & -8 & 0 & -16 & -1 & 0 & 0 & -6 & 5 \\ \hline {\color{gray}1} & x_6^a & -8 & 0 & -16 & -1 & 0 & 1 & -5 & 5 \\ {\color{gray}0} & x_5^s & 6 & 0 & 8 & 0 & 1 & 0 & 3/2 & 35/2 \\ {\color{gray}0} & x_2 & 1 & 1 & 1 & 0 & 0 & 0 & 1/2 & 5/2 \\ \hline \end{array}\]

Como el valor de la función objetivo es $5 \neq 0$, hay al menos una variable artificial en la base, en este caso $x_6^a$ y, por tanto, el problema original no tiene solución factible.

Si se hubiera conseguido una solución básica con $w=0$, se hubiera continuado con la segunda fase, considerando la función objetivo del problema inicial.

Ambos métodos permiten construir una base inicial para el Símplex. El método de las penalizaciones incorpora las variables artificiales directamente en la función objetivo, mientras que el método de las dos fases separa explícitamente la búsqueda de factibilidad del proceso de optimización.

En definitiva, tanto el método de las penalizaciones como el método de las dos fases proporcionan una forma sistemática de iniciar el algoritmo símplex cuando no se dispone de una base inicial evidente. Aunque ambos conducen al mismo objetivo, el método de las dos fases suele resultar más claro desde el punto de vista conceptual y es el que se utiliza con mayor frecuencia en implementaciones modernas.