1 Dualidad en Programación Lineal

2 Dualidad en Programación LinealAsociado a cada problema de programación matemática (lineal o no lineal), existe otro problema denominado problema dual, que posee importantes propiedades y relaciones notables con respecto al problema original. Definición: Dado un problema que llamaremos primal: Llamaremos problema dual asociado:

3 Dualidad en Programación LinealSe verifican, entre otras, las siguientes propiedades entre ellos:

4 Dualidad en Programación LinealEn el caso lineal: El problema dual resulta: Y en general, se pueden demostrar las siguientes relaciones:

5 Dualidad en Programación Linealdonde en el lado de la izquierda aparecen el signo de la restricciones primales y la no negatividad de las variables (leyendo por columnas) y en el lado de la derecha aparecen la no negatividad de las variables duales y el signo de sus restricciones.

6 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

7 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

8 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

9 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

10 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

11 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

12 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0 λ2 cualquiera

13 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

14 Dualidad en Programación LinealEjemplo Dado el siguiente problema: Maximizar 3x + 6y + 2z Sujeta a: 3x + 4y + z ≤ 2 x + 2y + 3z = 10 y ≥ 0 (x,z cualquiera) Su problema dual resulta: Minimizar 2λ1 +10λ2 Sujeta a: 3λ1 + λ2 = 3 4λ1 + 2λ2 ≥ 6 λ1 + 3λ2 = 2 λ1 ≥ 0

15 Dualidad en Programación LinealEjercicio: Obtener el dual del: Maximizar 3 x + 2 y Sujeta a: x – 4 y = 4 3 x – 2 y ≤ 1 5 x - 8 y ≤ -7 x ≥ 0 (y cualquiera) Solución: Minimizar 4 λ1 + 1 λ2 – 7 λ3 Sujeta a: λ1 +3 λ2 + 5 λ3 ≥ 3 - 4 λ1 - 2 λ2 - 8 λ3 = 2 λ2, λ3 ≥ 0 (λ1 cualquiera)

16 Dualidad en Programación LinealPropiedades de la dualidad: Sean ambos problemas: Se verifican las siguientes propiedades: 1) F(x) ≤ H(λ) 2) Si el interior de X es no vacío y x* es solución del primal, entonces existe λ*, solución del dual con: F(x*) = H(λ*)

17 Dualidad en Programación Lineal3) Si uno de los problemas tiene solución ilimitada, el otro posee un conjunto de oportunidades vacío (carece de puntos admisibles). 4) El problema primal tiene solución finita si y solo si los conjuntos de oportunidades de ambos problemas son no vacíos. 5) Teorema fundamental de dualidad. Sea el problema primal en forma estándar y sea x* su solución. Si el interior de X es no vacío y λ* es la solución del dual, entonces:

18 Dualidad en Programación LinealEjemplo TABLA 1 C1=5 C2=4 C3=0 C4=0 Base Cb P1 P2 P3 P4 Sol. 3 1 10 12 6 24 -5 -4 Z0=0 TABLA 3 C1=5 C2=4 C3=0 C4=0 Base Cb P1 P2 P3 P4 Sol. 5 1 -1/3 1/6 2/3 4 -1/6 8/3 Z0=14

19 Dualidad en Programación LinealEjemplo TABLA 1 C1=5 C2=4 C3=0 C4=0 Base Cb P1 P2 P3 P4 Sol. 3 1 10 12 6 24 -5 -4 Z0=0 TABLA 3 C1=5 C2=4 C3=0 C4=0 Base Cb P1 P2 P3 P4 Sol. 5 1 -1/3 1/6 2/3 4 -1/6 8/3 Z0=14

20 Dualidad en Programación LinealLuego el teorema fundamental nos dice que la solución del problema dual del dado será el producto: TABLA 3 C1=5 C2=4 C3=0 C4=0 Base Cb P1 P2 P3 P4 Sol. 5 1 -1/3 1/6 2/3 4 -1/6 8/3 Z0=14

21 Dualidad en Programación Linealque no es más que los Zj asociados a la base canónica inicial: TABLA 3 C1=5 C2=4 C3=0 C4=0 Base Cb P1 P2 P3 P4 Sol. 5 1 -1/3 1/6 2/3 4 -1/6 8/3 Z0=14 (Nótese que ni hemos obtenido el dual del dado)

22 Dualidad en Programación LinealEjemplo Primal: Dual: Maximizar x1+3x2-3x Minimizar 12λ1+10λ2+8λ3 Sujeta a: 3x1+4x2+x = Sujeta a: 3λ1+3λ2+4 λ3≥ 4 3x1+3x x = λ1+3λ2+2λ3 ≥ 3 4x1+2x x5= λ ≥0 x1,x2,x3,x4,x5≥ λ ≥-3 λ3≥0 Solución del primal: (x1,x2,x3,x4,x5) = (4/5 , 12/5 , 0 , 2/5 , 0) con: Z1-C1=0 , Z2-C2=0 , Z3-C3=11/5 , Z4-C4=0 , Z5-C5=8/5

23 Dualidad en Programación LinealBase canónica inicial: {P3 , P4 , P5} Luego la solución del problema dual es {Z3 , Z4 , Z5}: