7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
1/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
1Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
SEMANA 07
EL PROBLEMA PRIMALDUAL
SOLUCIN GRFICA
I .- Problema Primal y Dual en la Programacin Lineal
Cada problema original de Maximizacin (llamado PRIMAL), tiene asociado un segundo
problema de minimizacin (llamado DUAL); de manera similar cada problema original de
Minimizacin (llamado DUAL), tiene su correspondiente problema PRIMAL. Estos dos
problemas PRIMAL DUAL estn estrictamente relacionados de tal manera que la
solucin optima de uno de ellos proporciona informacin completa para la solucin del otro
problema asociado, esta relacin completa se ve claramente en la solucin por l mtodo
simplex, ms no con la solucin grfica (donde solo se ve la coincidencia en l valor de la
funcin objetivo en ambos problemas.
1.- Definicin del Problema DualLa definicin del problema dual esta sujeto a la presentacin del problema primal.
A. El problema Dual cuando el Primal esta en
presentacin CannicaEn general : MODELO PRIMAL
Max : Xo =
n
j
CjXj
1
n
j
aijXi1
bi
Xj 0
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
2/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
2Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Donde :
i = 1, 2, . . ., m variables
j = 1, 2, . . ., n variables
X j : Variables de decisin primales ( j = 1,2, . . ., n), ( n variables de decisin)
C j : Valor por unidad de actividad j.
bi : Cantidad disponible del recurso i ( i = 1, 2, . . . , m) ( m restricciones).
a ij : Cantidad de recurso que debe asignarse a cada unidad de actividad j.
Caractersticas de la forma cannica
1. Todas las variables son no negativas.
2.
Todas las restricciones son del tipo ( o =).3.
La funcin objetivo es del tipo de Maximizacin.
Nota : Cualquier problema de programacin lineal puede llevarse a su presentacin
cannica.
Proceso de Cambio para Generar el Modelo Dual a
partir del Modelo Primal en su forma Cannica
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
3/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
3Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
MODELO PRIMAL:
Max : Z0 = 8X1 + 6X2
s.a.
4X1 + 2X2 60 (horas Mquina 1, en ensamble) Y12X1 + 4X2 48 (48 (horas Mquina 2, en acabado) Y2
X1, X2 0
Solucin ptima al Modelo Primal
1.
Si resolvemos por el mtodo grfico o por el mtodo Simplex, la solucin sera:
X1 = 12 (fabricar y vender 12 unidades de este tipo de producto)
X2 = 6 (fabricar y vender 6 unidades de este tipo de producto)
Zo = S/. 132 nuevos soles (Utilidad mxima)
Cuadro de solucin ptima Primal
VB
X1 X2 S1 S2 Solucin
LD Bi/aij>0Cj 8 6 0 0
X1 8 1 0 1/3 -1/6 12
X2 6 0 1 -1/6 1/3 6
Zj 8 6 5/3 2/3 132Cj-Zj 0 0 -5/3 -2/3
2. Una alternativa sera: Si tengo 60 horas Mq1 en ensamble y 48 horas Mq2 en
acabado (son mis recursos limitados) los cuales en mi proceso productivo los
estoy utilizando para fabricar productos tipo X1 y X2, y segn la solucin estoy
logrando una utilidad de S/. 132, entonces mi inters es saber:
a)
Econmicamente cuanto representa las 60 horas mq1 en ensamble; para estoimplemento una variable econmica Y1 que sera el costo de 1 hora en
ensamble; por lo tanto si tengo 60 horas de Mq1, mi costo total por las 60
horas ser: 60*Y1, asimismo, econmicamente cuanto representa las 48
horas de mq2 en acabado; para esto implemento otra variable econmica Y2
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
4/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
4Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
que sera el costo de 1 hora en acabado; por lo tanto si tengo 48 horas de
Mq2, mi costo total por las 48 horas ser: 48*Y1; por lo tanto, mi costo total
en ensamble y acabado sera 60Y1 + 48Y2. De esta manera tengo mi
funcin objetivo del modelo Dual, que sera Min Yo = 60Y1 + 48Y2.
b) Ahora veamos cmo se generan las restricciones Duales. Analicemos la
primera variable primal X1. Para fabricar una unidad de este tipo de
producto se requiere o se consume 4 horas en ensamble, costeando estas 4
horas sera 4*Y1 (por qu Y1 es el costo por hora en ensamble); pero esa
misma unidad tambin requiere 2 horas en acabado, costeando estas 2 horas
sera 2*Y2; ahora veamos, si produzco una unidad del tipo X1 mi utilidad o
contribucin que obtengo es de S/. 8 nuevos soles; por lo tanto, si mi costototal para fabricar una unidad de X1 es 4Y1 + 2Y2 por lo tanto mi
contribucin debe ser por lo menos S/. 8 nuevos soles, de esta manera, se
sustenta que esta primera variable primal X1 genera la primera restriccin
Dual la que sera: 4Y1 + 2Y2 8.
Del mismo modo, analicemos la segunda variable primal X2. Para fabricar
una unidad de este tipo de producto se requiere o se consume 2 horas en
ensamble, costeando estas 2 horas sera 2*Y1 (por qu Y1 es el costo por
hora en ensamble); pero esa misma unidad tambin requiere 4 horas en
acabado, costeando estas 4 horas sera 4*Y2; ahora veamos, si produzco una
unidad del tipo X2 mi utilidad o contribucin que obtengo es de S/. 6 nuevos
soles; por lo tanto, si mi costo total para fabricar una unidad de X1 es 2Y1 +
4Y2 por lo tanto mi contribucin debe ser por lo menos S/. 6 nuevos soles,
de esta manera, se sustenta que esta segunda variable primal X2 genera la
segunda restriccin Dual la que sera: 2Y1 + 4Y2 6.
3. De esta manera, si se tiene ms recursos (bi) el anlisis es semejante, para
generar tanto la funcin objetivo Dual como sus correspondientes restricciones
Duales; por lo tanto, para este caso el modelo Dual es:
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
5/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
5Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
MODELO DUAL
Min : Y0 = 60Y1 + 48Y2
s.a.
4Y1 + 2Y2 8
2Y1 + 4Y2 6
Y1, Y2 0
NOTA: RESOLVER EL MODELO GRFICAMENTE
Nota: este modelo dual lo podemos resolver por el mtodo grfico o por elmtodo simplex, y la solucin sera
Yo = S/. 132 nuevos soles
Y1 = S/. 5/3 o S/. 1.666667 de nuevos soles
Y2 = S/. 2/3 o S/. 0.666667 de nuevos soles
4. Solucin Dual a partir de la Solucin Primal. El mtodo grfico de la solucin
primal, solamente me brinda la solucin dual de la funcin objetivo, o sea Zo =
Yo = S/. 132, ms no los valores de Y1 y de Y2; pero si resuelvo el modelo
primal por el mtodo simplex, si me da la solucin completa del modelo Dual;
pero solamente si se tiene la iteracin optima primal, veamos cmo lograr esto:
Cuadro de solucin ptima Primal
VB
X1 X2 S1 S2 Solucin
LD Bi/aij>0Cj 8 6 0 0
X1 8 1 0 1/3 -1/6 12
X2 6 0 1 -1/6 1/3 6
Zj 8 6 5/3 2/3 132
Cj-Zj 0 0 -5/3 -2/3
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
6/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
6Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Como la primera restriccin 4X1 + 2X2 60, o variable bsica inicial o ecuacin
S1 genera la 1era Variable dual Y1, entonces bajo esta variable S1 en Cj Zj se
obtiene el valor de Y1 cmo? Cambiando de signo ese valor y sumndole su Cj
correspondiente., as:
Y1 = 5/3 + 0 = S/. 5/3 o 1 = 1.66667 + 0 = S/. 1.66667
Como la segunda restriccin 2X1 + 4X2 48, o variable bsica inicial o
ecuacin S2 genera la 2da Variable dual Y2, entonces bajo esta variable S2 en Cj
Zj se obtiene el valor de Y2 cmo? Cambiando de signo ese valor y sumndole suCj correspondiente., as:
Y2 = 2/3 + 0 = S/. 2/3 Y2 = 0.66667 + 0 = S/. 0.66667
Por lo tanto la solucin al modelo Dual a partir de la solucin Primal sera:
Y1 = S/. 1.666667
Y2 = S/. 0.666667
Yo = S/. 132
Iteracin ptima Dual
VB
Y1 Y2 S1 S2 A1 A2 Solucin
LDCj 60 48 0 0 M M
Y1 60 1 0 -1/3 1/6 1/3 -1/6 5/3
Y2 48 0 1 1/6 -1/3 -1/6 1/3 2/3
Zj 60 48 -12 -6 12 6 132
Cj-Zj 0 0 12 6 -12+M -6+M
Respuestapara obtener una contribucin mnima de S/. 132 nuevos soles por mis
recursos de 60 horas mq1 en ensamble y de 48 horas mq2 en acabado, mis costos
son de S/. 1.666667 nuevos soles por hora en ensamble y de S/. 0.666667 nuevos
soles por hora en acabado.
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
7/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
7Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
5.
Asimismo, si se resuelve el modelo Dual, a partir de la solucin del modelo
dual, tambin se puede dar la solucin directa al modelo primal, en el supuesto
caso que no hayamos resuelto el modelo primal, el procedimiento es semejante;
veamos, esto:
MODELO DUAL
Min : Y0 = 60Y1 + 48Y2
s.a.
4Y1 + 2Y2 8
2Y1 + 4Y2 6
Y1, Y2 0
6. El mtodo grfico de la solucin dual, solamente me brinda la solucin primal
de la funcin objetivo, o sea Yo = Zo = S/. 132, ms no los valores de X1 y de
X2; pero si resuelvo el modelo dual por el mtodo simplex, si me da la solucin
completa del modelo Primal; pero solamente si se tiene la iteracin optima dual,
veamos cmo lograr esto:
Cuadro de solucin ptima Dual
VB
Y1 Y2 S1 S2 A1 A2 Solucin
LDCj 60 48 0 0 M M
Y1 60 1 0 -1/3 1/6 1/3 -1/6 5/3
Y2 48 0 1 1/6 -1/3 -1/6 1/3 2/3
Zj 60 48 -12 -6 12 6 132
Cj-Zj 0 0 12 6 -12+M -6+M
Como la primera restriccin 4Y1 + 2Y2 8, ovariable bsica inicial o ecuacin
A1 genera la 1era Variable primal X1, entonces, en la iteracin optima bajo esta
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
8/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
8Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
variable A1 en Cj Zj se obtiene el valor de X1 cmo? Cambiando de signo ese
valor y sumndole su Cj correspondiente., as:
X1 = - M + 12 + M = 12 unidades del producto tipo X1
Como la segunda restriccin 2Y1 + 4Y2 6, o variable bsica inicial o ecuacin
A2 genera la 2da Variable primal X2, entonces bajo esta variable A2 en Cj Zj se
obtiene el valor de X2 cmo? Cambiando de signo ese valor y sumndole su Cj
correspondiente., as:
X2 = - M + 6 + M = 6 unidades del producto tipo X2
Por lo tanto la solucin al modelo Primal a partir de la solucin del modelo Dual
sera:
Zo = S/. 132 nuevos solesX1 = 12 unidades del producto terminado tipo X1 o como se haya definido esta
variable.
X2 = 6 unidades del producto terminado tipo X2 o como se haya definido esta
variable.
Respuestapara obtener una contribucin o utilidad mxima de S/. 132 nuevos soles
se debe fabricar y vender 12 unidades del producto tipo X1 y 6 unidades del
producto tipo X2.
PROCESO PARA CONSTRUIR EL MODELO DUAL A PARTIR DEL
MODELO PRIMAL Y VICEVERSA
1. Si la funcion objetivo del primer modelo (primal) busca maximizar, entonces, la
funcion objetivo del modelo dual buscara minimizar. Antes de comenzar a construir
el otro modelo, se debe tener en cuenta lo siguiente: Si el problema es de
maximizacion, entonces todas sus restricciones deben ser del tipo y si el modelo
es de minimizacion todas las restricciones deben ser del tipo , si en algn caso no
se cumple este requisito, hacer lo necesario para cumplir con este requisito.
ejemplo 01
Max : Zo = 12 X 1+ 14 X 2
s.a.
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
9/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
9Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
1X 1+ 3 X 2 130
3X 1+ 2 X 2 45 esta restriccin no cumple el requisito
1X 1+ 2 X 2 85
X 1, X 2 0
Hacemos lo necesario para que la segunda restriccin cumpla el requisito
Max : Zo = 12 X 1+ 14 X 2
s.a.
1X 1+ 3 X 2 130
-3X 1- 2 X 2 - 45 ahora esta restriccin si cumple el requisito
1X 1+ 2 X 2 85
X 1, X 2 0
Ejemplo 02
Min : Zo = 10X 1+ 7 X 2
s.a.
2X 1+ 1 X 2 160 esta restriccin no cumple con el requisito
1X 1+ 3 X 2 140
2X 1+ 2 X 2 125
X 1, X 2 0
Hacemos lo necesario para que la segunda restriccin cumpla el requisito
Min : Zo = 10X 1+ 7 X 2
s.a.
-2X 1- 1 X 2 -160 ahora si esta restriccin cumple con el requisito
1X 1+ 3 X 2 140
2X 1+ 2 X 2 125
X 1, X 2 0
2. Cada restriccion primal determina una variable dual, entonces m restricciones
primales generan m variables duales (Yi : i = 1, 2, . . . , m) cuyos coeficientes para
dichas variables duales Yi son sus corrrespondientes biprimales.
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
10/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
10Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Asociando 1 y 2 tenemos la funcion objetivo dual.
3.
El numero de variables primales determinan el numero de restricciones duales,
entonces n variables primales i ( i = 1, 2, . . . , n), establece n restricciones duales
donde las Cj primales se constituyen en elementos del lado derecho para las
restricciones duales.
4. Tanto las variables primales como las duales son no negativas.
En general: MODELO PRIMAL EN SU FORMA CANONICA
Max : Xo =
n
j
CjXj1
n
j
aijXi1
bi
Xj 0
En general su MODELO DUAL :
Min : Yo =
m
i
biYi
1
m
i
aijYi1
Cj
Donde : Yi 0
i = 1, 2, . . ., m variables
j = 1, 2, . . ., n variables
Observacin: Cmo la dificultad en la solucin de un problema lineal depende del numero
de restricciones y no del numero de variables, entonces en este caso la recomendacin sera
resolver el problema dual.
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
11/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
11Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
B. El Problema Dual cuando el primal esta en su
presentacin estndar
-
En la forma estndar la funcin objetivo puede ser de maximizacin o deminimizacin.
- Todas las variables son no negativas.
-
Los elementos del lado derecho son todos mayores o iguales a cero.
- Todas las restricciones son ecuaciones.
PRIMAL
Max : Xo =
n
jCjXj
1
n
j
aijXi1
= bi
Xj 0
Proceso de Cambio para Generar el Modelo Dual a
partir del Modelo Primal en su forma Estndar
DUAL :
Min : Yo =
m
i
biYi1
m
i
aijYi1
Cj
Yi es irrestricta en signoEntonces Yi puede tomar valores positivos , negativo o ceros
Yi = Yi+ - Yi- (se lee Yi = Yi ms, MENOS, Yi menos)
Despus del cambio correspondiente, el modelo quedara
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
12/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
12Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
MODELO DUAL :
Nota : A PARTIR DE AQU SE PUEDE COMBINAR LAS DOS FORMAS
(CANNICA Y ESTNDAR), PARA QUE UN MODELO LLAMADO
PRIMAL SI ES DE MAXIMIZACIN DESPUES DE CUMPLIR EL
REQUISITO PUEDA TENER RESTRICCIONES DEL TIPO , = Y UN
MODELO LLAMADO DUAL SI ES DE MINIMIZACIN PUEDA
TENER RESTRICCIONE DEL TIPO , =.APLICAR LAS SIGUIENTESRECOMENDACIONES PARA PASAR DE UN MODELO (PRIMAL O
DUAL) A SU OTRO MODELO (DUAL O PRIMAL):
1. El proceso de cambio es semejante al anterior excepto que para toda
restriccin de igualdad (ecuacin) en el primal original genera una variable
dual que es irrestricta en el signo ( que puede ser positivo, negativo o
cero).
2.
En el proceso inverso a una variable irrestricta en el dual le corresponde
una restriccin de igualdad (ecuacin).
Proceso de Cambio de Primal al Dual para Diferentes tipos de Desigualdades
Ejemplo: Dado el modelo Primal construir su modelo Dual
Modelo Primal (Original)
Max : Zo = 22 X1 + 28 X2
s.a.
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
13/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
13Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
3 X1- 4 X2 18
X1- 2 X2 = 10
2 X1+ X2 12
X1 : irrestricta en el signo
X2 0
Analicemos el modelo Primal:
1. El modelo es de maximizacin entonces en este caso todas sus restricciones deben
se del tipo (cumple la 1era y 3era restriccin, por lo tanto la primera restriccin o
ecuacin S1 genera la 1era variable dual Y1 la que ser 0, la tercera restriccin o
ecuacin S3 genera la 3era variable dual Y3 la que ser 0 ), inclusive tener
restricciones del tipo de ecuacin (cumple la 2da restriccin, en este caso la 2da
restriccin o ecuacin A2 genera la 2da variable dual Y2 la que ser irrestricta en
signo).
2. Ahora analicemos las variables del modelo primal, nos dicen que la variable X1es
irrestricta en signo, por lo tanto como esta variable X1 del modelo primal genera la
primera restriccin del modelo dual, entonces esta restriccin ser del tipo de
ecuacin en el modelo dual. en cambio, la variable X2 del modelo primal genera la
segunda restriccin del modelo dual, esta restriccin debe ser del tipo .
Modelo Primal
Max : Zo = 22 X1 + 28 X2
s.a.
3 X1- 4 X2 18 Y1(sta primera restriccin o ecuacin S1(VBI) genera Y1)X1- 2 X2 = 10Y2 ( o ecuacin A2 (VBI)genera Y2, la que ser irrestricta en signo)
2 X1+ X2 12 Y3 (sta tercera restriccin o ecuacin S3(VBI)genera Y3
X1 : irrestricta en el signo (Esta variable X1 que genera la 1era restriccin en el
modelo Dual, entonces esa primera restriccin ser del tipo de ecuacin)
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
14/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
14Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
X2 0
VBI = Variable Bsica en la solucin inicial
Con las indicaciones dadas el Modelo Dual quedara, as:
Modelo Dual
Min : Yo = 18 Y1 + 10 Y2 + 12 Y3
s.a.
3 Y1 + 1 Y2 + 2 Y3 = 22
-4 Y1 -2 Y2 + 1 Y3 28
Y1, Y3 0
Y2 : irrestricta en el signo.
Este modelo debemos concluirlo reemplazando Y2 = Y2+- Y2-
Min : Yo = 18 Y1 + 10 Y2+ - 10 Y2- + 12 Y3
s.a.
3 Y1 + 1 Y2+- 1Y2- + 2 Y3 = 22
-4 Y1 -2 Y2++ 2Y2-
+ 1 Y3 28
Y1, Y2+ , Y2-,Y3 0
y su forma estndar sera:
Min : Yo = 18 Y1 + 10 Y2+ -10 Y2- + 12 Y3 + 0S2 + MA1 + MA2
s.a.
3 Y1 + 1 Y2+- 1Y2- + 2 Y3 + A1 = 22
-4 Y1 -2 Y2++ 2Y2- + 1 Y3S2 + A2 28
Y1, Y2+ , Y2-,Y3, S2, A1, A2 0
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
15/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
15Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
TRABAJO DE ASIGNACIN INDIVIDUAL DE
PRCTICA, TRABAJAR EN FRACCIONES.
NOTA: Desarrollar segn se pide en suCUADERNO PARA ser presentado el da 14.10.15
asimismo, en archivo Word.
Dado el siguiente modelo Primal
Modelo Primal (Original)Max : Zo = 44 X1 + 56 X2
s.a.
6 X1- 8 X2 36
2 X1- 4 X2 = 20
4 X1+ 2 X2 24
X1 : irrestricta en el signo
X2
01. Resolver este modelo primal y a partir de dicha solucin primal dar la solucin al
modelo dual
2. Resolver el modelo dual y a partir de dicha solucin dual dar la solucin al modelo
primal
Indicaciones para resolver la prctica y dar Solucin a lo que se pide:
1. El modelo es de maximizacin y cumple los requisitos, lo nico que debemos
tener en cuenta es la variable X1 que es irrestricta en signo.
Su forma estndar del modelo Primal sera:
Max : Zo = 44 X1+ - 44X1- + 56 X2 + 0S1 - MA2 + 0S3
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
16/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
16Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
s.a.
6 X1+ - 6X1- - 8 X2 + 1 S1 = 36
2 X1+ - 2X1- - 4 X2 + 1 A2 = 20
4 X1+ - 4X1- + 2 X2 + 1 S3 = 24
X1+, X1- , X2, S1, A2, S3 0
Ahora si el modelo est listo para aplicar el mtodo simplex el que deben
resolverlo en primer lugar en manuscrito en cuaderno y en la iteracin
ptima de la solucin primal se dar la solucin al modelo dual, y en
segundo lugar utilizando un software resolver este modelo para verificar la
solucin manual.
2. Para el punto 2 debemos construir el modelo dual a partir del modelo primal
Modelo Primal
Max : Zo = 44 X1 + 56 X2
s.a.
6 X1- 8 X2 36
2 X1- 4 X2 = 20
4 X1+ 2 X2 24X1 : irrestricta en el signo
X2 0
Este modelo cumple los requisitos por lo tanto hacemos la construccin del
modelo dual
El Modelo Dual ser:
Min : Yo = 36 Y1 + 20 Y2 + 24 Y3
s.a.6 Y1 + 2 Y2 + 4 Y3 = 44
- 8 Y1 - 4 Y2 + 2 Y3 56
Y1, Y3 0
Y2 : irrestricta en el signo.
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
17/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
17Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Como Y2 es irrestricta para aplicar el simplex tenemos que tener todas las
variables 0
Para esto se debe hace la forma estndar, reemplazando Y2 = Y2 +- Y2-
Min : Yo = 36 Y1 + 20 Y2+ - 20 Y2- + 24 Y3 + 0S2 + MA1 + MA2
s.a.
6 Y1 + 2 Y2+- 2Y2- + 4 Y3 + A1 = 44
- 8 Y1 - 4 Y2++ 4Y2-
+ 2 Y3 S2 + A2 56
Y1, Y2+, Y2-, Y3, S2, A1, A2 0
Ahora si el modelo est listo para aplicar el mtodo simplex el que deben
resolverlo en primer lugar en manuscrito en cuaderno y en la iteracin
ptima de la solucin dual se dar la solucin al modelo primal, y en
segundo lugar utilizando un software resolver este modelo para verificar la
solucin manual.
C.
Relacin entre los valores de la funcin objetivo del primaly del dual
Propiedad : Si los dos problemas tienen soluciones optimas finitas, entonces los
valores de Z0y Yo en funcin objetivo son iguales.
Esta propiedad indica que para dos soluciones factibles, el valor de Yo (en el
modelo de minimizacin acta como una cota superior para el valor de Z0 (en el
problema de maximizacin).
APLICACIN DEL PROBLEMA PRIMAL - DUALDado el esquema de un sistema productivo donde se procesan 3 tipos de productos,
componente 1, componente 2 y componente 3; pasan por tres departamentos ensamble,
acabado y empaque. Los requerimientos en horas por unidad de tipo de componente, la
utilidad por componente, la disponibilidad del numero de horas en cada departamento se
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
18/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
18Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
dan en el esquema, con esta informacin se pide: Confeccionar el modelo primal y hallar la
solucin, y a partir de la solucin al modelo primal dar la solucin al modelo dual.
Solucin
Definicin de Variables de decisin:
X1 : Nde componentes (C 1) a fabricar y vender
X2 : Nde componentes (C 2) a fabricar y vender
X3 : Nde componentes (C 3) a fabricar y vender
Modelo Primal: Modelo original
Max : Zo = 2 X 1+ 4 X 2+ 3 X 3
s.a.
3X 1+ 4 X 2+ 2 X 3 60
2X 1+ 1 X 2+ 2 X 3 40
1X 1+ 3 X 2+ 2 X 3 80
X 1, X 2, X 3 0
Resolver EN CUADERNO DE MANERA PERSONAL los siguientes modelos y comparar
las soluciones (en cada cambio regresara al modelo original)
a) C1 varia de 2 a 4
b) B1 varia de 60 a 63 horas
C1
3
4
2
2
1
2
4
3
60 40
1
3
2
80
EmpaqueEnsamble
$ 2
Utilid./unid.Acabado
C2
C3
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
19/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
19Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
c)
B2 varia de 40 a 38
d)
B3 varia de 80 a 78 horas
TODAS ESTAS SOLUCIONES MAS LAS DOS SOLUCIONES ANTERIORES
HACERLO EN PAPEL OCFICIO CUADRICULADO A MANUSCRITO TINTA
AZUL O NEGRO PRESENTARLO EL PROXIMO MIERCOLES 29 DE
OCTUBRE DE 2014 EN CLASE.
Solucin ptima Primal
Solucin Dual a partir de la solucin optima Primal
Para esto construimos el modelo Dual
Min : Yo = 60Y 1+ 40Y2+ 80Y3
s.a.
3Y 1+ 2Y 2+ 1Y 3 24Y 1+ 1 Y 2+ 3Y 3 4
2Y 1+ 2Y 2+ 2 Y 3 3
Y1, Y2, Y3 0
V . B . Cj X1 X2 X3 S1 S2 S3 Bi
2 4 3 0 0 0
X2
X3
S3
ZjCj- Zj
4
3
0
1/3 1 0 1/3 -1/3 0
5/6 0 1 -1/6 2/3 0
-5/3 0 0 -2/3 -1/3 1
23/6 4 3 5/6 2/3 0-11/6 0 0 -5/6 -2/3 0
20/3
50/3
80/3
230/3
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
20/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
20Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Como se dijo, la solucin al modelo dual, solamente se d en la solucin ptima primal, o
viceversa. En este caso: Bajo las V.B.I. (variables bsicas iniciales) en Cj - Zj en forma
secuencial se obtienen los valores para las variables duales.
S1 S2 S3
Cj 0 0 0
Cj- Zj - 5/6 - 2/3 0
Variables Duales Y1 Y2 Y3
S1: Llamado tambin ecuacin S1 en la forma estndar del primal, genera la primera
variable dual Y1, cuyo valor se encuentra cambiando el signo a su valor correspondiente en
Cj - Zj (-5/6 al cambiar de signo se convierte en 5/6) y sumndole su coeficiente respectivoCjde S1 (Cj = 0), as se procede para el resto de las variables duales.
Y1 = 5/6 + 0 = $ 5/6 (Trabajamos con la columna de S1)
Y2 = 2/3 + 0 = $ 2/3 (Trabajamos con la columna de S2)
Y3 = 0 + 0 = $ 0 (Trabajamos con la columna de S3)
Yo = $ 230/3
Verificacin del valor de Yo
El valor de la funcin objetivo dual es igual al valor de la funcin objetivo primal
Min : Yo = 60 Y1 + 40 Y2 + 80 Y3
Min : Yo = 60 ( $ 5/6) + 40 ($ 2/3) + 80 ($ 0) = $ 230/3
Interpretacin Econmica de la Dualidad
1. Una alternativa a la solucin primal, es no utilizar los recursos (horas
disponibles en cada departamento) para producir los componentes C1, C2 y C3;
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
21/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
21Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
si no por ejemplo alquilar estos recursos a una tercera persona, para que esta los
utilice de acuerdo a su conveniencia.
Para que el dueo de los recursos, alquilar estos recursos en vez de Producir, la
retribucin por el alquiler de estos recursos deben sumar cuanto menos tantocomo se puede obtener produciendo.
Esto se demuestra a travs de las funciones objetivos, as:
Valor de la funcin objetivo primal Valor de la funcin objetivo dual
2 X1 + 4 X2 + 3 X3 60 Y1 + 40 Y2 + 80 Y3
2( 0) + 4 ( 20/3) + 3 ( 50/3) 60 ( 5/6) + 40 ( 2/3) + 80 (0)
Valor de Zo = $ 230/3 Valor de Yo = $ 230/3
2. Si el modelo primal tiene solucin, entonces, tambin la tendr el dual y sus
valores en la solucin ptima sern iguales en la funcin objetivo. Esto quiere
decir que, el valor de todos los recursos productivos es igual a la utilidad que
obtendra la empresa o sistema productivo si los recursos son empleados en
forma eficiente.
3.
Ahora, analicemos los valores de las variables duales:
Y1 = $ 5/6 de dolarEsta variable dual es generada por la primera restriccin primal
3X 1+ 4 X 2+ 2 X 3 60
Conocemos que en la solucin ptima primal
X1 = 0 unidades del componente C1
X2 = 20/3 de unidades del componente C2
X3 = 50/3 de unidades del componente C3
Por lo tanto en la forma estndar esta restriccin ser:
3X 1+ 4 X 2+ 2 X 3 + S1 = 60 horas
Reemplazando los de las variables de decisin, tendramos:
3*(0) + 4*(20/3) + 2*(50/3) + S1 = 60
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
22/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
22Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
por lo tanto S1 = 0 eso significa que se ha consumido las 60 horas en
ensamble; es por esta razn que no aparece S1 en la iteracin ptima.
Por lo tanto, si el dueo de los recursos, por x motivos desea incrementar por
ejemplo una hora adicional en ensamble (por que con la produccin que tiene a
consumido las 60 horas y ya no tiene ninguna hora sobrante en ensamble), debe
invertir $ 5/6 de dlar, esto econmicamente se interpreta de la siguiente
manera Y1 = $ 5/6 de dlar, conocido como precio sombra de Y1, es la
cantidad mxima que estara dispuesto a invertir por una hora adicional en
ensamble. Lo interesante de este asunto es que, si resuelve el nuevo modelo
variando las horas de ensamble de 60 a 61 horas y el resto de datos permanecen
igual. Los nicos valores que cambian son de las variables bsicas y el valor dela funcin objetivo se incrementa en 1*$Y1, o sea el nuevo Zo = $ 230/3 + $
5/6.
Un siguiente ejemplo para aclarar mejor esto: Si deseamos incrementar 5 horas
en ensamble y se resuelve el nuevo modelo variando las horas de ensamble de
60 a 65 horas y el resto de datos permanecen igual. Los nicos valores que
cambian son de las variables bsicas y el valor de la funcin objetivo se
incrementa en 5*$Y1, o sea el nuevo Zo = $ 230/3 + 5*$ 5/6.
Un siguiente ejemplo aclarara ms an sta situacin: Si deseamos reducir
nuestra produccin, entonces debo reducir las hora en ensamble, supongamos el
nmero de horas en ensamble se reducen de 60 a 57 horas y se resuelve el
nuevo modelo variando las horas de ensamble de 60 a 57 horas y el resto de
datos permanecen igual. Los nicos valores que cambian son de las variables
bsicas y el valor de la funcin objetivo se reduce en 3*$Y1, o sea el nuevo Zo
= $ 230/3 - 3*$ 5/6.
Nota: Esto funciona as, para cualquier recurso
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
23/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
23Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Y2 = $ 2/3 de dolar
Esta variable dual es generada por la segunda restriccin primal
2X 1+ 1 X 2+ 2 X 3 40
Conocemos que en la solucin ptima primalX1 = 0 unidades del componente C1
X2 = 20/3 de unidades del componente C2
X3 = 50/3 de unidades del componente C3
Por lo tanto en la forma estndar esta restriccin ser:
2X 1+ 1 X 2+ 2 X 3 + S2 = 40 horas
Reemplazando los de las variables de decisin, tendramos:
2*(0) + 1*(20/3) + 2*(50/3) + S2 = 40
por lo tanto S2 = 0 eso significa que se ha consumido las 40 horas en acabado;
es por esta razn que no aparece S2 en la iteracin ptima.
Por lo tanto, volviendo al modelo original sin variar nada, si el dueo de los
recursos, por x motivos desea incrementar por ejemplo dos horas adicionales en
acabado (por que con la produccin que tiene a consumido las 40 horas y ya no
tiene ninguna hora sobrante en acabado), debe invertir $ 2/3 de dlar, esto
econmicamente se interpreta de la siguiente manera Y2 = $ 2/3 de dlar,conocido como precio sombra de Y2, es la cantidad mxima que estara
dispuesto a invertir por una hora adicional en acabado. Lo interesante de este
asunto es que, si resuelve el nuevo modelo variando las horas de acabado de 40
a 42 horas y el resto de datos del modelo permanecen igual. Los nicos valores
que cambian son de las variables bsicas y el valor de la funcin objetivo se
incrementa en 2*$Y2, o sea el nuevo Zo = $ 230/3 + 2*$ 2/3.
Un siguiente ejemplo aclarara ms an sta situacin, volviendo al modelo
original sin variar nada: Si deseamos reducir nuestra produccin, entonces debo
reducir las hora en acabado, supongamos el nmero de horas en acabado se
reducen de 40 a 36 horas y se resuelve el nuevo modelo variando solamente las
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
24/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
24Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
horas de acabado de 40 a 36 horas y el resto de datos permanecen igual. Los
nicos valores que cambian son de las variables bsicas y el valor de la funcin
objetivo se reduce en 4*$Y2, o sea el nuevo Zo = $ 230/3 - 4*$ 2/3.
Nota: Esto funciona as, para cualquier recurso, teniendo en cuenta que en
cada anlisis de sensibilidad como se llama se vuelve al modelo original y
solamente se cambia un solo valor de inters el resto de valores
permanecen iguales.
Y3= $ 0 de dolar
Esta variable dual es generada por la tercera restriccin primal
1X 1+ 3 X 2+ 2 X 3 80
Conocemos que en la solucin ptima primal
X1 = 0 unidades del componente C1
X2 = 20/3 de unidades del componente C2
X3 = 50/3 de unidades del componente C3
Por lo tanto en la forma estndar esta restriccin ser:
1X 1+ 3 X 2+ 2 X 3 + S3 = 80 horas
Reemplazando los de las variables de decisin, tendramos:1*(0) + 3*(20/3) + 2*(50/3) + S3 = 80
Por lo tanto S3 = 80/3 eso significa que NOse ha consumido las 80 horas en
EMPAQUE; es por esta razn que SIaparece S3 en la iteracin ptima, con un
valor de 80/3 de horas sobrantes.
4. Por lo tanto, volviendo al modelo original sin variar nada, si el dueo de los
recursos, por x motivos desea incrementar por ejemplo cinco horas adicionalesen empaque (pero con la produccin que tiene no ha consumido las 80 horas ya
que tiene 80/3 de horas adicionales en empaque), por lo tanto como tiene horas
sobrantes en empaque su inversin es $ 0 de dlar, esto econmicamente se
interpreta de la siguiente manera Y3 = $ 0 de dlar, conocido como precio
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
25/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
25Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
sombra de Y3, significa que no todo el tiempo un empaque fue utilizado. Se
tiene tiempo de empaque en exceso, este tiempo adicional no se puede utilizar
en forma rentable, por lo tanto carece de valor. Esta caracterstica se identifica
como la primera mitad del PRINCIPIO DE LA HOLGURA
COMPLEMENTARIA.
Volviendo al incremento de 5 horas adicionales en empaque, si resuelve el
nuevo modelo variando solamente las horas de empaque de 80 a 85 horas y el
resto de datos del modelo permanecen igual, el nico valor que cambian es el de
S3 de 80/3 a 80/3 de horas + 5 horas, por lo tanto S3 en la nueva solucin ser
95/3 de horas, y el valor de la funcin objetivo permanece igual Zo = $ 230/3
5. Ahora analicemos la variable de decisin X1 que queda fuera de
la solucin ptima: En la solucin primal no recomienda producir
componente C1 (X1 = 0 es una variable de decisin no bsica), esta variable
primal genera la restriccin dual 3Y1 + 2 Y2 + Y3 2, la parte izquierda
representa el valor econmico del tiempo (cantidad de horas en ensamble,
acabado y empaque) que se necesita para producir una unidad del componente
C1 reemplazando Y1 = $ 5/6, Y2 = $ 2/3, Y3 = $ 0, en la parte izquierda nos da
$ 23/6 ($ 3.8333 dlares); pero la utilidad de una unidad del componente C1solo brinda $ 2 dlares que es una cantidad mucho menor) . Esta es la razn por
que no se produce X1, interpretndolo diremos puesto que el tiempo necesario
para producir una unidad del componente C1 vale mas que la utilidad del
componente C1, la solucin optima primal indica no producir ninguna unidad
del componente C1 para la empresa, esto es segunda mitad del PRINCIPIO DE
LA HOLGURA COMPLEMENTARIA.
D.Solucin Primal a partir de la Solucin Optima Dual
En este caso resolveramos por el mtodo simplex el modelo Dual
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
26/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
26Ing. Juan Pablo Snchez Chvez Semestre 2015 II - UNS
Modelo Dual
Min : Yo = 60 Y1 + 40 Y2 + 80 Y3
s.a.
3 Y1 + 2 Y2 + Y3 2
4 Y1 + Y2 + 3 Y3 4
2 Y1 + 2 Y2 + 2 Y3 3
Y1, Y2, Y3 0
Forma estndar del Modelo DualMin : Yo = 60 Y1 + 40 Y2 + 80 Y3 + 0S1 + 0S2 + 0S3 + MA1 + MA2 + MA3
s.a.
3 Y1 + 2 Y2 + Y3 S1 + A1 = 2
4 Y1 + Y2 + 3 Y3 S2 + A2 = 4
2 Y1 + 2 Y2 + 2 Y3 S3 + A3 = 3
Y1, Y2, Y3, S1, S2, S3, A1, A2, A3 0
A continuacin se tiene la iteracin ptima de la solucin al modelo dual
V.B. Cj Y1 Y2 Y3 S1 S2 S3 A1 A2 A3 Bi
60 40 80 0 0 0 M M M
Y1
S1
Y2
ZjCjZj
60
0
40
1 0 2/3 0 -1/3 1/6 0 1/3 -1/6
0 0 5/3 1 -1/3 -5/6 -1 1/3 5/6
0 1 1/3 0 1/3 -2/3 0 -1/3 2/3
60 40 160/3 0 -20/3 -50/3 0 20/3 50/30 0 80/3 0 20/3 50/3 M -20/3+M -50/3+M
5/6
11/6
2/3
230/3
En la iteracin optima dual los valores bajo las variables bsicas iniciales Cj Zj, nos
permiten encontrar los valores para las variables primales. Si tenemos en cuenta que A1 se
7/23/2019 Semana 07 Invope I Primal Dual 07.10.15
27/27
II UNIDAD: PROBLEMA PRIMALDUAL Investigacin de Operaciones I
27
le conoce inicialmente como ecuacin A1, entonces esta ecuacin genera la primera
variable primal X1, a A2 se le conoce inicialmente como ecuacin A2 en el dual, entonces
genera la segunda variable primal X2 y la ecuacin inicial A3 genera la variable primal X3.
El proceso es el siguiente, bajo las variables bsica iniciales (A1, A2 y A3) a los
correspondientes valores en Cj Zj se le cambia de signo y se le suma su respectivo
coeficiente.
Ejm.
VBI A1 A2 A3Sus Cj M M M
Valores en (Cj - Zj) M - 20/3 + M - 50/3 + M
Valores buscados X1= -M+M=0 X2= 20/3-M+M=20/3 X3=50/3-M+M= 50/3
Solucin directa al modelo PrimalX1 = 0 unidades a producir del componente C1
X2 = 20/3 de unidades a producir y vender del componente C2
X3 = 50/3 de unidades a producir y vender del componente C3
Verificacin del valor de la funcin objetivo primal
Max : Zo = 2 X1 + 4 X2 + 3 X3
= 2 ( 0 ) + 4 ( 20/3 ) + 3 ( 50/3 )
Zo = $ 230/3 de dlares
Respuesta:Para obtener una utilidad mxima de $ 230/3 de dlares de debe producir 20/3 de unidadesdel componente C2, 50/. de unidades del componente C3 y 0 unidades del componente C1.