Primal - óptimo degenerado, Dual - óptimo único

Question

Una pregunta sencilla

¿Es posible que un problema de optimización de programación lineal tenga una solución óptima degenerada mientras que el dual tiene una solución óptima única? No puedo encontrar un escenario en el que esto sea posible, pero intuitivamente parece que es posible.

Answer 1

La respuesta es sí, pero sólo si existen otras soluciones óptimas distintas de la degenerada. Por ejemplo, supongamos que el problema primario es

$$\max x_1 + x_2$$ con sujeción a $$x_1 \leq 1,$$ $$x_1 + x_2 \leq 1,$$ $$x_1, x_2 \geq 0.$$

La solución $(1,0)$ es óptima y degenerada, pero toda solución $(a,1-a)$ , para $0 \leq a \leq 1$ también es óptima.

El doble es

$$\min y_1 + y_2$$ con sujeción a $$y_1 + y_2 \geq 1,$$ $$y_2 \geq 1,$$ $$y_1, y_2 \geq 0.$$

El dual tiene la única solución óptima (degenerada) $(0,1)$ . Así que tenemos una situación con una solución óptima degenerada en el primario, pero un óptimo dual único.

Sin embargo, si la solución óptima degenerada es única, entonces hay debe sean múltiples soluciones óptimas en el dual. La siguiente tabla procede de la obra de Sierksma Programación lineal y entera: Teoría y práctica Volumen 1, página 144.

Primal Optimal Solution                     Dual Optimal Solution
(a) Multiple                     implies    Degenerate
(b) Unique and nondegenerate     implies    Unique and nondegenerate
(c) Multiple and nondegenerate   implies    Unique and degenerate
(d) Unique and degenerate        implies    Multiple

Answer 2

Si una solución óptima es degenerada, entonces a) Existen soluciones óptimas alternativas b) La solución es inviable c) La solución no es útil para el decisor d) Ninguna de las anteriores

Answer 3

Prueba 1: 1) Considere un LP de minimización en forma estándar, si existe un bfs óptimo no degenerado para este LP, entonces el LP dual tendrá una solución óptima única.

Prueba 2: Si el LP primario tiene una solución óptima única, entonces el LP dual tendrá una solución óptima no degenerada.