Download - 06_IND2209_Alumno_15
-
7/23/2019 06_IND2209_Alumno_15
1/62
Investigacin
de
OperacionesIND2209
Profesor:Pamelalvarez M.
Facultad de Ingeniera
Departamento de Ciencias de la Ingeniera
Unidad N4
-
7/23/2019 06_IND2209_Alumno_15
2/62
IND2209.Prof.:PamelalvarezM.
Martes13deoctubre:PruebaSolemne
Contenidos:
UnidadN 3
UnidadN 4
Literaturaobligatoria:
Ttulo:IntroduccinalaInvestigacindeOperaciones. Autor:HILLIER,F.yLIBERMAN,G Captulos:4(complete,exceptApndice),5(5.1,5.2,5.3),6(completo)
Literaturacomplementaria:
Ttulo:InvestigacindeOperaciones Autor:TAHA,H. Captulos:2(2.12.22.3),3(completo),4(completo),7(7.1)
2
RECORDATORIO
-
7/23/2019 06_IND2209_Alumno_15
3/62
IND2209.Prof.:PamelalvarezM.
ElsupuestofundamentaldelosmodelosdeLPesqueunoconoceen
formaexactalosdistintosparmetrosdelproblema
Engeneral,almodelarnoseconocenlosvaloresquepuedenadoptar
losparmetros
Muchasveceslosparmetrosnosondeterminsticos,sinoque
estocsticos
Dadoesto,esimportantepodersabercuanrobustassonnuestras
solucionesfrenteaestosparmetros.
3
DUALIDAD Y ANLISIS DE SENSIBILIDAD
-
7/23/2019 06_IND2209_Alumno_15
4/62
IND2209.Prof.:PamelalvarezM.
Queremosresponderpreguntasdeltipo:
Cuntopuedecambiarunladoderechodeunarestriccinyan
mantenerlamismabaseptima?
Cuntopuedecambiarlafuncinobjetivoyanmantenerla
mismabaseptima?
Qupuedeocurrirsiagregamosunavariableluegodellegarala
solucinptima?
Cuntopagaraporunaunidadderecursoadicional?
4
DUALIDAD Y ANLISIS DE SENSIBILIDAD
-
7/23/2019 06_IND2209_Alumno_15
5/62
IND2209.Prof.:PamelalvarezM.
Definicin:
SeaunproblemadePLenlaformaestndarqueyaconocemos,
yseaBunabase
factible
delproblema.Puedeescribirselaforma
cannicadeunproblemadePLdadapor:
5
FORMA CANNICA DE UN PL
1 11 1. .
, 0
T T TB R B R
B R
B R
in c B b c c B R x
s a Ix B Rx B b
x x
-
7/23/2019 06_IND2209_Alumno_15
6/62
IND2209.Prof.:PamelalvarezM.
Supongamos hemos resuelto un problema deminimizacinde
PL hasta la optimalidad.
SeaBla base ptima. Tenemos:
Veremos como responder estas preguntas en forma
algebraica.
6
ANLISIS DE SENSIBILIDAD
0*,0* 1 RB xbBx
1 0T
T TR
R B
c c c B R
1* T TB B Bz c x c B b
-
7/23/2019 06_IND2209_Alumno_15
7/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
Modificar la funcin objetivo no cambia la regin factible (o dominio)
del problema.
Una funcin objetivo diferente slo puede modificar el vrtice ptimo.
Afecta la pendiente de la funcin objetivo.
Puede haber un cambio de base.
Queremos identificar el rango de las perturbaciones en uno de los
coeficientes de la funcin objetivo de modo de no alterar la solucin
ptima alcanzada.
7
ANLISIS DE SENSIBILIDAD
-
7/23/2019 06_IND2209_Alumno_15
8/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
Supongamos el coeficientecj cambia acj+
Como sabemos, el vector de costos de la funcin objetivo se puede
dividir en:
Nos interesa ver qu ocurre con la condicin deoptimalidad
A medida que la base cambia en bsqueda de una base ptima, los
costos reducidos tambin cambian.
Y el anlisis depender de si el coeficiente que cambia es de una
columna bsicaono.
8
ANLISIS DE SENSIBILIDAD
T T T
B B R Rc x c x c x
1 0T
T TR R Bc c c B R
-
7/23/2019 06_IND2209_Alumno_15
9/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
Supongamos primero que el ndice jcorresponde a una variable NO
BASICA.
Cules costos reducidos se ven afectados?
En la solucin eljsimo costo reducido es:
Y cuando cambia enqueda:
Qu condicin debe cumplirse para que la solucin siga siendo
ptima?
9
ANLISIS DE SENSIBILIDAD
1Tj j B jc c c B R
1( ) Tj j B jc c c B R
-
7/23/2019 06_IND2209_Alumno_15
10/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
Esta condicin permite evaluar hasta donde puede cambiar el
costo no bsico.
10
ANLISIS DE SENSIBILIDAD
1( ) 0Tj j B jc c c B R
1( )T jj B jc c B R c
jc
-
7/23/2019 06_IND2209_Alumno_15
11/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
Supongamos ahora que el ndice jcorresponde a una variable
BASICA.
El anlisis respecto a variaciones de los costos asociados a
variables bsicas es ms complejo que en las no bsicas
Los costos reducidos son:
Cules costos reducidos se ven afectados...?
Si ante esta perturbacin los costos reducidos no bsicos siguen
siendo no negativos la base ptima permanece inalterada.
Los costos reducidos bsicos seguirn siendo 0 por construccin11
ANLISIS DE SENSIBILIDAD
1T T TR R Bc c c B R
-
7/23/2019 06_IND2209_Alumno_15
12/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
SeaRm dado por:
Entonces, los nuevos costos reducidos son:
Qu tiene que pasar para que se mantenga la optimalidad?
12
ANLISIS DE SENSIBILIDAD
jcaientecorrespondposicin
0
0
1( )T
T TR R Bc c c B R
-
7/23/2019 06_IND2209_Alumno_15
13/62
IND2209.Prof.:PamelalvarezM.
Cambio en coeficientes de la funcin objetivo
Donde rcorresponde al ndice de la fila de B-1R asociada a la
componente decBque se est modificando.
13
ANLISIS DE SENSIBILIDAD
1
( ) 0
TT T
R R Bc c c B R
011 RBRBcc T
T
B
T
R
01 RBc T
T
R
0)( 1
r
T
R RBc
-
7/23/2019 06_IND2209_Alumno_15
14/62
IND2209.Prof.:PamelalvarezM.
Cambio en la cantidad de recurso o lado derecho
Al cambiar el vector de nivel de recursos b, se mantiene
inalterada la funcin objetivo, pero se modifica el dominio de
las soluciones.
Si se modifica el nivel de recursos de una restriccin activa, la
solucin ptima, a menos que sea degenerada, cambia
inmediatamente.
Si la solucin ptima contina siendo definida por la mismabase entonces los costos reducidos permanecen inalterados, ya
que no dependen deb.
14
ANLISIS DE SENSIBILIDAD
-
7/23/2019 06_IND2209_Alumno_15
15/62
IND2209.Prof.:PamelalvarezM.
Cambio en la cantidad de recurso o lado derecho
Perturbaciones pequeas en uno de los recursos disponibles no
cambia el conjunto de variables bsicas, pero s el valor que
ellas toman en la solucin ptima.
15
ANLISIS DE SENSIBILIDAD
-
7/23/2019 06_IND2209_Alumno_15
16/62
IND2209.Prof.:PamelalvarezM.
Cambio en la cantidad de recurso o lado derecho
Perturbaciones mayores a un determinado umbral pueden
convertir la base en una base infactible: el valor que toma una
de las variables bsicas se hace negativo.
16
ANLISIS DE SENSIBILIDAD
-
7/23/2019 06_IND2209_Alumno_15
17/62
IND2209.Prof.:PamelalvarezM.
Cambio en la cantidad de recurso o lado derecho
La solucin ptima es:
Supongamos quebicambia abi+.
La pregunta es: cunto puede valer y mantener la misma
baseBcomo ptima?
17
ANLISIS DE SENSIBILIDAD
0*,0* 1 RB xbBx
-
7/23/2019 06_IND2209_Alumno_15
18/62
IND2209.Prof.:PamelalvarezM.
Cambio en la cantidad de recurso o lado derecho
Sea Rm dado por:
Entonces, la solucin cambia de la siguiente forma:
debe ser tal que se siga cumpliendo quexBnueva 0
18
ANLISIS DE SENSIBILIDAD
ibaientecorrespondposicin
0
0
)(1 bBx nueva
B
-
7/23/2019 06_IND2209_Alumno_15
19/62
IND2209.Prof.:PamelalvarezM.
Cambio en la cantidad de recurso o lado derecho
Esto lleva a:
Y por la forma de se tiene:
Esta condicin impone un sistema de desigualdades quedebecumplir, y de ah se deducen los lmites.
19
ANLISIS DE SENSIBILIDAD
*11 BxbBB
*)( 1 Bi xB
-
7/23/2019 06_IND2209_Alumno_15
20/62
IND2209.Prof.:PamelalvarezM.
Problema del carpintero
20
ANLISIS DE SENSIBILIDAD
70 90. . 4 3 40
4 7 56
, 0
ax x ys a x y
x y
x y
2 4 6 8 10 12
2
4
6
8
10
Cunto puede variar c1 de modo
de que la base siga siendo ptima?
*
*
*
7
4850
x
yz
Solucin ptima:
-
7/23/2019 06_IND2209_Alumno_15
21/62
IND2209.Prof.:PamelalvarezM.
Problema del carpintero
21
ANLISIS DE SENSIBILIDAD
70 90. . 4 3 40
4 7 56
, 0
ax x ys a x y
x y
x y
1T T TR R B
c c c B R
4 3 1 0
4 7 0 1A
?B
1
7 316 16
1 14 4
B
1( ) 0T
R rc B R
Costos reducidos:
65 758 8T
Rc
Variacinc1:
150 1303 7
-
7/23/2019 06_IND2209_Alumno_15
22/62
IND2209.Prof.:PamelalvarezM.
Problema del carpintero
22
ANLISIS DE SENSIBILIDAD
70 90. . 4 3 40
4 7 56
, 0
ax x ys a x y
x y
x y
2 4 6 8 10 12
2
4
6
8
10
Cunto puede variar b1 de modo
de que la base siga siendo ptima?
*
*
*
7
4
850
x
y
z
Solucin ptima:
*)(1
Bi xB
16 16
-
7/23/2019 06_IND2209_Alumno_15
23/62
IND2209.
Prof.:
Pamela
lvarez
M.
Vimos qu pasa si cambia un coeficiente de la funcin objetivo
y qu pasa si cambia el lado derecho de una restriccin.
Pero qu pasa si agregamos una variable con toda su
informacin asociada?
23
ANLISIS DE SENSIBILIDAD
. .
0
Tin z c x
s a Ax b
x
. .
, 0
T
n n
in n
n
Min z c x c x
s a Ax a x b
x x
-
7/23/2019 06_IND2209_Alumno_15
24/62
IND2209.
Prof.:
Pamela
lvarez
M.
Cambia el tamao de la base?
Qu se ve afectado.. la factibilidad o la optimalidad?
Por lo tanto proceder como si hubiera cambiado un costo no
bsico.24
ANLISIS DE SENSIBILIDAD
mxmB
0*,0* 1 RB
xbBx
1 0T
T TR R Bc c c B R
-
7/23/2019 06_IND2209_Alumno_15
25/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ya vimos qu pasa si los parmetros de los modelos cambian, ahora
veremos que todo problema se puede plantear de 2 formas distintas, lo
que entrega informacin adicional importante.
Todo problema de PL tiene un problema, tambin lineal, asociado
denominado problema dual.
Puede utilizarse para obtener informacin de la solucin ptima del
problema original (primal) y conocerla, si es que existe.
Adems, tiene una interpretacin econmica interesante.
Ambos problemas (primal y dual) utilizan los mismos parmetros, es decir,
el vector de costos, el vector de lados derechos y la matriz de coeficientes
de restricciones.
Si un problema es de maximizacin el otro es de minimizacin.25
DUALIDAD
-
7/23/2019 06_IND2209_Alumno_15
26/62
IND2209.
Prof.:
Pamela
lvarez
M.
Relacin entre los problemas:
26
DUALIDAD
0,
3
14
43..
3
21
2
21
21
21
yy
y
yy
yyas
yywMin
0,,
33
14..
34
321
321
21
321
xxx
xxx
xxas
xxxzMax
-
7/23/2019 06_IND2209_Alumno_15
27/62
IND2209.
Prof.:
Pamela
lvarez
M. 27
TRANSFORMACIN PRIMAL-DUAL
Problema de minimizacin Problema de maximizacin
Si la restriccin es de:
La variable asociada es:
airrestrict
0
0
Si la variable es:
airrestrict
00
La restriccin correspondiente es:
-
7/23/2019 06_IND2209_Alumno_15
28/62
IND2209.
Prof.:
Pamela
lvarez
M.
Teorema Dbil de Dualidad:
Si el problema primal es deminimizacinen xy el problema dual es
de maximizacin en y, entonces para todo e factibles se
cumple que:
Si el problema primal es demaximizacinenxy el problema dual es
de minimizacin eny, entonces para todo e factibles se cumple
que:
28
DUALIDAD EN PL
x y
z x w y
x y
z x w y
-
7/23/2019 06_IND2209_Alumno_15
29/62
IND2209.
Prof.:
Pamela
lvarez
M.
Teorema Dbil de Dualidad (dem. caso minimizacin):
Sean el par de problemas:
Si es factible para P) entonces , y premultiplicando porse tiene que:
Si es factible para D) entonces , y premultiplicando por
se tiene que:
Luego:
29
DUALIDAD EN PL
. .
0
TP Min z c x
s a Ax b
x
. .
0
T
T
D Max w y b
s a A y c
y
x x b0y
T Ty Ax y b
y Ty c0x T Ty Ax c x
T T Tc x y Ax y b
-
7/23/2019 06_IND2209_Alumno_15
30/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
30
DUALIDAD EN PL
1 2
1 2
1 2
1 2
) 70 90
. . 4 3 40
4 7 56
, 0
Max z x x
s a x x
x x
x x
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 70
3 7 90
, 0
D Min w y y
s a y y
y y
y y
5 10 15 20 25 30
5
10
15
20
25
2 4 6 8 10 12
2
4
6
8
10
1 0z
2 380z 3 700z
*850z
1 1200w 2 1500w
*
850w
-
7/23/2019 06_IND2209_Alumno_15
31/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:Soluciones factibles:
31
DUALIDAD EN PL
z x w y
0,0 0
0,4.2 380
10,0 700
z
z
z
30,0 12000, 26.8 1500
ww
1 2
1 2
1 2
1 2
) 70 90
. . 4 3 40
4 7 56
, 0
P Max z x x
s a x x
x x
x x
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 70
3 7 90
, 0
D Min w y y
s a y y
y y
y y
-
7/23/2019 06_IND2209_Alumno_15
32/62
IND2209.
Prof.:
Pamela
lvarez
M.
Teorema Fuerte de Dualidad:
Dado un par de problemas primaldual, si uno de ellos admite
solucin ptima, entonces el otro tambin la admite y lo respectivos
ptimos son iguales.
32
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
33/62
IND2209.
Prof.:
Pamela
lvarez
M.
Teorema Fuerte de Dualidad (demostracin):
Sean el par de problemas:
Sea x* una solucin bsica ptima de P) y B* su base ptimaasociada. Por lo tanto se tiene que y adems,
Luego, es dual factible.
Y por otra parte:
33
DUALIDAD EN PL
. .
0
T
Min z c xs a Ax b
x
. .
T
TD Max w y b
s a A y c
1
* 0B b
*1
* 0TB
c c c B A
*1
* *TBc B
*
*
*
*
1*
*
B
T
B
T
B
w b
c B b
c b
z x
-
7/23/2019 06_IND2209_Alumno_15
34/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
34
DUALIDAD EN PL
1 2
1 2
1 2
1 2
) 70 90
. . 4 3 40
4 7 56
, 0
Max z x x
s a x x
x x
x x
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 70
3 7 90
, 0
D Min w y y
s a y y
y y
y y
5 10 15 20 25 30
5
10
15
20
25
2 4 6 8 10 12
2
4
6
810
* 850z * 850w
-
7/23/2019 06_IND2209_Alumno_15
35/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:Solucin ptima:
35
DUALIDAD EN PL
* *z x w w
7, 4 850z 65 75, 8508 8w
1 2
1 2
1 2
1 2
) 70 90
. . 4 3 40
4 7 56
, 0
P Max z x x
s a x x
x x
x x
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 70
3 7 90
, 0
D Min w y y
s a y y
y y
y y
-
7/23/2019 06_IND2209_Alumno_15
36/62
IND2209.
Prof.:
Pamela
lvarez
M.
Corolario:
Dado un par de problemas primaldual, si alguno de ellos esfactible
pero NO acotado, entonces el otro problema esinfactible.
Dado un par de problemas primaldual, si alguno de ellos esfactible
y el otro es infactible, entonces el problema que admite solucin
factible es NO acotado.
36
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
37/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
37
DUALIDAD EN PL
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 703 7 90
, 0
Max z x x
s a x xx x
x x
5 10 15 20 25 30
5
10
15
2025
Problemafactibleperonoacotado
1 2
1 2
1 2
1 2
) 70 90
. . 4 3 40
4 7 56
, 0
D Min w y y
s a y y
y y
y y
2 4 6 8 10 12
2
4
6
810
-
7/23/2019 06_IND2209_Alumno_15
38/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
38
DUALIDAD EN PL
1 2
1 2
1 2
1 2
) 2 3
. . 2
1
, 0
Min z x x
s a x x
x x
x x
1 2
1 2
1 2
1 2
) 2
. . 2
3
, irrestricta
D Max w y y
s a y y
y y
y y
-
7/23/2019 06_IND2209_Alumno_15
39/62
IND2209.
Prof.:
Pamela
lvarez
M.
Teorema de Holguras complementarias:
Sean e las soluciones ptimas de los problemas P) y D),
respectivamente. Una condicin necesaria y suficiente para que e
sean ptimas viene dada por:
39
DUALIDAD EN PL
x
x
0 1,...,
0 1,...,
i i i
i j j
x b y i m
c yA x j n
-
7/23/2019 06_IND2209_Alumno_15
40/62
IND2209.
Prof.:
Pamela
lvarez
M.
Propiedades:
Soluciones complementarias: en cada iteracin, el mtodo Simplex
identifica una solucin factible para el PP y una solucin
complementaria para el PD. Si la solucin no es ptima para el PP,
entonces la solucin de PD es infactible.
40
DUALIDAD EN PL
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
41/62
IND2209.
Prof.:
Pamela
lvarez
M.
Propiedades:
Soluciones complementarias ptimas: en la ltima iteracin del
mtodo simplex se identifica simultneamente una solucin ptima
del PP y del PD. Y la solucin del PD corresponde a los precios
sombra del PP.
Simetra: para cualquier PP y su PD, las relaciones entre ellos son
simtricos. El dual del dual es el primal.
41
DUALIDAD EN PL
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
42/62
IND2209.
Prof.:
Pamela
lvarez
M.
Por lo tanto, si tengo la solucin de un problema, cmo se deriva la
solucin del otro problema?:
Las variables duales y los multiplicadores Simplex coinciden en el
ptimo de un problema lineal estndar.
Y qu pasa con las variables de holgura?
Se puede determinar el valor de las variables duales asociadas a
restricciones de desigualdad a partir del costo reducido de la
variable de holgura de la misma restriccin. 42
DUALIDAD EN PL
. .
0
T
Min z c xs a Ax b
x
. .
T
TD Max w y b
s a A y c
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
43/62
IND2209.
Prof.:
Pamela
lvarez
M.
Por lo tanto, si tengo la solucin de un problema, cmo se deriva la
solucin del otro problema?:
Teorema fuerte:
Calculemos las variables. SiB*es ptima tenemos:
43
DUALIDAD EN PL
. .
0
TMin z c x
s a Ax b
x
. .
T
T
D Max w y b
s a A y c
* *z w
*1
* 0TB
c c c B A
*
DualfactibleyptimoparaD
ANLISIS MATRICIAL
-
7/23/2019 06_IND2209_Alumno_15
44/62
IND2209.
Prof.:
Pamela
lvarez
M.
Consideraciones de las holguras:
Si una variable de holgura no est en la base tiene valor cero, y
la restriccin asociada est activa. El costo reducido de una variable de holgura que no est en la
base, es igual al multiplicador de Lagrange de la restriccin con
signo contrario.
44
ANLISIS MATRICIAL
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
45/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
Un industrial salmonero posee varias piscinas de crianza de salmones. Los animales en
esas piscinas son alimentados con una mezcla consistente en distintas materias primas
alimenticias y cada una de estas materias primas, entrega un cierto aporte en una serie
de nutrientes que son importantes para el desarrollo de los salmones. Por otro lado,
existen costos asociados a usar una u otra materia prima. El problema de este industrial
consiste en determinar la mezcla ms econmica de materias primas que satisfacen los
aportes mnimos en una porcin de alimento.
El anterior es un clsico problema de dieta", similar a algunos ejemplos que ya hemos
visto en el curso.
Vamos a suponer, en general, que existen nmaterias primas, y mnutrientes que deben
estar presentes en la dieta de un salmn. Considere los siguientes datos:
45
INTERPRETACIN ECONMICA
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
46/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
cj: costo, por gramo, de la materia primaj,j= 1;;n.
bi: requerimiento mnimo del nutrienteique debe haber en una porcin de alimento, en
gramos,i=1;;m.
aij: cantidad del nutrientei(en gramos), aportados por un gramo de materia primaj.
El modelo de Programacin Lineal que resuelve el problema es, como ya sabemos:
46
INTERPRETACIN ECONMICA
1
1
. . 1,...,
0 1,...,
n
j j
j
n
ij j i
j
j
P Min z c x
s a a x b i m
x j n
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
47/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
Si el industrial resuelve este problema, obtendr los valores para formar una porcin de
alimento.
Supongamos ahora que el industrial ya ha determinado una cierta mezcla y la est
usando y ahora necesita fabricar ms alimento, para lo cual debiera comprar ms
materia prima a los costos indicados. Sin embargo, se acerca a la crianza de salmones un
vendedor de una industria farmacutica y le expone al industrial lo siguiente:
Para qu compra todas estas materias primas si yo puedo ofrecerle los mismos
nutrientes para preparar sus porciones de alimentos, en forma de concentrados listos
para usar, arrojndolos a las piscinas?"
El industrial salmonero entonces pregunta:
A qu precio me ofrece los nutrientes en forma directa?"
47
INTERPRETACIN ECONMICA
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
48/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
Paso siguiente, el farmacutico pide un poco de tiempo para pensarlo y descubre que
debe formular unmodeloque le permita determinar los precios que debe cobrar por
cada gramo de nutriente concentrado de modo de obtener la mxima ganancia, pero de
modo que al salmonero le resulte igual o ms conveniente que comprar las materias
primas para obtener de ellas los nutrientes.
Cmo sera el modelo?
Para formular el problema del farmacutico, definamos yicomo elprecio al cual debe
ofrecer el nutriente i. Ahora pensemos: el farmacutico aspira a vender cantidades de
nutrientes en las mismas proporciones de los requerimientos mnimosb1; ; bm.
Ingreso por venta es igual
48
INTERPRETACIN ECONMICA
1
m
i i
i
b y
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
49/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
Por otra parte, los precios que se definan deben ser convenientes para el industrial, y si
ste quiere evaluar si le conviene ms comprar los nutrientes o materias primas, deber
comparar el costo entre uno y otro.
Recordemos que de un gramo de materia prima j el industrial obtiene a1j;a2j ;;amj
gramos de los nutrientes. Esas son, entonces, las cantidades que aspirar a comprar si
quiere reemplazar un gramo de la materia primal j. El costo de esas cantidades de
nutrientes, si los comprara al farmacutico, ser:
Para que convenga comprar al farmacutico se debe cumplir que este costo por gramo
no debe ser mayor al costo por gramo de la materia prima:
49
INTERPRETACIN ECONMICA
1 1 2 2 ....j j mj ma y a y a y
1 1 2 2 ....j j mj m ja y a y a y c
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
50/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ejemplo:
Luego, para determinar los precios ptimos a cobrar al industrial, el farmacutico
debiera resolver el problema:
50
INTERPRETACIN ECONMICA
1
1
. . 1,...,
0 1,...,
m
i i
i
m
ij i j
i
i
D Max w b y
s a a y c j n
y i m
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
51/62
IND2209.
Prof.:
Pamela
lvarez
M.
EjemploCaso particular:
Si se resuelva el problema de la dieta para determinar la mezcla ptima de ingredientes, el
resultado es que el costo de una porcin de alimentos es de $ 21,07. La solucin ptima indica
que se deben usar 38,46 gr. de arroz y 47,69 gr. de grasa animal, generndose, en la porcin
de alimento, 22 gramos de protenas, 19,46 gr. de lpidos, 2,4 gr. de Zinc y 13,38 gr. de hierro.
Por otro lado, si se resuelve el problema de determinacin de precios del farmacutico, se
obtiene que se debe cobrar $0,54 por gramo de protena y $3,85 por gramo de Zinc. Los
precios de lpidos y hierro son, sorprendentemente, igual a 0. El valor de venta de la porcin
equivalente para el farmacutico es de $21,07. Notemos que ese es precisamente el valor
ptimo del problema del industrial.51
INTERPRETACIN ECONMICA
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
52/62
IND2209.
Prof.:
Pamela
lvarez
M.
En nuestro ejemplo, podemos ver que las variables duales son precios de los
requerimientos. En otros problemas tambin tienen una interpretacin similar y
eso hace que se les llame, en Economa, precios sombra.
Veremos ahora un significado ms formal de las variables duales. Para esto
consideremos el dual del problema en forma estndar y supongamos que
hemos resuelto este problema hasta el ptimo. El valor ptimo es:
52
INTERPRETACIN ECONMICA
* *
1
m
i i
i
z w b y
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
53/62
IND2209.
Prof.:
Pamela
lvarez
M.
Ahora, consideremos el lado derecho de la de la restriccin idel primal. En
cunto cambia la funcin objetivo ptima si se cambia biabi+?
Este anlisis lo podemos hacer de la siguiente manera:
Esto significa que la variable dual de una restriccin mide cunto es el cambio
marginal en el valor ptimo cuando se cambia el lado derecho en una cantidad
(tambin marginal).
53
INTERPRETACIN ECONMICA
*
i
i
zy
b
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
54/62
IND2209.
Prof.:
Pamela
lvarez
M.
Problema del carpintero
Un carpintero fabrica 2 tipos de mesas mediante 2 procesos, de
acuerdo a la informacin del cuadro.
Ud. debe determinar el nmero de mesas de cada tipo que han de
producirse diariamente para maximizar el beneficio obtenido.
54
INTERPRETACIN ECONMICA
Tipodemesa Disponibilidad(hr/maq/da)1 2
Preparacindepiezas 4 3 40
Ensambladoybarnizado 4 7 56
Beneficio(US$) 70 90
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
55/62
IND2209.
Prof.:
Pamela
lvarez
M.
Problema del carpintero
55
INTERPRETACIN ECONMICA
2 4 6 8 10 12
2
46
8
10
Cunto est dispuesto a pagar por
una unidad adicional deb2?
Solucin ptima:1 2
1 2
1 2
1 2
) 70 90. . 4 3 40
4 7 56
, 0
Max z x xs a x x
x x
x x
*
1
*
2
*
7
4
850
x
x
z
INTERPRETACIN ECONMICA
-
7/23/2019 06_IND2209_Alumno_15
56/62
IND2209.
Prof.:
Pamela
lvarez
M.
Problema del carpintero
56
*
1
*
2
*
658
758
850
y
y
w
Solucin ptima:
5 10 15 20 25 30
5
10
15
20
25
* 850w
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 70
3 7 90
, 0
D Min w y y
s a y y
y y
y y
DUALIDAD
-
7/23/2019 06_IND2209_Alumno_15
57/62
IND2209.
Prof.:
Pamela
lvarez
M.
Problema del carpintero
57
1 0 7/16 -3/16 7
0 1 -1/4 1/4 4
0 0 -65/8 -75/8 850
x1 x2 x3 x4 b
1 2
1 2
1 2
1 2
) 40 56
. . 4 4 70
3 7 90
, 0
D Min w y y
s a y y
y y
y y
1 2
1 2
1 2
1 2
) 70 90
. . 4 3 404 7 56
, 0
Max z x x
s a x xx x
x x
1 0 7/16 -1/4 65/8
0 1 -3/16 1/4 75/8
0 0 7 4 850
y1 y2 y3 y4 b
DUALIDAD
-
7/23/2019 06_IND2209_Alumno_15
58/62
IND2209.
Prof.:
Pamela
lvarez
M.
Qu ocurre si uno de los problemas tiene mltiples
soluciones?
58
Pconmltiplessoluciones Dconsolucindegenerada
Pconsolucindegenerada Dconmltiplessoluciones
RESUMEN DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
59/62
IND2209.
Prof.:
Pamela
lvarez
M.
Qu hemos visto de dualidad?
Relaciones entre los dos problemas:
Teorema dbil de dualidad soluciones factibles del dual entregan unacota al primal.
Qu tipo de cota?
Teorema fuerte de dualidad en el ptimo ambos valores ptimos son
iguales!!
Por lo tanto, ambos problemas se pueden utilizar de manera
complementaria para obtener informacin de la solucin ptima si es
que existe.
El problema dual tiene una interpretacin econmica que entrega
informacin relevante.59
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
60/62
IND2209.
Prof.:
Pamela
lvarez
M.
Qu hemos visto de dualidad?
Otras relaciones posibilidades
60
PrimalfactiblePrimal
infactiblePoseesolucinptima
Noacotado
DualFactible
Posee
solucin
ptima
No
acotado
Dual
infactible
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
61/62
IND2209.
Prof.:
Pamela
lvarez
M.
Retomemos la siguiente pregunta cmo se deriva la solucin de un
problema si se tiene la del otro problema?.
Sea el siguiente par de problemas primaldual:
Sea x* una solucin bsica ptima de P) y B* su base ptima
asociada.
Qu tenemos? factibilidad y optimalidadDual factible
Variables duales en el ptimomultiplicadores del Simplex
Teorema Fuerte de dualidad.61
. .
0
TP Min z c x
s a Ax b
x
. .
T
T
D Max w y b
s a A y c
DUALIDAD EN PL
-
7/23/2019 06_IND2209_Alumno_15
62/62
IND2209.
Prof.:
Pamela
lvarez
M.
Hay relacin entre los costos reducidos de las variables de holgura
y las variables duales?
Se puede determinar el valor de las variables duales asociadas a
restricciones de desigualdad a partir del costo reducido de la
variable de holgura (o exceso) de la misma restriccin.
62
*1
* 0TB
c c c B A
*