Problema Dual
Mtodo Dual Smplex
I
OBJETIVOS
Reconocer el problema primal y el problema dual.
Convertir problemas primales en duales.
Conocer y aplicar el mtodo dual smplex, para solucionar problemas de
programacin lineal.
II
TEMAS A TRATAR
Problema Primal.
Problema Dual.
Concepto, pasos para llegar a l, ventajas.
Mtodo dual smplex.
III
MARCO TEORICO
PROBLEMA PRIMAL
Es el modelo matemtico que obtenemos luego de analizar y plantear un problema de
programacin lineal. En otras palabras es el modelo que obtenemos luego de plantear un
problema.
PROBLEMA DUAL
Modelo relacionado al problema primal.
CONVERSIN DE PRIMAL A DUAL
Para obtener el dual, se siguen los siguientes pasos:
a) Si el primal es maximizacin, el dual es minimizacin; y viceversa.
b) Si dual es maximizacin, entonces el smbolo de todas sus restricciones es . Si dual
es minimizacin, entonces el smbolo de todas sus restricciones es .
c) Se define una variable dual por cada restriccin primal.
Sesin
d) Se define una restriccin dual por cada variable primal.
e) Los coeficientes en cada una de las restricciones duales son iguales a los coeficientes
de las variable primales asociadas.
f) Los lmites de cada una de las restricciones duales, son iguales a los coeficientes de
la funcin objetivo primal.
g) Los coeficientes de la funcin objetivo dual son los lmites del problema primal.
NOTA: Desde el mometo que se define una variable dual, sta es no restringida (puede
ser negativa), solamente cambiar esta concepto si el problema dual dice lo
contrario (nos dice que no es negativa).
NOTA: Si el problema dual, nos da una variable redundante (nos afirma que una variable
sigue siendo no restringida), entoces esa variable debe ser considerada como una
restriccin completa..
Ejemplo 1
Max. Z = 5X
1
+ 4X
2
Max. Z = 5X
1
+ 4X
2
+ 0X
3
+ 0X
4
+ 0X
5
+ 0X
6
6X
1
+ 4X
2
24 6X
1
+ 4X
2
+ X
3
= 24 (Y
1
)
X
1
+ 2X
2
6 X
1
+ 2X
2
+ X
4
= 6 (Y
2
)
-X
1
+ X
2
1 -X
1
+ X
2
+ X
5
= 1 (Y
3
)
X
2
2 X
2
+ X
6
= 2 (Y
4
)
El dual es:
Min. B = 24Y
1
+ 6Y
2
+ Y
3
+ 2Y
4
6Y
1
+ Y
2
Y
3
5
4Y
1
+ 2Y
2
+ Y
3
+ Y
4
4
Y
1
0
Y
2
0
Y
3
0
Y
4
0
Las soluciones son:
Primal Dual
Z 21 B 21
X1 3 Y1
X2 3/2 Y2
Y3 0
Y4 0
X
1
X
2
S
1
S
2
S
3
S
4
Solucin
Z 0 0 3/4 1/2 0 0 21
X
1
1 0 1/4 -1/2 0 0 3
X
2
0 1 -1/8 0 0 3/2
S
3
0 0 3/8 -5/4 1 0 5/2
S
4
0 0 1/8 -3/4 0 1 1/2
VENTAJAS DE USAR EL PROBLEMA DUAL
Nos permite realizar menos clculos al hallar las soluciones, por ejemplo un
problema de 2 variables y 4 restricciones, se convierte en uno de 2 restricciones y 4
variables.
Nos permite hacer un anlisis econmico.
MTODO DUAL SIMPLEX
Antes de ingresar a este concepto, vale la pena indicar que ste no tiene nada que ver con
el concepto anterior, ste es un nuevo mtodo de solucin de problemas de programacin
lineal, usado cuando tenemos restricciones >=.
Se ver el mtodo dual smplex, mediante el siguiente ejemplo 2:
Min Z = 2X
1
+ X
2
Min Z = 2X
1
+ X
2
Min Z = 2X
1
+ X
2
+ 0X
3
+ 0X
4
+ 0X
5
3X
1
+ X
2
3 -3X
1
X
2
-3 -3X
1
X
2
+ X
3
= -3
4X
1
+ 3X
2
6 -4X
1
3X
2
-6 -4X
1
3X
2
+ X
4
= -6
X
1
+ 2X
2
3 X
1
+ 2X
2
3 X
1
+ 2X
2
+ X
5
= 3
X1 X2 X3 X4 X5 Solucin
Z -2 -1 0 0 0 0
X3 -3 -1 1 0 0 -3
X4 -4 -3 0 1 0 -6 Dividir entre -3
X5 1 2 0 0 1 3
Para hallar el pivote, se trabaja con la columna de solucin:
a) Se busca el nmero ms negativo (-6).
b) Entre todos los valores asociados (2/-4 y 1/-3) se busca el valor mnimo.
Luego se trabaja el smplex normal.
X1 X2 X3 X4 X5 Solucin
Z -2/3 0 0 -1/3 0 2
X3 -5/3 0 1 -1/3 0 -1 Dividir entre 5/3
X2 4/3 1 0 -1/3 0 2 (1) (1) (-2)
X5 -5/3 0 0 2/3 1 -1
Nota: Los empates se rompen arbitrariamente.
X1 X2 X3 X4 X5 Solucin
Z 0 0 -2/5 -1/5 0 12/5
X1 1 0 -3/5 1/5 0 3/5 (2/3) (-4/3) (5/3)
X2 0 1 4/5 -3/5 0 6/5
X5 0 0 -1 1 1 0
Cuando en la columna de soluciones ya no existen nmeros negativos, entonces tenemos
la solucin final.
La respuesta al problema es Z = 12/5, X1 = 3/5 y X2 = 6/5.
IV
(La prctica tiene una duracin de 02 horas) ACTIVIDADES
01. Ingrese el problema ejemplo 1 de la presente prctica en sus dos formas (Primal y
dual) al LINDO y verifique los resultados, as como cada una de las tablas generadas.
02. Ingrese el ejemplo 2 al LINDO, verifique resultados y tablas.
03. Convierta el ejemplo 2 en Dual, luego ingrselo al LINDO y verifique cada una de
las tablas y los resultados obtenidos.
04. Resuelva el siguiente problema en forma manual (mtodo dual simplex), verifique su
resultado con el LINDO:
Min Z = 5X1 + 6X2
X1 + X2 2
4X1 + X2 4
05. Convierta los siguientes problemas en sus respectivos duales, y halle los resultados
por el LINDO. Verifique cada una de las respuestas y analice.
Max Z = 5X1 + 12X2 + 4X3 Min 15X1 + 12X2 Max Z = 3X1 + 5X2
X1 + 2X2 + X3 10 X1 + 2X2 3 X1 4
2X1 X2 + 3X3 = 8 2X1 4X2 5 2X2 12
3X1 + 2X2 18
06. Un agricultor cultiva trigo y maz en sus tierras de 45 acres. Es capaz de vender
cuando ms 140 toneladas de trigo y 120 toneladas de maz. Cada acre sembrado con
trigo rinde 5 toneladas, y cada acre sembrado con maz produce 4 toneladas. El trigo
se vende en 30 dlares la tonelada y el maz se vende en 50 dlares la tonelada. La
cosecha de un acre con trigo requiere de 6 horas de mano de obra, y la de u acre con
maz consume 10 horas. Se puede comprar hasta 350 horas de mano de obra a 10
dlares la hora. Determine la cantidad de acres de trigo y maz que debe cultivar el
agricultor con la finalidad de maximizar sus ganancias.
07. Una fbrica ha seguido constantemente una poltica de fabricacin de aquellos
productos que contribuyan con la mayor cantidad a los costos fijos y a las ganancias.
Sin embargo, siempre se ha procurado producir los requerimientos mnimos
semanales de ventas, que son los siguientes para los productos K, L, M y N:
Producto K 25 unidades
Producto L 30 unidades
Producto M 30 unidades
Producto N 25 unidades
Los requerimientos de produccin y el tiempo disponible para la semana siguiente son:
Tiempo requerido por producto Tiempo disponible
(horas) la prxima semana
K L M N (horas)
Departamento 1 0.25 0.2 0.15 0.25 400
Departamento 2 0.3 0.4 0.5 0.3 1000
Departamento 3 0.25 0.3 0.25 0.3 500
Departamento 4 0.25 0.25 0.25 0.25 500
Contribucin unitaria $10.50 $9.00 $8.00 $10.00
a) Obtenga el modelo matemtico Primal y muestre su solucin.
b) Formule el modelo Dual y defnase las variables respectivas.
c) Utilizando el software Lindo o WinQsb, obtenga la solucin del problema dual y
compare con la solucin del Problema Primal.
08. Una empresa manufacturera est considerando la fabricacin de una nueva lnea de
productos, compuesta por cuatro productos. Cada producto puede fabricarse con dos
mtodos diferentes y completamente distintos, uno de los cuales consta de dos
procesos y el otro de tres. Se fabricarn basndose en un segundo turno. El precio de
venta de esos productos y sus costos variables, as como las cantidades que
probablemente puedan venderse, de acuerdo con el grupo de investigaciones de
mercadotecnia, son los siguientes:
PRODUCTO
1 2 3 4
Precio de venta al mayoreo
(40% de descuento) $100 $150 $125 $140
Costos variables mtodo A 80 135 120 135
Costos variables mtodo B 110 150 100 110
Cantidad que puede venderse 1000 3000 4000 6000
La seccin de manufactura de la empresa ha determinado que los tiempos de
manufactura para cada proceso son los siguientes:
PRODUCTO
1 2 3 4
Mtodo A
Dpto. 20 3.0 3.6 2.0 3.5
Dpto. 21 9.0 10.0 8.0 9.0
Dpto. 22 1.0 1.0 0.5 0.5
Mtodo B
Dpto. 31 4.0 4.0 2.0 4.0
Dpto. 32 5.0 8.0 4.0 3.0
Horas disponibles al mes:
Departamento 20 15000
Departamento 21 50000
Departamento 22 8000
Departamento 31 10000
Departamento 32 10000
a) Obtenga el modelo matemtico Primal y muestre su solucin.
b) Formule el modelo Dual y defnase las variables respectivas.
c) Utilizando el software Lindo o WinQsb, obtenga la solucin del problema dual y
compare con la solucin del Problema Primal
