Dualidad en Programación Lineal
Dualidad en Programación Lineal
Asociado 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:
Maximizar
S .A .
Llamaremos problema dual asociado:
F(x)
g( x )  b
Dualidad en Programación Lineal
Minimizar
S .A .
L ( x ,  )  F ( x )   g ( x )  b 
L
(x , )  0
x
  0
t
x D
Se verifican, entre otras, las siguientes propiedades entre ellos:
1)
F(x) £ L(x, l)
2)
Si x* es solución del Primal, entonces existe l* tal que
(x* , l* )
lo es del dual
3)
Si el Primal tiene solución y (x* , l* ) es solución del dual, entonces x*
lo es del Primal y se verifica que F(x* ) = L(x* , l* )
Dualidad en Programación Lineal
En el caso lineal:
Maximizar
S .A .
t
c x
Ax  b
El problema dual resulta:
Minimizar
S .A .
t
 b
t
A   c
  0
Y en general, se pueden demostrar las siguientes relaciones:
Dualidad en Programación Lineal
donde 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.
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejemplo
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
Dualidad en Programación Lineal
Ejercicio:
Obtener el dual del:
Maximizar 3 x + 2 y
Sujeta a:
x–4y=4
3x–2y≤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)
Dualidad en Programación Lineal
Propiedades de la dualidad:
Sean ambos problemas:
Maximizar F(x) = c t x
S.A.
Minimizar H(l) = l t b
Ax £ b
S.A.
A tl = c
l³0
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(λ*)
Dualidad en Programación Lineal
3) 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:
t

t
 cBB
1
Dualidad en Programación Lineal
Ejemplo
TABLA 1
C1=5
C2=4
C3=0
C4=0
Base
Cb
P1
P2
P3
P4
Sol.
P3
0
3
3
1
0
10
P4
0
12
6
0
1
24
-5
-4
0
0
Z0=0
C1=5
C2=4
C3=0
C4=0
TABLA 3
Base
Cb
P1
P2
P3
P4
Sol.
P1
5
1
0
-1/3
1/6
2/3
P2
4
0
1
2/3
-1/6
8/3
0
0
1
1/6
Z0=14
Dualidad en Programación Lineal
Ejemplo
TABLA 1
C1=5
C2=4
C3=0
C4=0
Base
Cb
P1
P2
P3
P4
Sol.
P3
0
3
3
1
0
10
P4
0
12
6
0
1
24
-5
-4
0
0
Z0=0
C1=5
C2=4
C3=0
C4=0
TABLA 3
Base
Cb
P1
P2
P3
P4
Sol.
P1
5
1
0
-1/3
1/6
2/3
P2
4
0
1
2/3
-1/6
8/3
0
0
1
1/6
Z0=14
Dualidad en Programación Lineal
TABLA 3
C1=5
C2=4
C3=0
C4=0
Base
Cb
P1
P2
P3
P4
Sol.
P1
5
1
0
-1/3
1/6
2/3
P2
4
0
1
2/3
-1/6
8/3
0
0
1
1/6
Z0=14
Luego el teorema fundamental nos dice que la solución del problema dual del dado
será el producto:

t
t
 cB B
1
 5
*
 1 / 3
4
 2/3
 1  1,
*
1/6 
  1
1 / 6 
2  1 / 6
1 / 6
Dualidad en Programación Lineal
que no es más que los Zj asociados a la base canónica inicial:
*
TABLA 3
*
 1  Z 3  1,
2  Z4  1 / 6
C1=5
C2=4
C3=0
C4=0
Base
Cb
P1
P2
P3
P4
Sol.
P1
5
1
0
-1/3
1/6
2/3
P2
4
0
1
2/3
-1/6
8/3
0
0
1
1/6
Z0=14
(Nótese que ni hemos obtenido el dual del dado)
Dualidad en Programación Lineal
Ejemplo
Primal:
Maximizar
4x1+3x2-3x4
Sujeta a: 3x1+4x2+x3
=12
3x1+3x2 +x4 =10
4x1+2x2
+x5=8
x1,x2,x3,x4,x5≥0
Dual:
Minimizar 12λ1+10λ2+8λ3
Sujeta a: 3λ1+3λ2+4 λ3≥ 4
4λ1+3λ2+2λ3 ≥ 3
λ1
≥0
λ2
≥-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
Dualidad en Programación Lineal
Base canónica inicial: {P3 , P4 , P5}
Luego la solución del problema dual es {Z3 , Z4 , Z5}:
11
11
l1 = Z3 =
+0 =
5
5
l2 = Z4 = 0 + (-3) = -3
l 3 = Z5 =
8
8
+0=
5
5
Descargar

y ≥ 0 - Matemáticas