teoria de la dualidad

Teoría de la dualidad

El dualismo es una teoría que surge como consecuencia de una profundización en el estudio de la programación lineal porque la distribución de los recursos y la formación de los precios son dos aspectos del mismo problema. Entonces la doble formulación de la programación lineal no se debe considerar como un simple ejercicio matemático, sino que una y otra versión del problema vienen a explicar dos aspectos económicos distintos para una misma situación problemática. Una propiedad fundamental de la relación entre el primal y el dual es que la solución óptima de cualquiera de estos problemas proporciona la solución óptima para el otro.                                       

                                                Dualidad

 

El concepto de dualidad desempeña importantes papeles dentro de la programación lineal (también en la no lineal), tanto desde un punto de vista teórico como práctico. Todo programa lineal lleva asociado otro programa lineal conocido como su programa dual; el programa inicial se conoce también como programa primal.

 

 

IMPORTANCIA DE LA DUALIDAD

 

La importancia de la teoría de la dualidad se puede resumir, entre otros aspectos, en lo siguiente:

• Permite resolver problemas de programación lineal de forma más rápida y sencilla.
• Es otra vía para resolver un problema de programación lineal.
• Facilita profundizar en el contenido económico del problema original (primal).
• Puede ser utilizada para resolver el caso en que se debe considerar la introducción de una nueva variable en el primal una vez que ha de sido obtenida la solución óptima, sin tener que resolver completamente el problema.

RELACIONES ENTRE EL METODO PRIMAL Y DUAL

De lo anteriormente expuesto se puede deducir que existe una estrecha relación entre el problema primal y dual que puede expresarse en lo siguiente:

• El dual tiene la matriz D transpuesta, es decir, si suponemos que D es de orden sx r, entonces Dt es de orden r x s. Además las variables del primal y el dual son diferentes, ya que X será un vector de r-componentes mientras que el vector Y tendrá s-componentes.
• Los términos independientes del conjunto de las restricciones del problema primal forman los coeficientes de la función objetivo del dual.
• Los coeficientes de la función objetivo del primal forman los términos independientes de las restricciones del dual.
• Las restricciones del dual cambian su sentido al igual que el criterio de optimización en términos de mínimo o máximo.
• A cada restricción del problema primal le corresponde una variable dual y análogamente a cada restricción del dual le corresponde una variable del primal.
• Si se halla el dual del problema dual, obtendremos el problema primal.

TABLA DE TUCKER

NOTACIÓN MATEMÁTICA

       Notación primal

min cx

Ax >= b

x >= 0

       Notación dual

max b'z

A'z <= c'

z >= 0

TEOREMAS DE LA DUALIDAD

TEOREMA DE DUALIDAD DÉBIL: En general, el valor de cualquier solución factible del problema de minimización, provee una cota superior del valor óptimo del problema de maximización. Análogamente, el valor de la función objetivo de cualquier solución factible del problema de maximización es una cota inferior del valor óptimo del problema de minimización.

TEOREMA DE DUALIDAD FUERTE: En el óptimo el valor de la función objetivo del problema primal será igual al valor de la función objetivo del problema dual evaluada en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es infactible. Alternativamente si el problema primal es infactible, entonces el dual es no acotado.

TEOREMA DE HOLGURAS COMPLEMENTARIAS: Una variable en el primal está asociada a una restricción en el dual (y viceversa). En este sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en un problema lineal la solución óptima (en caso de existir) está en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad).

Interpretación económica del problema dual

El problema primal y dual explica dos aspectos económicos distintos de un mismo problema.

Las variables duales nos vienen a medir el valor de los recursos imputados a la producción, pero esta valoración tiene unas características peculiares, está realizada en términos de costos de oportunidad. Esto quiere decir que aquellos factores (o restricciones) cuyas existencias no quedan agotadas en el programa óptimo establecido, tienen un costo nulo desde el anterior punto de vista, pues bajo el prisma exclusivo del sistema empresarial es un bien libre al estar en exceso.

En consecuencia, la función objetivo, medirá el costo total de los factores imputados a la producción, valor que ha de igualarse al rendimiento total hallado en la función económica del primal para que se produzca el equilibrio. Explicaremos con más detalle la interpretación económica del problema dual.

Para la realización de este análisis vamos a partir del supuesto que se tiene un problema de programación lineal donde se maximiza el valor de la función objetivo, por ejemplo la ganancia.

Conversiones de primal a dual

 

 

            

PRIMAL

1. MINZ = 8X1 + 2X2
    
   3X1 + 5X2 ≥ 6

         12X1 + 2X2 ≤ 3 (-1)

   X1, X2 ≥ 0

 

FORMATO CANÓNICO

 

MINZ = 8X1 + 2X2

 

   3X1 + 5X2 ≥ 6

-12X1 -  2X2 ≥ -3

       X1, X2 ≥ 0

 

FORMADO DUAL

 

MAXZ = 6Y1 – 3Y2

 

3Y1 – 12Y2 ≤ 8

5Y1 -  2Y2 ≤ 2

   Y1, Y2 ≥ 0

 

  

PRIMAL.

1. MIN Z= 4X1 + 12X2
     X1 + 3X2 ≥ 3
   2X1 + 2X2 = 5
       X1, X2 ≥ 0
    

FORMATO CANONICO

 

MINZ= 4X1 + 12X2

 

  X1 + 3X2 ≥ 3

2X1 + 2X2 ≥ 5

2X1 + 2X2 ≤ 5 (-1)

   X1, X2 ≥ 0

 

 

MINZ= 4X1 + 12X2

 

  X1 +3X2 ≥ 3

2X1 + 2X2 ≥ 5

         -2X1 - 2X2 ≥ -5

             X1, X2 ≥ 0

 

FORMATO DUAL

 

              MAX Z= 3Y1 + 5Y2 – 5Y3

             

                  Y1 + 2Y2 – 2Y3 ≤ 4

                3Y1 + 2Y2 – 2Y3 ≤ 12

                     Y1, Y2, Y3 ≥ 0

 

 

 

PRIMAL

1. MINZ = 2X1 + 3X2
    
   2X1 + 8X2 ≤ 16 (-1)
   5X1 + 3X2 ≥ 20
   7X1 + 6X2 = 10
       X1, X2 ≥ 0

 

 

 

FORMATO CANONICO

           MINZ = 2X1 + 3X2

 

-2X1 – 8X2 ≥ -16

5X1 + 3X2 ≥ 20

7X1 + 6X2 ≥ 10

7X1 + 6X2 ≤ 10 (-1)

 

MINZ = 2X1 + 3X2

          -2X1 – 8X2 ≥ -16

5X1 + 3X2 ≥ 20

7X1 + 6X2 ≥ 10

         -7X1  - 6X2 ≥ -10

 

FORMATO DUAL

 

MAXZ = 16Y1 + 20Y2 + 10Y3 – 10Y4

 

      -2Y1 + 5Y2 + 7Y3 – 7Y4 ≤ 2

      -8Y1 + 3Y2 + 6Y3 – 6Y4 ≤ 3

              Y1,Y2, Y3,Y4 ≥ 0

 

 

FORMATO PRIMAL

 

1. MIN Z = 5X1 + 2X2 + 4X3

       

                  3X1 +   X2 + 2X3 ≥ 4

       6X1 + 3X2 + 5X3 ≥ 10

               X1, x2, x3 ≥ 0

 

 

FORMATO DUAL

 

            MAX Z = 4Y1 + 10Y2

                            

                3Y1 + 6Y2 ≤ 5

                  Y1 + 3Y2 ≤ 2

                2Y1 + 5Y2 ≤ 4

                    Y1, Y2 ≤ 0

 

 

 

 

FORMATO ESTANDAR

 

                 MAX Z = 4Y1 + 10Y2 + 0S1 + 0S2

 

                            3Y1 + 6Y2 + S1 = 5

                              Y1 + 3Y2          + S2 = 2

                            2Y1 + 5Y2                   + S3 = 4

                                   Y1, Y2, S1, S2, S3 ≥ 0

IGUALAMOS LA FUNCION OBJETIVO A CERO

 

               Z – 4Y1 – 10Y2 – 0S1 – 0S2 – 0S3 = 0

BASE	Z	Y1	Y2	S1	S2	S3	SOLUCION
Z	1	-4	--10	0	0	0	0
S1	0	3	6	1	0	0	5
S2	0	1	3	0	1	0	2
S3	0	2	5	0	0	1	4

 

APLICACIÓN DE LA FORMULAS

 

FP / CP = FN

FP=	0	1	3	0	1	0	2
CP=	3	3	3	3	3	3	3
FN=	0	1/3	1	0	1/3	0	2/3

 

FV— (CP * FN)

 

S3 (FV)	0	2	5	0	0	1	4
CP	5	5	5	5	5	5	5
FN	0	1/3	1	0	1/3	0	2/3
S3	0	1/3	0	0	-5/3	1	2/3

 

 

S1 (FV)	0	3	6	1	0	0	5
CP	6	6	6	6	6	6	6
FN	0	1/3	1	0	1/3	0	2/3
S1	0	1	0	1	-2	0	1

 

 

Z(fv)	1	--4	--10	0	0	0	0
CP	--10	--10	--10	--10	--10	--10	--10
FN	0	1/3	1	0	1/3	0	2/3
Z	1	-2/0	0	0	10/3	0	20/3

 

 

BASE	Z	Y1	Y2	S1	S2	S3	SOLUCION
Z	1	--2/3	0	0	10/3	0	20/3
S1	0	1	0	--1	-2	0	1
Y2	0	1/3	1	0	1/3	0	2/3
S3	0	1/3	0	0	--5/3	1	2/3

 

 

 

FP/CP

 

FP=	0	1	0	1	--2	0	1
CP=	1	1	1	1	1	1	1
FN=	0	1	0	1	--2	0	1

 

FV – (CP * NF)

 

Y2(fv)	0	1/3	1	0	1/3	0	2/3
CP	1/3	1/3	1/3	1/3	1/3	1/3	1/3
FN	0	1	0	1	--2	0	1
Y2	0	0	1	--1/3	1	0	1/3

 

 

S3(fv)	0	1/3	0	0	--5/3	1	2/3
CP	1/3	1/3	1/3	1/3	1/3	1/3	1/3
FN	0	1	0	1	--2	0	1
S3	0	0	0	--1/3	--1	1	1/3

 

 

Z(fv)	1	--2/3	0	0	10/3	0	20/3
CP	--2/3	--2/3	--2/3	--2/3	--2/3	--2/3	--2/3
FN	0	1	0	1	--2	0	1
Z	1	0	0	2/3	2	0	22/3

 

 

BASE	Z	Y1	Y2	S1	S2	S3	SOLUCION
Z	1	0	0	2/3	2	0	22/3
Y1	0	1	0	1	--2	0	1
Y2	0	0	1	--1/3	1	0	1/3
S3	0	0	0	--1/3	--1	1	1/3

 

 

 

 

 

Y por ultimo realizamos la comprobación

 

Z= 22/3

Y1= 1

Y2=1/3

S3= 1/3

 

                            3(1) + 6(1/3) + 0 = 5

                              (1) + 3(1/3)          + 0 = 2

                            2(1) + 5(1/3)                  + 1/3 = 4