運(yùn)籌學(xué)題9787302102144課件

第1章第2章第3章第4章1清華大學(xué)出版社線性規(guī)劃與單純形法對(duì)偶理論與靈敏度分析運(yùn)輸問(wèn)題目標(biāo)規(guī)劃第1節(jié)單純形法的矩陣描述2清華大學(xué)出版社第2節(jié)第3節(jié)第4節(jié)第5節(jié)第6節(jié)第7節(jié)改進(jìn)單純形法

對(duì)偶問(wèn)題的提出線性規(guī)劃的對(duì)偶理論對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格對(duì)偶單純形法靈敏度分析第8節(jié)*參數(shù)線性規(guī)劃3清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述設(shè)線性規(guī)劃問(wèn)題可以用如下矩陣形式表示：目標(biāo)函數(shù)max

z=CX約束條件

AX≤b非負(fù)條件

X≥04清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述將該線性規(guī)劃問(wèn)題的約束條件加入松弛變量后，得到標(biāo)準(zhǔn)型：max

z=CX+0XsAX+IXs=bX，X

s≥0其中I

是m×m單位矩陣。5清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述若以Xs為基變量，并標(biāo)記成XB，可將系數(shù)矩陣（A，I）分為（B，N）兩塊。B是基變量的系數(shù)矩陣，N是非基變量的系數(shù)矩陣。并同時(shí)將決策變量也分為兩部分：相應(yīng)地可將目標(biāo)函數(shù)系數(shù)C分為兩部分：CB和CN，分別對(duì)應(yīng)于基變量XB和非基變量XN，并且記作C=（CB,

CN）

N

XB

X

=

X6清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述若經(jīng)過(guò)迭代運(yùn)算后，可表示為：基變量相應(yīng)有非基變量：XXNB

X

XN=

S2

1

;

X

XB=

S1

1

可包含原基變量和松弛變量松弛變量：X=

1

fi

S2

X

XS

2

基變量非基變量

N1

B

系數(shù)矩陣A

=

;其中N

=

;N

SS7清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述線性規(guī)劃問(wèn)題可表示為：+

S2

XS2(

2

-

2

)(

3

-

2

)BXB

+

NXN=

bXB

,

XN

?

0=

BXB

+

N1

XN1(

2

-1)max

z

=

CB

XB

+

CN

XN=

CB

XB

+

CN

XN

+

CS

XS1

1

2

2非負(fù)條件約束條件目標(biāo)函數(shù)8清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述將（2-2）式移項(xiàng)及整理后得到：BX

B

=

b

-

N1

X

N

-

S2

X

S

;1

2X

=

B

-1b

-

B

-1

N

X

-

B

-1S

X

;B

1

N1

2

s2目標(biāo)函數(shù)：z

=

C B

-1b

+

(

C

-

C B

-1

N )

XB

N1

B

1

N1+

(

C

-

C B

-1

I

)

XS2

B

S9清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述令非基變量=0，由上式得到：-1目標(biāo)函數(shù)的值

z

=

CBB

b0

B-1bX

(

1

)

=

;

基可行解10清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述（1）非基變量的系數(shù)表示為：-

1(

C

N

-

C

B

B N

1

)1對(duì)應(yīng)已用的檢驗(yàn)數(shù)符號(hào)c

j

-

z

j

(

j

=

1

,2

,

,

n

)檢驗(yàn)數(shù)也可表示為：-1

-1C

-C

B

B A

與-C

B

B第1節(jié)

單純形法的矩陣描述（2）θ規(guī)則表示為：RHS值 表示選用>0的分量換入變量的系數(shù)向量j

i

i

j

ij

i

i

(

B-1P

)(

B-1b

)(

B

P

)-1-1=(

B

P

)

>

0

(

B-1b

)q

=

min11清華大學(xué)出版社12清華大學(xué)出版社第1節(jié)

單純形法的矩陣描述(

2

-

7

)B-1bXN11C

-

C B-1NN

B1

XN

（3）單純形表與矩陣表示的關(guān)系

-

z

B

-

C

B

b-1=

B

1

2

X

B0

10-

C B-1B-1B-1N第1節(jié)

單純形法的矩陣描述單純形表中的數(shù)據(jù)基變量非基變量等式右邊XBXNXsRHS系數(shù)矩陣B-1B=1B-1N1B-1B-1b檢驗(yàn)數(shù)0C

-C

B-1NN1

B

1-C

B-1B-C

B-1bB13清華大學(xué)出版社14清華大學(xué)出版社小結(jié)掌握矩陣的運(yùn)算；理解基矩陣的作用；了解矩陣運(yùn)算與單純表的關(guān)系。15清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法求解線性規(guī)劃問(wèn)題的關(guān)鍵是計(jì)算B-1

，以下介紹一種比較簡(jiǎn)便的計(jì)算B-1的方法。16清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法設(shè)m·n系數(shù)矩陣為A，求其逆矩陣時(shí)，可先從第1列開(kāi)始。mm

aa

a

m1

m

2a2m

a1m

a11

a12A

=

a21

a22第2節(jié) 改進(jìn)單純形法以a11為主元素,進(jìn)行變換(1)1

/

aa

m1 11

-

a /

a

1111211

a1P

=11-

a /

a21

x

=

1m

a

主元素17清華大學(xué)出版社18清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法然后構(gòu)造含有（1）列，而其他列都是單位列的矩陣11E

=-

am1

/

a11-

a21

/

a111/

a11

0

01第2節(jié) 改進(jìn)單純形法可得到mm

E

P

=

;E

A

=(1)2m1m

a(1)m2a(1)a(1)

a

a(1)

a(1)

121

1

1001

00122

1122

12

aa211121 11

aa21a

-

aa

-

a19清華大學(xué)出版社20清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法a(

1

)22而后以第2列的 為主元素，進(jìn)行變換(

2)/

a(1)

(1)1/

a(1)2222P(1)

12 22

m2 22

-a-a(1)

/

a(1)

x

=21清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法1

0

0

0

01

E2

=

2212

221

/

a(

1

)-

a(

1

)

/

a(

1

)m2

22-

a(

1

)

/

a(

1

)然后構(gòu)造含有（2）列，而其他列都是單位列的矩陣可得到mm

E

E

A

=(

2

)1m2m

a(

2

)

a(

2

)

a(

2

)m3a(

2

)a(

2

)

a13232

1

01

0

0

10

22清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法重復(fù)以上的步驟，直到獲得11

=

A-1m

2

1E

E

E

A

=

1可見(jiàn)En…E2E1=A-1。用這方法可以求得單純形法的基矩陣B的逆矩陣B-123清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法以例1為例進(jìn)行計(jì)算。max

z

=

2x1

+

3x2

+

0x3

+

0x4

+

0x5x1

+

2x2

+

x3

=

84x1

+

x4

=

164x2

+

x5

=

12第2節(jié) 改進(jìn)單純形法第1步：確定初始基，初始基變量;確定換入，換出變量（1）確定初始基和初始基變量：（2）計(jì)算非基變量的檢驗(yàn)數(shù)，確定換入變量。

5

4

0

3

4

501

1

x

x3

1

;

X

=

xB

=

(P

, P

, P

)=

B=

(2,=

(2,3)對(duì)應(yīng)(x1

,x2

)換入變量0

1

2B0

0

01

0

40

4

0

0N0

N0(

注意：N

=

(P

,P

))B-1Ns

=

C

-

C

0

1

21

03)-(

0,0,0

)

0

1024清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法(3)確定換出變量表示選擇>0的元素504

0

2(B P

)(B

b)0

2

i0

i

2=min

8

,16

,12

=3

對(duì)應(yīng)x

B-1P

>

0-1-1q

=

min25清華大學(xué)出版社26清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法（4）基變換計(jì)算將新的基

(P3

,P4

,P2)

單位矩陣。計(jì)算：1

/

4

-

1

/

2

-

1

/

2

10

；構(gòu)造

E1

=

1

0

1

/

4

x1

=

4

2

P2

=

0

主元素1

/

4

-1

/

2

=

11

1

/

4

-1

/

211=-1-11

011

01

0=

E

B1B27清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法（5）計(jì)算非基變量的系數(shù)矩陣（6）計(jì)算RHS=

4

01

/

4

1

-1

/

2

1

4

1

/

4

-1

/

2

1

1

1

1-11

01

1N

=

B1N

=

4

3

2

16

=

161

/

4

12-1

/

2

8

1-11

01B b

=28清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法價(jià)值系數(shù)C

=NBTN1非基變量X111

5(C

,C

)=

((

0,0,3

),(

2,0

))=

(x

,x

)

;第1步計(jì)算結(jié)束后的結(jié)果基B1

=(P3

,P4

,P2

);基變量

X

B

=

(x3,x4

,x2

)

;T1第2節(jié) 改進(jìn)單純形法計(jì)算非基變量的檢驗(yàn)數(shù)，確定換入變量(注意：N1

=(P1

,P5

))=

(2,-3

/4)對(duì)應(yīng)(x1

,x5

)換入變量11

/

4

0

1N1s

=

C

-

C

B-1NN1

B1

1

0

4

0

01

0

-1

/

2

1

010=

(2,

0)-(

0,0,3

)

029清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法確定換出變量(B P

)(B

b)130清華大學(xué)出版社=2

對(duì)應(yīng)x42

16

3>

01

11

i

1

1

i,

,0

B

P-1

1=

min-1-1q

=

min31清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法由此得到新的基B2

=

(P1

,

P4

,

P2

)

0201

0

02

121

/

4

1 0

0

10

0 1

/

4

1

0

-

1

/

2

=

-

4

10=

E B

-1

=

-

4B

-1主元素

1

P1

=

4

0

x2

1

=

-

4

0

E

2

=

1

0

-

4

1

0

00

0

1

100

10-

1

/

2

32清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法計(jì)算RHS

3

216

=

8

02-121

/

4

12

1

0

-1

/

2

8

10B b

=

-

433清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法第2步計(jì)算結(jié)束后的結(jié)果基B2

=(P1

,P4

,P2

);BTTB2基變量X22N23

5C

,CN

)=

((

2,0,3

),(

0,0

))=

(x

,x

)

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

=(非基變量X1

4

2=

(x

,x

,x

)

;第2節(jié) 改進(jìn)單純形法第3步：計(jì)算非基變量（x3,x5）的檢驗(yàn)數(shù)(注意：N2=(P3

,P5

))=

(0,=(-2,

1

/4)對(duì)應(yīng)(x3,x5

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

換入變量B2

2

21

/

4

0

1N2N2B-1Ns

=

C

-

C

0

1

0

-1

/

21

0

-

4

1

3

0

000)-(

2,0,3

)34清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法確定換出變量435清華大學(xué)出版社=4

對(duì)應(yīng)x2

8

3>

02

52P

)(B(B

b)2

5

i,

,B

P-1i-1-1

-1

/

2

2 1

/

4

=

minq

=

min36清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法新的基B3

=

P1

,

P5

,

P2

);換入變量x5

的系數(shù)向量是

1/

4

2

fi

主元素

0

=

1/

4

1

02

1

0

-1/

2

0

-1/

210-12

5B

P

=

-

437清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法計(jì)算B的逆矩陣

33

1

/

4

0=

0 1

/

2

0

0

-1

/

8

1

-1

/

8

1

/

4

1x

=

1

/2

構(gòu)造E001

0

01

/

2=

-

2 1

/

2

1-1

/

81

/

4

1 1

/

4

0

1

0

-1

/

2

=

0 1

/

2

0-

4

1

2-1

/

8

0

0 1

/

4B-1

=

E

B-13

3

238清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法計(jì)算非基變量的檢驗(yàn)數(shù)=

(P3,P4

)已無(wú)正檢驗(yàn)數(shù)0

0

01

0

13N3s

=C

-C B-1N

注意：NN3

B3

3

3

1

/

2=

(-

3

/

2,

-1

/

8)

0 1

/

4

01

0-

2 1

/

2-1

/

8=

(0,

0)-(

2,0,3

)39清華大學(xué)出版社第2節(jié) 改進(jìn)單純形法得到最優(yōu)解：

2

=

4

4

目標(biāo)函數(shù)的最優(yōu)值為：

121/

216

0

1/

4 8

1/

2-1/

8-13

2

5*

x

x1

X

=

x

=

B b

=

-

2=

14

2

4-12,0,3B

3z*

=

C

B b

=

(

)

440清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出什么是對(duì)偶？對(duì)同一事物（或問(wèn)題），從不同的角度（或立場(chǎng)）提出相對(duì)的兩種不同的表述。例如：在平面內(nèi)，矩形的面積與其周長(zhǎng)之間的關(guān)系，有兩種不同的表述方法。周長(zhǎng)一定，面積最大的矩形是正方形。面積一定，周長(zhǎng)最短的矩形是正方形。這種表述有利于加深對(duì)事物的認(rèn)識(shí)和理解。線性規(guī)劃問(wèn)題也有對(duì)偶關(guān)系。41清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出對(duì)第1章例1從對(duì)偶的角度進(jìn)行表述。假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品Ⅰ、Ⅱ，而將其所有資源出租或外售。這時(shí)工廠的決策者就要考慮給每種資源如何定價(jià)的問(wèn)題。設(shè)用y1，y2，y3分別表示出租單位設(shè)備臺(tái)時(shí)的租金和出讓單位原材料A，B的附加額。他在做定價(jià)決策時(shí)，做如下比較：若用1個(gè)單位設(shè)備臺(tái)時(shí)和4個(gè)單位原材料A可以生產(chǎn)一件產(chǎn)品Ⅰ，可獲利2元，那么生產(chǎn)每件產(chǎn)品Ⅰ的設(shè)備臺(tái)時(shí)和原材料出租或出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品Ⅰ的利潤(rùn)，這就有

y1+4y2≥242清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出對(duì)第1章例1從對(duì)偶的角度進(jìn)行表述。同理將生產(chǎn)每件產(chǎn)品Ⅱ的設(shè)備臺(tái)時(shí)和原材料出租或出讓的所有收入應(yīng)不低于生產(chǎn)一件產(chǎn)品Ⅱ的利潤(rùn)，這就有2y1+4y3≥3把工廠所有設(shè)備臺(tái)時(shí)和資源都出租或出讓?zhuān)涫杖霝閣

=

8y1+16y2+12y3從工廠的決策者來(lái)看當(dāng)然w愈大愈好；但受到接受方的制約，從接受者來(lái)看他的支付愈少愈好，所以工廠的決策者只能在滿足大于等于所有產(chǎn)品的利潤(rùn)條件下，提出一個(gè)盡可能低的出租或出讓價(jià)格，才能實(shí)現(xiàn)其原意，為此需解如下的線性規(guī)劃問(wèn)題：43清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出稱(chēng)這個(gè)線性規(guī)劃問(wèn)題為例1線性規(guī)劃問(wèn)題(這里稱(chēng)為原問(wèn)題)的對(duì)偶問(wèn)題。這就是從另一角度提出的線性規(guī)劃問(wèn)題。min

w=8y1+16y2+12y3y1+4y2

≥22y1

+4y3≥3yi≥0，i=1,2,3(2-8)44清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出進(jìn)一步來(lái)討論它們之間的關(guān)系。從第1節(jié)得到檢驗(yàn)數(shù)的表達(dá)式是CN?CBBN-1與?CBB-1由第1章已知：當(dāng)檢驗(yàn)數(shù)CN?CBBN-1≤0?CBB-1≤0(2-9)(2-10)時(shí)，表示線性規(guī)劃問(wèn)題已得到最優(yōu)解。這也是最優(yōu)解的判斷條件。45清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出現(xiàn)在討論這兩個(gè)條件。(1)

由于(2-9)式，(2-10)式中都有乘子CBB-1，稱(chēng)它為單純形乘子，用符號(hào)Y=CBB-1表示。由(2-10)式，得到Y(jié)≥0(2)

對(duì)應(yīng)基變量XB的檢驗(yàn)數(shù)是0，CB?CBB-1B=0。包括基變量在內(nèi)的所有檢驗(yàn)數(shù)可用C?CBB-1A≤0表示。從此可得C?CBB-1A=C?YA≤0，移項(xiàng)后，得到Y(jié)A≥C(3)

Y由(2-10)式，得到?

Y=

?

CBB-1將(2-11)式兩邊右乘b，得到?

Yb=

?

CBB-1b(2-11)(2-12)Yb=CBB-1b=z，因Y的上界為無(wú)限大，所以只存在最小值。46清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出現(xiàn)在討論這兩個(gè)條件。(4)

從這里可以得到另一個(gè)線性規(guī)劃問(wèn)題min

w=YbYA≥CY≥0稱(chēng)它為原線性規(guī)劃問(wèn)題｛maxz=CX｜AX≤b，X≥0｝的對(duì)偶規(guī)劃問(wèn)題。47清華大學(xué)出版社第3節(jié)

對(duì)偶問(wèn)題的提出對(duì)偶規(guī)劃問(wèn)題目標(biāo)函數(shù)：y

,

y ,

y

?

o

1

2

3+

4

y3

?

3?

2

Y

=

(y1

,

y2

,

y3

)Y

?

0

?

(2,3)

0

4Y

4

0

1

221

2

y1

y

+

4

y3min

w

=

Y

(8,16,12)T

min

w

=

8

y

+16

y

+12

y1

2約束條件：48清華大學(xué)出版社第4節(jié)

線性規(guī)劃的對(duì)偶理論原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系對(duì)偶問(wèn)題的基本性質(zhì)49清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系原問(wèn)題（LP）：max

z

=

c1

x1

+

c2

x2

+

+

cn

xnx1

,

x2

,

,

xn

?

02

m

b

b1

=

n

mnm1

m

2

ax

x

x1

a1n

a

a

a11

a12

50清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系對(duì)偶問(wèn)題(DP)min

w

=

y1b1

+

y2b2

++

ymbmy1,

y2

,,

yn

?

0mn

m

2m11

2

m

a

a11a

a

?

(c1,

c2

,,

cn

)a12

a1n

(y

,

y

,,

y

)4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系標(biāo)準(zhǔn)型原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系x

jyix1x2xn原關(guān)系min

wy1y2a11a21a12a22a1na2n￡￡b1b2ymam1am

2amn￡bm對(duì)偶關(guān)系???maxz

=min

wmaxzc1c2cmn51清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系例2

根據(jù)表2-3寫(xiě)出原問(wèn)題與對(duì)偶問(wèn)題的表達(dá)式xyx1x2x2y1111y2222y3888c44452清華大學(xué)出版社53清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系下列形式的變換關(guān)系為對(duì)稱(chēng)形式對(duì)偶問(wèn)題(DP)min

w

=

8

y1

+16

y2

+12

y3y1

,

y2

,

y3

?

0x1

,

x2

?

0￡

164x2

￡

12原問(wèn)題（LP）max

z

=

2x1

+

3x2

x1

+

2x2

￡

81

31

2

2

y

+

y

?

3

y

+

4

y

?

214x54清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系非對(duì)稱(chēng)形式的變換關(guān)系原問(wèn)題的約束條件中含有等式約束條件時(shí)，按以下步驟處理。設(shè)等式約束條件的線性規(guī)劃問(wèn)題為x?

0,

j

=

1,2,

,n=

bi

, i

=

1,2,mjnaij

x

j

j=1nmax

z

=

cj

x

jj=1554.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系清華大學(xué)出版社(2

-13)(2

-14)-nj=1aij

x

j

￡

-b i

=

1,2,,mi

=

1,2,m

nj=1aij

x

j

￡

b j

=

1,2,,mnaij

x

j

?

bj=1j

=

1,2,,mjnaij

x

j

=

bi

,

j=1x

?

0,

j

=

1,2,,nn非對(duì)稱(chēng)形式的變換關(guān)系第一步：先將等式約束條件分解為兩個(gè)不等式約束條件max

z

=

cj

x

jj=1清華大學(xué)出版社56原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系非對(duì)稱(chēng)形式的變換關(guān)系第二步：按對(duì)稱(chēng)形式變換關(guān)系可寫(xiě)出它的對(duì)偶問(wèn)題

設(shè)yi′是對(duì)應(yīng)(2-13)式的對(duì)偶變量，yi″是對(duì)應(yīng)(2-14)式的對(duì)偶變量，i=1,2,…，m(-

b

y

)i

=

1,2,mb

y

+min

w

=i

im''(-

aij

yi

)'maij

yi

+

y'

,

y''

?

0,?

c

j

,

j

=

1,2,n

i=1i=1m

m''i

i'i

i

i=1

i=1574.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系?

0i=1i

iy'

,

y'''

''i

iimi=1j''i'ij

i-

ya

(y

)?

c

, j

=

1,2,

,n''i'i

i-

yb

(y

)min

w

=將上述規(guī)劃問(wèn)題的各式整理后得到m,令y

=

(y

-

y

)

y

i

maij

yi為無(wú)約束，i

=1.2.

,m?

c

j

, j

=

1,2,

,nm

i=1min

w

=

bi

yii=1清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系RHS00約束條件

RHS目標(biāo)函數(shù)變量系數(shù)無(wú)約束約束條件變量

目標(biāo)函數(shù)變量的系數(shù)

約束條件的

變

量?

0￡

0

m

個(gè)

=

?

￡

件

束

條n

個(gè)

約?￡=

無(wú)約束

n

個(gè)?

0￡

0m

個(gè)綜合上述，線性規(guī)劃的原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系克表示為：原問(wèn)題 對(duì)偶問(wèn)題目標(biāo)函數(shù)

max

z

目標(biāo)函數(shù)

min

w58清華大學(xué)出版社59清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系例3試求下述線性規(guī)劃原問(wèn)題的對(duì)偶問(wèn)題min

z

=

2x1

+

3x2

-

5x3

+

x4

x1

+

x2

-

3x3

+

x4

?

5x4無(wú)約束342

3x

+

x

+

x

=

62(3)

y(2)

y(1)

y11

3

4x1

￡

0,

x2

,x3

?

0,2x

+

2x

-

x

￡

460清華大學(xué)出版社4.1

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系由表2-4中原問(wèn)題和對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系，可以直接寫(xiě)出上述問(wèn)題的對(duì)偶問(wèn)題，2

3131

y

1

?0

, y

2

￡

0

, y3

無(wú)約束

-

3

y

1

+

2

y

2+

y

￡

3+

y

3

￡

-

5y

-

y

+

y

=

1y+

4

y

2

+

6

y

3?

2max z

'

=

5

y1

y

1

+

2

y

261清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)(1)

對(duì)稱(chēng)性：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題;(2)弱對(duì)偶性：若X是原問(wèn)題的可行解，Y是對(duì)偶問(wèn)題的可行解。則存在CX≤Yb;(3)

無(wú)界性：若原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)界解，則其對(duì)偶問(wèn)題(原問(wèn)題)無(wú)可行解;(4)

可行解是最優(yōu)解時(shí)的性質(zhì);(5)

對(duì)偶定理：若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解；且目標(biāo)函數(shù)值相等;(6)

互補(bǔ)松弛性;(7)

原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題解的關(guān)系。62清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)

(1)對(duì)稱(chēng)性：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。證明：設(shè)原問(wèn)題是max

z=CX;

AX≤b；

X≥0根據(jù)對(duì)偶問(wèn)題的對(duì)稱(chēng)變換關(guān)系，可以找到它的對(duì)偶問(wèn)題是min

w=Yb;

YA≥C；

Y≥0若將上式兩邊取負(fù)號(hào)，又因min

w=max(-ω)可得到max(?w)=?Yb;

?YA≤

?

C；

Y≥0根據(jù)對(duì)稱(chēng)變換關(guān)系，得到上式的對(duì)偶問(wèn)題是min(?

w′)=

?

CX；

?

AX≥

?

b;

X≥0又因min(?w′)=max

w′，可得Max

w′=max

z=CX；

AX≤b;

X≥0這就是原問(wèn)題。634.2

對(duì)偶問(wèn)題的基本性質(zhì)將X右乘上式,得到Y(jié)AX

?C.于是得到CX

￡

YAX

￡清Y華b

大學(xué)出證版畢社.(2)弱對(duì)偶性若X是原問(wèn)題的可行解，Y

是對(duì)偶問(wèn)題的可行解則存在CX

￡

Yb設(shè)原問(wèn)題是max

z

=CX;

AX

￡

b;

X

?0因X是原問(wèn)題的可行解，所以滿足約束條件,即AX

￡

b若Y是對(duì)偶問(wèn)題的可行解，將Y左乘上式，得到Y(jié)AX

￡

Yb原問(wèn)題的對(duì)偶問(wèn)題是:min

w

=Yb;YA

?C;Y

?0因Y是對(duì)偶問(wèn)題的可行解，所以滿足YA

?C644.2

對(duì)偶問(wèn)題的基本性質(zhì)(3)

無(wú)界性若原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)界解，則其對(duì)偶問(wèn)題(原問(wèn)題)無(wú)可行解。證：由性質(zhì)（2）可知，Yb

?CX

fi

￥

,是不可能成立。例：清華大學(xué)出版社

1

2y

,

y

?

0-

2

y1

+

y2

?

1y1

-

y2

?

1x1

-

x2

￡

2

1

2x

,x

?

0-

2x1

+

x2

￡

4DP

:min

w

=

y1

+

y2LP

:max

z

=

x1

+

x2654.2

對(duì)偶問(wèn)題的基本性質(zhì)y2y1-

2

y1

+

y2

?

1y1

,

y2

?

0y1

-

y2

?

1x1

,

x2

?

0x1

-

x2

￡

2從兩圖對(duì)比可明顯看到原問(wèn)題無(wú)界，其對(duì)偶問(wèn)題無(wú)可行解-

2

x1

+

x2

￡

4清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)(4)

可行解是最優(yōu)解時(shí)的性質(zhì)設(shè)

X?

是原問(wèn)題的可行解，Y?是對(duì)偶問(wèn)題的可行解，當(dāng)CX?

=

Y?b

時(shí)，X?

,Y?

是最優(yōu)解。證明:=

Y?b

,最小的可行解，66清華大學(xué)出版社證：若

C

X?

=

Y?b

，根據(jù)性質(zhì)所有可行解

Y

都存在Y

b

?

C?

X

;因

C

X?所以

Y

b

?

Y?b

.可見(jiàn)是使目標(biāo)函數(shù)取值因而是最優(yōu)解

.同理可證明，對(duì)原問(wèn)題 的所有可行解

X

，存在

C

X?

=

Y?b

?

CX

,所以是最優(yōu)解

.

證畢。Y?是對(duì)偶問(wèn)題的可行解.2可知，對(duì)偶問(wèn)題的設(shè)：

X?

是原問(wèn)題的可行解，當(dāng)

C

X?

=

Y?b

時(shí)，

X?

,Y?是最優(yōu)解67清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)(5)

對(duì)偶定理

若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解；且目標(biāo)函數(shù)值相等。證：設(shè)X?是原問(wèn)題的最優(yōu)解，它對(duì)應(yīng)的基矩陣B,必存在C

-

CBB A

￡

0,即得到Y(jié)?A

?

C,其中Y?

=

CB

B

.-1

-1若Y?是對(duì)偶問(wèn)題的可行解，使得w

=

Y?b

=

CBB

b-1因原問(wèn)題的X?是最優(yōu)解，使目標(biāo)函數(shù)取值z(mì)

=

CX?

=

CBB

b-1由此，得到Y(jié)?b

=

CB

B b

=

CX?-1可見(jiàn)Y?是對(duì)偶問(wèn)題的最優(yōu)解。68清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)對(duì)偶問(wèn)題min

w

=YbYA

-YS

=CY

,YS

?

0原問(wèn)題max

z

=

CXAX

+

XS

=

bX

,

XS

?

0(6)

互補(bǔ)松弛性若X?,Y?分別為原問(wèn)題和對(duì)偶問(wèn)題的可行解，那么Y?X

S

=

0和YS

X?

=

0;當(dāng)且僅當(dāng)，X?

,Y?為最優(yōu)解。證：設(shè)原問(wèn)題和對(duì)偶問(wèn)題的標(biāo)準(zhǔn)關(guān)系是清華大學(xué)出版社694.2

對(duì)偶問(wèn)題的基本性質(zhì)(6)

互補(bǔ)松弛性將原問(wèn)題目標(biāo)函數(shù)中的系數(shù)向量C用C=YA-YS代替后，得到z=(YA

?

YS)X=YAX

?

YSX

(2-15)將對(duì)偶問(wèn)題的目標(biāo)函數(shù)中系數(shù)列向量b，用b=AX+XS代替后，得到

w=Y(AX+XS)=YAX+YXS

(2-16)若YS

X?

=

0,Y?X

S

=

0;則Y?b

=

Y?AX? =

CX?

,由性質(zhì)（4），可知X?

,Y?是最優(yōu)解。又若分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解， 根據(jù)性質(zhì)（4），則有CX

=YAX

=Yb由（2

-15），（2

-16）式可知，必有Y?X

S

=

0,YS

X?

=

070清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)

(7)原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題解的關(guān)系設(shè)原問(wèn)題是max

z=CX;

AX+XS=b;

X,XS≥0它的對(duì)偶問(wèn)題是min

w=Yb;

YA

?

YS=C;

Y,YS≥0則原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解，其對(duì)應(yīng)關(guān)系見(jiàn)表2-5。71清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)(7)

原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題解的關(guān)系XBX

NXS0-1CN

-

CB

B

N-1-

CB

BYS1YS

2-YYS1是對(duì)應(yīng)原問(wèn)題中基變量XB的剩余變量，

YS2是對(duì)應(yīng)原問(wèn)題中非基變量XN的剩余變量。72清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)(7)

原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題解的關(guān)系證:

設(shè)B是原問(wèn)題的一個(gè)可行基，于是A=(B,N)；原問(wèn)題可改寫(xiě)為max

z=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS≥0相應(yīng)地對(duì)偶問(wèn)題可表示為min

w=Yb(2-17)(2-18)YB

?

YS1=CBYN?

YS2=CNY，YS1,YS2≥0這里YS=(YS1，YS2)。73清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)(7)

原問(wèn)題檢驗(yàn)數(shù)與對(duì)偶問(wèn)題解的關(guān)系當(dāng)求得原問(wèn)題的一個(gè)解：XB=B-1b,其相應(yīng)的檢驗(yàn)數(shù)為CN

?CBB-1N

與

?CBB-1現(xiàn)分析這些檢驗(yàn)數(shù)與對(duì)偶問(wèn)題的解之間的關(guān)系：令Y=CBB-1,將它代入(2-17)式，(2-18)式得YS1=0,

?YS2=CN?

CBB-1N證畢。74清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)例4

已知線性規(guī)劃問(wèn)題max

z=x1+x2-x1+x2+x3≤2-2x1+x2-x3≤1x1,x2,x3≥0試用對(duì)偶理論證明上述線性規(guī)劃問(wèn)題無(wú)最優(yōu)解。4.2

對(duì)偶問(wèn)題的基本性質(zhì)上述問(wèn)題的對(duì)偶問(wèn)題為min

w=2y1+y2-y1-2y2≥1y1+

y2≥1y1-

y2≥0y1，y2≥0由第1約束條件，可知對(duì)偶問(wèn)題無(wú)可行解；原問(wèn)題雖然有可行解，但無(wú)最優(yōu)解。75清華大學(xué)出版社76清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)例5

已知線性規(guī)劃問(wèn)題min

w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其對(duì)偶問(wèn)題的最優(yōu)解為y

*=4/5，y

*=3/5；z=5。試1

2用對(duì)偶理論找出原問(wèn)題的最優(yōu)解。77清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)例5

已知線性規(guī)劃問(wèn)題解：先寫(xiě)出它的對(duì)偶問(wèn)題max

z=4y1+3y2y1+2y2≤2y1-y2≤32y1+3y2≤5y1+y2≤23y1+y2≤3y1，y2≥0①②③④⑤78清華大學(xué)出版社4.2

對(duì)偶問(wèn)題的基本性質(zhì)例5

已知線性規(guī)劃問(wèn)題將y

*

=4/5,y

*

=3/5的值代入約束條件，1

2得②=1/5<3，③=17/5<5，④=7/5<2它們?yōu)閲?yán)格不等式；由互補(bǔ)松弛性得x

*=x

*=x

*=0。2

3

4因y1，y2≥0；原問(wèn)題的兩個(gè)約束條件應(yīng)取等式，故有x

*+3x

*=4，2x

*+x

*=31

5

1

5求解后得到x

*=1,x

*=1；故原問(wèn)題的最優(yōu)解為1

5X*=(1，0，0，0，1)T；w*=5第5節(jié)

對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格在單純形法的每步迭代中，目標(biāo)函數(shù)取值z(mì)=CBB-1b，和檢驗(yàn)數(shù)CN

?CBB-1N中都有乘子Y=CBB-1，那么Y的經(jīng)濟(jì)意義是什么?設(shè)B是｛max

z=CX｜AX≤b，X≥0｝的最優(yōu)基，由(2-12)式可知z*=CBB-1b=Y*b對(duì)z求偏導(dǎo)數(shù)，得B79清華大學(xué)出版社=

C

B-1

=

Y*?z*?b由上式可知，變量yi*的經(jīng)濟(jì)意義是在其他條件不變的情況下，單位資源變化所引起的目標(biāo)函的最優(yōu)值的變化。80清華大學(xué)出版社第5節(jié)

對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。由表1-5可知cj23000θCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1

=1.5，y2

=0.125，y3

=0。*

*

*81清華大學(xué)出版社第5節(jié)

對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。這說(shuō)明是其他條件不變的情況下，若設(shè)備增加一臺(tái)時(shí)，該廠按最優(yōu)計(jì)劃安排生產(chǎn)可多獲利1.5元；原材料A增加1kg，可多獲利0.125元；原材料B增加1kg，對(duì)獲利無(wú)影響。從圖2-1可看到，設(shè)備增加一臺(tái)時(shí)，代表該約束條件的直線由①移至①′，相應(yīng)的最優(yōu)解由(4，2)變?yōu)?4，2.5)，目標(biāo)函數(shù)

z=2×4+3×2.5=15.5，即比原來(lái)的增大1.5。又若原材料A增加1kg時(shí)，代表該約束方程的直線由②移至②′，相應(yīng)的最優(yōu)解從(4

，2)

變?yōu)?4.25

，1.875)

，目標(biāo)函數(shù)z=２×4.25+3×1.875=14.125。比原來(lái)的增加0.125。原材料B增加1kg時(shí)，該約束方程的直線由③移至③′，這時(shí)的最優(yōu)解不變。第5節(jié)

對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格第1章中例1的影價(jià)格及其經(jīng)濟(jì)解釋。82清華大學(xué)出版社83清華大學(xué)出版社第5節(jié)

對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋——影子價(jià)格yi*的值代表對(duì)第i種資源的估價(jià)——影子價(jià)格。這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱(chēng)它為“影子價(jià)格”。在該廠現(xiàn)有資源和現(xiàn)有生產(chǎn)方案的條件下，設(shè)備的每小時(shí)租費(fèi)為1.5元，1kg原材料A的出讓費(fèi)為除成本外再附加0.125元，1kg原材料B可按原成本出讓?zhuān)@時(shí)該廠的收入與自己組織生產(chǎn)時(shí)獲利相等。影子價(jià)格隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買(mǎi)進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣(mài)掉?？梢?jiàn)影子價(jià)格對(duì)市場(chǎng)有調(diào)節(jié)作用。84清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法前節(jié)講到原問(wèn)題與對(duì)偶問(wèn)題的解之間的對(duì)應(yīng)關(guān)系時(shí)指出：在單純形表中進(jìn)行迭代時(shí)，在b列中得到的是原問(wèn)題的基可行解，而在檢驗(yàn)數(shù)行得到的是對(duì)偶問(wèn)題的基解。通過(guò)逐步迭代，當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問(wèn)題的解也是基可行解時(shí)，根據(jù)性質(zhì)(2)、(3)可知，已得到最優(yōu)解。即原問(wèn)題與對(duì)偶問(wèn)題都是最優(yōu)解。根據(jù)對(duì)偶問(wèn)題的對(duì)稱(chēng)性，可以這樣考慮：若保持對(duì)偶問(wèn)題的解是基可行解，即cj?CBB-1Pj≤0，而原問(wèn)題在非可行解的基礎(chǔ)上，通過(guò)逐步迭代達(dá)到基可行解，這樣也得到了最優(yōu)解。其優(yōu)點(diǎn)是原問(wèn)題的初始解不一定是基可行解，可從非基可行解開(kāi)始迭代。85清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法設(shè)原問(wèn)題為max

z=CXAX=bX≥0又設(shè)B是一個(gè)基。不失一般性，令B=(P1，P2，…，Pm)，它對(duì)應(yīng)的變量為XB=(x1，x2，…,xm)。當(dāng)非基變量都為零時(shí)，可以得到XB=B-1b。若在B-1b中至少有一個(gè)負(fù)分量，設(shè)(B-1b)i＜0，并且在單純形表的檢驗(yàn)數(shù)行中的檢驗(yàn)數(shù)都為非正，即對(duì)偶問(wèn)題保持可行解，它的各分量是對(duì)應(yīng)基變量x1，x2，…,xm的檢驗(yàn)數(shù)是σi=ci?

zi=ci

?

CBB-1Pj=0，i=1,2,…,m對(duì)應(yīng)非基變量xm+1，…，xn的檢驗(yàn)數(shù)是σj=cj

?

zj=cj?

CBB-1Pj≤0，j=m+1,…,n86清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法每次迭代是將基變量中的負(fù)分量xl取出，去替換非基變量中的xk，經(jīng)基變換，所有檢驗(yàn)數(shù)仍保持非正。從原問(wèn)題來(lái)看，經(jīng)過(guò)每次迭代，原問(wèn)題由非可行解往可行解靠近。當(dāng)原問(wèn)題得到可行解時(shí)，便得到了最優(yōu)解。第6節(jié) 對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟如下：根據(jù)線性規(guī)劃問(wèn)題，列出初始單純形表。檢查b列的數(shù)字，

若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解。停止計(jì)算。若檢查b列的數(shù)字時(shí)，至少還有一個(gè)負(fù)分量，檢驗(yàn)數(shù)保持非正，那么進(jìn)行以下計(jì)算。確定換出變量。按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l對(duì)應(yīng)的基變量xi為換出變量確定換入變量。在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有αlj≥0，則無(wú)可行解，停止

計(jì)算。若存在αlj＜0

(j=1,2,…，n),

計(jì)算alk87清華大學(xué)出版社jaljck

-

zk

c

j

-

z

jq

=

min

alj

<

0

=88清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法對(duì)偶單純形法的計(jì)算步驟如下：按θ規(guī)則所對(duì)應(yīng)的列的非基變量xk為換入變量，這樣才能保持得到的對(duì)偶問(wèn)題解仍為可行解。(4)

以αlk為主元素，按原單純形法在表中進(jìn)行迭代運(yùn)算，得到新的計(jì)算表。重復(fù)步驟(1)～(4)。清華大學(xué)出版社89第6節(jié) 對(duì)偶單純形法例6

用對(duì)偶單純形法求解min

w=2x1+3x2+4x3x1+2x2+x3≥32x1?x2+3x3≥4x1，x2，x3≥0解：先將此問(wèn)題化成下列形式，以便得到對(duì)偶問(wèn)題的初始可行基max z=

?

2x1

?

3x2

?

4x3?

x1

?

2x2

?

x3+x4

=

?

3?2x1+x2

?

3x3

+x5=

?

4xj≥0，j=1,2,…,590清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法例6的初始單純形表，見(jiàn)表2-6。cj→-2-3-400CBXBbx1x2x3x4x500x4x5-3-4-1[-2]-21-1-31001cj-zj-2-3-400從表2-6看到，檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解。因b列數(shù)字為負(fù)，故需進(jìn)行迭代運(yùn)算。91清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法換出變量的確定：按上述對(duì)偶單純形法計(jì)算步驟(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l對(duì)應(yīng)的基變量xi為換出變量。計(jì)算min(?

3,

?

4)=

?

4故x5為換出變量。換入變量的確定：按上述對(duì)偶單純形法計(jì)算步驟(3)，即在單純形表中檢查xl所在行的各系數(shù)αlj(j=1,2,…，n)。若所有

αlj≥0，則無(wú)可行解，停止計(jì)算。

-

2

-

3

-

2q

=

min

-

2

,-,

-

4

=

-

2

=

1故x1為換入變量。換入、換出變量的所在列、行的交叉處“?2”為主元素。按單純形法計(jì)算步驟進(jìn)行迭代，得表2-7。92清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法cj→-2-3-400CBXBbx1x2x3x4x50-2x4x1-1201[-5/2]-1/21/23/210-1/2-1/2cj-zj0-4-101由表2-7

看出，對(duì)偶問(wèn)題仍是可行解，而b

列中仍有負(fù)分量。故重復(fù)上述迭代步驟，得表2-8。93清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法cj→-2-3-400CBXBbx1x2x3x4x5-3-2x2x12/511/50110-1/57/2-2/5-1/51/5-2/5cj-zj00-9/5-8/5-1/5表2-8中，b列數(shù)字全為非負(fù)，檢驗(yàn)數(shù)全為非正，故問(wèn)題的最優(yōu)解為X*=(11/5，2/5，0，0，0)T若對(duì)應(yīng)兩個(gè)約束條件的對(duì)偶變量分別為y1和y2，則對(duì)偶問(wèn)題的最優(yōu)解為*

*Y*=(y1

,y2

)=(8/5,1/5)94清華大學(xué)出版社第6節(jié) 對(duì)偶單純形法從以上求解過(guò)程可以看到對(duì)偶單純形法有以下優(yōu)點(diǎn)：(1)初始解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)數(shù)時(shí)就可以進(jìn)行基的變換，這時(shí)不需要加入人工變量，因此可以簡(jiǎn)化計(jì)算。(2)當(dāng)變量多于約束條件，對(duì)這樣的線性規(guī)劃問(wèn)題用對(duì)偶單純形法計(jì)算可以減少計(jì)算工作量，因此對(duì)變量較少，而約束條件很多的線性規(guī)劃問(wèn)題，可先將它變換成對(duì)偶問(wèn)題，然后用對(duì)偶單純形法求解。(3)在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時(shí)需要用對(duì)偶單純形法，這樣可使問(wèn)題的處理簡(jiǎn)化。對(duì)偶單純形法的局限性主要是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可行基，因而這種方法在求解線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)應(yīng)用。95清華大學(xué)出版社第7節(jié) 靈敏度分析以前討論線性規(guī)劃問(wèn)題時(shí)，假定αij，bi,cj都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值。如市場(chǎng)條件一變，cj值就會(huì)變化；αij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩個(gè)問(wèn)題：當(dāng)這些系數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問(wèn)題的 最優(yōu)解會(huì)有什么變化；或者這些系數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解或最 優(yōu)基不變。后一個(gè)問(wèn)題將在第8節(jié)參數(shù)線性規(guī)劃中討論。96清華大學(xué)出版社第7節(jié) 靈敏度分析顯然，當(dāng)線性規(guī)劃問(wèn)題中某一個(gè)或幾個(gè)系數(shù)發(fā)生變化后，原來(lái)已得結(jié)果一般會(huì)發(fā)生變化。當(dāng)然可以用單純形法從

頭計(jì)算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也

沒(méi)有必要。因在單純形法迭代時(shí)，每次運(yùn)算都和基變量

的系數(shù)矩陣B有關(guān)，因此可以把發(fā)生變化的個(gè)別系數(shù)，經(jīng)過(guò)一定計(jì)算后直接填入最終計(jì)算表中，并進(jìn)行檢查和分

析，可按表2-9中的幾種情況進(jìn)行處理。原問(wèn)題對(duì)偶問(wèn)題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解表中的解仍為最優(yōu)解可行解非可行解非可行解可行解用用單純形法繼續(xù)迭代求最優(yōu)解對(duì)偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表，求最優(yōu)解97清華大學(xué)出版社7.1

資源數(shù)量變化的分析資源數(shù)量變化是指資源中某系數(shù)br

發(fā)生變化，即

br′=br+Δbr。并假設(shè)規(guī)劃問(wèn)題的其他系數(shù)都不變。這樣使最終表中原問(wèn)題的解相應(yīng)地變化為XB′=B-1(b+Δb)這里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最終表中檢驗(yàn)數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以XB′為新的最優(yōu)解。新的最優(yōu)解的值可允許變化范圍用以下方法確定。7.1

資源數(shù)量變化的分析98清華大學(xué)出版社

mr

r

a1r

Dbr

0

0

B

-1

(b

+

Db)

=

B

-1b

+

B

-1Db

=

B

-1b

+

B

-1

Dbr

0mr

a

Db

a1rB

-1

Dbr

=

air

Dbr

=

Dbr

air

0

a新的最優(yōu)解的值可允許變化范圍用以下方法確定。7.1

資源數(shù)量變化的分析新的最優(yōu)解的值可允許變化范圍用以下方法確定。在最終表中求得的經(jīng)過(guò)變化后的b列的所有元素，要求b

i+a

irΔbr≥0，i=1,2,…,m。由此可得ai