Tipología de soluciones, degeneración y método de las dos fases

1. La pregunta

El símplex del tema 16 funcionaba porque el problema venía bien portado: todas las restricciones de tipo $\le$, el origen era factible, y cada iteración mejoraba el objetivo.

Los problemas reales no son así. Una dieta exige mínimos, no máximos, y entonces el origen no es factible: no hay por dónde empezar. Y a veces el algoritmo da vueltas sin mejorar, repitiendo tablas. Este tema resuelve las dos cosas: el método de las dos fases para arrancar, y el diagnóstico de la degeneración para no quedarse atrapado.

También enseña a leer en la tabla final los tres casos que el método gráfico permitía ver a simple vista: solución única, soluciones múltiples y problema no acotado.

2. Intuición

El problema de arranque. El símplex empieza en un vértice factible y va saltando a vecinos mejores. Con restricciones de tipo $\le$, el origen —no hacer nada— siempre es factible y sirve de arranque. Pero si hay que producir al menos 100 unidades, no hacer nada está prohibido: el origen queda fuera de la región y no hay dónde poner el pie.

La solución es un truco elegante. Se inventan unas variables artificiales que permiten hacer trampa —cumplir las restricciones sin cumplirlas de verdad— y se resuelve primero un problema auxiliar cuyo único objetivo es eliminar la trampa. Si se consigue, se ha encontrado un vértice factible auténtico y desde ahí se sigue con el problema real. Eso son las dos fases.

Y si no se consigue eliminar la trampa, es que no hay ningún punto factible: las restricciones se contradicen. El método diagnostica la infactibilidad como subproducto.

El problema de los bucles. A veces, al calcular la razón mínima, hay empate. Eso significa que en ese vértice coinciden más restricciones de las necesarias: un vértice «sobredeterminado». Al pivotar, la variable entrante crece cero unidades, el objetivo no mejora y solo cambian las etiquetas de la base. Es una iteración degenerada.

Casi siempre es inofensivo: a la siguiente iteración se sale. Pero en teoría se puede volver a una base ya visitada y entrar en un ciclo infinito. Es rarísimo en la práctica y hay reglas que lo evitan por completo.

3. Formalización

Los cuatro desenlaces posibles

Caso	Cómo se detecta en la tabla	Qué significa
Solución única	óptimo con todos los $z_j-c_j$ de las no básicas estrictamente positivos	un solo plan óptimo
Soluciones múltiples	óptimo con algún $z_j-c_j=0$ en una variable no básica	infinitos planes óptimos, todos con el mismo $z$
No acotado	la columna de la variable entrante no tiene ningún coeficiente positivo	falta una restricción en el modelo
Infactible	la fase I termina con valor objetivo distinto de cero	las restricciones se contradicen

Los cuatro se corresponden con lo que se veía gráficamente en el tema 15.

Soluciones múltiples

Si en la tabla óptima una variable no básica tiene $z_j-c_j=0$, esa variable puede entrar en la base sin cambiar el valor de $z$. Se obtiene otro vértice óptimo, y todos los puntos del segmento que une los dos vértices son también óptimos.

La solución general se escribe como combinación convexa (tema 9):

$$\mathbf{x}=\lambda {\mathbf{x}}^A+(1-\lambda ){\mathbf{x}}^B,\lambda \in [0,1]$$

Económicamente es una buena noticia: hay margen para elegir por criterios que el modelo no recoge (plazos, preferencias del cliente, riesgo) sin perder ni un euro.

Degeneración

Una solución básica factible es degenerada si alguna variable básica vale cero.

Ocurre cuando hay empate en la razón mínima: dos filas alcanzan el mismo $\theta$. Al pivotar, la que no sale se queda en la base con valor cero.

Consecuencias:

• La iteración siguiente puede tener $\theta =0$: la variable entra con valor cero, el objetivo no mejora y solo cambian las etiquetas de la base.
• En teoría se puede volver a una base ya visitada y ciclar indefinidamente.

Cómo se evita. La regla de Bland: entre las candidatas a entrar, elegir siempre la de menor índice; y en caso de empate al salir, también la de menor índice. Con esa regla se demuestra que el símplex termina siempre. Converge más despacio, así que se aplica solo si se detecta ciclado.

Interpretación económica. La degeneración señala que en ese vértice hay restricciones redundantes: más limitaciones activas de las necesarias para determinar el punto. Suele indicar que el modelo tiene condiciones duplicadas o que algunos recursos se agotan exactamente a la vez.

Método de las dos fases

Se usa cuando hay restricciones de tipo $\ge$ o $=$, porque entonces el origen no es factible.

Preparación. Tras pasar a forma estándar:

• $a^{\top }\mathbf{x}\ge b$ se convierte en $a^{\top }\mathbf{x}-e+A=b$, con $e$ la variable de excedente y $A$ una artificial.
• $a^{\top }\mathbf{x}=b$ se convierte en $a^{\top }\mathbf{x}+A=b$.

Las artificiales no tienen ningún significado económico: son un andamio. Si alguna acaba con valor positivo, la «solución» viola una restricción.

Fase I. Se resuelve

$$\min w=\sum _j{A}_j$$

sujeto a las mismas restricciones. Como las artificiales forman una base factible inmediata, el símplex arranca sin problema.

• Si el óptimo es $w^{\ast }=0$, todas las artificiales han salido de la base (o valen cero) y se ha encontrado un vértice factible del problema real. Se pasa a la fase II.
• Si $w^{\ast }>0$, no hay forma de anularlas: el problema es infactible.

Fase II. Se eliminan las columnas de las artificiales, se recupera la función objetivo original y se sigue iterando desde la tabla obtenida.

Detalle práctico. Antes de empezar la fase I hay que poner la fila objetivo en términos de las no básicas: como las artificiales están en la base, se restan sus filas de la fila $w$. Es el paso que más se olvida y sin él la tabla inicial es incorrecta.

Alternativa: método de la penalización (Gran M)

En lugar de dos fases, se añaden las artificiales a la función objetivo original con un coeficiente enorme $-M$ (en un problema de máximo). Así el algoritmo las expulsa por su cuenta.

Es más corto de escribir pero incómodo a mano —hay que arrastrar la $M$ simbólicamente— y numéricamente inestable en ordenador. En este curso se prefieren las dos fases, que es también lo que hace el material de la UPV/EHU.

4. Ejemplo económico resuelto

Problema. Un centro debe preparar una mezcla nutritiva con al menos 90 g de proteína y al menos 120 g de hidratos, usando dos ingredientes. Cada unidad de $x_1$ aporta 3 g de proteína y 2 g de hidratos y cuesta 4 €; cada unidad de $x_2$ aporta 1 g y 4 g y cuesta 3 €. Minimiza el coste.

Paso 1. Formular.

$$\min z=4x_1+3x_2$$ $$\text{s.a.}3x_1+x_2\ge 90,2x_1+4x_2\ge 120,x_1,x_2\ge 0$$

El origen no es factible ($0\ge 90$ es falso): hacen falta las dos fases.

Paso 2. Forma estándar con artificiales.

$$3x_1+x_2-e_1+A_1=90$$ $$2x_1+4x_2-e_2+A_2=120$$

Paso 3. Fase I. Objetivo auxiliar: $\min w=A_1+A_2$.

Base inicial $\{A_1,A_2\}$, con $A_1=90$, $A_2=120$, luego $w=210$.

Para escribir la fila $w$ en términos de las no básicas, se despeja $A_1=90-3x_1-x_2+e_1$ y $A_2=120-2x_1-4x_2+e_2$, y se suman:

$$w=210-5x_1-5x_2+e_1+e_2$$

Trabajaremos con la fila de $w$ escrita como coeficientes de las variables, buscando minimizar, de modo que entra la variable con coeficiente más negativo en la expresión de $w$ (la que más reduce $w$ al crecer):

$$\begin{array}{cccccccc}\text{Base}& x_1& x_2& e_1& e_2& A_1& A_2& b\\ A_1& 3& 1& -1& 0& 1& 0& 90\\ A_2& 2& 4& 0& -1& 0& 1& 120\\ w& -5& -5& 1& 1& 0& 0& 210\end{array}$$

Iteración 1 (fase I). Empate entre $x_1$ y $x_2$ con $-5$; por la regla de menor índice, entra $x_1$. Razones: $90/3=30\leftarrow$, $120/2=60$. Sale $A_1$. Pivote: 3.

$$F_1^{\prime }:(1,0,333,-0,333,0,0,333,0\mid 30)$$ $$F_2\leftarrow F_2-2F_1^{\prime }:(0,3,333,0,667,-1,-0,667,1\mid 60)$$ $$F_w\leftarrow F_w+5F_1^{\prime }:(0,-3,333,-0,667,1,1,667,0\mid 60)$$

Iteración 2 (fase I). Entra $x_2$ ($-3,333$). Razones: $30/0,333=90$, $60/3,333=18\leftarrow$. Sale $A_2$. Pivote: 3,333.

$$F_2^{\prime }:(0,1,0,2,-0,3,-0,2,0,3\mid 18)$$ $$F_1\leftarrow F_1-0,333F_2^{\prime }:(1,0,-0,4,0,1,0,4,-0,1\mid 24)$$ $$F_w\leftarrow F_w+3,333F_2^{\prime }:(0,0,0,0,1,1\mid 0)$$ $$w^{\ast }=0$$

Las artificiales han salido de la base. Hay solución factible y se pasa a la fase II. El vértice encontrado es $x_1=24$, $x_2=18$.

Paso 4. Fase II. Se eliminan las columnas $A_1$ y $A_2$ y se recupera el objetivo original. Como es un mínimo, minimizamos $z=4x_1+3x_2$ directamente, entrando la variable con $z_j-c_j$ más positivo —o, más seguro, maximizamos $-z$ con la regla habitual—.

La fila objetivo hay que expresarla en función de las no básicas. Las básicas son $x_1$ y $x_2$, así que sustituimos usando las filas de la tabla:

$$x_1=24+0,4e_1-0,1e_2,x_2=18-0,2e_1+0,3e_2$$ $$z=4(24+0,4e_1-0,1e_2)+3(18-0,2e_1+0,3e_2)$$ $$z=96+1,6e_1-0,4e_2+54-0,6e_1+0,9e_2=150+e_1+0,5e_2$$

Los coeficientes de $e_1$ y $e_2$ son positivos, así que aumentar cualquiera de las dos sube el coste. En un problema de minimización eso es el criterio de parada:

$$\boxed{x_1^{\ast }=24,x_2^{\ast }=18,z^{\ast }=150\text{ €}}$$

Paso 5. Comprobar.

$$\text{Proteıˊna: }3(24)+18=72+18=90\ge 90✓\text{ (justo)}$$ $$\text{Hidratos: }2(24)+4(18)=48+72=120\ge 120✓\text{ (justo)}$$ $$z=4(24)+3(18)=96+54=150✓$$

Los dos requisitos se cumplen exactamente: $e_1=e_2=0$. No sobra ni un gramo de nada, que es lo típico de un problema de dieta bien planteado.

Paso 6. Leer los coeficientes finales. Los números 1 y 0,5 que acompañan a $e_1$ y $e_2$ en la expresión de $z$ dicen lo que costaría exigir más: cada gramo adicional de proteína encarecería la mezcla 1 €, y cada gramo de hidratos, 0,50 €. Son los precios sombra de los requisitos nutricionales, y el tema 18 los obtendrá directamente del problema dual.

5. Errores típicos

Olvidar la variable de excedente y poner solo la artificial. En $\ge$ hacen falta las dos: $-e+A$. Con solo la artificial se convierte la desigualdad en igualdad estricta y se cambia el problema.

Poner artificiales donde no hacen falta. Las restricciones de tipo $\le$ ya traen su holgura, que sirve de base. Añadir artificiales alarga el cálculo sin necesidad.

No expresar la fila objetivo en términos de las no básicas. Al empezar la fase I, las artificiales están en la base y sus columnas deben tener cero en la fila $w$. Sin ese ajuste, la tabla inicial es incorrecta y todo lo demás también.

Continuar la fase II con las columnas artificiales. Se eliminan. Si alguna quedara y volviera a entrar en la base, la solución dejaría de ser factible.

Interpretar $w^{\ast }>0$ como error de cálculo. Es un resultado con contenido: el problema es infactible. Las restricciones se contradicen y hay que revisar el enunciado, no el pivotaje.

Confundir degeneración con infactibilidad. Degeneración es una básica que vale cero —el problema tiene solución, solo que el vértice está sobredeterminado—. Infactibilidad es que no hay región factible en absoluto.

Pasar por alto un $z_j-c_j=0$ en una no básica. Es la señal de soluciones múltiples, y es información valiosa: hay flexibilidad gratis.

Aplicar el criterio de entrada de máximo a un problema de mínimo. O se convierte $\min z$ en $\max (-z)$ y se usan siempre las mismas reglas, o se invierten todos los criterios. Mezclar es la vía rápida a un resultado incorrecto.

6. Ejercicios

Ejercicio 1 · Preparar un problema para las dos fases

básico

Escribe en forma estándar, indicando qué variables hacen falta en cada restricción:

$$\min z=2x_1+5x_2\text{s.a.}{x}_1+x_2\ge 10,3x_1+x_2\le 24,x_1=4$$

Ver solución

• Primera ($\ge$): excedente y artificial.

$$x_1+x_2-e_1+A_1=10$$

• Segunda ($\le$): solo holgura.

$$3x_1+x_2+s_2=24$$

• Tercera ($=$): solo artificial.

$$x_1+A_3=4$$

Con $x_1,x_2,e_1,s_2,A_1,A_3\ge 0$.

Fase I: $\min w=A_1+A_3$, con base inicial $\{A_1,s_2,A_3\}$, es decir $A_1=10$, $s_2=24$, $A_3=4$ y $w=14$.

Nótese que $s_2$ entra en la base de forma natural y no necesita artificial: solo las restricciones $\ge$ y $=$ la necesitan.

Ejercicio 2 · Reconocer soluciones múltiples

básico

Una tabla óptima de un problema de máximo es:

$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ x_1& 1& 2& 1& 0& 20\\ s_2& 0& 3& -1& 1& 15\\ z_j-c_j& 0& 0& 4& 0& 80\end{array}$$

Interpreta y da la solución general.

Ver solución

Solución actual: $x_1=20$, $x_2=0$ (no básica), $s_1=0$, $s_2=15$, $z=80$.

Todos los $z_j-c_j\ge 0$: es óptima. Pero $x_2$ es no básica y tiene $z_j-c_j=0$. Eso significa que puede entrar en la base sin cambiar $z$: hay soluciones múltiples.

Segundo vértice óptimo. Entra $x_2$; razones con los coeficientes positivos de su columna:

$$\frac{20}{2}=10\frac{15}{3}=5\leftarrow \text{mıˊnimo}$$

Sale $s_2$. Pivote: el 3 de la segunda fila.

$$F_2^{\prime }:(0,1,-0,333,0,333\mid 5)$$$$F_1\leftarrow F_1-2F_2^{\prime }:(1,0,1,667,-0,667\mid 10)$$

La fila $z$ no cambia, porque el coeficiente de la variable entrante en ella era cero: ese es justamente el motivo de que $z$ siga valiendo 80.

$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ x_1& 1& 0& 1,667& -0,667& 10\\ x_2& 0& 1& -0,333& 0,333& 5\\ z_j-c_j& 0& 0& 4& 0& 80\end{array}$$

Segundo vértice óptimo: $x_1=10$, $x_2=5$, con el mismo $z=80$.

Solución general:

$$(x_1,x_2)=\lambda (20,0)+(1-\lambda )(10,5),\lambda \in [0,1]$$

Todos esos planes dan $z=80$.

Lectura económica. La empresa puede elegir cualquier combinación del segmento sin perder beneficio. Eso da margen para atender otros criterios —diversificar la producción, cumplir un pedido concreto— gratis.

Ejercicio 3 · Detectar infactibilidad con la fase I

medio

Aplica la fase I a:

$$\max z=x_1+x_2\text{s.a.}{x}_1+x_2\le 5,x_1+x_2\ge 12,x_1,x_2\ge 0$$

Ver solución

Forma estándar:

$$x_1+x_2+s_1=5$$$$x_1+x_2-e_2+A_2=12$$

Fase I: $\min w=A_2$. Base inicial $\{s_1,A_2\}$ con $s_1=5$, $A_2=12$, $w=12$.

Fila $w$ en términos de no básicas: $A_2=12-x_1-x_2+e_2$, luego

$$w=12-x_1-x_2+e_2$$$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& s_1& e_2& A_2& b\\ s_1& 1& 1& 1& 0& 0& 5\\ A_2& 1& 1& 0& -1& 1& 12\\ w& -1& -1& 0& 1& 0& 12\end{array}$$

Iteración. Entra $x_1$ (menor índice entre los empatados a $-1$). Razones: $5/1=5\leftarrow$, $12/1=12$. Sale $s_1$. Pivote: 1.

$$F_1^{\prime }:(1,1,1,0,0\mid 5)$$$$F_2\leftarrow F_2-F_1^{\prime }:(0,0,-1,-1,1\mid 7)$$$$F_w\leftarrow F_w+F_1^{\prime }:(0,0,1,1,0\mid 7)$$$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& s_1& e_2& A_2& b\\ x_1& 1& 1& 1& 0& 0& 5\\ A_2& 0& 0& -1& -1& 1& 7\\ w& 0& 0& 1& 1& 0& 7\end{array}$$

Parada. Todos los coeficientes de la fila $w$ son $\ge 0$: no se puede reducir más $w$. Y sin embargo:

$$w^{\ast }=7>0,A_2=7>0$$

La artificial no ha podido salir de la base. El problema es INFACTIBLE.

Por qué era evidente sin calcular. Las dos restricciones exigen que $x_1+x_2$ sea a la vez $\le 5$ y $\ge 12$. Ninguna cantidad cumple las dos. La fase I lo ha detectado mecánicamente, que es su valor: en un problema con veinte restricciones la contradicción no se ve a simple vista.

Qué hacer. No es un fallo del método: es un diagnóstico del modelo. Hay que revisar los datos —¿el 5 era el máximo o el mínimo?— o relajar alguna condición. Si las dos restricciones son ciertas, el problema tal como está planteado no tiene respuesta.

Ejercicio 4 · Degeneración: una iteración que no mejora

avanzado

Resuelve por símplex y explica lo que ocurre en la segunda iteración:

$$\max z=3x_1+2x_2$$$$\text{s.a.}{x}_1+x_2\le 8,2x_1+x_2\le 16,x_1\le 8,x_1,x_2\ge 0$$

Ver solución

Tabla inicial.

$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& s_1& s_2& s_3& b\\ s_1& 1& 1& 1& 0& 0& 8\\ s_2& 2& 1& 0& 1& 0& 16\\ s_3& 1& 0& 0& 0& 1& 8\\ z_j-c_j& -3& -2& 0& 0& 0& 0\end{array}$$

Iteración 1. Entra $x_1$ ($-3$). Razones:

$$\frac{8}{1}=8,\frac{16}{2}=8,\frac{8}{1}=8$$

Triple empate. Por menor índice, sale $s_1$. Pivote: 1.

$$F_1^{\prime }:(1,1,1,0,0\mid 8)$$$$F_2\leftarrow F_2-2F_1^{\prime }:(0,-1,-2,1,0\mid 0)$$$$F_3\leftarrow F_3-F_1^{\prime }:(0,-1,-1,0,1\mid 0)$$$$F_z\leftarrow F_z+3F_1^{\prime }:(0,1,3,0,0\mid 24)$$$$\begin{array}{ccccccc}\text{Base}& x_1& x_2& s_1& s_2& s_3& b\\ x_1& 1& 1& 1& 0& 0& 8\\ s_2& 0& -1& -2& 1& 0& 0\\ s_3& 0& -1& -1& 0& 1& 0\\ z_j-c_j& 0& 1& 3& 0& 0& 24\end{array}$$

Solución degenerada. Dos variables básicas, $s_2$ y $s_3$, valen cero. Es la consecuencia directa del triple empate: en el vértice $(8,0)$ coinciden tres restricciones, cuando en ${\mathbb{R}}^2$ bastan dos para determinar un punto. La tercera es redundante en ese vértice.

Criterio de parada. Todos los $z_j-c_j\ge 0$ ($0,1,3,0,0$): la solución es óptima.

$$x_1^{\ast }=8,x_2^{\ast }=0,z^{\ast }=24$$

Comprobación: $8+0=8\le 8✓$; $16+0=16\le 16✓$; $8\le 8✓$. Los tres recursos se agotan a la vez.

Qué habría pasado con otra elección. Si en el empate hubiera salido $s_2$ en lugar de $s_1$, la tabla siguiente habría tenido $x_1=8$ igualmente pero con $s_1=0$ básica, y haría falta otra iteración para llegar al mismo punto, con $\theta =0$: la variable entrante crecería cero unidades y $z$ no mejoraría. Esa es la iteración degenerada característica: mucho cálculo para quedarse donde estaba.

Diagnóstico económico. Los tres recursos se agotan exactamente en el mismo plan. Eso casi nunca es casualidad: sugiere que las capacidades se dimensionaron con la misma regla, o que una de las tres restricciones sobra. Comprobando: en el óptimo $x_1=8$, la primera da $8\le 8$ y la tercera $8\le 8$; con $x_2=0$ la primera restricción y la tercera dicen lo mismo. La tercera restricción es redundante en toda la región donde $x_2\ge 0$, porque $x_1\le x_1+x_2\le 8$. Eliminarla no cambiaría nada y evitaría la degeneración.

7. Qué desbloquea

Necesitas antes:

• El algoritmo símplex: conceptos, teoremas fundamentales y funcionamiento — tema 16

Te abre la puerta a:

• Dualidad: formulación del dual, relaciones e interpretación económica — tema 18

8. Recursos externos

• OCW UPV/EHU — Investigación Operativa. Programación Lineal. Método símplex con penalización y con dos fases, y tipología completa de soluciones. Es el recurso más ajustado a este tema.
• OCW Unizar — vídeos de matemáticas básicas, programación lineal. Hay vídeos específicos sobre variables artificiales, símplex fase I y método de las dos fases: conviene verlos después de intentar el ejemplo a mano.
• OCW Unizar — Modelos de Investigación Operativa. Colección de ejercicios y pruebas de evaluación resueltas, con casos degenerados e infactibles.
• LINDO. Ante un problema infactible o no acotado, LINDO lo dice explícitamente: comparar su mensaje con el diagnóstico hecho a mano confirma que se ha interpretado bien la tabla.