運(yùn)籌學(xué)課件：對(duì)偶及靈敏度分析

線性規(guī)劃的對(duì)偶理論及靈敏度分析空中交通系統(tǒng)優(yōu)化與管理線性規(guī)劃問題線性規(guī)劃的對(duì)偶理論對(duì)偶問題的提出任何線性規(guī)劃問題都有其對(duì)偶問題對(duì)偶問題有其明顯的經(jīng)濟(jì)含義1 221 2s.t.maxf(x)

2x1

x2

5x2

15

6x

2x

24

x

x

5

1

x

,

x

0

例

3.11設(shè)備A資源設(shè)備B資源時(shí)間資源假設(shè)有商人要向廠方購(gòu)買資源A、B和時(shí)間的所有資源，問他們談判原料價(jià)格的模型是怎樣的？二種產(chǎn)品23

s.t.

5

y1

y

,

16

y2

y3

2產(chǎn)品1

的所得廠方

2

y2

y3

1產(chǎn)品

2

的所得的y

,y

0目標(biāo)設(shè)A、B和時(shí)間資源的出售價(jià)格分別為y1 ，y2和y3顯然商人希望總的收購(gòu)價(jià)越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少目標(biāo)函數(shù)

min

g(y)=15y1+24y2+5y3 (商人的目標(biāo))3.3.1

對(duì)偶問題的的提出1 2 3 41 2 3 4

x,x,x

,

x

0

例

3.12maxf(x)

x1

2x2

3x3

4x4

x1

2x2

2x3

3x4

25假設(shè)有商人要向廠方購(gòu)買資源A和B，問他們談判原料價(jià)格的模型是怎樣的？四種產(chǎn)品A資源s.t.

2x

x

3x

2x

15 B資源3.3.1

對(duì)偶問題的的提出廠方的目標(biāo)

產(chǎn)品1的所得產(chǎn)品2的所得產(chǎn)品3的所得產(chǎn)品4的所得11 22y1,y2

0

3y

2

y

4

2y1

3y2

3

2

y

y

2

y1

2

y2

1s.t.設(shè)A、B資源的出售價(jià)格分別為

y1

和

y2顯然商人希望總的收購(gòu)價(jià)越小越好工廠希望出售資源后所得不應(yīng)比生產(chǎn)產(chǎn)品所得少目標(biāo)函數(shù)

min

g(y)=25y1+15y2 (商人的目標(biāo))3.3.1

對(duì)偶問題的的提出

a y

a y1n 1 2n 2

a y

a y12 1 22 2

a11y1

a21

y2s.t.

am1ym

c1

am

2

ym

c2

amnym

cn

y1,

y2

,

,

ym

0對(duì)偶問題的一般形式:min

b1y1

b2y2

bmym

Y

0

CT

AT

YTs.t.對(duì)偶問題習(xí)慣寫為:min

bT

YT

Y

0

YA

Cs.t.min

Yb3.3.2

原問題與對(duì)偶問題的表達(dá)形式3.3.2

原問題與對(duì)偶問題的表達(dá)形式

X

0

AX

bs.t.maxz

CX原問題:

Y

0

YA

Cs.t.min

Yb對(duì)偶問題:C

(c1,

c2

,

,

cn

)b

(b1,b2

,

,bm

)T上兩式中X

(

x1,

x2

,

,

xn

)TY

(

y1,

y2

,

,

ym

)

mn

m1 m2

a2n

A

a21a1n

a12

a22

a a

a

a11

a x

a xm1

1 m

2 2

a x

a x21

1 22 2

a11x1

a12

x2s.t.

a1nxn

b1

a2nxn

b2

amnxn

bm

x1,

x2

,

,

xn

0原問題標(biāo)準(zhǔn)形:maxz

c1x1

c2x2

cnxn

12

122

2

m

2

m

2

a y

a y1n 1 2n 2

a

a11y1

a21

y2s.t.

amnym

cn

y1,y2,

,

ym

0y

a y

a y

c

am1ym

c1把對(duì)偶問題展開min

b1y1

b2y2

bmym3.3.2

原問題與對(duì)偶問題的表達(dá)形式(max,

)標(biāo)準(zhǔn)型的對(duì)偶變換目標(biāo)函數(shù)由

max

型變?yōu)?/p>

min

型對(duì)應(yīng)原問題每個(gè)約束行有一個(gè)對(duì)偶變量

yi，i=1,2,…,m對(duì)偶問題約束為

型，有

n

行原問題的價(jià)值系數(shù)

C

變換為對(duì)偶問題的右端項(xiàng)(資源向量)原問題的右端項(xiàng)(資源向量)

b

變換為對(duì)偶問題的價(jià)值系數(shù)原問題的技術(shù)系數(shù)矩陣

A

轉(zhuǎn)置后成為對(duì)偶問題的技術(shù)系數(shù)矩陣原問題與對(duì)偶問題互為對(duì)偶對(duì)偶問題可能比原問題容易求解對(duì)偶問題還有很多理論和實(shí)際應(yīng)用的意義3.3.2

原問題與對(duì)偶問題的表達(dá)形式s.t.

3x1

2x2

204x1

3x2

10

x1

x2

5

例

3.13 原線性規(guī)劃問題maxf(x)

4x1

5x2

1 2 21 2 2

x

,

x

,

x

0x1

x2

x2

5

x1

x2

x2

5

4x

3x

3x

10s.t.化為(max,

)型問題maxf(x)

4x1

5x2

5x2

3x1

2x2

2x2

20

1 2 3 41 2 3 4w,w,w

,

w

0

2w

3w

w

w

5s.t.應(yīng)用標(biāo)準(zhǔn)型對(duì)偶變換規(guī)則minh(w)

20w1

10w2

5w3

5w43w1

4w2

w3

w4

42w1

3w2

w3

w4

5

1y

0,

y2

0,

y3

不限2y1

3y2

y3

53y1

4y2

y3

4s.t.

x2

不限,

x1

0令

y1

w1,y2

w2,y3

w3

w4經(jīng)整理得:min

g(

y)

20y1

10y2

5y33.3.3

非對(duì)稱形式的原-對(duì)偶問題的關(guān)系約束條件的類型與非負(fù)條件對(duì)偶

? 非標(biāo)準(zhǔn)的約束條件類型對(duì)應(yīng)非正常的非負(fù)條件 對(duì)偶變換是一一對(duì)應(yīng)的對(duì)偶變換的規(guī)則表原問題(max) 對(duì)偶問題(min)技術(shù)系數(shù)矩陣

A價(jià)值系數(shù)

C右端項(xiàng)

b第

i

行約束條件為

型第

i

行約束條件為

型第

i行約束條件為

=

型決策變量

xj

0決策變量

xj

0決策變量

xj

不限

技術(shù)系數(shù)矩陣

AT右端項(xiàng)

b價(jià)值系數(shù)

C對(duì)偶變量

yi

0對(duì)偶變量

yi

0對(duì)偶變量

yi

不限第

j

行約束條件為

型第

j

行約束條件為

型第

j

行約束條件為

=

型3.3.3

非對(duì)稱形式的原-對(duì)偶問題的關(guān)系3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)為了便于討論，下面不妨總是假設(shè):

X

0

AX

bs.t.maxz

CX原問題:

Y

0

YA

Cs.t.min

Yb對(duì)偶問題:00

Y

0

X

0容易看出有 Y0b

Y0AX0

CX0.1弱對(duì)偶定理定理

對(duì)偶問題(min)的任何可行解Y0，其目標(biāo)函數(shù)值

總是不小于原問題(max)任何可行解X0的目標(biāo)函數(shù)值z(mì)，即CX0≤

Y0

b證:

由于X0

,

Y0分別為原問題和對(duì)偶問題的可行解,故有

AX0

b

Y0A

C3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)弱對(duì)偶定理幾何意義弱對(duì)偶定理推論當(dāng)CX→∞時(shí)（無界解），則對(duì)偶問題無解當(dāng)Yb

→∞時(shí)（無界解），則原問題無解當(dāng)CX、

Yb有最優(yōu)解時(shí)，

CX0=

Y0bCXYb2

最優(yōu)解判別定理定理

若原問題的某個(gè)可行解X0的目標(biāo)函數(shù)值與對(duì)偶問題某個(gè)可行解Y0的目標(biāo)函數(shù)值相等，則X0,

Y0分別是相應(yīng)問題的最優(yōu)解證：由弱對(duì)偶定理推論，結(jié)論是顯然的。即CX0

=Y0b

CX, Y0b=CX0

Yb

。證畢。3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)3

主對(duì)偶定理(強(qiáng)對(duì)偶性、對(duì)偶定理）定理

如果原問題和對(duì)偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標(biāo)函數(shù)值相等。證：由弱對(duì)偶定理推論可知，原問題和對(duì)偶問題的目標(biāo)函數(shù)有界，故一定存在最優(yōu)解。現(xiàn)證明定理的后一句話。3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)主對(duì)偶定理的證明證：現(xiàn)證明定理的后一句話。設(shè)

X0為原問題的最優(yōu)解，它所對(duì)應(yīng)的基矩陣是

B，

X0=B

1

b，則其檢驗(yàn)數(shù)滿足

C

CBB

1A

0令

Y0=

CBB1，則有

Y0

A

C

；而對(duì)原問題松弛變量的檢驗(yàn)數(shù)有

0

CBB1I

0，即

Y0

0。顯然Y0為對(duì)偶問題的可行解。因此有對(duì)偶問題目標(biāo)函數(shù)值，

=g(Y0)=Y0b=CBB

1

b而原問題最優(yōu)解的目標(biāo)函數(shù)值為z=f(X0)=CX0=CBB

1

b故由最優(yōu)解判別定理可知Y0

為對(duì)偶問題的最優(yōu)解。證畢。該定理的證明告訴我們一個(gè)非常重要的概念：對(duì)偶變量的最優(yōu)解等于原問題松弛變量的機(jī)會(huì)成本。

即對(duì)偶變量的最優(yōu)解是原問題資源的影子價(jià)格

3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)問題：由此定理的可知，對(duì)偶問題的最優(yōu)解的表達(dá)式Y(jié)*=？——Y*=

CBB

1求Y*是否有必要重新的求解對(duì)問題？——不必，可能從原問題的單純表中獲得3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)例：min

=

5y1+y23y1+ y2

9y1+ y2

5y1+8y2

8y1,y2

0(P)maxZ=9x

+5x +8x1 2 33x1+x2+ x3

5x1+x2+8x3

1x1

,

x2

,

x3

0(D)3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)x1x2x3x4x5CBxB9580000x4x55131111810019580009x4x12101-21-23810-310-4-640-9(P)最優(yōu)解(0,

9,

0,

4,

64),

=

9 n=

3m=

2xn+i

yi

=0(i=1……m

)(i=1,2

)xj

ym+j

=0xjy2+j(j=1……n

)(j=1……3

)x3 y5x1 y3x4 y1x3+i yix2

y4x5 y23.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)其對(duì)偶解 y1﹡

=4/5 y2﹡

=3/5 Z﹡

=5用對(duì)偶理論求(P)的最優(yōu)解例：

min

=

2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5

42x1-x2+3x3+x4+x5

3xi

0(i=1…5

)(P)3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)解：(D)為①②③④⑤maxZ

=4y1+3y2y1+2y2

2y1-y2

32y1+3y2

5y1+y2

23y1+y2

3y1,y2

03.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)1 2將y

﹡

，y

﹡

代入，知②,

③,

④為嚴(yán)格不等式∴

x2=x3=x4=0由y1 ，y2 ﹥0知原約束為等式﹡ ﹡x1+3x5

=42x1+x5

=3∴

x=(1,0,0,0,1)T

Z=5 3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)4

互補(bǔ)松馳性定理

在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。即：n

若

aij

x

j

bi

,即xsi

0,則yi

0j

1因此一定有:xsi

yi

0(i

1,...,

m)n

1)若yi

0,則

aij

x

j

bi

,即xsi

0j

1m

m

2)若xi

0,則

aij

yi

c

j

,即ysj

0i

1若

aij

y

j

c

j

,即ysj

0,則xj

0i

1因此一定有:

ym

j

x

j

0(

j

1,...,

n)3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)

s

AX

Xs

bX,

X

0s.t.原問題:maxz

CXss.t.

對(duì)偶問題:min

YbT1 2 nXs

[xn

1,

xn

2

,

,

xn

m

]TX

[x

,

x

,

,

x ]

YA

Ys

CY,Y

0Y

[

y1,

y2

,

,

ym

]Ys

[

ym

1,

ym

2

,

,

ym

n

]3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)

Y

(

AX

b)

01

xn

m

而(

AX

b)

Xs

0 Y

0

xn

1

即:

[

y

ym

]

0則問題得證(i

1,...,

n)因此:

yi

xn

i

0證明：1）

YAX

C

X

YAX

Yb因此C

X

Y

AX

Yb而C

X

Yb

Y

A

C

AX

b3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)

m

n

]

m

1

xn

即:

[

y

y

0則問題得證(i

1,...,

n)

因此:

ym

i

xi

0證明：2）C

X

Y

AX

Yb

(Y

A

C)

X

0(Y

A

C)

Ys

0 X

0

x1

3.3.4

線性規(guī)劃對(duì)偶問題的基本性質(zhì)

b= CBB-1 = y對(duì)偶解y：b

的單位改變量所引起的目標(biāo)函數(shù)改變量。1

影子價(jià)格1、Z=

CBB-1b

+

(CN-

CBB-1

N)XN (*)Z=

Z(b) b為資源對(duì)(*)求偏導(dǎo)：

Z3.3.5

靈敏度分析2

對(duì)偶的經(jīng)濟(jì)解釋1)原始問題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問題xn

1xn

2

xn

1

c2

x2

a12

x2

a22

x2

xn

2

xn

mxn

mmax z

c1x1s.t. a11x1a21x1

am1x1

c2

xn

a1n

xn

a2nxn

amnxnxn

b1

b2

bm

0

am2

x2

x1

x2

單位產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）單位產(chǎn)品消耗的資源（噸/件）剩余的資源（噸）消耗的資源（噸）m mym

1 ym

2

ym

1

ym

2

ym

nym

nmin

b1

y1

b2y2

b

ys.t.

a21

y2

a11

y1a12

y1

a1n

y1y1

c1

c2

cn

0

am1

ym

a22

y2

am

2

ym

a2n

y2

amn

ymy2

ym

資源限量（噸）資源價(jià)格（元/噸）總利潤(rùn)（元）對(duì)偶問題是資源定價(jià)問題，對(duì)偶問題的最優(yōu)解y1、y2、...、ym稱為m種資源的影子價(jià)格（Shadow

Price）2)對(duì)偶問題原始和對(duì)偶問題都取得最優(yōu)解時(shí)，最大利潤(rùn)max

z=min

y2

對(duì)偶的經(jīng)濟(jì)解釋3

資源影子價(jià)格的性質(zhì)影子價(jià)格越大，說明這種資源越是相對(duì)緊缺影子價(jià)格越小，說明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0oi

zo 最大利潤(rùn)的增量yi

b

第i種資源的增量

第i種資源的邊際利潤(rùn)z

b1

y1

b2

y2

bi

yi

bm

ymz

z

b1

y1

b2

y2

(bi

bi)

yi

bm

ym

z

bi

yiy1y2ym4

產(chǎn)品的機(jī)會(huì)成本機(jī)會(huì)成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤(rùn)當(dāng)資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，可以買進(jìn)這種資源。a1jy1

a2jy2

aijyi

amjym增加單位資源可以增加的利潤(rùn)減少一件產(chǎn)品可以節(jié)省的資源s.t.a

2jx

j

a12

x

2

a

22

x

2max z

c1x1

c2

x

2

amnxn

xnam2

x

2

amjx

jx

2

x

ja1n

xn

b1a

2n

xn

b2

bm

0

a11x1a

21x1

am1x1x1

a1jx

j

c

jx

j

cnxn

機(jī)會(huì)成本利潤(rùn)差額成本b1

y1a11

y1a12

y1ym

1 ym

2min

s.t.

ym

1

c1

ym

2

c2

ym

nym

n

b2

y2

bm

ym

a21

y2

am1

ym

a22

y2

am

2ym

a1n

y1y1

cn

0

a2n

y2

amn

ymy2

ym

5

產(chǎn)品的差額成本（Reduced

Cost）ym

j

(y1a1j

y2a2j

ymamj)

cj

YPj

cj差額成本=機(jī)會(huì)成本—

利潤(rùn)6

互補(bǔ)松弛關(guān)系的經(jīng)濟(jì)解釋ji n

ij m

jm

j0

xn

i

0y

x

0

yi

x0

y

0

n

ii0

wm

j

0x y

0

xj

y0

x

0

在利潤(rùn)最大化的生產(chǎn)計(jì)劃中邊際利潤(rùn)大于0的資源沒有剩余有剩余的資源邊際利潤(rùn)等于0安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本等于利潤(rùn)機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn)以例3.1.1為例，求

原問題與對(duì)偶問題的最優(yōu)解

2 51x1,

x2

,

x3

,

x4

,

x5

0

x

7x

2x1s.t.

0x3

0x4

0x5

x2

x3

10x

x2

x4

8maxz

6x1

4x2

1 2 31 2 3y,y

,

y

0

2

y

y

y

42y1

y2

6s.t.

2x1,x2

0x

7

x

x

81 2s.t.原問題：maxz

6x1

4x2

2x1

x2

10原問題的標(biāo)準(zhǔn)形：對(duì)偶問題：min

10

y1

8

y2

7

y3以例1.1為例，求

原問題與對(duì)偶問題的最優(yōu)解序x1x2x3x4x5號(hào)CBXB B-1b64000

I0x310[2]11005初0x48110108始0x5701001解cj-zj

64000II6x1511/21/20010改0x430[1/2]-1106進(jìn)0x5701001解cj-zj

01-300III6x12103/2-10最0x2601-220優(yōu)解0 x5cj-zj

100002-1-2-210用單純形法解原問題的最優(yōu)解：以例1.1為例，求

原問題與對(duì)偶問題的最優(yōu)解III最優(yōu)解6x12103/2-100x2601-2200x51002-21cj-zj

00-1-20原問題最優(yōu)解：x1=2

; x2=6;maxz=6x1+4x2

=36銅資源的影子價(jià)格：1；

鉛資源的影子價(jià)格：2經(jīng)濟(jì)意義：當(dāng)銅、鉛分別增加工廠單位時(shí)，可使總收入分別是增加1、2對(duì)偶問題最優(yōu)解： y1=1; y2=2;

y3=0;minω=10x1+8y2+7y3

=362.4

對(duì)偶單純形法思路：(max型)單純形法：找基B，滿足B-1b

0，但

C

-

CBB-1

A不全

0，（即檢驗(yàn)數(shù)）。迭代保持B-1b

0，使C-CBB-1

A

0，即CBB-1

A

C對(duì)偶單純形法：找基B，滿足C-

CBB-1

A

0，但B-1b不全

0迭代保持C

-CBB-1

A

0，使B-1b

0例1：MaxZ=2X1

+X2X1+

X2

+ X3=

52X2

+ X3

54X2+6X3

9X1,X2,X3

0maxZ=2X1

+X2X1+ X2

+

X3 =

52X2+

X3+X4 =

5+X5

=-9-4X2

-6X3X1…X5

04121000X1X2X3X4X5100-1-200CBXB2X15111000X45021100X5-90(-4)-601XB31/400-1/20-1/42X111/410-1/201/40X41/200-211/21X29/4013/20-1/4對(duì)偶單純形法基本步驟 max型(min型)(1)、作初始表，要求全部σj

0

(

0)(2)、判定：

B-1

b全

0，停。否則，取max{ B-1

b }=(B-1

b)lB-1

b<0令第

l行的Xj

l為換出變量.(3)、確定換入變量① 若Xi

l行的alj

全

0，停，原問題無可行解。② 若Xi

l行的alj

有alj

<0

,則求θ=min{σj }=

σkaljalklja <0kX

為換入變量σkalk(4)、以alk

為主元，換基迭代

關(guān)于①的解釋：第

l

個(gè)方程(B-1b)l=xil+

aljxjj

N<即 xil=(B-1b)l-

alj

xj0 0 0某xj

從0↗

，xil不能變>0②為保持σj

0

，即對(duì)偶解可行性例2minZ=2X1+3X2

+4X3X1+2X2+X3

32X1-X2+3X3

4X1,X2,X3

0maxZ=-2X1-3X2-4X3-X1-2X2-X3+X4=-

3+X5=-

4-2X1+X2

-3X3X1…X5

0-2-3 -4 0 0XBX1X2 X3 X4 X50-2-3 -4 0 00X4-3-1-2 -1 1 00X5-4(-2)1 -3 0 140-4 -1 0 -10X4-10(-5/2) 1/2 1 -1/22X1211/2 3/2 0 -1/228/500 -9/5 -8/5 -1/5X22/501 -1/5 -2/5 1/5X111/510 7/5 -1/5 -2/5練習(xí)：maxZ=-X1-4X2

-3X4X1+2X2-X3+X4

3-2X1

- X2+4X3+X4

2X1…X4

0解最優(yōu)解：X=(7,0,4,0)TZ=

-7-1

-4

0

-3

0

0X1 X2X3 X4 X5 X6CBXB0-1 -40 -3 0 000X5X6-3-2(-1) -22 11 -1 1 0-4 -1 0 1CBXB-

30 -2-1 -2 -1 0-10X1X63-81 20 -3-1 1 -1 0(-2) -3 2 1CBXB-70 -1/20 -1/2 -2 -1/2-10X1X3741 7/20 3/20 5/2 -2 -1/21 3/2 -1 -1/2

對(duì)偶單純形法

單純形法解線性規(guī)劃問題的方法

如何用？求解線性規(guī)劃問題的方法與步驟：1、

把原問題化為標(biāo)準(zhǔn)型maxAX

bs

.tz

CX

找不到基X

02、找初始基

找到一個(gè)基

B ，轉(zhuǎn)第3步，轉(zhuǎn)第4步3、把問題寫成關(guān)于基B的典則形式若對(duì)應(yīng)的基本解可行，

即B

1b

0

，用單純形法若對(duì)應(yīng)的基解不可行，

存在檢驗(yàn)數(shù)

0，對(duì)偶單純形法，轉(zhuǎn)第4步4、增加人工變量，用大M法或兩階段法求解 即B

1b

0

檢驗(yàn)數(shù)均

0

2 3

12 31 3321x

x

2s.t

x

2x

5

x

，x

，x

0例求min

Z

4x

3x

8x

2 3 4 5

12 3 511 2 3

2x

x

5x

x3

x4

2s.t

x

x

，x

，x ,

x ,

x

0標(biāo)準(zhǔn)型為maxZ

4x

3x

8x

1 2 3 4 5

2x3

x5

5

x1

x3

x4

2若取初始基

B1

P4，P5

則關(guān)于B1的典則形式為maxZ

4x1

3x2

8x3x

，x

，x ,

x ,

x

0對(duì)應(yīng)B1的基本解：X

0，0，0，

2，

5

1檢驗(yàn)數(shù)全部≤0可用對(duì)偶單純形法求解不s可.t

行

x2若取初始基

B2

P1，P2

則關(guān)于B2的典則形式為

1 2 3 4 52 3 513 4 5

2x

x

5x

x3

x4

2s.t

xmaxZ

18x

4x

3x對(duì)應(yīng)B2的基本解2X

2，5，0，0，0

用單純形法求解

x

，x可，行x ,

x ,

x

03.3.5

線性規(guī)劃的靈敏度分析線性規(guī)劃是靜態(tài)模型參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu)哪些參數(shù)容易發(fā)生變化C,

b,

A,

我們主要討論C，b和變量結(jié)構(gòu)發(fā)生變化時(shí)對(duì)解的影響每個(gè)參數(shù)發(fā)生多大的變化最優(yōu)解或最優(yōu)基不變？影響解的最優(yōu)性——σ

≤0影響解的最優(yōu)性——B

1

b

保證非負(fù)即可原始數(shù)據(jù)A，b，CA=(P1 P2…Pn

)公式① Z0=

CBB-1b XB=

B-1b②σA=C-

CBB-1

A σN=CN-CBB-1

Nσj=Cj-CBB-1

Pj③ A=B-1

APj=B-1

Pj標(biāo)準(zhǔn)型 maxZ=CXAX

=bX

0B-1

b B-1ACBB-1b C-CBB-1

A3.3.5

靈敏度分析靈敏度分析的步驟可歸納如下：將參數(shù)的改變計(jì)算反映到最終單純形表上來：檢查原問題是否仍為可行解；檢查對(duì)偶問題是否仍為可行解；按表所列情況得出結(jié)論和決定繼續(xù)計(jì)算的步驟原問題對(duì)偶問題結(jié)論或繼續(xù)計(jì)算步驟可行解可行解最優(yōu)基不變可行解非可行解用單純形法繼續(xù)求最優(yōu)解非可行解可行解用對(duì)偶單純形法求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新單純形重新計(jì)算(1)、參數(shù)A，b，C在什么范圍內(nèi)變動(dòng)，對(duì)當(dāng)前方案無影響？(2)、參數(shù)A，b，C中的一個(gè)(幾個(gè))變動(dòng)，對(duì)當(dāng)前方案影響？(3)、如果最優(yōu)方案改變，如何用簡(jiǎn)便方法求新方案？例：產(chǎn)品原料ABC備用資源甲11112乙12220利潤(rùn)586問：如何安排產(chǎn)品產(chǎn)量，可獲最大利潤(rùn)？ maxZ=5X1+8X2

+6X3+X5

=20X1+ X2

+X3+X4 =

12X1+2X2+2X3X1…X5

0解58600X1X2X3X4X5CBXB0586000X412111100X52012201…CBXB8400-2-2-35X141002-18X28011-112.4.1

價(jià)值系數(shù)

cj

的靈敏度分析cj

變動(dòng)可能由于市場(chǎng)價(jià)格的波動(dòng)，或生產(chǎn)成本的變動(dòng)cj

的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj

允許的變動(dòng)范圍

cjcj

的變化只會(huì)引起檢驗(yàn)數(shù)的變化，有兩種情況非基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，不影響其它檢驗(yàn)數(shù)基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)cj

是非基變量xj

的價(jià)值系數(shù)的靈敏度分析要保持

(c

c)

C B

1P

0j j B j故有

c

(c

C B

1P

)j j B j(一)、目標(biāo)函數(shù)系數(shù)Cj的靈敏度分析(1)、非基變量系數(shù)Cj① Cj

改變，

σj仍

0

時(shí)對(duì)最優(yōu)方案無影響。假設(shè)C3發(fā)生變化，3 j B j

C B

1P)

2B j要保持

(c

c)

C B

1P

0故有

c3

(cj則c3

8時(shí)最優(yōu)解不變.② C3改為10，σ3

=2>0CBXB8400(2)-2-358X1X24810010(1)2-1-11XB1000-200-5510X1X3481001012-1-11由于基變量對(duì)應(yīng)的價(jià)值系數(shù)

cj

在CB中出現(xiàn)，因此它會(huì)影響所有非基變量的檢驗(yàn)數(shù)所有非基變量的檢驗(yàn)數(shù)σi

i

ci

(c1,...,

c

j

cj

,...,

cm

)B

1

Pi應(yīng)有所有的

i

0解得

cj(2)、基變量系數(shù)Cj例中C1改變?chǔ)褹

=C

-CBB-1

A=(C1,8,6,0,0)-(C1

8)1 0 0 2 -10 1 1 -1

1=(0,0,-2,-2C1+8,C1-8)

0-2C1+8

0C1-8

014

C

8(二)、約束條件右端項(xiàng)

bj

的靈敏度分析(1)、bj

改變，

B-1

b仍

0時(shí)，最優(yōu)方案不變。例中b1改變2 -1-1 1b120

10

b1

20B-1

b=

02b1-20

01-b+20

0(2)、

b1改變,

b1=30

，CBXB12000-2-2-358X1X240-101001012(-1)-111000-2-40-550X1X2010102-12-1011-14-1

1 202 -1 30B-1

b==40-10(三)、添加新變量的靈敏度分析例

對(duì)于新產(chǎn)品D，已知1個(gè)單位D要消耗甲：3 乙：2 可以得利潤(rùn)10問：投產(chǎn)產(chǎn)品D是否有利？

6

=C6-CBB-1P6=10

-

(5 8) 2 -1 3-1 1 2=10-12=-2<

0結(jié)論：無利（1）利潤(rùn)為多少時(shí)，投產(chǎn)產(chǎn)品D有利？

6

=C6-CBB-1P6=C6-

12

>0 得C6

>12（2）C6

=15

時(shí)

6

=3P’6=B-1

P6

= 2-1-1 3 = 41 2 -1X1X2X3X4X5X6XB8400-2-2-33X141002-1(4)X28011-11-187-3/40-2-7/2-9/40X611/400-1/2-1/41X291/411-1/23/40(四)、添加新約束的靈敏度分析增加一個(gè)約束條件在實(shí)際問題中相當(dāng)增添一道工序。分析的方法是先將原問題最優(yōu)解的變量值代入新增的約束條件，如滿足，說明新增的約束末起到限制作用，原最優(yōu)解不變。否則，將新增的約束直接反映到最終單純形表中再進(jìn)一步分析。例

新增加電力約束：13A、B、C每單位需電 2、1、3問：原方案是否改變？

2X1

+X2

+3X3

13原方案 A：4 B：8 C：016>13 原方案要改變2X1+X2+3X3+X6=

13XB8400-2-2-3 0X141002-10X2X6813021113-101001XB8400-2-2-3 0580X1X2X648-31000100122-1(-3)-1 01 01 18200-10/30 -11/3 -2/3580X1X22910014/31/300-1/3 2/32/3 -1/3X4100-2/31-1/3 -1/3………

…(五)、aij改變aij的變化使線性規(guī)劃的約束系數(shù)矩陣A發(fā)生變化。若變量人在最終單純形表中為非基變量，其約束條件中系數(shù)aij的變化分析步驟可參照本節(jié)之三；若變量xj在最終單純形表中為基變量，則aij的變化將使相應(yīng)的B和B-1發(fā)生變化，因此有可能出現(xiàn)原問題相對(duì)偶問題均為非可行解的情況。出現(xiàn)這種情況時(shí)，需引進(jìn)人工變量將原問題的解轉(zhuǎn)化為可行解，再用單純形法求解，下面舉例說明。(計(jì)劃生產(chǎn)的產(chǎn)品工藝結(jié)構(gòu)改變)、非基變量Xj工藝改變只影響單純形表Pj

列，

j

.關(guān)鍵看

j

0?還是>0?

. 用(三)類似方法解決(添加新變量的方法。、基變量Xj工藝改變，復(fù)雜例：產(chǎn)品A工藝改變，對(duì)甲、乙需求變?yōu)?，2。利潤(rùn)為7，問最優(yōu)方案如何？先計(jì)算 p1’= 2-12=2-1120

1’=

-3取代 p1

與λ1

放入最優(yōu)表X1X1’X2X3X4X50-30-2-2-3X1412002-1X280011-117800-21-3/27X1’21001-1/28X28011-1180-10-20-10X421001-1/28X210111 0 1/2也可能

B-1

b出現(xiàn)負(fù)數(shù)檢驗(yàn)數(shù)與基變量均不滿足最優(yōu)解要求例 p1’

= 1C1’=

732 -1 1 = -1-1

1

3

21

’=

-4p一’=B-1p’

=1 1一-MX1’ X2X3X4X5X6-4 0-2-2-3X14-1 002-1X282 11-110 0-2-101X1’-41 00-21X2160 113-1X1’-2X4+X5=

-4-X1’+2X4-X5+X6=

4-M+7 0-22M-24 -M+8 0X64-1 00(2) -1 1X2160 113 -1 0-5 0-20 -4 -M+12X42-1/2 001 -1/2 1/2X2103/2 110 1/2 -3/22.4.1

價(jià)值系數(shù)

cj

的靈敏度分析cj

變動(dòng)可能由于市場(chǎng)價(jià)格的波動(dòng)，或生產(chǎn)成本的變動(dòng)cj

的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj允許的變動(dòng)范圍

cjcj的變化只會(huì)引起檢驗(yàn)數(shù)的變化，有兩種情況非基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，不影響其它檢驗(yàn)數(shù)基變量對(duì)應(yīng)的價(jià)值系數(shù)變化，影響所有非基變量檢驗(yàn)數(shù)1 cj

是非基變量xj

的價(jià)值系數(shù)的靈敏度分析要保持

(c

c)

C B

1P

0j j B j故有

c

(c

C B

1P

)j j B j例2.4.2x1x2x3x4x5x6x7CBXBb15340000x51001/40-13/4011/4-14x420020-2101-15x2100-3/4111/400-3/4113004.2555.75400.251cj-zj-3.250-2.7500-0.25-1x1,

x3為非基變量所以

c1

3.25,

c1

4.25

c3

2.75,

c3

5.752 cj

是非基變量xj

的價(jià)值系數(shù)的靈敏度分析由于基變量對(duì)應(yīng)的價(jià)值系數(shù)

cj 在CB中出現(xiàn)，因此它會(huì)影響所有非基變量的檢驗(yàn)數(shù)所有非基變量的檢驗(yàn)數(shù)σi

i

ci

(c1,...,

c

j

cj

,...,

cm

)B

1

Pi應(yīng)有所有的

i

0解得

cjσ6,σ7 ≤0求出設(shè)x4的價(jià)格系數(shù)增加

c4，由所有非基變量σ1,

σ3,的

c4變化范圍即可CB XB bx1 x2 x3 x4 x5 x6 x71 5 3 4 0 0 00 x5 100 1/4 0 -13/4 0 1 1/4 -14 x4 200 2 0 -2 1 0 1 -15 x2 100 -3/4 1 11/40 0 -3/4

11300cj-zj4.25-3.255 5.750 -2.754 0 0.25 10 0 -0.25

-124457744456425)

(1

/

4

215)

(

1

1

0

(01 5 4 4

1

(0

1 1)T1)T

02 1

3/

4)T5)

(1/

4 1

3

/

4)T

05)(

13

/

4

2 11

/

4)T

02

3/

4)T

3

/

4)T

04

c4c)(

1c

c6

0

(0 4

cc)(1/

4c

cc2)(

13

/

4

2 11/

4)Tc4

c44

c44

c

c

(c

c

(c

3

c3

(c5

3

(0

c

(c c

c c)(1/4解得：

c4≥-13/8；

c4≤11/8

；

c4≥-1/4；

c4≤

1取公共解得：-1/4≤

c4

≤12.4.3

資源向量

bi

的靈敏度分析

設(shè)XB=B

1b是最優(yōu)解，則有XB=B

1b

0b的變化不會(huì)影響檢驗(yàn)數(shù)b的變化量

b可能導(dǎo)致原最優(yōu)解變?yōu)榉强尚薪鈘 rr

b

0解出

b

的范圍即可b1只要由X

B-1b

B

1

b

bm

0

0

r

r

r

r

bm

b1

bm

b

B

1

b

B

1

b

0b1X

B-1b

B

1

b以b2為例,

假設(shè)b2的增量是△b2，所以有x1 x2 x3 x4 x5 x6 x7CB XB b1 5 3 4 0 0 00x51001/40-13/4011/4

-14 x4 200 2 0 -2 1 0 1 -15 x2 100 -3/4 1 11/4