Condiciones de
Kuhn-Tucker en los problemas lineales (primales y duales).
Consideremos el
siguiente programa lineal, que denominaremos PRIMAL:
Máx Z(x) = ct x
s.a:
A x ≤ b
x ≥ 0
La función
lagrangiana de esta programa será:
L(x,λ) = c x +
λ ( b - Ax
) donde λ = ( λ1, λ2,....,λm )
representa el vector de los multiplicadores de Lagrange asociados a las
restricciones.
Las condiciones
de optimalidad de este problema (Condiciones de Kuhn-Tucker) respecto de las
variables, son:
∂L
= c - λ A ≤ 0
∂x
∂L
x = ( c - λ A ) x = 0
∂x
x ≥ 0
Respecto a los multiplicadores,
son:
∂L
= b - Ax ≥ 0
∂λ
∂L
λ = λ ( b - Ax ) = 0
∂λ
λ ≥ 0
Asociado a este programa primal tenemos otro problema lineal
denominado DUAL (posteriormente
explicaremos las relaciones entre ambos):
Mín G(λ) = λ b
s.a:
λ A ≥ c
λ ≥ 0
La función lagrangiana de este programa será:
L(λ,x) = λ b + ( c - λA ) x en donde el
vector x = ( x1, x2, ..., xn ) representa los multiplicadores asociados a las
restricciones del dual.
Obteniendo las
condiciones de Kuhn-Tucker respecto de las variables son:
∂L
= b - Ax ≥ 0
∂λ
∂L
λ = λ ( b - Ax ) = 0
∂λ
λ ≥ 0
Respecto a los multiplicadores, son:
∂L
= c - λ A ≤ 0
∂x
∂L
x = ( c - λ A ) x = 0
∂x
x ≥ 0
Como puede
observarse, ambas condiciones de optimalidad son las mismas para los dos
problemas. A la misma consideración se puede llegar sin más que comparar la
función de Lagrange de los dos problemas y ver que son iguales:
L(x,λ) = c x + λ ( b - Ax )
L(λ,x) = λ b +( c - λA )x = λ b + cx-λAx = cx + λ( b - Ax )
Por lo tanto,
asociado a todo problema de programación lineal existe otro problema de
programación lineal denominado programa
dual que tiene importantes relaciones con el problema original
denominado programa primal. Como
acabamos de ver, es evidente, que el programa dual de un programa dual
proporciona el programa primal original.
No hay comentarios:
Publicar un comentario