Elproblema dual

Vista previa del material en texto

INVESTIGACIÓN OPERATIVA I
El Problema Dual
Objetivos
Conocer las características del problema dual.
Entender como se aplica y resuelve la dualidad en un MPL .
Aplicar dualidad en casos practicos.
1. EL PROBLEMA DUAL
 	Cada problema de PL(primal), ésta 	asociado a él otro modelo lineal 	llamado dual. 
 	Los dos problemas poseen información 	complementaria, de tal manera que la 	solución optima del primal, proporciona 	información complementaria de la 	solución optima del dual y viceversa.
 	Más importante será la utilización de 	estas relaciones, para obtener 	información adicional sobre las 	variaciones en la solución optima, 	debido a ciertos cambios en los 	coeficientes y en la formulación del 	problema.
Dado el primal:
	Max Z =  cj Xj
	Sa
		  aij Xj  bi i=1,..,m.
			Xj  0	 j=1,..,n
Su dual:
	Min G =  bi Yi
	Sa
		  aij Yi  cj	j=1,..,m
			Yi  0	 i=1,..,n
 
Donde 	Max Z = Min G
De la definición se observa:
1.   Cada restricción en un problema, 	corresponde a una variable del otro 	problema.
2.      Un problema es de maximizar y el otro es 	de minimizar y viceversa.
3.  Los valores de los recursos, de las 	restricciones en un problema, 	corresponden como coeficientes de la FO 	en el otro y viceversa.
4.      En ambos problemas, las variables son no 	negativas.
2. USOS DE LA FORMULACION DUAL.
1.  Resolver problemas lineales que tienen 	más restricciones que actividades.
2.     Hacer interpretaciones económicas de las 	soluciones optimas de los problemas de 	PL.
3.   Generar nuevos algoritmos para la 	solución de los problemas reales de 	optimización.
3. ALGORITMO SIMPLEX DUAL.
a.     	CONDICION DE FACTIBILIDAD.
 	Variable basica saliente, con el valor 	más negativo ( XBi ). 
 	Caso de empate elección arbitraria. 
 	Si todas las variables básicas son no 	negativas ( XBi > 0 el proceso termina y 	se obtiene la solución optima del 	problema.
b.     	CONDICION DE OPTIMALIDAD
 	Variable no basica entrante.
 	Elegir el cociente donde el numerador 	es	el coeficiente de la FO y el 	denominador del coeficiente asociado 	con las variables no básicas. 
 	Ignorar cocientes asociados con 	denominadores positivos o cero.
 	La variable entrante; es el cociente 	más 	pequeño. 
 	Si todos los denominadores son ceros o 	positivos el problema sin solución 	factible.
4. EL DUAL DEL PRIMAL CANONICO.
Dado el problema:
	Max Z =  cj Xj
	Sa
		  aij Xj  bi	 i
			Xj  0		 j
 
Su dual asociado:
	Min G =  bi Yi
	Sa
		  aij Yi  cj	 j 
			Xj  0		 j
Ejemplo: Dado el primal
	Max Z = X1 + 3 X2 /2
	SA
		2 X1 + 2 X2  160  Y1
		 X1 + 2 X2  120  Y2
		4 X1 + 2 X2  280  Y3
			X1 , X2  0
Su dual:
	Min G = 160 Y1 + 120 Y2 + 280 Y3
	Sa	2 Y1 + Y2 + 4 Y3  1
		2 Y1 + 2 Y2 + 2 Y3  3/2
			Y1 Y2 Y3  0
Los problemas se pueden resolver:
1.     Solución del primal con simplex primal
2.     Solución del dual con el simplex dual.
3.     Solución del dual con el simplex primal.
Transformando las restricciones:
	Min G = 160 Y1 + 120 Y2 + 280 Y3
	Sa
		-2 Y1 - Y2 - 4 Y3  - 1
		-2 Y1 - 2 Y2 - 2 Y3  - 3/2
			Y1 Y2 Y3  0
Estandarizando:
 Min G = 160 Y1 + 120 Y2 + 280 Y3
 Sa
	-2 Y1 - Y2 - 4 Y3 + S1 = - 1
	-2 Y1 - 2 Y2 - 2 Y3 + S2 = - 3/2
			Y1, Y2, Y3  0
 
 Y1 Y2 Y3
 S1 S2
 
 
-160 -120 -280
 0 0
  0
 S1
 S2
 -2 -1 -4
 -2 -2* -2
 1 0
 0 1
-1
-3/2 
 
 
-160/ -120/ -280/
 -2 -2  -2
 - 0
 
 
 -40 0 -160
 0 -60
 90
 S1
(120)(1) Y2
 -1* 0 -3
 1 1 1 
 1 -1/2
 0 -1/2
 -1/4
 3/4
 
 -40/-1 - -160/-3
 -160/(-1/2)
 
 
 0 0 -40
 -40 -40
 100
(40)(-1) Y1
 Y2
 1 0 3
 0 1 -2
 -1 1/2
 1 -1
1/4
2/4
5. EL DUAL DEL PRIMAL ESTANDAR
Sea el problema del PL en forma estandar:
	Max Z =  cj Xj
	Sa	  aij Xj = bi i=1,..,m.
			Xj  0	 j=1,..,n
Su dual:
	Min G =  bi Yi
	Sa	  aij Yi  cj	j=1,..,m
			Yi is	 i=1,..,n
Ejemplo:
	Max Z = 3 X1 + X2
	Sa:		 X1  4
		 		2 X2 = 10
	 		3 X1 + 2 X2  18
			 X1, X2  0
Operando:
		X1  4  Y1
		 2 X2  10  Y’2
		 -2 X2  -10  Y”2
	 -3 X1 - 2 X2  -18  Y3
Transformando:
 Min G = 4 Y1 + 10 Y’2 – 10 Y”2 – 18Y3
 Sa		Y1			 - 3 Y3  3
		 2Y’2 – 2Y”2 – 2 Y3  1
		Y1, Y3, Y’2,Y”2  0
Estandarizando:
 
Min G = 4Y1 + 10Y’2 – 10Y”2 – 18Y3 + 0S1 + 0S2
Sa
	-Y1			 + 3 Y3 + S1 = - 3
 -2Y’2 + 2Y”2 + 2 Y3 + S2 = -1
Siendo el modelo:
 Min G = 4 Y1 + 10 Y2 – 18Y3
 Sa		Y1 - 3 Y3  3
		 2 Y2 – 2 Y3  1
		Y1, Y3  0 , Y2 is.
 
 Y1 Y’2 Y”2 Y3
 S1 S2
 
 
 -4 - 10 + 10 18
 0 0
 0
 S1
 S2
 -1* 0 0 3
 0 - 2 2 2
 1 0
 0 1
-3
-1 
 
- 4/-1
 - 0
 
 
 0 -10 10 6
 -4 0
 12
 Y1
 S2
 1 0 0 -3
 0 -2* 2 2 
-1 0
 0 1
 3
 -1
 
 -10/-2
 
 
 
 0 0 0 -4
 -4 -5
 17
 Y1
 Y’2
 1 0 0 -3
 0 1 -1 -1
 -1 0
 0 -1/2
 3
 1/2
Y’2 = 1/2
Y2 = Y’2 – Y”2 = 1/2 - 0 = 1/2
6. INTERPRETACIONES DEL DUAL
 
Problema primal (MAX):
	Max Z =  cj Xj
	Sa
		 aij Xj  bi
			 Xj  0
Donde:
Xj: Cantidad a producir del artículo j
Cj: Utilidad por producir el artículo j
CjXj: Utilidad por producir Xj cantidades 	del 	artículo j.
CjXj: Utilidad total por producir n 			 artículos en las cantidades Xj 
Max Z: Máxima Utilidad total.
 aij: Cantidad consumida del recurso i por 	 
 cada unidad del artículo j.
aijXj; Número de unidades consumidas del 	 
 recurso i / unidad del artículo j.
aijXj: Número de unidades consumidas del 	recurso i por producir n artículos en 	las cantidades Xj de cada artículo j.
	bi: Cantidad disponible del recurso i.
Una cia. Fabrica dos tipos de artefactos; manuales y eléctricos, cada uno de ellos requiere el uso de la máquina A y B en su producción.
EJEMPLO:PROBLEMA PRIMAL
ARTEFACTO MAQUINA A MAQUINA B UTILIDAD/UNIDAD
Manuales 1 hr 1 hr $ 10.0
Eléctrico 2 hrs 4 hrs $ 24.0
HRS DISPONIBLES 120 hrs 180 hrs
Suponiendo que la Cia. Puede vender todos los artefactos que puede fabricar. Determinar la utilidad mensual de la producción de artefactos:
SOLUCION:
 Variable de decisión
 X1: Nro de artefactos manuales a 	fabricar/mes
 X2: Nro de artefactos eléctricos a 	fabricar / mes
 Restricciones:
Disponibilidad de horas mensual / máquina.
 Maquina A: X1 + 2X2 < 120
 Máquina B: X1 + 4X2 < 180
 Función Objetivo:
Producir artefactos, maximizando la utilidad
 Max Z = 10X1 + 24X2
 OBS: X1 + 2X2 : Número de horas necesarios en la producción de artefactos; manuales y eléctricos en la máquina A.
Estandarizando:
 Max Z = 10X1 + 24X2
s.a
 	X1 + 2X2 + S1 = 120
 	X1 + 4X2 +S2 = 180
 
 X1 X2
 S1 S2 
 RHS
 
 -10 -24
 0 0
 0
 S1
 S2
 1 2
 1 4
 1 0
 0 1
 120
 180
 
 -4 0
 0 6
 1,080
 S1
 X2
 1/2 0
 1/4 1
 1 -1/2 
 0 1/4
 30
 45
 
 0 0
 8 2
 1,320
 X1
 X2
 1      0
 0 1
 2      -1
 -1/2 1/2
 60
 30
Problema dual:
	Min G =  bi Xi
	Sa
		 aij Yi  cj
			Yi  0
Donde: 
bi: Cantidad disponible del recurso i	
Yi: Valor marginal de utilidad/costo del 	recurso i.
biYi: Valor marginal de utilidad/costo,del 	consumo de bi unidades del recurso i.
biYi: Valor marginal de utilidad/costo,del 	consumo de las bi unidades de cada 	recurso i.
aijYi: Valor marginal de utilidad/costo del 	consumo de aij del recurso i en la 	producción del artículoj.
aijYi: Valor marginal de utilidad/costo del 	consumo de aij de los recursos i en la 	producción del artículo j.Tambien; 	unidades de cada recurso i asignados en la 	producción del articulo j.
Min G: Valor marginal de utilidad mínima, del 	consumo de las bi unidades de cada 	recurso 	i.
Consideremos el punto de vista:
La Cia desea rentar las máquinas A, B a un costo accesible del cliente. Sabiendo que las horas disponibles para la máquina A es de 120/mes y la máquina B de 180/mes.
	El alquiler de las máquinas para producir artefactos manuales debe ser por lo menos de $10/hr y para artefactos eléctricos por lomenos $24/hr. Cuál es el costo/hr por la renta de las maquinas A y B?
7. EJEMPLO: PROBLEMA DUAL
SOLUCION
Programa lineal primal:
 
 Max Z = 10X1 + 24X2
s.a
 	X1 + 2X2 < 120  Y1
 	X1 + 4X2 < 180  Y2
		X1, X2 > 0
Programa lineal dual:
 Variable de decisión
	Y1 : Tarifa / hr por rentar la máquina A
	Y2 : tarifa / hr por rentar la máquina B
 Restricciones:
	Utilidades por fabricar artefactos
	Manuales: 	 Y1 + Y2 > 10
	Eléctricos:	2Y1 + 4Y2 > 24
 Función Objetivo:
	Minimizar las tarifas por la renta de 	las máquinas.
		Min G = 120 Y1 + 180 Y2
OBS: utilidad por la renta de las máquinas A y B en la producción de artefactos manuales. Y esto debe ser al menos 10 u.m.
Simplex dual.
Dado el PL:
	Min G = 120Y1 + 180Y2
	s.a.
	Y1 + Y2 > 10
	2Y1 + 4Y2 > 24
		Y1, Y2 > 0
transformando:
	s.a.
-   Y1 – Y2 < -10
- 2Y1 – 4Y2 < -24
estandarizando.
	s.a.
-   Y1 – Y2 + S1 = -10
- 2Y1 – 4Y2 + S2 = -24
 
 Y1 Y2
 S1 S2
 RHS
 
 -120 -180
 0 0
 
 S1
 S2
 -1 -1
 -2 -4*
 1 0
 0 1
 -10
 -24
 
 -120/-2 -180/-4
 
 
 
 -30 0
 0 -45
1,080
 S1
 Y2
 -2/4* 0
 2/4 1
 1      -1/4
 0 -1/4
 -4
 6
 
-30/(-2/4)
 -45/(-1/4)
 
 
 0 0
 -60 -30
1,320
 Y1
 Y2
 1 0
 0 1
 -2 1/2
 1 -1/2
 8
 2
8. PROPIEDADES PRIMAL – DUAL.
 Programas primal
 Max Z = 10X1 + 24X2	
 s.a				 
 	X1 + 2X2 < 120 	 
 	X1 + 4X2 < 180 	 
	X1, X2 > 0		
 
 X1 X2
 S1 S2 
 RHS
 
 0 0
 8 2
 1,320
 X1
 X2
 1 0 
 0 1
   2 -1
 -1/2 1/2
 60
 30
Tabla optima primal:
 
 Y1 Y2
 S1 S2
 RHS
 
 0 0
 -60 -30
1,320
 Y1
	Y2
   2 0
 0 1   
 -2 1/2
 1 -1/2
 8
 2
Tabla optima dual:
Programa dual:
 Min G = 120Y1 + 180Y2
 s.a.
 Y1 + Y2 > 10
 	2Y1 + 4Y2 > 24
	Y1, Y2 > 0
PROPIEDAD I:
Coeficientes de la FO de la tabla derecha:
Ultima iteración del primal:
(C1 , C2) = (10, 24)
Calculando:
PROPIEDAD II:
Coeficientes de la FO de la tabla izquierda:
	Zj – Cj = - Cj +  aij Yi j = 1,2, .., n
Z1 – C1 = -C1 + a11 Y1 + a21 Y2 
		= -10 + 1(8) + 1(2) = 0
Z2 – C2 = -C2 + a12 Y1 + a22 Y2 
		= -24 + 2(8) + 4(2) = 0
PROPIEDAD III:
Calculo de los valores de las variables básicas:
PROPIEDAD IV
Elementos de la tabla izquierda, restricciones.
 
X1
 
X2
PROPIEDAD V 
	Z =  bi Yi 
	Z = b1 Y1 + b2 Y2 = 120(8) + 180 (2) = 1,320
31
(
)
(
)
2
8
2
/
1
2
/
1
1
2
24
10
=
÷
÷
ø
ö
ç
ç
è
æ
-
-
÷
÷
ø
ö
ç
ç
è
æ
=
÷
÷
ø
ö
ç
ç
è
æ
÷
÷
ø
ö
ç
ç
è
æ
-
-
30
60
180
120
2
/
1
2
/
1
1
2
=
÷
÷
ø
ö
ç
ç
è
æ
÷
÷
ø
ö
ç
ç
è
æ
-
-
1
1
2
/
1
2
/
1
1
2
÷
÷
ø
ö
ç
ç
è
æ
0
1
=
÷
÷
ø
ö
ç
ç
è
æ
÷
÷
ø
ö
ç
ç
è
æ
-
-
4
2
2
/
1
2
/
1
1
2
÷
÷
ø
ö
ç
ç
è
æ
1
0