Cómo reconocer los distintos tipos de soluciones en optimización lineal con el Símplex

En un problema de optimización lineal no siempre existe una única solución óptima. Dependiendo de la geometría de la región factible y de la dirección de la función objetivo, pueden aparecer diferentes situaciones: una solución óptima única, múltiples soluciones óptimas, solución óptima no acotada o incluso problemas sin solución factible.

En el post La resolución gráfica como punto de partida en optimización lineal analizamos estos casos desde un punto de vista geométrico, representando gráficamente la región factible y la función objetivo. Aquella perspectiva permite comprender intuitivamente qué está ocurriendo en el problema.

Sin embargo, cuando el número de variables crece, la interpretación gráfica deja de ser viable. Aquí es donde entra en juego el Algoritmo del Símplex, que recorre los vértices del politopo factible y permite identificar de forma algebraica el tipo de solución del problema.

En este post veremos cómo el Símplex permite reconocer los cinco tipos de solución que puede presentar un problema de optimización lineal resolviendo los mismos problemas presentados en el post La resolución gráfica como punto de partida en optimización lineal.

Solución óptima única

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

Geométricamente, esto ocurre cuando la recta (o hiperplano) de la función objetivo toca la región factible en un único vértice.

Sea el 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}\]

su forma estándar

\[\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 tabla final del Símplex es:

\[\begin{array}{cc|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}\]

donde se observa que se cumplen las condiciones del primer teorema del Símplex, $z_j-c_j > 0$ (se trata de un problema de maximización) para toda variable no básica, es decir, ninguna variable no básica puede mejorar el valor de la función objetivo. Por tanto, el problema tiene solución óptima única:

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

Múltiples óptimos

El caso de multiplicidad de soluciones óptimas tiene dos opciones:

• Los óptimos se encuentran en una región convexa acotada.
• Los óptimos se encuentran en una región no acotada.

Se estudiarán ambos casos a continuación.

Múltiples óptimos en región acotada

El caso en que los óptimos se encuentran en una región convexa acotada queda determinado por la combinación lineal convexa de todos los puntos extremos que son óptimos. En el caso particular de $\mathbb{R}^2$ la única posibilidad es que exista un segmento de soluciones óptimas, delimitado por dos puntos extremos que serán los extremos del segmento.

Sea el problema de optimización lineal:

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

cuya forma estándar es:

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

La tabla final del Símplex es:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\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 & 1 & 0 & 0 & 8 \\ \hline {\color{gray}1} & x_2 & 0 & 1 & 2/3 & 0 & -1/3 & 10/3 \\ {\color{gray}0} & x_4^h & 0 & 0 & -4/3 & 1 & {\color{#2698ba}8/3} & 40/3 \\ {\color{gray}1} & x_1 & 1 & 0 & 1/3 & 0 & 1/3 & 14/3 \\ \hline \end{array}\]

donde se observa que se cumplen las condiciones del primer teorema del Símplex, $z_j-c_j \geqslant 0$ (se trata de un problema de maximización) para toda variable no básica. Sin embargo, para la variable no básica $x_5^h$, $z_5-c_5=0$, lo que indica que la solución no es única. Si se introduce la variable $x_5^h$ en la base, se obtiene la siguiente tabla del Símplex:

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

donde se obtiene otro punto extremo. Al estar en $\mathbb{R}^2$, el conjunto de soluciones óptimas se encuentra en el segmento que une los dos puntos extremos alcanzados. Por tanto, el conjunto de soluciones óptimas del problema se puede expresar:

\[\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2 = \lambda \left( \begin{array}{c} 3 \\ 5 \\ 0 \\ 0 \\ 5\end{array} \right) + (1-\lambda) \left(\begin{array}{c} 14/3 \\ 10/3 \\ 0 \\ 40/3 \\ 0\end{array}\right),\;\; \lambda \in [0,1] \qquad z^* = 8\]

Múltiples óptimos en región no acotada

Este caso tiene su interés matemático, pero no suele ser habitual en un contexto real ya que, las variables suelen estar acotadas por valores impuestos por la propia realidad.

Sea el problema de optimización lineal:

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

cuya forma estándar es:

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

en el que se ha introducido una variable artificial. Por tanto, se puede usar, o bien el método de las 2-fases o el método de las penalizaciones.

Con el método de las dos fases, la primera fase viene dada por el siguiente problema de optimización:

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

donde se obtiene esta tabla final para la primera fase:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}1} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^a & \\ \hline & w_j-c_j & 0 & 0 & 0 & 0 & -1 & 0 \\ \hline {\color{gray}0} & x_3^h & 2 & 0 & 1 & -1/2 & 1/2 & 5/2 \\ {\color{gray}0} & x_2 & 1 & 1 & 0 & -1/2 & 1/2 & 1/2 \\ \hline \end{array}\]

Como se obtiene $w=0$, se puede continuar con la segunda fase, actualizando la fila $z_j-c_j$ y eliminando la columna de la variable artificial $x_5^a$, obteniendo la siguiente tabla:

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

que resulta ser la tabla final. Se observa que la variable no básica $x_4^h$ tiene $z_4-c_4 = 0$. Por tanto, el problema tiene múltiples óptimos. Sin embargo, al intentar forzar la entrada de $x_4^h$ en la base, no se puede aplicar el criterio de salida al ser $\mathbf{y}_4 \leqslant \mathbf{0}$. Por tanto, se ha detectado una dirección extrema:

\[(\mathbf{d}^1)^\intercal = (0, 1/2, 1/2, 1)\]

Por tanto, las soluciones óptimas del problema vienen dadas por:

\[\mathbf{x}_1^* + \mu \mathbf{d}^1 = \left( \begin{array}{c} 0 \\ 1/2 \\ 5/2 \\ 0\end{array} \right) + \mu \left( \begin{array}{c} 0 \\ 1/2 \\ 1/2 \\ 1 \end{array} \right) \;\; \mu \geqslant 0 \qquad z^*=0\]

Con el método de las penalizaciones, el problema de optimización a resolver viene dado por:

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

La tabla final viene dada por:

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

de la que se observa que la variable no básica $x_4^h$ tiene $z_4-c_4 = 0$, al igual que usando el procedimiento de las dos fases, llegando a la misma conclusión.

Solución óptima no acotada

Que un problema tenga solución óptima no acotada, en la realidad puede suponer que falta alguna restricción por incorporar que termine por cerrar la región factible. Sin embargo, este caso es estudiado en dualidad y en métodos de descomposición que permiten resolver problemas de optimización más complejos.

Sea el siguiente problema de optimización lineal:

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

cuya forma estándar es:

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

en el que se han introducido dos variables artificiales. Por tanto, se puede usar, o bien el método de las 2-fases o el método de las penalizaciones.

Con el método de las dos fases, la primera fase viene dada por el siguiente problema de optimización:

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

donde se obtiene esta tabla final para la primera fase:

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

Como se ha obtenido una solución básica de modo que $w=0$, se puede continuar con la segunda fase, actualizando la fila $z_j-c_j$ y eliminando la columna de las variable artificial $x_5^a$.

La tabla final de la segunda fase viene dada por:

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

donde se observa que $x_1$ es candidata a entrar pero no puede hacerlo porque $\mathbf{y}_1 \leqslant \mathbf{0}$, por lo que se está en las condiciones del segundo teorema del Símplex y, por tanto, el problema tiene solución óptima no acotada.

Se puede obtener un rayo de no acotación que viene dado por el punto extremo de la tabla final y la dirección extrema obtenida en la variable $x_3^h$:

\[R=\left\{\left(\begin{array}{r} 0 \\ 4\\ 6 \\ 0\end{array} \right) + \mu\left(\begin{array}{r} 1 \\ 2 \\ 5 \\ 0\end{array} \right): \mu \geqslant 0\right\}\]

Con el método de las penalizaciones, el problema de optimización a resolver viene dado por:

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

La tabla final viene dada por:

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

donde se observa que la variable $x_1$ es candidata a entrar en la base, pero ninguna puede salir ya que $\mathbf{y}_1 \leqslant \mathbf{0}$, por tanto el problema tiene solución óptima no acotada. Al alcanzar el mismo punto extremo que con el procedimiento de 2 fases, el rayo de no acotación que se obtiene es el mismo.

Problema infactible

El caso de infactibilidad suele deberse al exceso de restricciones impidiendo que existan soluciones en el problema estudiado.

Sea el problema de optimización lineal:

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

cuya forma estándar es:

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

en el que se ha introducido una variable artificial. Por tanto, se puede usar, o bien el método de las 2-fases o el método de las penalizaciones.

Con el método de las dos fases, la primera fase viene dada por el siguiente problema de optimización:

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

donde se obtiene esta tabla final para la primera fase:

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

Se observa que $w \neq 0$ y la variable $x_5^a$ está en la base con $x_5^a \neq 0$. Por tanto, el problema original es infactible.

Con el método de las penalizaciones, el problema de optimización a resolver viene dado por:

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

La tabla final viene dada por:

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

donde se observa que la variable $x_5^a$ está en la base con $x_5^a \neq 0$ y, por tanto, el problema original es infactible.

Conclusión

El análisis gráfico permite entender intuitivamente qué ocurre en un problema de optimización lineal. Sin embargo, el Algoritmo del Símplex ofrece una forma sistemática de detectar exactamente esas mismas situaciones mediante operaciones algebraicas. Comprender esta conexión entre geometría y algoritmo es clave para interpretar correctamente el comportamiento del Símplex y los resultados que produce.

En la práctica, reconocer estos patrones en las tablas del Símplex permite diagnosticar rápidamente el tipo de problema al que nos enfrentamos y entender el significado de la solución obtenida.