Precios Sombra, Degenerancia y Fase 1

¿Cuánto vale un recurso extra?

Los precios sombra miden el valor marginal de cada restricción. Se obtienen de la base óptima y coinciden con las variables duales óptimas $y^{\ast }$ (lo veremos a fondo en el módulo de dualidad).

Interpretación

Regla clave: holgura ⇒ precio sombra cero

Si una restricción no está activa en el óptimo (le sobra holgura, $>0$), su precio sombra es ${\pi }_i=0$: tener más de ese recurso no mejora nada, porque ni siquiera estás usando todo el que ya tienes.

Sensibilidad del recurso

La base óptima se mantiene mientras la solución básica siga siendo factible, es decir, mientras al variar $b_i$ se conserve $A_B^{-1}b\ge 0$. Dentro de ese rango, $z^{\ast }$ cambia linealmente con pendiente ${\pi }_i$.

¿Qué es una solución degenerada?

Una SBF degenerada es aquella donde al menos una variable básica vale 0. Algebraicamente: $A_B^{-1}b$ tiene alguna componente nula.

Lectura geométrica

En el vértice se activan más de $n$ restricciones (más de las necesarias para definirlo). Eso hace que varias bases distintas representen el mismo vértice.

Por qué importa: ciclaje

Al haber varias bases para un mismo vértice, el Simplex puede repetir una base y quedar girando sin mejorar $z$ (ciclaje), sin avanzar hacia el óptimo.

Ejemplo resuelto (Ayudantía 10)

Para $\alpha x_1+x_2+x_3=5$, $x_1+\beta x_2+x_4=4$ con base $B=\{1,2\}$, se resuelve $A_B{x}_B=b$ y se busca cuándo una básica se anula:

Con $\alpha =\frac{5}{4}$ o $\beta =\frac{4}{5}$, una variable básica vale 0 y la SBF es degenerada (en el gráfico, 3 restricciones se cruzan en ese vértice). $■$

Cómo evitar el ciclaje

La regla de Bland es una forma de elegir variables entrante y saliente que garantiza que el Simplex termina en un número finito de pasos, incluso con degenerancia.

Las dos reglas

• Variable entrante: entre todas las no básicas con costo reducido negativo ($r_j<0$), elegir la de menor índice $j$.
• Variable saliente: si hay empate en el ratio test, elegir la variable básica de menor índice.

La gracia es que romper los empates siempre por el menor índice impide que el algoritmo vuelva a una base ya visitada, cerrando la puerta al ciclaje.

¿Y si no hay una base factible obvia?

Cuando el problema tiene restricciones $\ge$ o $=$, no aparece de forma natural una matriz identidad para arrancar el Simplex. La Fase 1 construye una solución básica factible inicial.

Variables artificiales

A cada restricción sin base obvia se le agrega una variable artificial $y_i\ge 0$, que sí da una identidad de partida. Luego se resuelve un problema auxiliar que busca expulsarlas (llevarlas a 0):

El criterio de factibilidad

• Si $z_{\text{FaseI}}={\sum }_i{y}_i=0$: todas las artificiales salieron ⇒ el problema original es factible. Se pasa a Fase II (se eliminan las artificiales y se restaura el objetivo original).
• Si $z_{\text{FaseI}}>0$: alguna artificial quedó positiva ⇒ el problema original es infactible (no existe solución).

Ejemplo (Ayudantía 10)

Para $\min 3x_1+x_2$ con $2x_1+4x_2\ge 2$ y $4x_1-x_2\ge 3$: se agregan excesos $x_3,x_4$ y artificiales $y_1,y_2$, y se plantea el auxiliar con base inicial $\{y_1,y_2\}$:

El recorrido completo (Ayudantía 10)

Seguimos el mismo problema $\min 3x_1+x_2$ con dos restricciones $\ge$. La Fase I itera el auxiliar $\min y_1+y_2$ hasta sacar las artificiales:

Al llegar a la base $\{x_1,x_2\}$ ya no quedan artificiales y se obtiene la SBF inicial del problema original:

Fase II

Se restaura el objetivo original $\min 3x_1+x_2$ y se calculan los costos reducidos desde la base $\{x_1,x_2\}$:

Como ${\bar{c}}_N\ge 0$, la solución ya es óptima. El óptimo del problema original es: