# 最新文档-运筹学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

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

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

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

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

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

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

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