MODELO DUAL
FIGMM
Introduccin
En este tema planteamos , en primer lugar la
construccin del problema dual de un problema de
programacin lineal dado, denominado primal.
En algunos casos la resolucin del problema dual
es mas sencilla que la del problema primal.
Los valores ptimos de las variables duales
proporcionan una interpretacin econmica del
problema, adems facilita el estudio del anlisis de
sensibilidad.
Introduccin
La formulacin del problema dual se lleva a cabo
aplicando ciertas reglas, que exigen que el
problema primal tenga un formato determinado.
Comenzaremos explicando como se construye el
problema dual, a partir del problema primal.
Se muestran las relaciones algebraicas entre el
problema primal y su dual.
Ejemplo
Sea el PL.(Forma cannica)
max Z = c1x1+c2x2+..............+cnxn
s.a
a11x1+a12x2+.................+a1nxn <=b1
a21x1+a22x2+.................+a2nxn <=b2
.............................................................
am1x1+am2x2+...............+amnxn <=bm
xj=>0; j=1,2,3..............,n
Ejemplo
De acuerdo a las reglas dadas del dual se tiene:
minW =b1y1+b2y2+..............+bmym
sa:
a11y1+a21y2+.........+am1ym=>c1
a12y1+a22y2+.........+am2ym=>c2
.....................................................
a1ny1+a2ny2+.........+amnym=>cn
yi =>0; i=1,2,3,............,m
Observaciones
1.
2.
3.
4.
A un problema de mnimo le corresponde un problema
de mximo(viceversa).
En un problema original de n variables y m
restricciones, su dual tendr n restricciones y m
variables.
Los coeficientes de la funcin objetivo del primal pasan
a ser los segundos miembros de las restricciones duales.
Los valores bi(2do miembro del primal) pasan a ser los
coeficientes de la funcin objetivo del problema dual.
Ejemplo
Hallar el dual del sgte. PL:
maxZ = 4x1+3x2
sa:
9x1+7x2 <=100
8x1+6x2 <=75
2x1+5x2 <=50
x1,x2=>0
Ejemplo
Aplicando las reglas se tiene:
minW = 100y1+75y2+50y3
sa:
9y1+8y2+2y3=>4
7y1+6y2+5y3=>3
y1,y2,y3=>0
Interpretacin del Dual
Se sabe que para un programa primal P, expresado en
forma cannica, existe un Programa Dual D.
La obtencin del programa dual a partir del primal, es una
operacin relativamente mecnica, por cuanto solo es
necesario seguir un procedimiento compatible con las
reglas dadas.
A continuacin nuestro objetivo es derivar un programa
dual a partir del primal correspondiente, pero no siguiendo
un procedimiento matemtico formal, sino mas bien a
travs de una discusin con sentido fsico.
Ejemplo
La compaa JR, produce radios y TV. Cada radio se vende con
una ganancia de 3000 soles, mientras que en cada TV vendido se
gana 5000 soles.
Ambos productos deben pasar por los departamentos A y
B(impresin de circuitos y ensamblaje respectivamente).
Mensualmente, se dispone de 200 y 140 horas de los Dptos A y B
respectivamente.
Adems cada radio requiere 1 hora de A y 1 hora de B, cada TV
requiere 2 horas de A y 1 hora de B.
a)Cul es el programa de produccin que maximiza la ganancia?.
b)Cual seria el costo por hora en cada departamento?
Formulacin del Primal
Sea x1 = numero de radios que se deben producir
mensualmente.
Sea x2 = numero de TV que se deben producir
mensualmente.
maxZ = 3000x1+5000x2
sa:
1x1+2x2<=200
1x1+1x2<=140
x1,x2=>0
Salida Primal
Formulacin del Dual
Sean :
y1=valor de una unidad de recurso 1(valor de una hora en
el Dpto A , $/ hora Dpto A)
y2=valor de una unidad del recurso 2(valor de una hora en
el Dpto B, $/hora Dpto B).
min W = 200y1+140y2
sa:
1y1+1y2 =>3000
2y1+1y2 =>5000
y1,y2=>0
Observacin
Del problema anterior se deduce que las
variables yi nos indican la informacin sgte:
y1=valor de una unidad de recurso 1(valor
de una hora en el Dpto A , $/ hora Dpto A)
y2=valor de una unidad del recurso 2(valor
de una hora en el Dpto B, $/hora Dpto B).
Es decir cuanto me cuesta por cada hora en
cada Dpto.
Salida Dual
Anlisis de Equivalencias
Dimensionales
X j:
Cj :
a ij:
bi :
yi :
unidad del producto
unidad monetaria/unidad de producto
unidad de recurso/unidad de producto
unidad de recurso
unidad monetaria/unidad de recurso
Relaciones Primal - Dual
El dual del programa dual es el primal
El valor objetivo de un problema de minimizacin
es >= que el valor objetivo para cualquier solucin
factible de un problema de maximizacin.
cxo >=byo, donde xo y yo son soluciones factibles
de los problemas primal y dual respectivamente
Si xo y yo son soluciones factibles de los
problemas primal y dual y son tales que :
cxo=byo, entonces xo y yo son soluciones optimas
de los respectivos problemas
Indicadores Econmicos
El Precio Dual
Representa el valor por unidad de los recursos ($/recurso)
Las variables duales yi representan el valor por unidad del
recurso i en la literatura tambin se le llama precio dual ,
precio sombra o valor marginal, nos indica:
yo=Z/ bi representa la rapidez de cambio de la
funcin objetivo del primal respecto al i esimo recurso.
yo=Z/ bi tambin variacin incremental en Z
variacin incremental en bi
Ejemplo
Sea max Z= x1+5x2
sa:
2x1+3x2<=30 -----------(1)
x2<=6-------------(2)
Sol optima del primal es x1=6, x2=6, Z=36
Verifique que en el dual la solucin es :
y1=0,5 , y2=3.5
Interpretacin
y1=0.5 indica que por incremento de 1 unidad de
recurso 1 , la ganancia se incrementa en 0.5.
Es decir si el recurso 1 cambia de 30 a 31 la nueva
solucin optima del primal es :
x1=6,5 y x2=6, Z=36.5, Z=36.5-36=0.5
y2=3.5 indica que por incremento de 1 unidad del
recurso 2, la ganancia se incrementara en 3.5.
Es decir si el recurso 2 cambia de 6 a 7 se tiene:
x1=4,5 , x2=7, Z=39.5, Z=39.5-36=3.5