当前位置:首页 >> 管理学 >> 最新文档-运筹学2对偶问题-PPT精品文档_图文

最新文档-运筹学2对偶问题-PPT精品文档_图文


Operations Research
Chapter 2
Dual Problem

1. Dual Model of LP

2.

Dual property

3.

Dual Simplex Method

4.

Sensitivity Analysis

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 2 of 19



2.1




AB

C

98

6

500



54

7

450



83

2

300



76

4

550

100 80 70



2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 3 of 19

x1x2x3ABC
max Z 100 x1 80 x 2 70 x 3

9 x1 8 x 2 6 x 3 500



5 8

x x

1 1



4x2 3x2



7 x3 2x3



450 300



7

x

1



6x2



4x3



550

x1 , x 2 , x 3 0













2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 4 of 19

y1y2y3y4

min w=500y1+450y2+300y3+550y4

A9 587100, 100

9y15y28y37y4100

BC

8y14y23y36y4 80 6y17y22y34y4 70

yi0,i=1, ...,4.

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 5 of 19

minw 500y1 450y2 300y3 550y4
9y1 5y2 8y3 7y4 100 8y1 4y2 3y3 6y4 80 6y1 7y2 2y3 4y4 70 yi 0,i 1,,4



2.1

Ch2 Dual Problem

Dual model of LP

2019/4/17

Page 6 of 19

2.2ABC

A80B150

C180

















A

13 25 14 40 8 11 80

B

24

9

30 25 12 15 150

C

18

7

21 34 10 0 180

/100g 0.5 0.4 0.8 0.9 0.3 0.2

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 7 of 19

xjj
minZ0.5x1 0.4x2 0.8x3 0.9x4 0.3x5 0.2x6

13x1 25x2 14x3 40x4 8x5 11x6 80 24x1 9x2 30x3 25x4 12x5 15x6 150 18x1 7x2 21x3 34x4 10x5 180 x1x2x3x4x5x6 0

ABC

yii=123i

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 8 of 19

max w 80 y 1 150 y 2 180 y 3

13 y 1 24 y 2 18 y 3 0 . 5



25

y1



9

y2



7

y3



0 .4

14

y1



30

y2



21

y3



0 .8

40 y 1 25 y 2 34 y 3 0 . 9



8

y

1



12

y2



10

y3



0 .3

11 y 1 15 y 2 0 . 2



y 1

y 2

y3



0

(Shadow price):


2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 9 of 19



Z C B X B C B B 1b Yb

m
bi y i i 1

Z bi



yi

i 1, , m

yiibk(ki) biZyi

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 10 of 19

y1=2 y2=2Z2 Z2


Z i





yi bZi BB yi

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 11 of 19

2.1X24.24046.96 Y10.60.9100 z=w=5712.12


1. y1=10.6 10.6 10.6
2. y3=0

1.
2.

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 12 of 19










2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 13 of 19

2.3

min Z 5x1 2 x2 3x3



4 x1 x1 7

x x

2 2



x3 4 5x3 1

x1 , x2 , x3 0

Y=y1y2
4 maxwYb (y1, y2)1 4y1 y2

4 1 1

YA (y1, y2)1 7

5



(4y1 y2, y1 7y2 y1 5y2) (5,2,3)



2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 14 of 19

max Z 4 y 1 3 y 2

4 y1 y2 5



y1 y1

7

y2 5 y2



2 3

y 1 0 , y 2 0

yixi

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 15 of 19

2.4

max Z 4 x 1 3 x 2

5 x1 x2 6



7 x

x
1

1


3

5 x

x
2

2


8 10

x 1 0 , x 2 0



" "

min w 6 y1 8 y2 10 y3

5 y1 7 y2 y3 4 y1 2 y2 3y3 3 yi 0, i 1,2,3

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 16 of 19

21

2-1

1. i" "iyj0 2i" = "iyi 3xj0j" "xj j" = "

21

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 17 of 19

21



max AAT



n

j0

j 0



j



m

i

i



i=

min
ATA



n

j

j



j=



m

i0

i0



i

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 18 of 19

2.5

min Z x1 5 x2 4 x3 9 x4

7 x1 2 x2 8 x3 x4 18





2

x1

6x2 8x2

x3



5x4 14



10

x1 , x2 0, x3 , x4 0

21 34 3 421

max w 18 y1 10 y 2 14 y 3

7 y1 2 y3 1



2

y1



6

y2



8

y3



5

8 y1 y3 4




y1 y1

0

5 y2 , y2



9 0,

y


3

2.1 Dual model of LP

Ch2 Dual Problem

2019/4/17

Page 19 of 19

;

;

1. 2.
P74 T2.312

The End of Section 2.1


Exit

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 20 of 23

LP DP

max Z CX

min w Yb

AX b



X

0

YA C



Y



0

AmnXn1Y1m

XsYsLPDP

1

m Z a C x ,A X X b ,X 0

2.2 Dual Property
21

Ch2 Dual Problem

2019/4/17

Page 21 of 23

m w iY n ,bY A C ,Y 0


m w ) a Y x , Y b ( A C ,Y 0

m w ' i C n , A X X b ,X 0


m Z a C x ,A X X b ,X 0



2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 22 of 23

2 XYLPDP
CX0Y0b
XYAXb, X0 YACY0, AXb Y

YAXYb YACX
C XYAX



C XYAXYb



2.2 Dual Property


Ch2 Dual Problem

2019/4/17

Page 23 of 23

1LPDP DPLP

2

(3
23

2.2 Dual Property



min z x 1 2 x 2





x1



x1



1 2 x2 x2 2



2



x

1

,

x

2



0



max w 2 y 1 2 y 2

y1 y2 1




y

1

1
2 ,

y1 y2



y2 0



2

3

Ch2 Dual Problem

2019/4/17

Page 24 of 23

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 25 of 23

3 XYLPDP XYLPDP C X= Yb.
X Y B LP
Y=CBB1C 0X C BB 1bY0b
X Y
C X= YbC X Y 10bC 0 X Y b

YbDPC X LPXY

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 26 of 23

4 LPDP
LPXB C CBB-1A0CBB-10YACY0 Y= CBB-1 Y
C 0 X C B X B C B B 1 b Y 0 b
3Y

4 LPDP

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 27 of 23

5 XYLP DPXSYS XY
YSX=0YXS=0
XY3 C X= Yb
XSYSA XXSb
YAYS=C YX
YA XYXSYb
YA XYS X=C X

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 28 of 23



YXS=YS X

YXsYsX0



YXS=0YS X=0

YXS=0YS X=0
YA XYb
YA X=C X
Yb=C X,3YXLPDP

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 29 of 23

5 YXXY

YXS=0YS X=0

m
yi0 x Si 0
i1

m

y

S

j

x

0 j



0

j1





2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 30 of 23

1yi>0xSi 0 xSi 0 yi=0
(2 )y S j 0 x 0 j 0 ,x 0 j 0 y S j 0
5

2.6 max z 3 x1 4 x 2 x3



x1 2 x1

2

x 2

2
x

x 2

3
x


3

10 16



x

j



0,

j

1,2,3

X(6,2,0)T

max z 3 x1 4 x2 x3



x1 2 x1

2

x 2

2
x

x 2

3
x

10 3 16



x

j



0,

j



1,2,3



min w 10 y 1 16 y 2

y1 2 y2 3



2 y

y
1

1


y

2
2

y2 1

4

y 1 , y 2 0

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 31 of 23

X(6,2,0)T


X10X20
2y1y1 22y2y234
y1=1,y2=1, Y=11 w=26

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 32 of 23

2.7

min z 2x1 x2 2x3



x1 x1



x2 x2



x34 x3 6

x1 0, x2 0, x3



Y=0, -2

max w 4 y 1 6 y 2 y20 x S =2 0 yS2 1

y1 y2 2

x2=0:



y y

1 1



y2 1

y


2

2



x1 x1



x3 x3



4 6



y 1 y 2 0

X=(-5, 0, -1)TminZ = -12

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 33 of 23

2.8
min Z x1 x 2 x 3



x x

1 1



x3 x2



4 2x3



3



x

j



0,

j



1, 2 ,3

X=400



max w 4 y 1 3 y 2

y1 y2 1







y2 1 y1 2 y2



1

y 1 0 , y 2 0



y2



1 2



y21





2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 34 of 23

6 LPDP .

x jjySj ixjiyiS i DDPP
LP

2.9

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 35 of 23

max z 6 x1 2 x2 x3



2 x1 x1

4

x x

2 3



x3 4



2

x1 , x2 , x3 0

1 2 3 4Y=CBB-1 1x4x522

22

XB

x1

(1)

x4 x5

2* 1

j

6

(2)

x1 x5

1 0

j

0

(3)

x1 x2

1 0

j

0

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 36 of 23

x2

x3

x4

x5

b

-1

2

1

0

2

0

4

0

1

4

-2

1

0

0

-1/2 1

1/2

0

1

1/2*

3

-1/2

1

3

1

-5

-3

0

0

4

0

1

4

1

6

-1

2

6

0

-11 -2

-2

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 37 of 23

X=460Z=6426=12 2y1y2,y3y4y5,Y=y1
y2 y3y4y56 y1y2 y3y4y5 =45123
221=62100 Y1=00-621
222=01530 Y2=30015
223=001122 Y3=220011

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 38 of 23

1223 Y3=220011

1223B



1 2

1

0



B-1 223x4x 5

B1



0 1

1 2

CB=62

Y (y1, y2) CBB1

(6,2)01

1 2



(2,2)

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 39 of 23



23



23

max

min





4





4





2











5

1 6

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 40 of 23



1. 2i""yi0. 3 . 4. 5. 6 . 7.
8. 9. 10. 11. 12. 13X*Y*X*=Y*. 14 .

2.2 Dual Property

Ch2 Dual Problem

2019/4/17

Page 41 of 23

The End of Section 2.2

P75 T2.42.6 2.5

Exit

2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 42 of 9

LP DP

max Z CX

min w Yb

AX b



X



0

YA C



Y



0

j0j0

6


2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 43 of 9

1
j0maxj0min, bi<0

2

bi m i b ii|n bi 0,l xl

3

k

mj inaljj

| alj

0

4alkl,k

2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 44 of 9

2.10

min z 2 x1 3x2 4 x3



x1 2 2 x1

x2 x2



x3 3 3x3 4

x1, x2 , x3 0

1

min z 2x1 3x2 4x3



x1 2 2x1

x2 x2



x3 x4 3 3x3 x5 4



x

j



0,

j

1,2,,5

()

2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 45 of 9

24

XB

b

x1 x2 x3 x4 x5

x4

-3

-1

-2

-1

1

0

x5

-4

-2

1

-3

0

1

0

-2

-3

-4

0

0



1

-- 1.3333 -- --

x4

-1

x1

2

4



0 -2.5 0.5

1 -0.5

1 -0.5 1.5

0 -0.5

0

-4

-1

0

-1

-- 1.6 -- --

2

x2

0.4

0

1 -0.2 -0.4 0.2

x1

2.2

1

0

1.4 -0.2 -0.4

5.6

0

0 -1.8 -1.6 -0.2

x2=0.4 x1=2.2

Max z = -5.6

2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 46 of 9

1


2

3 j
a ij

j0aij<0

j0aij<0

a

j ij





mz'a x 4 x 1x2 3 x3 j0k

2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 47 of 9

4



5miinabiik aik 0



min j

j
alj

| alj

0



6
b lmb ii|n b i0
bi

2.3 The Dual Simplex Method
2.12

max z 7 x1 3 x 2



2

x1 x1



x2 2x2

x3 x4

2 2



x

j



0,

j



1,2, ,4

Ch2 Dual Problem

2019/4/17

Page 48 of 9

Excel

2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 49 of 9

2.126 222

2

j

bi , j b i ,

aik

aLj

a ik

2

a Lj


2.3 The Dual Simplex Method

Ch2 Dual Problem

2019/4/17

Page 50 of 9

6 --

1. 2. 3. 4. P76 T2.7

The End of Section 3
Exit

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 51 of 34

cjbiaij

1

2

2.4.1cj cj



2.4 Sensitivity Analysis
max z CX

Ch2 Dual Problem

2019/4/17

Page 52 of 34

AX b



X



0

Amn
B 1 (1 ,2 , ,m ) i (1 i,2 i, ,m )i



jcjcBB 1P j,j1 ,2, ,n

cj cj'cj cj


j'cj'CBB1Pi 0

cj

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 53 of 34

cjxj
j'cj'C BB1P j cjcjC BB1P j cjC BB1P jcj jcj0



cj j

cj c j cj


2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 54 of 34

cixi

ciCB

jc

i,c

ic


i



j '

cj



C

' B

B

1

Pj

c j (C B C B )B 1 Pj

c j C B B 1 Pj C B B 1 Pj

j C B B 1 Pj

j (0, ,0, ci ,0, ,0)(a1 j , a2 j , , amj )'

j ci aij 0

aij

0 ci

j
aij

,

aij

0 ci

j
aij

ci j






1

max j

j



a

ij

a ij



0





2



min j



a

j ij

a ij



0





2.4 Sensitivity Analysis
j ' 0
1ci 2

Ch2 Dual Problem

2019/4/17

Page 55 of 34

2 1 ci

2.13 max Z x 1 x 2 3 x 3

x1 x 2 2 x 3 40



x x

1 2



2x2 x3 x 3 15



20

x 1 , x 2 , x 3 0

1

2c1,c2,c3

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 56 of 34

1x4,x5,x6

26

26

Cj

1

1

3

0

0

0

b

CB XB x1

x2

x3

x4

x5

x6

0 x4 0

2

0

1 1 1 5

1 x1 1

1

0

0

1 1 5

3 x3 0

1

1

0

0

1

15

j

0 3 0

0 1 2

X=5015 ; Z=50

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 57 of 34

2x2x 1x 3

c223
c2 c 2 c 2 ( 2 ) 1 3 4 c 2 , 4

c126x


1



a221 a251, 1 max



2 a 22

, 5 a 25



a26



1

,

max



3 1

,

1

1





1

2 min



6 a 26





2 1



2

1 c1 2
c1
c 1 1 c 1 ' c 1 2 , 0 c 1 ' 3 c 1 [ 0 , 3 ]

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 58 of 34

c326x3 a32 1 a36 1 , a35 0,

1



max



2
a32

,

6
a36





max



3 1

,

2 1





2

c3c32c3
c3'1 c3 1 ,

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 59 of 34

c326c3=3 c3'c3c3



2 '

c2



C

' B

B

1 P 2

2

1 ( 0 ,1 , 3 c 3 1



1

3 c3 0 5 ' c 5 C `B B 1 P 5

1



( 0 ,1 ,3





c

3

)



1



0

1

1

6 '

( 0 ,1 ,3





c

3

)





1



1

2 c3 0

2.4 Sensitivity Analysis
5'10

Ch2 Dual Problem

2019/4/17

Page 60 of 34

2 ' 6 '



3 2



c3 c3



0 0

c32c2c1 2.4.2 bi Bbi

brbrb b (0 ,0 , , b r,0 , ,0 )'
XXB=B1bB
XB'Bb'0 1



2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 61 of 34

XB' B1b' B1(bb)

B1b B1b

XB B1b

0

B

1 b



( 1,

2 ,

,

m





0

)





b

r





br

1r





2

r





0











mr



0



2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 62 of 34

XB'



bb12





br

1r 2r




bb21bbrr21r






0

bm



mr







bm brmr

bi brir 0,i 1,,m



ir

0 br

bi
ir



1

max i





b
ir

i

ir

0


2



min i





b
ir

i

ir



0







2.4 Sensitivity Analysis
xi'0,br
1br 2

Ch2 Dual Problem

2019/4/17

Page 63 of 34

c i B1r br

ir 0br
2.142.13b1,b2,b3

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 64 of 34

26BB1

1 1 2

11 12 13 1 1 1

B(P4,P1,P3)0 1 1,B1 21 22 230 1 1

0 0 1

31 32 33 0 0 1

XB

bb12

5 5,XB

5 5

b3 15

15

b1B111=1 21=31=0
1maxb111155

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 65 of 34

b1b15b1

[35,)

b2B1120,220

1



max






b2
22





5 1



5

2



min






b1
12





5 1



5

5 b2 5

b2[1525]

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 66 of 34

b3B1

b 113 , b 223 , b 333 1 5, 1 5, 1 1 5 5 ,5 , 15

15 b35,b3[020]

cjbi

aij

2.4 Sensitivity Analysis
2.15

Ch2 Dual Problem

2019/4/17

Page 67 of 34

mZ a 2 x x 1 x 2 4 x 3

3x1 2x2 4x3 5

xx11



x2 x2



x3 x3



3 4

1 (2) (3)

x1, x2, x3 0

1

mzi n 2x1x24x3

1:

10

b





4



2

2.4

Ch2 Dual Problem

Sensitivity Analysis
3x3c3=1;
4x2c2=2

2019/4/17

Page 68 of 34

5x2



c a

' 2
' 12







3 3



a a

' 22
' 32



1



2



61

3x1x24x33;

7 5x1x26x35

8 5x1x22x310

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 69 of 34

x4x5x627

27

Cj

2 -1

4

0

0

0

b

CB XB x1

x2

x3

x4

x5

x6

4 x3 0 5/7

1

1/7 3/7

0

2

2 x1 1 2/7

0 1/7 4/7

0

1

0 x6 0 2

0

0

1

1

1

j

0 31/7 0 2/7 20/7 0

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 70 of 34

X=102001Z=10

4 B 1
1

3 1 1

1

0 0, 1

B1



71 7 0

3
7 4

0
0

7

1 1





1 mzi n 2x1x24x3 mza x 2 x 1x2 4 x3
cj214c1=2c3=4 c2=1

2.4

Sensitivity Analysis

5

(2 , 4,5 )



(1,0,0)



(4,2,0)

7 2
7

2



31, 2 , 20 0 7 7 7

Ch2 Dual Problem

2019/4/17

Page 71 of 34

1 3

7 1

7 4



7 7

0 1



2727 28

2.4 Sensitivity Analysis

cj

2 1

4

0

0

CB XB x1

x2

4 x3

0

5/7

2 x1

1

2/7

0

x6

0

2

j

0 31/7

x3

x4

x5

1

1/7

3/7

0 1/7 4/7

0

0

1

0

2/7 20/7

1

x2

0

1

7/5

1/5

3/5

2 x1

1

0 2/5 1/5 2/5

0

x6

0

0

14/5 2/5

1/5

j

0

0 31/5 3/5 1/5

1 x2 3/2 1

2

1/2

0

0 x5 5/2

0

0 x6 1/2 0

1 1/2 1

3

1/2

0

j

1/2 0

6 1/2 0

Ch2 Dual Problem

2019/4/17

Page 72 of 34

28

0

x6

b

0

2

0

1

1

1

0

0

14/5

0

1/5

0

33/5

0

0

5/2

0

1/2

1

13/2

0



2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 73 of 34

X(0,5,0,0,1,1)` 3, Z 5

2 22

2

2

1

XB



B1b



71 7

0

3
7 4
7 1

1001240



22



7 6



7

2







XB27 29

Cj

2

CB XB x1

4 x3

0

2 x1

1

0 x6

0

j

0

4 x3

0

2 x1 1

1 x2

0

j

0

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 74 of 34

29

1

4

0

0

0

b

x2

x3

x4

x5

x6

5/7

1

1/7 3/7

0

22/7

2/7

0 1/7 4/7

0

6/7

2

0

0

1

1

2

31/7 0 2/7 20/7 0

0

1

1/7 1/14 5/14 17/7

0

0 1/7 3/7 1/7 4/7

1

0

0

1/2 1/2 1

0

0

2/7 9/14 31/14

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 75 of 34

X(4,1,1,7 0,0,0),' Z6 9

77

7

327x3c3

c32, c3 [2,]

c3=127

5 1 3

2 , 4 , 5

(1,0,0)



(1,2,0)

7 2
7

7 1
7

7 4



7

2 0 1





( 16 , 1 , 11) 77 7

x4210

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 76 of 34

210

XB

x1

x2

x3

x4

x5

x6

b

x3

0

5/7

1

1/7 3/7

0

2

x1

1

2/7

0 1/7 4/7

0

1

x6

0

2

0

0

1

1

1

j

0 16/7 0

1/7 11/7 0

x4

0

5

7

1

3

0

14

x1

1

1

1

0

1

0

3

x6

0

2

0

0

1

1

1

j

0

3 1

0

2

0

X=3001401`z=6

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 77 of 34

4c2x2211c2

2c2

3

31, 7

x2



31, 7

c2

1

5

2 '



2 (42,0)

7 2
7





10 7



0

2



X=102001

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 78 of 34

(5) 2

1

a12



a

22

a 32





B

1 P2 '



7 1

7

0



3
7 4
7 1

0
0 1





3 1 2



0





1

3



`2 c 2 ' C B B 1 P2 '

0



3



(

4

,2

,0

)





1





5



0

3

x2211

2.4 Sensitivity Analysis

Cj

2

3

4

0

0

CB XB

x1

x2

x3

x4

x5

4 x3

0

0

1

1/7 3/7

2 x1

1

1

0 1/7 4/7

0 x6

0

3

0

0

1

j

0

5

0 2/7 20/7

x3

0

0

1

1/7 3/7

x1

1

0

0 1/7 5/21

x2

0

1

0

0 1/3

j

0

0

0

2/7 25/21

X(4,1,2,0,0,0),' Z3 5

33

3

Ch2 Dual Problem

2019/4/17

Page 79 of 34

211

0

b

x6

0

2

0

1

1

1

0

0

2

1/3 4/3

1/3 1/3 5/3

2.4

Ch2 Dual Problem

Sensitivity Analysis

2019/4/17

Page 80 of 34

6 3x1x24x33,

a12b12XB

2 ' c 2 C B B 1P2

1



1

(

4

,

2

,

0

)





7

1

7

0



3
7 4
7 1

0
0 1







1

1 1





25 7

0



1

X

B '

B

1b '





7

1

7

0



3
7 4
7 1

0
0 1





3 3 4





12



7 9

7

1







2'0,XB'

X(9,0,1,2 0,0,1),' Z6 6

77

7

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 81 of 34

j ' 0 XB'0 j ' 0 X B ' j ' 0 X B '
.

7x7
5 x1x26 x3x75

x1x327x1x3 13 11 2
7x27x47x5x72

x7X=1020012 279-12

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 82 of 34

212

XB

x1

x2

x3

x4

x5

x6 x7

b

x3

0

5/7

1

1/7 3/7

0

0

2

x1

1

2/7

0 1/7 4/7

0

0

1

x6

0

2

0

0

1

1

0

1

x7

0 13/7 0 11/7 2/7

0

1

2

j

0 31/7 0 2/7 20/7 0

0

x3

0

6/11

1

0 5/11 0 1/11 20/11

x1

1

5/11

0

0

6/11

0 1/11 13/11

x6

0

2

0

0

1

1

0

1

x4

0 13/11 0

1 2/11 0 7/11 14/11

j

0 45/11 0

0 32/11 0 2/11

X(1,0 3,2,0 1,0 4,1 ,0),' Z97

1111 11

11

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 83 of 34

8 5x1x22x310
5122=1<10

cjbi


1.Cj 2.bi 3.

2.4 Sensitivity Analysis

Ch2 Dual Problem

2019/4/17

Page 84 of 34

1. 2. 3.
MBAQSB Modify problem
P76 T2.8 2.9
The End of Chapter 2
Exit


Dual sensitivity analysis shadow price opportunity cost

Ch2 Dual Problem

2019/4/17

Page 85 of 1


更多相关文档:

新编文档-运筹学课件ch3运输问题-精品文档_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 管理学新编文档-运筹学课件ch3运输问题-精品文档_管理学_高等教育_教育专区 ...

运筹学对偶问题-PPT文档资料_图文.ppt

运筹学对偶问题-PPT文档资料 - 第二章 LP的对偶理论与灵敏度分析 线性规划

运筹学第二章对偶问题-文档资料_图文.ppt

运筹学第二章对偶问题-文档资料_管理学_高等教育_教育专区。运筹学第二章对偶...运筹学2对偶问题-PPT精品... 暂无评价 85页 免费 运筹学 第2章线性规划...

运筹学线性规划的对偶问题-精选文档_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 自然科学 数学运筹学线性规划的对偶问题-精选文档_数学_自然科学_专业资料 ...

运筹学ppt课件-PPT精品文档_图文.ppt

运筹学ppt课件-PPT精品文档 - 运筹学 ? ? ? ? §1 §2 §3

线性规划对偶理论-PPT精品文档_图文.ppt

线性规划对偶理论-PPT精品文档 - 运筹学 Operations Resear

...单纯形法的灵敏度分析与对偶-精品文档_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 专业资料 ...管理运筹学(第二版)-第6章 单纯形法的灵敏度分析与对偶-精品文档_数学_自然...

新编文档-第4章最优化方法运筹学-精品文档_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...新编文档-第4章最优化方法运筹学-精品文档_计算机...对偶问题与影子价格在经济活动中可以追求最大利润,也...

《运筹学教学资料》运筹学第3章第2节[2019]-PPT精品文档_图文_....ppt

运筹学教学资料》运筹学第3章第2节[2019]-PPT精品文档_管理学_高等教育_...v j 分别是m+n 个约束条件对应的对偶变量, 得到运输问题的对偶问题: 表上...

...教材相应的授课文档第二章-PPT精品文档_图文.ppt

与清华大学《运筹学》教材相应的授课文档章-PPT精品文档 - 第章 §1 对偶理论与灵敏度分析 单纯形法的矩阵描述 设max z = CX AX = b X≥0 A为m...

新编文档-运筹学图与网络优化-精品文档_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...新编文档-运筹学图与网络优化-精品文档_计算机软件及...破圈法是Dijkstra算法的对偶算法。最适合于图上作业...

对偶问题(运筹学)_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...对偶问题(运筹学)_理学_高等教育_教育专区。运筹学...运筹学对偶问题-精品文档... 暂无评价 54页 免费...

最新文档-智能交通与车联网课件-PPT精品文档_图文.ppt

最新文档-智能交通与车联网课件-PPT精品文档_语文_小学教育_教育专区。第一讲车...它是将先进的信息技术、传感器技术、自动控 制理论、运筹学、人工智能等有效地...

运筹学基础及应用第2章-线性规划的对偶问题(胡运权版)_....ppt

100w优质文档免费下载 赠百度阅读VIP精品版立即开通 ...搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...运筹学基础及应用第2章-线性规划的对偶问题(胡运权...

运筹学5单纯形法-PPT精品文档_图文.ppt

运筹学5单纯形法-PPT精品文档 - 第五章 单纯形法 1. 线性规划问题的解 2 单纯形法 3 求初始基的人工变量法 1.线性规划问题的解 Max (1) 解的基本概念 ...

《管理运筹学》04-目标规划-PPT精品文档_图文.ppt

《管理运筹学》04-目标规划-PPT精品文档 - Goal Programming 第四章 目标规划 GP 第4章 目标规划 4.1 目标规划问题及其建模 4.2 目标规划的图解法 4...

运筹学原理和实践 绪论-PPT精品文档_图文.ppt

运筹学原理和实践 绪论-PPT精品文档 - 运筹学原理与实践 绪论 为什么要学习? ? 运筹原理和实践是工业工程专业的一门重要 专业课,它以管理决策问题为实际...

最新文档-07质量管理的新七种工具-PPT精品文档_图文.ppt

最新文档-07质量管理的新七种工具-PPT精品文档_图片/文字技巧_PPT制作技巧_实用...将运筹学、系统工程、行为科学等更 多、更广的方法来解决生产中的质量管理问题...

最新文档-常用数据分析软件-PPT精品文档_图文.ppt

最新文档-常用数据分析软件-PPT精品文档_图片/文字技巧_PPT制作技巧_实用文档。...运筹学和线性规划模块:SAS/OR; ? 经济预测和时间序列分析模块SAS/ETS等. SAS...

《管理运筹学》07-网络规划1-PPT精品文档_图文.ppt

《管理运筹学》07-网络规划1-PPT精品文档 - 第七章 网络规划 第七章 网络规划 第一节:现实中的网络规划问题节:图的基本概念 第三节:树 第四节:最大...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com