Demuestra que la solución óptima del dual no es única si la solución óptima del primal es degenerada y única.

Question

¿Cómo puedo demostrar que una solución óptima del dual no es única si una solución óptima del primal es degenerada y única?

---

Lo que intenté:

Sea el primal como

$$\max z=cx$$

sujeto a

$$Ax \le b, x \ge 0$$

Sea el dual como

$$\min z'=b^Ty$$

sujeto a

$$A^Ty \le c^T, y \ge 0$$

Sea la (asumimos que solo hay una) solución primal como

variables básicas: $(x_{B_1}, x_{B_2}, ..., x_{B_i})$

variables no básicas: $(x_{NB_1}, x_{NB_2}, ..., x_{NB_i})$

Sea una (podría haber más de una) solución dual como

variables básicas: $(y_{B'_1}, y_{B'_2}, ..., y_{B'_i})$

variables no básicas: $(y_{NB'_1}, y_{NB'_2}, ..., y_{NB'_i})$

Por degeneración de la solución primal, una de las variables básicas es cero:

$$x_{B_{i_0}} = 0$$

Cero o no, como es una variable básica primal, tenemos:

$$z_{B_{i_0}} - c_{B_{i_0}} = 0 = y_{B_{i_0}}$$

Nótese que $y_{B_{i_0}}$ no necesariamente es igual a $y_{B'_{i_0}}$

Por unicidad de la solución primal, todas las variables no básicas del primal tienen costo reducido positivo:

$$z_{NB_1} - c_{NB_1} > 0$$

$$\vdots$$

$$z_{NB_i} - c_{NB_i} > 0$$

Para demostrar que el dual tiene soluciones alternativas, debemos mostrar que una de estas es verdadera:

$$z_{NB'_1} - b_{NB'_1} = 0$$

$$\vdots$$

$$z_{NB'_i} - b_{NB'_i} = 0$$

Creo que podría demostrar esto asumiendo

$$\text{no básico = holgura}$$

lo cual no necesariamente es cierto por supuesto.

¿Cómo entonces podría demostrar esto?

Answer 1

Puedes encontrar una prueba de la afirmación en la tabla que citas en el libro

Linear and Integer Programming: Theory and Practice, Second Edition
páginas 141-145, prueba de Teorema 4.5.

Sin embargo, la afirmación exacta es que la existencia de una solución degenerada y (además) única del primal implica múltiples soluciones para el dual.

---

Utilizando la notación del libro citado anteriormente, la prueba de esta afirmación procede de la siguiente manera:

Sea $x^*$ una solución óptima primal básica factible con variables básicas $x_B^*$ (a partir de esto y debido a los teoremas de dualidad, ya sabes que el dual tiene una solución óptima finita). Dado que es degenerada, entonces existe $$x_{i_0}^*=0, \qquad \text{ con } i_0 \in B$$ Pero la variable $y_{j_0}^*$ (que corresponde a $x_{i_0}$) de la solución factible básica dual correspondiente $y^*$ es no básica y por lo tanto $$y_{j_0}^*=0 \tag1$$ Por otro lado, el Teorema de Holgura Complementaria Fuerte

(Teorema 3.6 del libro) implica que (dado que el primal en forma estándar tiene una solución óptima) hay un par de soluciones óptimas primal y dual $x^*$ e $y^*$ tales que para cada par de variables duales complementarias $(x_i^*,y_j^*)$ se cumple que $x_i^*>0$ o $y_j^*>0$ (o ambos).

Por lo tanto, debido a la unicidad de la solución óptima primal (por lo que esta suposición es necesaria para esta prueba) existe una solución óptima dual (no necesariamente básica factible) para la cual $$y_{j_0}^*> 0 \tag{2}$$
Las relaciones $(1)$ y $(2)$ juntas implican que existen múltiples soluciones duales óptimas.

---

Editar 1: Según esta pregunta y respuesta puedes ver que es imposible que tanto el primal como el dual tengan simultáneamente múltiples soluciones. Junto con la prueba anterior, esto responde tu pregunta.