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


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


Queremosresponderpreguntasdeltipo:

Cuntopuedecambiarunladoderechodeunarestriccinyan

mantenerlamismabaseptima?

Cuntopuedecambiarlafuncinobjetivoyanmantenerla

mismabaseptima?

Qupuedeocurrirsiagregamosunavariableluegodellegarala

solucinptima?

Cuntopagaraporunaunidadderecursoadicional?

4

DUALIDAD Y ANLISIS DE SENSIBILIDAD

7/23/2019 06_IND2209_Alumno_15

5/62


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


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


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


7/23/2019 06_IND2209_Alumno_15

8/62



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


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



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


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



Esta condicin permite evaluar hasta donde puede cambiar el

costo no bsico.

10


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



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


1T T TR R Bc c c B R

7/23/2019 06_IND2209_Alumno_15

12/62



SeaRm dado por:

Entonces, los nuevos costos reducidos son:

Qu tiene que pasar para que se mantenga la optimalidad?

12


jcaientecorrespondposicin

0

0

1( )T

T TR R Bc c c B R

7/23/2019 06_IND2209_Alumno_15

13/62



Donde rcorresponde al ndice de la fila de B-1R asociada a la

componente decBque se est modificando.

13


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


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


7/23/2019 06_IND2209_Alumno_15

15/62



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


7/23/2019 06_IND2209_Alumno_15

16/62



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


7/23/2019 06_IND2209_Alumno_15

17/62



La solucin ptima es:

Supongamos quebicambia abi+.

La pregunta es: cunto puede valer y mantener la misma

baseBcomo ptima?

17


0*,0* 1 RB xbBx

7/23/2019 06_IND2209_Alumno_15

18/62



Sea Rm dado por:

Entonces, la solucin cambia de la siguiente forma:

debe ser tal que se siga cumpliendo quexBnueva 0

18


ibaientecorrespondposicin

0

0

)(1 bBx nueva

B

7/23/2019 06_IND2209_Alumno_15

19/62



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


*11 BxbBB

*)( 1 Bi xB

7/23/2019 06_IND2209_Alumno_15

20/62


Problema del carpintero

20


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



21


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



22


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


. .

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


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



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


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


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



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


1

m

i i

i

b y


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


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


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


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


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



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


* *

1

m

i i

i

z w b y


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


*

i

i

zy

b


7/23/2019 06_IND2209_Alumno_15

54/62

IND2209.

Prof.:

Pamela

lvarez

M.


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


Tipodemesa Disponibilidad(hr/maq/da)1 2

Preparacindepiezas 4 3 40

Ensambladoybarnizado 4 7 56

Beneficio(US$) 70 90


7/23/2019 06_IND2209_Alumno_15

55/62

IND2209.

Prof.:

Pamela

lvarez

M.


55


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


7/23/2019 06_IND2209_Alumno_15

56/62

IND2209.

Prof.:

Pamela

lvarez

M.


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.


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

*

06_ind2209_alumno_15

Documents