DUALIDAD EN PROGRAMACIÓN LINEAL

DUALIDAD EN PROGRAMACIÓN LINEAL

Dado un modelo lineal determinado, podemos definir otro modelo lineal que nos permitirá obtener propiedades interesantes del primero y que será su dual. La solución del modelo dual, permite obtener interesantes resultados, relativos al análisis de sensibilidad de los términos independientes más concretamente, para los rangos de valores  de los términos independientes para los que se mantiene la base optima (que podemos conocer mediante el análisis de sensibilidad). La solución del dual nos permite conocer el precio sombra de la restricción, que será la variación de la función objetivo por unidad incrementada del termino independiente de la restricción. 

REGLAS DE OBTENCIÓN DEL DUAL

Si el modelo está escrito en la forma canónica, el dual resulta singularmente fácil de obtener. Por ejemplo, partiendo de la forma canónica del modelo de máximo:

Primal                                              Dual

[MIN] z= c^’. x                                 [MAX] w= b^’. u

           A . x ≥ b                                               A^’. u  ≤ c

            x_j ≥ 0                                                   u_i  ≥    0      

INTERPRETACIÓN DE LAS VARIABLES DUALES.

El significado de las variables duales es el mismo que en el caso de los multiplicadores de Lagrange, es decir miden la sensibilidad de la función objetivo respecto a cambios (infinitesimales) de los términos independientes de cada restricción.

Max F = ct x

s.a:

A x = b

x ≥ 0

Donde asumimos que x ∈ Rn, c ∈ Rn, b ∈ Rm y A ∈ Μ(n,m).

Si suponemos que x* es una solución factible básica no degenerada y óptima del problema anterior, es decir, verifica que: x* = B-1 b ≥ 0 ; b ≥ 0; A x* = b y que para una variación del vector de términos independientes b, cuando este vector pasa a ser (b+Δb), siendo (b+Δb) ≥ 0, y que esta variación deje inalterada las variables básicas de la solución, es decir que se cumpla que:

x* = B-1 (b + Δb) ≥ 0; (b + Δb) ≥ 0

A x* = (b + Δb)

En estas condiciones la derivada de la función de Lagrange:

L(x,λ) = cx + λ ( b - Ax )

∂ L

- = λ

∂ b este valor de λ nos indica en cuanto varia la función objetivo ante una variación (infinitesimal) de b, y que mantenga la factibilidad de la solución.

OBTENCIÓN  DE LA SOLUCIÓN DEL DUAL

El dual de un modelo lineal es otro modelo lineal, que puede solucionarse (después de las oportunas transformaciones, si algunas de las variables resultantes es no negativa o no restringida en signo) del mismo modo que el primal. Sin embargo, en general puede obtenerse la solución del dual resolviendo el primal.

DUALES SIMÉTRICOS

Son los 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 menores o igual para los problemas de maximización. Es decir, si el problema original es de la siguiente forma:

Máx Z(x) = c^t x

S.A:

A x ≤ b

x ≥ 0

El problema dual (dual simétrico) es:

Mín G (λ) = λ b

S. A:

λ A ≥ c

λ ≥ 0

DUAL ASIMÉTRICO

 Son los restantes tipos de combinaciones de problema. Como por ejemplo:

Máx Z(x) = c^t x

S. A:

A x = b

X ≥ 0

El problema dual (dual asimétrico) es:

Mín G (λ) = λ b

S. A:

λ A ≥ c

λ >< 0, es decir, variables libres.

CARACTERÍSTICAS DE LAS SOLUCIONES DEL DUAL Y DEL PRIMAL

      Si el primal tiene solución óptima acotada x*, el dual también tendrá solución óptima acotada u*  ambas soluciones darán el mismo valor de la función objetivo.

C’. x^*=b^’. u^*

      Si uno de los dos problemas tiene optimo no acotado, el otro no tendrá solución (la región factible será un conjunto vacío)

      Si uno de los dos problemas no tiene solución, el otro puede tener optimo no acotado o no tener tampoco solución.

RELACIONES PRIMAL-DUAL

Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual 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:

      El problema dual tiene tantas variables como restricciones tiene el programa primal.

      El problema dual tiene tantas restricciones como variables tiene el programa primal

      Los coeficientes de la función objetivo del problema dual son los términos independientes de las restricciones o RHS del programa primal.

      Los términos independientes de las restricciones o RHS del dual son los coeficientes de la función objetivo del problema primal.

      La matriz de coeficientes técnicos del problema dual es la traspuesta de la matriz técnica del problema primal.

      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 restricciones del mismo problema.