Probar la existencia de una solución a un LP

Question

Estoy trabajando en el siguiente ejercicio:

Dejemos que $c \in \mathbb{R}^n$ y $A \in \mathbb{R}^{m*n}$ . Para un número arbitrario de $b \in \mathbb{R}^m$ consideramos el siguiente problema $(P_b)$ :

$$min_{x \in \mathbb{R}^n} c^Tx$$

$$\text{such that } Ax = b, x \ge 0$$

Que además sea $B$ una base de $A$ . Establecemos $x(B,b)$ como la única solución del sistema de ecuaciones lineales: $Ax = b, x_i = 0 \ (\forall i \not \in B )$ . Sabemos que el mapeo $b \mapsto x(B,b)$ es continua.

Que ahora sea $\overline{b} \in \mathbb{R}^m$ . Hacemos las siguientes suposiciones:

1. El problema $(P_{\overline{b}})$ tiene una solución única $\overline{x}$ y hay una base única $\overline{B}$ tal que $\overline{x} = x(\overline{B},\overline{b})$ . Para todos los $i \in \overline{B}$ tiene $\overline{x}_i > 0$ .
2. Hay un número $\epsilon_0 > 0$ tal que para todo $b \in \mathbb{R}^m$ con $\| b - \overline{b} \| \le \epsilon_0$ el problema $(P_b)$ tiene una solución.

Demuestre que hay un $\epsilon >0$ tal que para todo $b \in \mathbb{R}^m$ con $\| x - \overline{x} \| \le \epsilon$ el punto $x(\overline{B},b)$ es una solución a $(P_b)$ .

Mi idea sería utilizar, la continuidad de la cartografía $b \mapsto x(B,b)$ con el punto 2) para mostrar desde $\| b - \overline{b} \| \le \epsilon_0$ que $\| x - \overline{x} \| \le \epsilon$ pero no sé cómo elegir $\epsilon$ para poder decir que $\| x - \overline{x} \|$ es efectivamente menor o igual a $\epsilon$ . Tampoco entiendo por qué la solución tiene que tener la forma $x(\overline{B},b)$ . ¿Podría darme una pista?

Answer 1

Supongamos, para mayor claridad, que $x(B, b)$ denota la solución óptima de $(P_b)$ . También creo que se le debería haber pedido que demuestre Este problema se puede interpretar como que se le pide que demuestre un hecho importante sobre el análisis de sensibilidad en ausencia de degeneración: que la base actual sigue siendo óptima mientras se mantenga la viabilidad.

La condición (1) implica que $x(\overline{B}, \overline{b})$ es no degenerado, así como único. Esto es suficiente para demostrar la condición (2), así como el resultado que deseas.

Consideremos la tabla óptima del simplex correspondiente a $\overline{x} = x(\overline{B}, \overline{b})$ . Sea $\overline{x}_{\overline{B}}$ denotan la parte básica de $\overline{x}$ . Obsérvese que la única parte del retablo que contiene $\overline{b}$ es el lado derecho, donde $\overline{B}^{-1} \overline{b}$ aparece. Observe que $\overline{x}_{\overline{B}} = \overline{B}^{-1} \overline{b} > 0$ por la no negatividad de la condición (1), y $\overline{B}^{-1}$ es un operador lineal. Los operadores lineales son continuos, por lo que existe un $\delta > 0$ tal que $\overline{B}^{-1} b > 0$ para todos $|| b - \overline{b} || < \delta$ . Esto significa que la sustitución de $\overline{B}^{-1} \overline{b}$ con $\overline{B}^{-1} b$ en la tabla óptima antes mencionada da lugar a una tabla óptima para $(P_b)$ ya que se mantiene la viabilidad, los costes reducidos no cambian, y multiplicando el nuevo cuadro óptimo por $\overline{B}$ da un cuadro inicial para $(P_b)$ . Esto demuestra simultáneamente la condición (2) y el resultado.