CREADO POR JUAN DELGADO Y JONNY BURGO

INTRODUCCION

Todo problema de programación lineal tiene asociado con él otro problema de programación lineal llamado DUAL. El problema inicial es llamado PRIMO y el problema asociado (sombra) es llamado el problema PRIMO. Los dos juntos son llamados problemas duales ya que ambos están formados por el mismo conjunto de datos. La solución básica factible óptima de estos problemas es tal que una puede fácilmente ser usada para la solución de la otra. La dimensión del problema de programación lineal influencia la elección del cálculo del primo o del dual.

Si el primo tiene mas ecuaciones que variables, es frecuentemente mas fácil obtener la solución del dual ya que menor numero de iteraciones son requeridas. Además si el primo tiene solución, el dual tendrá solución. Una vez que el problema dual es formulado, el procedimiento de solución es exactamente el mismo que para cualquier problema de programación lineal.

Interpretación de las variables duales   Cada variable del dual está asociada a una restricción del programa primal, y su valor óptimo representa el incremento de la función objetivo del primal por cada unidad que aumente el término independiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Es, por tanto, el precio adicional máximo que estamos dispuestos a pagar por el incremento del recurso. Los valores de estas variables se denominan precios sombra.

DUALIDAD EN PROGRAMACION LINEAL

El dual es un problema de PL que se obtiene matemáticamente de un modelo primal de PL dado. Los problemas dual y primal están relacionados a tal grado, que la solución símplex óptima de cualquiera de los dos problemas conduce en forma automática a la solución óptima del otro.

El  método símplex además de resolver un problema de PL llegando a una solución óptima nos ofrece más y mejores elementos para la toma de decisiones. La  dualidad y el análisis de sensibilidad son potencialidades de éste método.

En la mayoría de los procedimiento de PL, el dual se define para varias formas del primal, dependiendo de los tipos de restricciones, de los signos de las variables y del sentido de la optimización. La experiencia nos indica que en ocasiones, los principiantes se confunden con los detalles de esas definiciones. Más importante aún es que el uso de esas definiciones múltiples puede conducir a interpretaciones inconsistentes de los datos en la tabla símplex, sobre todo en lo que respecta a los signos de las variables.

El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.

ü      La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:

ü     Aporta elementos que aumentan sustancialmente la compresión de la PL.

ü     El análisis de dualidad es una herramienta útil en la solución de problemas de PL,  por ejemplo: más restricciones que variables.

ü      El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados implícitamente al buscar la solución óptima a un problema de PL.

La forma estándar general del primal se defina como; para maximizar o minimizar.                                                             

sujeto a;

¿Cómo convertir un problema primal a dual? 

Un problema dual se formula de un problema primal de la siguiente forma:

Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.

Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de la disponibilidad en el problema dual.

Los coeficientes del vector de disponibilidad del problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.

Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.

Los signos de desigualdad del  problema dual son contrarios a los del primal.

Cada restricción en un problema corresponde a una variable en el otro problema. Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así, las variables Xn del primal se convierte en nuevas variables Ym en el dual.

PROBLEMA PRIMAL EN FORMA CANONICA:

MAX  Z= CX

Sujeto a:

AX £ b

X ³ 0

PROBLEMA DUAL EN FORMA CANONICA:

MIN  Z= BY

Sujeto a:

AY ³ C

Y ³ 0

Ejemplo.

Si el problema primal es:  MAX  Z= 45X1 + 17X2 + 55X3

                              Sujeto a:

                                        X1   +    X2  +     X3   £ 200

                                       9X1  +  8X2  +  10X3  £ 5000

                                       10X1+  7X2  + 21 X3  £ 4000

Xj ³ 0

 El problema dual será:

          MIN  Z= 200Y1 + 5000Y2 + 4000Y3

          Sujeto a:

                      Y1 +   9Y2 + 10Y3  ³ 45

                      Y1 +   8Y2 +   7Y3  ³ 17

                      Y1 + 10Y2 + 21Y3 ³ 55

Yj ³ 0

FORMA DE PRESENTAR EL PROBLEMA DUAL

MIN  =  2X1 -  3X2                                                            

Sujeto a:                                                                                   

          1X1 +  2X2  £  12                                                                      

          4X1 -   2X2  ³   3

          6X1 -   1X2  = 10                                                                         

X1,2  ³ 0

  1.  Llevar el problema a su equivalente de maximización, multiplicando la función objetivo por –1:

MAX  -2X1 + 3X2

Convertir las restricciones ³ en una restricción equivalente £ multiplicando por –1 ambos lados:

-4x1 + 2x2  £ -3 

Para las restricciones de igualdad, obtener 2 restricciones de desigualdad, una de forma £ y la otra de forma ³; después regresar al punto anterior y cambiar la restricción ³ a la forma £:

6X1 – 1X2 £ 10

6X1 – 1X2 ³ 10

6X1 –  1X2  £   10

-6X1 + 1X2  £  -10

Así el problema primal se ha replanteado en la forma equivalente:

MAX  Z= -2X1 + 3X2

Sujeto a:

1X1 + 2X2  £  12

-4X1 + 2X2  £  - 3

6X1 – 1X2   £  10

-6X1 + 1X2  £ -10

X1,2 ³ 0  

Teniendo el problema primal convertido a la forma canónica de un problema de maximización, es fácil llevarlo al problema dual:

MIN    12Y1 – 3Y2 + 10Y3

Sujeto a:

Y1–4Y2 + 6Y3’–6Y3’’ ³-2          Y’3  y  Y’’3 ambas se refieren a la tercera restricción

2Y1 + 2Y2 – 1Y3’ + 1Y3’’  ³   3                  del problema  primal.

Y1, 2, 3’, 3’’ ³ 0

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

            xj ≥ 0                                                   ui  ≥    0      

Cada variable del dual está asociada

  A una restricción del programa primal, y su valor óptimo representa el incremento de la función objetivo del primal por cada unidad que aumente el término independiente de dicha restricción, siempre que este último aumento no suponga un cambio de base. Es, por tanto, el precio adicional máximo que estamos dispuestos a pagar por el incremento del recurso. Los valores de estas variables se denominan precios sombra.

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.

Dual simétrico y asimetrico

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) = ct 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) = ct 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.