Dualidad y Holgura Complementaria

El tema estrella de la I2 (5/5 semestres): pasar del primal al dual con la tabla de conversión, dualidad débil y fuerte, el teorema de holgura complementaria para hallar la solución óptima, uso del dual para detectar infactibilidad, y análisis de sensibilidad de costos. Con ejercicios resueltos de las Ayudantías 10 y 11.

Creado por

SebastianZ28

Valoración0 votos

-.-

hub

Del primal al dual

La idea de la dualidad

A cada restricción del problema primal se le asigna un multiplicador, llamado variable dual. El problema dual reorganiza esa información para dar una cota del óptimo desde el otro lado.

Par canónico (primal de minimización)

Primal: min c^{⊤} x s.a. A x \geq b, x \geq 0 ⟺ Dual: max b^{⊤} y s.a. A^{⊤} y \leq c, y \geq 0

Tabla de conversión (primal de min)

Cada tipo de restricción del primal define el signo de la variable dual, y cada tipo de variable del primal define el tipo de restricción dual:

Primal (min) restricci \overset{o}{ˊ} n \geq restricci \overset{o}{ˊ} n \leq restricci \overset{o}{ˊ} n = variable x \geq 0 variable x \leq 0 variable x libre Dual (max) y \geq 0 y \leq 0 y libre restricci \overset{o}{ˊ} n \leq restricci \overset{o}{ˊ} n \geq restricci \overset{o}{ˊ} n =

Ejemplo resuelto (Ayudantía 11)

Primal: $min 5 x_{1} + 3 x_{2} + x_{3}$ con $2 x_{1} + x_{2} + x_{3} \geq 5$ , $x_{1} + x_{2} + x_{3} = 2$ , $x_{1}, x_{2} \geq 0$ , $x_{3} \leq 0$ . Aplicando la tabla (la restricción $=$ da $y_{2}$ libre; la variable $x_{3} \leq 0$ da una restricción dual $\geq$ ):

\max\ 5y_1 + 2y_2 \quad \text{s.a.}\quad PH0\quad y_1 \ge 0,\ y_2 \text{ libre}

Cargando Quiz...

functions

Dualidad débil y fuerte

Dos teoremas que conectan primal y dual

Dualidad débil

Para cualquier par de soluciones factibles (primal $x$ y dual $y$ ), el valor dual nunca supera al primal: el dual entrega una cota inferior del primal de minimización.

b^{⊤} y \leq c^{⊤} x \forall x, y factibles

Dualidad fuerte

Si el primal tiene solución óptima, el dual también, y sus valores óptimos coinciden. Esto permite certificar optimalidad: si encuentras $x$ e $y$ factibles con igual valor objetivo, ambos son óptimos.

v_{P}^{*} = v_{D}^{*}

Corolario: no acotamiento ⇒ infactibilidad

De la dualidad débil se deduce que si un problema es no acotado, el otro debe ser infactible (su cota se iría al infinito).

Ejemplos resueltos

Ay11 P1: $x^{*} = (3, 0, - 1)$ da $z = 14$ e $y^{*} = (4, - 3)$ da $w = 14$ . Como $z = w$ , dualidad fuerte ⇒ ambos óptimos.
Ay10 P3: primal $min 3 x_{1} + 2 x_{2} + 4 x_{3}$ y su dual alcanzan $z^{*} = 17$ .

Cargando Quiz...

data_object

Holgura complementaria

El puente entre soluciones primal y dual

El teorema de holgura complementaria (THC) dice que, en el óptimo, no pueden estar "holgados" a la vez una variable y la restricción asociada del otro problema. Para cada par, el producto es cero:

y_{i}^{*} (A x^{*} - b)_{i} = 0 y x_{j}^{*} (A^{⊤} y^{*} - c)_{j} = 0

Cómo se usa para hallar la solución

Dado el óptimo dual $y^{*}$ : si una holgura dual es distinta de cero, su variable primal asociada debe ser $x_{j} = 0$ ; y si $y_{i}^{*} > 0$ , la restricción primal $i$ debe estar activa (igualdad). Con esas ecuaciones se despeja $x^{*}$ .

Recetario de holgura complementaria (desde $y^{*}$ ): (1) evalúa cada holgura dual $c_{j} - a_{j}^{⊤} y^{*}$ ; si es $\neq = 0$ ⇒ $x_{j} = 0$ . (2) cada $y_{i}^{*} > 0$ ⇒ vuelve igualdad la restricción primal $i$ . (3) resuelve el sistema para $x^{*}$ y (4) verifica factibilidad.

Recetario

Ejemplo resuelto completo (Ayudantía 11)

Con el dual de antes y $y^{*} = (4, - 3)$ , evaluamos las holguras duales:

PH0

Como $y_{1} = 4 > 0$ , la restricción primal 1 es activa. Con $x_{2} = 0$ resolvemos $2 x_{1} + x_{3} = 5$ y $x_{1} + x_{3} = 2$ :

x^{*} = (3, 0, - 1), factible: x_{1} = 3 \geq 0, x_{3} = - 1 \leq 0, restricciones OK

Cargando Quiz...

warning

Usar el dual: infactibilidad y no acotamiento

El dual como herramienta de diagnóstico

Las relaciones de dualidad permiten concluir cosas del primal mirando el dual, que muchas veces es más fácil de analizar:

Primal no acotado ⟺ Dual infactible Dual no acotado \Rightarrow Primal infactible

Teorema de la alternativa (Farkas)

Formaliza esta idea: de dos sistemas, exactamente uno tiene solución. Sirve para certificar que un conjunto de restricciones es factible o infactible sin resolver el problema completo.

Exactamente uno: {A x = b, x \geq 0} \overset{o}{ˊ} {A^{⊤} y \leq 0, b^{⊤} y > 0}

Pista de los ayudantes (histórica en las I2): si un problema se ve difícil de manipular con Simplex o por intuición, probablemente te están pidiendo el dual. Pasar a la dual suele reducir la dimensión (ej. de 3D a 2D) y vuelve el análisis gráfico directo.

Truco de examen

Ejemplo resuelto (Ayudantía 11)

Para $min 4 x_{1} + 6 x_{2} + 3 x_{3}$ con dos restricciones $\geq$ , el dual $max 2 y_{1} + y_{2}$ resulta factible pero no acotado (al graficarlo en 2D la región crece sin cota en la dirección del objetivo). Por dualidad débil, el primal es infactible.

Cargando Quiz...

memory

Sensibilidad de costos (post-óptimo)

¿Cuánto puede cambiar un costo sin romper el óptimo?

El análisis post-óptimo estudia la robustez de la base óptima frente a cambios en los datos. Vemos el caso de un cambio en el costo de una variable.

Costo de una variable no básica

Si cambia el costo $c_{j}$ de una variable no básica $x_{j}$ , la base sigue siendo óptima mientras su costo reducido se mantenga no negativo:

\overset{c}{ˉ}_{j} = c_{j}^{'} - c_{B}^{⊤} A_{B}^{- 1} A_{j} \geq 0

Qué cambia y qué no

No cambian: la base $A_{B}$ , su inversa $A_{B}^{- 1}$ , el vector $\overset{ˉ}{b} = A_{B}^{- 1} b$ , la solución $x_{B}$ y el valor $Z^{*}$ (porque $x_{j} = 0$ ).
Cambia: solo el costo reducido de esa variable.
Si en cambio se altera el costo de una variable básica, sí cambia $Z^{*}$ y la base podría dejar de ser óptima.

Ejemplo resuelto (Ayudantía 11)

Base óptima $B = {3, 4}$ con $x = (0, 0, 1, 1)$ . Para la no básica $x_{1}$ se calcula $A_{B}^{- 1} A_{1} = (2, 3)^{⊤}$ y $c_{B}^{⊤} A_{B}^{- 1} A_{1} = 4$ , de modo que:

\overset{c}{ˉ}_{1} = c_{1}^{'} - 4 \geq 0 ⟹ c_{1}^{'} \in [4, \infty)

Mientras el costo de $x_{1}$ sea $\geq 4$ , la base ${3, 4}$ sigue óptima y nada del resto se mueve. $■$

Cargando Quiz...