Degeneración en la programación lineal

Question

Consideremos el poliedro de forma estándar y supongamos que las filas de la matriz A son linealmente independientes.

$$\left \{ x | Ax = b, x \geq 0 \right \}$$

(a) Supongamos que dos bases diferentes conducen a la misma solución básica. Demuestre que la solución básica es degenerada (tiene menos de m entradas no nulas).

(b) Considere una solución básica degenerada. ¿Es cierto que corresponde a dos o más bases distintas? Demuestra o da un contraejemplo.

(c) Supongamos que una solución básica es degenerada. ¿Es cierto que existe una solución básica adyacente que es degenerada? Demuestra o da un contraejemplo.

Solución

(a) Creo que es obvio, pero cómo construir la prueba, las dos bases diferentes conducen a la misma solución básica, cuando la última variable que entra no puede ser aumentada en absoluto porque su valor b es igual a 0 por lo tanto como resultado tenemos la misma solución básica. ¿Pero cómo se demuestra eso?

(b) no, la solución básica degenerada puede corresponder a una sola base también. Pero, ¿cómo demostrarlo?

Anexo

Encontré una gran descripción de (a) y (b), pero el nivel de este texto es mucho más alto de lo que puedo aprehender. Agradeceré si alguien puede arrojar luz sobre esta explicación.

(a) toda solución básica factible es equivalente a un punto extremo. Sin embargo, puede existir más de un básico correspondiente a la misma solución básica factible o punto extremo. El caso de degeneración corresponde a la de un punto extremo en el que algún $r > p \equiv n- m$ definiendo los hiperplanos de $x\geq 0$ son vinculantes. Por lo tanto, para cualquier base asociada, $(r-p)$ de la $X_{B}$ - área de las variables también cero. En consecuencia, el número de variables positivas es $q = m-(r-p)<m$ . En este caso, cada posible elección de una base $B$ que incluye las columnas de estas q variables positivas representa este punto. Claramente, si existe más de una base que represente un punto extremo, entonces este punto extremo es degenerado

(b) Considere el ejemplo $$x_{1} + x_{2} + x_{3} = 1$$

$$-x_{1} + x_{2} + x_{3} = 1$$

$$x_{1}, x_{2}, x_{3} \geq 0$$

Considere la solución $\bar{x}=(0,1,0)$ . Obsérvese que se trata de un punto extremo o de una solución básica factible con una base correspondiente que tiene $x_{1}$ y $x_{2}$ como variables básicas. Además, se trata de un punto extremo degenerado. Hay cuatro hiperplanos de definición que se unen en $\bar{x}$ . Además, hay tres formas de elegir tres hiperplanos linealmente independientes de este conjunto que dan como resultado $\bar{x}$ como solución (única). Sin embargo, la base asociada a $\bar{x}$ es única. Consideremos una variable básica degenerada ${x_{B}}_{r}$ (con $\bar{b}_{r}=0$ ), que es tal que $Ax=b$ no implica necesariamente que ${x_{B}}_{r}=0$ . Dado que dicha variable existe, construiremos otra base que represente este punto. Sea $x_{k}$ sea algún componente de $x_{N}$ que tiene un coeficiente no nulo $\theta_{r}$ en la fila correspondiente a ${x_{B}}_r$ . Tenga en cuenta que $x_{k}$ existe. A continuación, considere una nueva elección de $(n-m)$ variables no básicas dadas por ${x_{B}}_{r}$ y $x_{N-k}$ , donde $x_{N-k}$ representa los componentes de $x_{N}$ que no sea $x_{k}$ . Poniendo ${x_{B}}_{r}= 0$ y $x_{N-k}=0$ anterior da de forma única $x_{k}=\frac{\bar{b}_{r}}{\theta_{r}}=0$ de la fila $r$ y así ${x_{B}}_{i} = \bar{b}_{i}$ se obtiene como antes de las otras filas. Por lo tanto, esto corresponde a una base alternativa que representa el mismo punto extremo. Por último, nótese que si ninguna variable básica degenerada ${x_{B}}_{r}$ de este tipo existe, entonces sólo hay una base que representa este punto extremo.

Answer 1

(La mayor parte de esto se escribió antes de la reciente adición. Aborda la pregunta original del PO, no el apéndice).

(a) Supongamos que tenemos bases distintas $B_1$ y $B_2$ que dan la misma solución básica ${\bf x}$ . Ahora, supongamos (buscamos una contradicción) que ${\bf x}$ es no degenerado; es decir, cada uno de los $m$ variables en ${\bf x}$ es distinto de cero. Así, cada uno de los $m$ variables en $B_1$ es distinto de cero, y cada uno de los $m$ variables en $B_2$ es distinto de cero. Como $B_1$ y $B_2$ son distintos, hay al menos una variable en $B_1$ no en $B_2$ . Pero esto produce al menos $m+1$ variables no nulas en ${\bf x}$ , lo cual es una contradicción. Por lo tanto, ${\bf x}$ debe ser degenerado.

(b) No. El contraejemplo al que se refiere la OP se refiere al sistema $$\begin{align} x_1 + x_2 + x_3 = 1, \\ -x_1 + x_2 + x_3 = 1, \\ x_1, x_2, x_3 \geq 0. \end{align}$$
Hay tres bases potenciales en este sistema: $B_1 = \{x_1, x_2\}$ , $B_2 = \{x_1, x_3\}$ , $B_3 = \{x_2, x_3\}$ . Sin embargo, $B_3$ no puede ser realmente una base porque la matriz correspondiente $\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}$ no es invertible . $B_1$ se obtiene la solución básica $(0,1,0)$ y $B_2$ se obtiene la solución básica $(0,0,1)$ . Ambos son degenerados, pero sólo hay una base correspondiente a cada uno.

(c) No. Mira el sistema $$\begin{align} x_1 + x_2 = 1, \\ x_2 + x_3 = 1, \\ x_1, x_2, x_3 \geq 0. \end{align}$$ La solución básica $(0,1,0)$ corresponde a las bases $\{x_1, x_2\}$ y $\{x_2, x_3\}$ . La única otra base es $\{x_1, x_3\}$ lo que implica que la única otra solución básica es $(1,0,1)$ . Así, la solución básica degenerada $(0,1,0)$ no es adyacente a otra solución básica degenerada.

---

( Más sobre la parte (a), abordando las preguntas del OP en los comentarios .)

Digamos que hay $n$ total de variables en el problema: $x_1, x_2, \ldots, x_n$ . Cada base $B$ consiste en unos $m$ de estas variables. La solución básica ${\bf x}$ correspondiente a una base determinada $B$ tiene el otro $n-m$ variables iguales a $0$ . (Si se pone en $0$ es en parte cómo se determina el valor de ${\bf x}$ (véanse, por ejemplo, los ejemplos anteriores). Si ${\bf x}$ es degenerado puede tener algunas de las variables en $B$ igual a $0$ también, pero el punto en términos del argumento es que ${\bf x}$ no puede tener más que $m$ variables no nulas.

Ahora, supongamos que $B_1$ y $B_2$ son distintos y cada uno tiene $m$ variables no nulas, pero ambas corresponden a ${\bf x}$ . Digamos que $B_2 = \{x_1, x_2, \ldots, x_m\}$ . Desde $B_1$ y $B_2$ son distintos, $B_1$ tiene al menos una variable que no está en $B_2$ . Digamos que esta variable es $x_{m+1}$ . Pero como cada variable en $B_1$ y $B_2$ es distinto de cero, lo que significa que $x_1, x_2, \ldots, x_m, x_{m+1}$ son todos distintos de cero. Sin embargo, $B_1$ y $B_2$ ambos corresponden a ${\bf x}$ lo que significa que hay al menos $m+1$ variables no nulas en ${\bf x}$ . Eso no puede ocurrir para una solución básica, y entonces tenemos una contradicción.

Answer 2

Tengo una prueba ligeramente diferente para la parte (a). Si las bases, $B$ y $B'$ son distintas, pero corresponden a la misma solución básica factible $x_b$ ( $x_b$ corresponde al vector de variables básicas), entonces, por definición $Bx_b=b$ y $B'x_b=b$ . Por lo tanto, $(B-B')x_b=0$ . Desde $B,B'$ son distintos, $dim(B-B') \geq 1$ . Por lo tanto, por el teorema de nulidad de rango, $dim(x_b) \leq (m-1)$ lo que implica que al menos uno de los componentes de $x_b$ es cero.