El óptimo no es el final, claves de la post-optimización

Imagina que tienes un negocio, programas un modelo matemático para maximizar tus ganancias (o minimizar tus costes), el algoritmo corre y, ¡listo! Tienes la solución óptima en tus manos. Sabes exactamente cuánto producir y qué recursos usar. Todo parece perfecto hasta que… la vida real pasa: el precio de una materia prima fluctúa, un proveedor te ofrece una tonelada extra de recursos, o decides lanzar un nuevo producto al mercado.

¿Significa esto que tienes que tirar todo a la basura y volver a calcular el problema desde cero? Afortunadamente, no. Aquí es donde entra en juego la post-optimización, una de las aplicaciones más potentes e inteligentes de la optimización lineal.

¿Qué es la post-optimización?

En la práctica, casi ningún problema permanece inalterado durante mucho tiempo. Cambian los costes, aparecen nuevos productos, aumenta la disponibilidad de recursos o surgen nuevas restricciones que no existían cuando se resolvió el modelo.

La post-optimización estudia precisamente cómo afectan esos cambios a una solución óptima ya obtenida. En lugar de resolver nuevamente el problema desde cero, aprovecha la información disponible en la tabla final del método del Símplex para determinar si la solución sigue siendo válida o cómo puede actualizarse de forma eficiente.

A grandes rasgos, cuando el contexto cambia, la post-optimización nos permite gestionar dos grandes escenarios:

Modificaciones al modelo inicial: ¿Qué sucede si varía la disponibilidad de los recursos que ya tenemos o si cambian los beneficios económicos de nuestros productos actuales?
Extender el modelo inicial: ¿Qué pasa si decidimos introducir nuevas variables (como un producto completamente nuevo) o si se deben imponer nuevas restricciones operativas?

Ejemplo: un problema de planificación de la producción

Para ilustrar las distintas situaciones de post-optimización utilizaremos el mismo problema durante todo el post. De esta forma será más sencillo apreciar qué cambia en cada escenario y qué información puede reutilizarse de la solución original.

Consideremos una empresa que fabrica tres productos utilizando dos recursos limitados.

El modelo de optimización lineal es

\[\begin{aligned} \max\quad & z=3x_1+2x_2+x_3\\ \text{s.a:}\quad & 4x_1 + 2x_2 + 3x_3 \leqslant 40\\ & 2x_1 + 2x_2 + x_3 \leqslant 30\\ & x_1,x_2,x_3 \geqslant 0 \end{aligned}\]

cuya tabla final del Símplex es:

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

La solución óptima es

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0)\]

con un beneficio

\[z^*=35\]

Una vez obtenida esta solución aparecen preguntas mucho más interesantes que el propio problema original:

¿Qué ocurre si aumenta el beneficio de uno de los productos?
¿Qué sucede si se dispone de más materia prima?
¿Qué recurso resulta realmente escaso?
¿Qué ocurre si cambia la línea de producción de un producto y cambian las especificaciones técnicas?
¿Qué ocurre si se incorpora un nuevo producto a la línea de producción?
¿Qué ocurre si se incluyen nuevas condiciones al problema?

Estas cuestiones constituyen el núcleo de la post-optimización.

Modificaciones del modelo

En los siguientes apartados estudiaremos modificaciones que no alteran la estructura del problema, sino únicamente los datos con los que fue formulado. La base óptima obtenida puede seguir siendo útil, aunque será necesario comprobar si continúa siendo factible y/o óptima. En este caso cambian los datos disponibles.

Vector de recursos

Un análisis de sensibilidad más habituales consiste en estudiar cómo afectan a la solución óptima los cambios en la disponibilidad de recursos. En términos del modelo, esto equivale a modificar el vector de recursos, $\mathbf{b}$.

Sea $\hat{\mathbf{b}}$ el nuevo vector de recursos. Si la base óptima $\mathbf{B}$ permanece inalterada, la nueva solución básica se obtiene como:

\[\hat{\mathbf{x}}_\mathbf{B} = \mathbf{B}^{-1}\hat{\mathbf{b}}\]

y el nuevo valor de la función objetivo es

\[\hat{z}= \mathbf{c}_\mathbf{B}^\intercal \hat{\mathbf{x}}_\mathbf{B}\]

Una vez calculada la nueva solución básica, pueden darse dos situaciones:

La solución sigue siendo factible, es decir,
\[\hat{\mathbf{x}}_\mathbf{B} \geqslant \mathbf{0}\]
En este caso, la base continúa siendo factible y, como los costes reducidos no han variado, también sigue siendo óptima. Por tanto, la nueva solución del problema es $\hat{\mathbf{x}}_\mathbf{B}$ y el nuevo valor óptimo de la función objetivo es $\hat{z}$.
La solución deja de ser factible, es decir, alguna de las componentes de $\hat{\mathbf{x}}_\mathbf{B}$ es negativa.

En esta situación se pierde la factibilidad primal, aunque la base sigue siendo dual factible. Por ello, no es necesario resolver el problema desde cero, sino que basta con aplicar el algoritmo Dual del Símplex, que permitirá recuperar la factibilidad y obtener la nueva solución óptima de forma eficiente.

Ejemplo: modificación del vector de recursos

Para ilustrar el procedimiento, consideremos el problema resuelto en la sección anterior y supongamos que el vector de recursos cambia. Analizaremos dos situaciones distintas:

$\hat{\mathbf{b}}_1^\intercal=(38,36)$
$\hat{\mathbf{b}}_2^\intercal=(20,60)$

En ambos casos utilizaremos la misma base óptima obtenida previamente y comprobaremos si continúa siendo factible.

Caso 1: la nueva base sigue siendo factible

Si el nuevo vector de recursos es

\[\hat{\mathbf{b}}^\intercal=(38,36)\]

la nueva solución básica viene dada por

\[\hat{\mathbf{x}}_\mathbf{B}=\mathbf{B}^{-1}\hat{\mathbf{b}}= \begin{pmatrix} \frac12 & -\frac12\\ -\frac12 & 1 \end{pmatrix} \begin{pmatrix} 38\\ 36 \end{pmatrix}= \begin{pmatrix} 1\\ 17 \end{pmatrix}\]

Como

\[\hat{\mathbf{x}}_\mathbf{B} \geqslant \mathbf{0}\]

la base continúa siendo factible y, por tanto, también sigue siendo óptima.

El nuevo valor de la función objetivo es

\[\hat{z}=\mathbf{c}_\mathbf{B}^\intercal\hat{\mathbf{x}}_\mathbf{B}=(3,2) \begin{pmatrix} 1\\ 17 \end{pmatrix} = 37\]

La nueva solución óptima es, por tanto,

\[(\mathbf{x}^*)^\intercal=(1,17,0,0,0)\qquad z^*=37\]

La tabla final únicamente cambia en la columna correspondiente al lado derecho:

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

En este caso no es necesario realizar ninguna iteración adicional del algoritmo del símplex.

Caso 2: la nueva base pierde la factibilidad

Consideremos ahora el nuevo vector de recursos

\[\hat{\mathbf{b}}^\intercal=(20,60)\]

La nueva solución básica es

\[\hat{\mathbf{x}}_\mathbf{B}=\mathbf{B}^{-1}\hat{\mathbf{b}}= \begin{pmatrix} \frac12 & -\frac12\\ -\frac12 & 1 \end{pmatrix} \begin{pmatrix} 20\\ 60 \end{pmatrix}= \begin{pmatrix} -20\\ 50 \end{pmatrix}\]

En este caso,

\[\hat{\mathbf{x}}_\mathbf{B} \ngeqslant \mathbf{0}\]

por lo que la base deja de ser factible.

Aunque el nuevo valor de la función objetivo asociado a esta base sería

\[\hat{z}=\mathbf{c}_\mathbf{B}^\intercal\hat{\mathbf{x}}_\mathbf{B}= (3,2) \begin{pmatrix} -20\\ 50 \end{pmatrix} =40\]

esta solución no es válida porque una de las variables básicas toma un valor negativo.

La tabla actualizada es

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & 0 & 1 & \frac12 & \frac12 & 40\\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac12 & {\color{#2698ba}-\frac12} & -20\\ {\color{gray}2} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 50\\ \hline \end{array}\]

Como la factibilidad primal se ha perdido, es necesario aplicar el algoritmo Dual del Símplex para recuperar una solución factible manteniendo la optimalidad dual.

Tras aplicar una iteración del algoritmo dual del símplex se obtiene el siguiente tableau óptimo:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}0} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & 1 & 0 & 2 & 1 & 0 & 20\\ \hline {\color{gray}0} & x_5^h & -2 & 0 & -2 & -1 & 1 & 40\\ {\color{gray}2} & x_2 & 2 & 1 & \frac32 & \frac12 & 0 & 10\\ \hline \end{array}\]

Por tanto, la nueva solución óptima es

\[(\mathbf{x}^*)^\intercal=(0,10,0,0,40) \qquad z^*=20\]

Vector de costes

Otro análisis de sensibilidad muy habitual consiste en estudiar cómo afectan a la solución óptima los cambios en los coeficientes de la función objetivo, es decir, en el vector de costes $\mathbf{c}$.

A diferencia de las modificaciones en el vector de recursos, en este caso la solución básica no cambia. Lo que cambia son los costes reducidos y, en consecuencia, el valor de la función objetivo.

Sea $\hat{\mathbf{c}}$ el nuevo vector de costes. Si se mantiene la misma base $\mathbf{B}$, los nuevos valores $\hat{z}_j-\hat{c}_j$ vienen dados por

\[\hat{z}_j-\hat{c}_j = \hat{\mathbf{c}}_\mathbf{B}^\intercal \mathbf{B}^{-1}\mathbf{a}_j - \hat{c}_j = \hat{\mathbf{c}}_\mathbf{B}^\intercal \mathbf{y}_j - \hat{c}_j\]

mientras que el nuevo valor de la función objetivo es

\[\hat{z} = \hat{\mathbf{c}}_\mathbf{B}^\intercal \mathbf{x}_\mathbf{B}\]

A partir de estos nuevos costes reducidos pueden darse dos situaciones:

La base continúa siendo óptima. En un problema de maximización esto ocurre si
\[\hat{z}_j-\hat{c}_j \geqslant 0 \qquad \forall j\]
En ese caso, la solución básica $\mathbf{x}_\mathbf{B}$ sigue siendo óptima y únicamente cambia el valor de la función objetivo.
La base deja de ser óptima. Si existe alguna variable no básica cuyo coste reducido verifica
\[\hat{z}_j-\hat{c}_j<0\]
entonces la tabla deja de ser final. Como la factibilidad no se ha perdido, basta con continuar las iteraciones mediante el algoritmo Primal del Símplex.

Ejemplo: modificación del vector de costes

Consideremos el problema anterior y supongamos ahora que el vector de costes se modifica. Analizaremos dos casos:

$\hat{\mathbf{c}}_1^\intercal=(4,3,1)$
$\hat{\mathbf{c}}_2^\intercal=(1,1,1)$

Caso 1: la base sigue siendo óptima

\[\hat{\mathbf{c}}^\intercal=(4,3,1)\]

los nuevos valores $z_j-c_j$ son

\[\begin{aligned} \hat{z}_1-\hat{c}_1 &=0\\ \hat{z}_2-\hat{c}_2 &=0\\ \hat{z}_3-\hat{c}_3 &=\frac32\\ \hat{z}_4-\hat{c}_4 &=\frac12\\ \hat{z}_5-\hat{c}_5 &=1 \end{aligned}\]

Como todos los costes reducidos son no negativos, la base continúa siendo óptima.

El nuevo valor de la función objetivo es

\[\hat{z} = (4,3) \begin{pmatrix} 5\\ 10 \end{pmatrix} = 50\]

por lo que la solución óptima sigue siendo

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0) \qquad z^*=50\]

La nueva tabla final es

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}4} & {\color{gray}3} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & 0 & \frac32 & \frac12 & 1 & 50\\ \hline {\color{gray}4} & x_1 & 1 & 0 & 1 & \frac12 & -\frac12 & 5\\ {\color{gray}3} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 10\\ \hline \end{array}\]

No es necesario realizar ninguna iteración adicional del algoritmo del símplex.

Caso 2: la base deja de ser óptima

Supongamos ahora que

\[\hat{\mathbf{c}}^\intercal=(1,1,1)\]

Los nuevos valores $z_j-c_j$ son

\[\begin{aligned} \hat{z}_1-\hat{c}_1 &=0\\ \hat{z}_2-\hat{c}_2 &=0\\ \hat{z}_3-\hat{c}_3 &=-\frac12\\ \hat{z}_4-\hat{c}_4 &=0\\ \hat{z}_5-\hat{c}_5 &=\frac12 \end{aligned}\]

Obsérvese que

\[\hat{z}_3-\hat{c}_3<0\]

por lo que la condición de optimalidad deja de cumplirse.

La tabla actualizada es

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\color{gray}1} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & 0 & -\frac12 & 0 & \frac12 & 15\\ \hline {\color{gray}1} & x_1 & 1 & 0 & {\color{#2698ba}1} & \frac12 & -\frac12 & 5\\ {\color{gray}1} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 10\\ \hline \end{array}\]

Como la solución sigue siendo factible pero ya no es óptima, basta con aplicar el algoritmo primal del Símplex.

Tras una iteración se obtiene la nueva tabla final

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}1} & {\color{gray}1} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & \frac12 & 0 & 0 & \frac14 & \frac14 & \frac{35}{2}\\ \hline {\color{gray}1} & x_3 & 1 & 0 & 1 & \frac12 & -\frac12 & 5\\ {\color{gray}1} & x_2 & \frac12 & 1 & 0 & -\frac14 & \frac34 & \frac{25}{2}\\ \hline \end{array}\]

Por tanto, la nueva solución óptima es

\[(\mathbf{x}^*)^\intercal = (0,25/2,5,0,0) \qquad z^* = 35/2\]

Coeficientes técnicos de un vector no básico

Otro análisis de sensibilidad consiste en estudiar cómo afectan a la solución óptima las modificaciones en una de las columnas no básicas de la matriz de restricciones. Este tipo de cambios puede aparecer, por ejemplo, cuando una actividad consume una cantidad diferente de recursos o cuando se modifica la formulación de una variable.

Si la columna modificada corresponde a una variable no básica, la base permanece inalterada. Sin embargo, cambian tanto la columna correspondiente de la tabla del Símplex como el coste reducido de dicha variable.

Sea $\hat{\mathbf{a}}_j$ la nueva columna asociada a la variable no básica $x_j$. La nueva columna de la tabla viene dada por

\[\hat{\mathbf{y}}_j = \mathbf{B}^{-1}\hat{\mathbf{a}}_j\]

mientras que su nuevo coste reducido es

\[\hat{z}_j-c_j = \mathbf{c}_\mathbf{B}^\intercal \mathbf{B}^{-1} \hat{\mathbf{a}}_j - c_j = \mathbf{c}_\mathbf{B}^\intercal \hat{\mathbf{y}}_j - c_j\]

A partir de este nuevo coste reducido pueden darse dos situaciones:

La base continúa siendo óptima. En un problema de maximización esto ocurre si
\[\hat{z}_j - c_j \geqslant 0\]
En este caso, la solución básica no cambia y el valor de la función objetivo permanece inalterado.
La base deja de ser óptima. Si
\[\hat{z}_j-c_j<0\]
la variable modificada pasa a ser candidata a entrar en la base. Como la solución sigue siendo factible, basta con continuar las iteraciones mediante el algoritmo primal del Símplex.

Ejemplo: modificación del vector de coeficientes técnicos

Consideremos el problema anterior y supongamos que la tercera columna de la matriz de restricciones se modifica. Analizaremos dos posibilidades:

$\hat{\mathbf{a}}_{3_1}^\intercal=(4,2)$
$\hat{\mathbf{a}}_{3_2}^\intercal=\left(\frac12,1\right)$

Caso 1: la base sigue siendo óptima

\[\hat{\mathbf{a}}_{3_1}^\intercal=(4,2)\]

la nueva columna de la tabla es

\[\hat{\mathbf{y}}_3 = \mathbf{B}^{-1} \hat{\mathbf{a}}_{3_1} = \begin{pmatrix} \frac12 & -\frac12\\ -\frac12 & 1 \end{pmatrix} \begin{pmatrix} 4\\ 2 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix}\]

El nuevo valor $z_j-c_j$ resulta

\[\hat{z}_3-c_3 = (3,2) \begin{pmatrix} 1\\ 0 \end{pmatrix} - 1 = 2\]

Como el coste reducido sigue siendo no negativo, la base continúa siendo óptima.

La solución óptima permanece inalterada,

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0)\]

y el valor óptimo sigue siendo $z^*=35$

La nueva tabla final es

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

No es necesario realizar ninguna iteración adicional.

Caso 2: la base deja de ser óptima

Supongamos ahora que

\[\hat{\mathbf{a}}_{3_2}^\intercal = \left(\frac12,1\right)\]

La nueva columna de la tabla es

\[\hat{\mathbf{y}}_3 = \mathbf{B}^{-1} \hat{\mathbf{a}}_{3_2} = \begin{pmatrix} -\frac14\\ \frac34 \end{pmatrix}\]

y el nuevo valor $z_j-c_j$ resulta

\[\hat{z}_3-c_3 = (3,2) \begin{pmatrix} -\frac14\\ \frac34 \end{pmatrix} - 1 = -\frac14\]

Como

\[\hat{z}_3-c_3<0\]

la condición de optimalidad deja de cumplirse.

La tabla actualizada es

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & 0 & -\frac14 & \frac12 & \frac12 & 35\\ \hline {\color{gray}3} & x_1 & 1 & 0 & -\frac14 & \frac12 & -\frac12 & 5\\ {\color{gray}2} & x_2 & 0 & 1 & \frac34 & -\frac12 & 1 & 10\\ \hline \end{array}\]

Como la solución sigue siendo factible, basta con continuar las iteraciones mediante el algoritmo primal del Símplex.

Tras una iteración se obtiene la siguiente tabla final:

\[\begin{array}{cc|rrrrr|r} & & {\color{gray}3} & {\color{gray}1} & {\color{gray}1} & {\color{gray}0} & {\color{gray}0} & \\ & & x_1 & x_2 & x_3 & x_4^h & x_5^h & \\ \hline & z_j-c_j & 0 & \frac13 & 0 & \frac13 & \frac56 & \frac{115}{3}\\ \hline {\color{gray}3} & x_1 & 1 & \frac13 & 0 & \frac13 & -\frac16 & \frac{25}{3}\\ {\color{gray}1} & x_3 & 0 & \frac43 & 1 & -\frac23 & \frac43 & \frac{40}{3}\\ \hline \end{array}\]

Por tanto, la nueva solución óptima es

\[(\mathbf{x}^*)^\intercal = (25/3,0,40/3,0,0) \qquad z^* = 115/3\]

Ampliaciones del modelo

Hasta ahora únicamente hemos modificado información existente del problema. A continuación analizaremos situaciones en las que el propio modelo cambia de dimensión al incorporar nuevas variables o nuevas restricciones. En este caso, el modelo aumenta de tamaño.

Incorporación de una nueva variable

Otro escenario habitual en post-optimización consiste en analizar qué ocurre cuando se incorpora una nueva variable de decisión al modelo. Esto sucede, por ejemplo, cuando una empresa estudia producir un nuevo producto o prestar un nuevo servicio sin necesidad de reformular completamente el problema.

Desde el punto de vista del algoritmo del Símplex, añadir una nueva variable implica incorporar una nueva columna a la tabla.

Sea $x_{n+1}$ la nueva variable, caracterizada por su columna de coeficientes $\mathbf{a}_{n+1}$ y su coeficiente en la función objetivo $c_{n+1}$. La nueva columna de la tabla se obtiene como

\[\mathbf{y}_{n+1} = \mathbf{B}^{-1}\mathbf{a}_{n+1}\]

mientras que su valor $z_j-c_j$ viene dado por

\[z_{n+1}-c_{n+1} = \mathbf{c}_\mathbf{B}^\intercal \mathbf{y}_{n+1} - c_{n+1}\]

A partir de este valor pueden darse dos situaciones:

La nueva variable no mejora la solución. En un problema de maximización esto ocurre cuando
\[z_{n+1}-c_{n+1} \geqslant 0\]
En ese caso, la nueva variable permanece fuera de la base y la solución óptima no cambia.
La nueva variable mejora la solución. Si
\[z_{n+1}-c_{n+1}<0\]
la nueva variable es candidata a entrar en la base. Como la solución sigue siendo factible, basta con continuar las iteraciones mediante el algoritmo Primal del Símplex.

Añadir una nueva restricción

Otro análisis habitual de post-optimización consiste en estudiar el efecto de incorporar una nueva restricción al modelo. Este caso aparece cuando el problema original debe adaptarse a nuevas limitaciones, como la disponibilidad de un nuevo recurso, una capacidad adicional o una nueva condición de funcionamiento.

A diferencia de los casos anteriores, añadir una restricción implica incorporar también una nueva variable de holgura, por lo que la tabla del Símplex aumenta una fila y una columna.

Inicialmente, la nueva fila no suele preservar la estructura de la matriz identidad correspondiente a las variables básicas. Sin embargo, esta puede recuperarse combinando adecuadamente las filas existentes de la tabla.

Una vez reconstruida la identidad, pueden darse dos situaciones:

La solución continúa siendo factible. En este caso, la tabla sigue siendo final y la solución no cambia.
La solución deja de ser factible. Si alguna variable básica toma un valor negativo, la factibilidad primal se pierde y es necesario continuar mediante el algoritmo Dual del Símplex.

Ejemplo: Incorporación de una nueva restricción

Partimos del problema resuelto anteriormente e incorporamos un tercer recurso, cuyos coeficientes son

\[(1,1,1)\]

Analizaremos dos disponibilidades distintas para este nuevo recurso:

$b_3=20$.
$b_3=10$.

Caso 1: la solución sigue siendo factible

La nueva restricción es

\[x_1+x_2+x_3 \leqslant 20\]

En forma estándar queda

\[x_1+x_2+x_3+x_6^h=20\]

Al añadir esta nueva ecuación a la tabla se obtiene inicialmente

\[\begin{array}{cc|rrrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\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 & 1 & \frac12 & \frac12 & 0 & 35\\ \hline {\color{gray}3} & x_1 & 1 & 0 & 1 & \frac12 & -\frac12 & 0 & 5\\ {\color{gray}2} & x_2 & 0 & 1 & -\frac12 & -\frac12 & 1 & 0 & 10\\ {\color{gray}0} & x_6^h & 1 & 1 & 1 & 0 & 0 & 1 & 20\\ \hline \end{array}\]

Obsérvese que la matriz identidad ya no aparece de forma explícita. Para recuperarla basta con restar a la nueva fila la suma de las dos filas básicas existentes.

Tras realizar esta operación se obtiene

Como todas las variables básicas continúan siendo no negativas, la factibilidad primal se mantiene.

Por tanto, la solución óptima pasa a ser

\[(\mathbf{x}^*)^\intercal=(5,10,0,0,0,5)\]

con el mismo valor de la función objetivo,

\[z^*=35\]

No es necesario realizar ninguna iteración adicional.

Caso 2: la solución deja de ser factible

Supongamos ahora que la disponibilidad del nuevo recurso es únicamente

\[b_3=10\]

La nueva restricción queda

\[x_1+x_2+x_3+x_6^h=10\]

Repitiendo el mismo procedimiento para reconstruir la matriz identidad se obtiene la tabla

En este caso aparece una variable básica negativa,

\[x_6^h=-5\]

por lo que la solución deja de ser factible.

La optimalidad dual se conserva, pero la factibilidad primal se ha perdido. En consecuencia, el tableau puede reoptimizarse directamente mediante el algoritmo Dual del Símplex.

Tras una iteración se obtiene la siguiente tabla final:

\[\begin{array}{cc|rrrrrr|r} & & {\color{gray}3} & {\color{gray}2} & {\color{gray}1} & {\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 & \frac32 & \frac12 & 0 & 1 & 30\\ \hline {\color{gray}3} & x_1 & 1 & 0 & \frac12 & \frac12 & 0 & -1 & 10\\ {\color{gray}2} & x_2 & 0 & 1 & \frac12 & -\frac12 & 0 & 2 & 0\\ {\color{gray}0} & x_5^h & 0 & 0 & -1 & 0 & 1 & -2 & 10\\ \hline \end{array}\]

La nueva solución óptima es

\[(\mathbf{x}^*)^\intercal=(10,0,0,0,10,0)\]

con un valor de la función objetivo

\[z^*=30\]

Resumen

A lo largo de este post hemos visto que no todas las modificaciones afectan del mismo modo a una solución óptima. Dependiendo del elemento que cambie, puede perderse la factibilidad, la optimalidad o ambas, lo que determina si es posible reutilizar la tabla final o si es necesario continuar iterando mediante alguno de los algoritmos del método del Símplex.

La siguiente tabla resume los casos más habituales:

Modificación	¿Se pierde la factibilidad primal?	¿Se pierde la factibilidad dual?	Algoritmo a aplicar
Cambio en el vector de recursos $\mathbf{b}$	Puede ocurrir	No	Símplex Dual (si se pierde la factibilidad)
Cambio en el vector de costes $\mathbf{c}$	No	Puede ocurrir	Símplex Primal (si se pierde la optimalidad)
Cambio en una columna no básica $\mathbf{a}_j$	No	Puede ocurrir	Símplex Primal (si se pierde la optimalidad)
Incorporación de una nueva variable	No	Puede ocurrir	Símplex Primal (si la nueva variable mejora la solución)
Incorporación de una nueva restricción	Puede ocurrir	No	Símplex Dual (si se pierde la factibilidad)

Puede observarse un patrón muy interesante:

Cuando una modificación afecta a la factibilidad de la solución, el algoritmo adecuado para recuperar el óptimo es el Símplex Dual.
Cuando la modificación afecta únicamente a la optimalidad, manteniéndose la factibilidad, basta con continuar mediante el Símplex Primal.

Una de las principales ventajas del método del Símplex es que la tabla final contiene mucha más información que una simple solución óptima. Esa información permite analizar rápidamente qué ocurre cuando cambian los datos del problema, evitando resolver nuevamente el modelo desde cero en muchas situaciones.

Como hemos visto, el tipo de modificación determina también el algoritmo que debe utilizarse para reoptimizar el problema. Si se pierde la factibilidad primal, el Símplex Dual resulta el procedimiento natural. Si se pierde la factibilidad dual, basta con continuar mediante el Símplex Primal.

La post-optimización convierte así una solución óptima en una herramienta dinámica, capaz de adaptarse de forma eficiente a los cambios que inevitablemente aparecen en problemas reales.

El óptimo no es el final, claves de la post-optimización

¿Qué es la post-optimización?

Ejemplo: un problema de planificación de la producción

Modificaciones del modelo

Vector de recursos

Ejemplo: modificación del vector de recursos

Vector de costes

Ejemplo: modificación del vector de costes

Coeficientes técnicos de un vector no básico

Ejemplo: modificación del vector de coeficientes técnicos

Ampliaciones del modelo

Incorporación de una nueva variable

Ejemplo: Incorporación de una nueva variable

Añadir una nueva restricción

Ejemplo: Incorporación de una nueva restricción

Resumen

Referencias

Le gustó leer este artículo?