Dualidades

DUALIDAD EN PROGRAMACION LINEAL Relaciones primal-dual Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual (PD) , que posee importantes propiedades y relaciones notables con respecto al problema lineal original, problema que para diferencia del dual se denomina entonces como problema primal (PP). Las relaciones las podemos enumerar como siguen: a)El problema dual tiene tantas variables como restricciones tiene el programa primal. b) El problema dual tiene tantas restricciones como variables tiene el programa primal c) Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal.

d) Los términos independientes de las restricciones o RHS del dual son loscoeficientes de la función objetivo del problema primal. e) La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal. f) El sentido de las desigualdades de las restricciones del problema dual y el signo de las variables del mismo problema, dependen de la forma de que tenga el signo de las variables del problema primal y del sentido de las restriccionesdel mismo problema. ( Ver tabla de TUCKER) g) Si el programa primal es un problema de maximización, el programa dual es un problema de minimización. h) El problema dual de un problema dual es el programa primal original.

Tabla de TUCKER

MAXIMIZACION

MINIMIZACION.

≤ RESTRICCIONES ≥ =

≥ ≤ >< VARIABLES

≥ VARIABLES ≤ ><

≥ ≤ = RESTRICCIONES

Los problemas duales simétricos sonlos que se obtienen de un problema primal en forma canónica y ‘normalizada’, es decir, cuando llevan asociadas desigualdades de la forma mayor o igual en los problemas de minimización, y desigualdades menor o igual para los problemas de maximización. Es decir, si el problema original es de la siguiente forma:

Máx Z(x) = ct x s.a: Ax≤b x≥0 El problema dual ( dual simétrico ) es : Mín G(λ) = λ bs.a: λA ≥c λ ≥0 Los restantes tipos de combinaciones de problemas, se conocen con el nombre de duales asimétricos. ejemplo: Máx Z(x) = ct x s.a: Ax=b x≥0 El problema dual ( dual asimétrico ) es : Mín G(λ) = λ b s.a: λA ≥c λ >< 0, es decir, variables libres. Como por

PREGUNTAS: ¿ Porqué se plantea el programa dual?. ¿ Que significado tiene su solución?. ¿ La solución del dual se puede obtenerdesde el primal?. RESPUESTAS: a) Por una parte permite resolver problemas lineales donde el numero de restricciones es mayor que el numero de variables. Gracias a los teoremas que expondremos a continuación la solución de unos de los problemas ( primal o dual) nos proporciona de forma automática la solución del otro programa. b) La dualidad permite realizar importantes interpretaciones económicasde los problemas de programación lineal. c) La dualidad permite generar métodos como el método dual del simplex de gran importancia en el análisis de postoptimización y en la programación lineal parametrica.

Otra de las ventajas de la dualidad, es la posibilidad de resolver gráficamente algunos problemas. Consideremos el siguiente problema lineal: Min Z(x) = 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5s.a: x1 + x2 + 2 x3 + x4 + 3 x5 ≥ 4 2 x1 - x2 + 3 x3 + x4 + x5 ≥ 3 x1 ≥ 0 , x2 ≥ 0 , x3 ≥ 0 , x4 ≥ 0 , x5 ≥ 0 Dado que se trata de un programa lineal en forma canónica, ello nos proporciona un dual en forma simétrica como el siguiente: Max G(λ) = 4 λ1 + 3 λ2 s.a: λ1 + 2 λ2 ≤ 2 λ1 - λ2 ≤3 2 λ1 + 3 λ2 ≤ 5 λ1 + λ2 ≤ 2 3 λ1 + λ2 ≤ 3 λ1 ≥ 0 , λ2 ≥ 0

Este problema solo tiene dos variables y cincorestricciones por tanto se puede resolver gráficamente:

4

3

2

1

0

-1 -1 0 1 2 3 4

Gráfico 2 vértice solución es el punto (4/5,3/5) con un valor de la función objetivo de 5. x1 + 3 x5 = 4 2 x1 + x5 = 3

La solución de este sistema es : x1 = 1 y x5 = 1, lo cual nos proporciona un valor de la función objetivo de Z(x) = 5, idéntico a la solución del dual 6.1. Condiciones de...