当前位置:首页 >> 管理学 >> 最新文档-运筹学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


更多相关文档:

最新文档-第二章线性规划-PPT精品文档_图文.ppt

最新文档-第二章线性规划-PPT精品文档 3 运筹学的主要内容 ?线性规划 ?非线性...线性规划问题 ? 可行区域与基本可行解 ? 单纯形方法 ? 初始解 ? 对偶性及...

运筹学对偶问题ppt课件_图文.ppt

运筹学对偶问题ppt课件 - 运筹学对偶问 题 一、对偶问题的一般形式 ? 若设一线性规划问题如下 : max F ? c 1 x 1 ? c 2 x 2 ? ? ? c n x n ...

第2章 对偶理论与灵敏度分析-第5,6节-PPT精选文档_图文.ppt

2019最新文档-管理系列 (PPT可编辑版) 运筹学(第三版)《运筹学》教材编写组 编 第2章 对偶理论 和灵敏度 分析第5节 对偶问题 的经济解 释影 子价格 ...

6运筹学建模-PPT精品文档_图文.ppt

6运筹学建模-PPT精品文档 - 运筹学建模 1.线性规划 2.对偶规划和影子价格 3.运输问题 4.整数规划 5.动态规划 运筹学简介 ? 1.引言: 运筹学(Operations Res...

《运筹学》第二章 对偶问题_图文.ppt

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 其它《运筹学》第二章 对偶问题_其它_高等教育_教育专区 ...

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

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

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

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

对偶问题运筹学2-5课件_图文.ppt

暂无评价|0人阅读|0次下载 | 举报文档 对偶问题运筹学2-5课件_其它_职业教育_教育专区。对偶问题运筹学2-5课件 三个问题:对偶问题、 对偶理论、 对偶单纯形算...

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

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

管理运筹学-PPT精选文档_图文.ppt

管理运筹学-PPT精选文档_管理学_高等教育_教育专区...(问题解决的过程): 1)提出问题:认清问题 2)寻求...可增加(减少)50元利 润,称为该约束条件的对偶价格...

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

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

运筹学复习资料-精品文档_图文.ppt

运筹学复习资料-精品文档_管理学_高等教育_教育专区。运筹学复习资料-精品文档 ...第 1、2 章 ?线性规划及对偶问题 1 (10分) 、写出如下线性规划问题的对偶...

运筹学2对偶理论和灵敏度分析_图文.ppt

暂无评价|0人阅读|0次下载 | 举报文档 运筹学2对偶理论和灵敏度分析_管理学_高等教育_教育专区。运筹学2对偶理论和灵敏度分析,运筹学对偶问题,运筹学对偶问题例题...

清华大学运筹学2对偶理论_图文.ppt

100w优质文档免费下载 赠百度阅读VIP精品版立即开通 ...搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS ...清华大学运筹学2对偶理论_管理学_高等教育_教育专区...

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

搜试试 2 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 高等教育 理学对偶问题(运筹学)_理学_高等教育_教育专区 ...

运筹学第1章-精品文档_图文.ppt

运筹学第1章-精品文档_管理学_高等教育_教育专区。运筹学第1章-精品文档 ...3 1.绪论 2.线性规划建模及单纯形法 3.线性规划问题对偶与灵敏度分析 4....

自然辩证法2 系统自然观-PPT文档资料-PPT精品文档_图文.ppt

自然辩证法2 系统自然观-PPT文档资料-PPT精品文档_自然景观_PPT模板_实用文档。...? 运筹学:在二战的需要中产生,是关于事理的科学, 旨在提高系统运行的整体效率...

《运筹学》对偶理论_图文.ppt

暂无评价|0人阅读|0次下载 | 举报文档运筹学对偶理论_理学_高等教育_教育...0 ? 1 2 3 4 线性规划的对偶模型 Page 6 把同种问题的两种提法所获得的...

...管理会计的产生和发展2011-1-7-PPT精品文档_图文.ppt

最新文档-第一章管理会计的产生和发展2011-1-7-PPT精品文档_财会/金融考试_...、新事物新科学产生条件 1、社会需要企业管理 2、客观可能运筹学,...

清华大学运筹学2对偶理论_图文.ppt

暂无评价|0人阅读|0次下载|举报文档清华大学运筹学2对偶理论_理学_高等教育_教育...y1 +3y3 ≥3 2y2 +2y3 ≥5 y1, y2, y3≥0 该问题叫做原问题(P)的...

更多相关标签:
网站地图

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