clase dualidad
Páginas: 4 (950 palabras)
Publicado: 20 de agosto de 2014
EL PROBLEMA DUAL
Definición:
OPTIMIZACIÓN
Problema Primal
(P) Min z = c·x
s.a.
Ax ≥ b
x≥0
¡¡ la ciencia de lo mejor !!
Problema Dual
( D) Max ω = y·b
s.a.
AT y ≤ c
y≥0
2010 -2
1
Optimización – Carmen Ortiz Z. ©
EL PROBLEMA DUAL
EL PROBLEMA DUAL
Problema Primal
(P) Min z = c·x
s.a.
Ax ≥ b
x≥0
(P) Min z = 2x1 + 5x2 - x3
s.a.
2x1 - x2 + 4x3 ≥ 4
5x1 +x2 - 2x3 ≥ 3
x1 , x2 , x3 ≥ 0
El d l d l problema lineal estándar
dual del
bl
li
l tá d
Problema Dual
( D) Max ω = y·b
s.a.
yT A ≤ c
y≥0
(D) Max ω = 4y1 + 3 y2
s.a.
2y1 + 5y2 ≤ 2-y1 + y2 ≤ 5
4y1 - 2y2 ≤ -1
y1 , y2 ≥ 0
Optimización – Carmen Ortiz Z. ©
2
Optimización – Carmen Ortiz Z. ©
Problema Primal
(P) Min z = c·x
s.a.
Ax = b
x≥0
3
Optimización –Carmen Ortiz Z. ©
Problema Dual
( D) Max ω = y·b
s.a.
yT A ≤ c
y irrestricto
4
EL PROBLEMA DUAL
EL PROBLEMA DUAL
Problema de
minimización
(D) Max ω = 4y1 + 6y2
(P) Min z = 2x1+ 3x2+5x3
s.a.
s.a.
4y1 + 3 y2 ≤ 2
4x1 + 3x2 - 2x3 = 4 → (y1)
3y
3 1- 2 2≤3
2y
3x1 - 2x2 + x3 = 6 → (y2)
-2y1 + y2 ≤ 5
x1 , x2, x3 ≥ 0
Si la restricción es:
≥
≤
=
irrestricta
≥0
≤0irrestricta
5
Optimización – Carmen Ortiz Z. ©
EL PROBLEMA DUAL
≤
≥
=
6
Optimización – Carmen Ortiz Z. ©
(P) Min z = 6x1 + 4x2+2x3
s.a.
x1 + 2x2 + 3x3 ≥ 6
4x1 - 2x2 + 2x3 = 8Optimización – Carmen Ortiz Z. ©
la restricción asociada es:
EL PROBLEMA DUAL
El dual del dual es el primal
Problema Primal
(P) Min z = c·x
s.a.
Ax
A ≥b
x≥0
la variableasociada es:
≥0
≤0
Si la variable es:
y1 , y2 irrestricto.
Problema de
maximización
Problema Dual
( D) Max ω = y·b
s.a.
yT A ≤ c
y≥0
x1 , x2 ≥ 0
x3 irrestricta
7
Optimización –Carmen Ortiz Z. ©
(D) Max ω = 6y1 + 8y2
s.a.
→ (y1)
y1 + 4y2 ≤ 6
2y1 - 2y2 ≤ 4
→ (y2)
3y1 + 2y2 = 2
y1 ≥ 0
y2 irrestricta.
8
RELACIONES DE DUALIDAD
Si
•el problema primal es...
Definición:
OPTIMIZACIÓN
Problema Primal
(P) Min z = c·x
s.a.
Ax ≥ b
x≥0
¡¡ la ciencia de lo mejor !!
Problema Dual
( D) Max ω = y·b
s.a.
AT y ≤ c
y≥0
2010 -2
1
Optimización – Carmen Ortiz Z. ©
EL PROBLEMA DUAL
EL PROBLEMA DUAL
Problema Primal
(P) Min z = c·x
s.a.
Ax ≥ b
x≥0
(P) Min z = 2x1 + 5x2 - x3
s.a.
2x1 - x2 + 4x3 ≥ 4
5x1 +x2 - 2x3 ≥ 3
x1 , x2 , x3 ≥ 0
El d l d l problema lineal estándar
dual del
bl
li
l tá d
Problema Dual
( D) Max ω = y·b
s.a.
yT A ≤ c
y≥0
(D) Max ω = 4y1 + 3 y2
s.a.
2y1 + 5y2 ≤ 2-y1 + y2 ≤ 5
4y1 - 2y2 ≤ -1
y1 , y2 ≥ 0
Optimización – Carmen Ortiz Z. ©
2
Optimización – Carmen Ortiz Z. ©
Problema Primal
(P) Min z = c·x
s.a.
Ax = b
x≥0
3
Optimización –Carmen Ortiz Z. ©
Problema Dual
( D) Max ω = y·b
s.a.
yT A ≤ c
y irrestricto
4
EL PROBLEMA DUAL
EL PROBLEMA DUAL
Problema de
minimización
(D) Max ω = 4y1 + 6y2
(P) Min z = 2x1+ 3x2+5x3
s.a.
s.a.
4y1 + 3 y2 ≤ 2
4x1 + 3x2 - 2x3 = 4 → (y1)
3y
3 1- 2 2≤3
2y
3x1 - 2x2 + x3 = 6 → (y2)
-2y1 + y2 ≤ 5
x1 , x2, x3 ≥ 0
Si la restricción es:
≥
≤
=
irrestricta
≥0
≤0irrestricta
5
Optimización – Carmen Ortiz Z. ©
EL PROBLEMA DUAL
≤
≥
=
6
Optimización – Carmen Ortiz Z. ©
(P) Min z = 6x1 + 4x2+2x3
s.a.
x1 + 2x2 + 3x3 ≥ 6
4x1 - 2x2 + 2x3 = 8Optimización – Carmen Ortiz Z. ©
la restricción asociada es:
EL PROBLEMA DUAL
El dual del dual es el primal
Problema Primal
(P) Min z = c·x
s.a.
Ax
A ≥b
x≥0
la variableasociada es:
≥0
≤0
Si la variable es:
y1 , y2 irrestricto.
Problema de
maximización
Problema Dual
( D) Max ω = y·b
s.a.
yT A ≤ c
y≥0
x1 , x2 ≥ 0
x3 irrestricta
7
Optimización –Carmen Ortiz Z. ©
(D) Max ω = 6y1 + 8y2
s.a.
→ (y1)
y1 + 4y2 ≤ 6
2y1 - 2y2 ≤ 4
→ (y2)
3y1 + 2y2 = 2
y1 ≥ 0
y2 irrestricta.
8
RELACIONES DE DUALIDAD
Si
•el problema primal es...
Leer documento completo
Regístrate para leer el documento completo.