第三章-對偶理論與靈敏度分析課件

§1單純形法的矩陣描述設(shè)線性規(guī)劃問題設(shè)B是一個可行基，令（A，I）=（B，N，I），則：§1單純形法的矩陣描述設(shè)線性規(guī)劃問題設(shè)B是一個可行基，令11.檢驗數(shù)的矩陣描述：

σB=CB-CBB-1B=0σN=CN-CBB-1NσS=-CBB-1

θ=min{(B-1b)i/(B-1Pk)i|(B-1Pk)i>0}=

(B-1b)l/(B-1Pk)l3.單純形表的矩陣描述：σ=C-CBB-1A2.θ的矩陣描述：1.檢驗數(shù)的矩陣描述：θ=min{(B-1b)i/(B-2§2改進單純形法用改進單純形法求解線性規(guī)劃問題的計算步驟：1.確定初始可行基B1。求出B1-1；2.計算非基變量的檢驗數(shù)σN。若σN≤0已求的最優(yōu)解，停止計算,否則進行下一步；3.確定換入變量xk；4.計算B1-1b，B1-1

Pk及θ；若θ≤0那么無最優(yōu)解，停止計算，否則進行下一步；5.確定換出變量xl;6.計算B2-1；7.重復(fù)2—7步?！?改進單純形法用改進單純形法求解線性規(guī)劃問題的計算步驟3

4例：用改進單純形法求解例：用改進單純形法求解5解：[]解：[]6[][][][]7[][][][]8[][][][]9§3對偶問題的提出例：

x1minx2x1x2y1y2y3§3對偶問題的提出例：x1minx2x110當該問題達到最優(yōu)時有：

z的上界為無限大，所以只存在最小值。于是得到另一個線性規(guī)劃問題對線性規(guī)劃問題對偶問題原問題當該問題達到最優(yōu)時有：z的上界為無限大，所以只11§4線性規(guī)劃的對偶理論

4.1原問題與對偶問題的關(guān)系§4線性規(guī)劃的對偶理論4.1原問題與對偶12原問題（對偶問題）對偶問題（原問題）例：23-51原問題（對偶問題）對偶問題（原問題）例：23-5113第三章-對偶理論與靈敏度分析ppt課件14第三章-對偶理論與靈敏度分析ppt課件154.2對偶問題的性質(zhì)1.對稱性對偶問題的對偶是原問題。2.弱對偶性若X*是原問題的可行解，Y*是對偶問題的可行解,則存在

CX*≤Y*b證設(shè)原問題及對偶問題為

maxz=CX，AX≤b，X≥0minω=Yb，YA≥CY≥0∵若X*是原問題的可行解，Y*是對偶問題的可行解∴AX*≤bY*A≥C∴Y*AX*≤Y*bY*AX*≥CX*∴CX*≤Y*AX*≤Y*bCX*Y*b4.2對偶問題的性質(zhì)CX*Y*b163.無界性若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。4.可行解是最優(yōu)解的性質(zhì)設(shè)X^是原問題的可行解，Y^是對偶問題的可行解，當CX^=

Y^b時，X^，

Y^是最優(yōu)解。5.對偶定理若原問題有最優(yōu)解，則對偶問題也有最優(yōu)解，且目標函數(shù)相等。6.互補松馳性若X^是原問題的可行解，Y^是對偶問題的可行解，那么Y^Xs=0，Ys

X^=0，當且僅當X^，

Y^為最優(yōu)解。3.無界性若原問題（對偶問題）為無界解，則其對偶問題（176.互補松馳性若X^是原問題的可行解，Y^是對偶問題的可行解，那么Y^Xs=0，Ys

X^=0，但且僅當X^，

Y^為最優(yōu)解。證：設(shè)原問題及對偶問題的標準型是

maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA—YS=CY，YS≥0z=(YA—YS)X=YAX—YSXω=Y(AX+XS)=YAX+YXS∵X^是原問題的可行解，Y^是對偶問題的可行解∴z^=Y^AX^—YSX^ω^=Y^AX^+Y^XS當Y^Xs=0，Ys

X^=0時z^=ω^，則X，Y^是最優(yōu)解。當X，Y^是最優(yōu)解時z^=ω^，則Y^Xs=0，Ys

X^=06.互補松馳性若X^是原問題的可行解，Y^是對偶問題18例：已知線性規(guī)劃問題max其對偶問題的最優(yōu)解為試用對偶理論求原問題的最優(yōu)解解：max∵∴∴∴例：已知線性規(guī)劃問題max其對偶問題的最優(yōu)解為試用對偶理論求19

7.設(shè)原問題及對偶問題的標準型是

maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA－YS=CY，YS≥0則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解，對應(yīng)關(guān)系如下表：證:CBB-1A－(0，－CN+CBB-1N)=CBB-1(B，N)－(0，－CN+CBB-1N)=(CB，CN)=C7.設(shè)原問題及對偶問題的標準型是證:20§5對偶問題的經(jīng)濟解釋

——影子價格

設(shè)B是線性規(guī)劃問題的一可行基，這目標函數(shù)為

所以變量yi的經(jīng)濟意義是在其他條件不變的情況下，單位資源變化所引起的目標函數(shù)值的變化。

yi的值代表對第i種資源的估價。這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價格，稱它為“影子價格”?！?對偶問題的經(jīng)濟解釋

——影子價格設(shè)B是21Q2(4,2)X2X10123454321Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3**A增加4，利潤增加4×1/8=1/2設(shè)備增加2，利潤增加2×3/2=3Q

(5,3/2)Q

(4,3)Q2(4,2)X2X10122§6對偶單純形法≤0變?yōu)椤?變?yōu)椤?/p>

0≥0θ單純形法對偶單純形法§6對偶單純形法≤0變?yōu)椤?變?yōu)椤?≥0θ單純形23對偶單純形法的計算步驟：

1.確定初始的基，使非基變量的檢驗數(shù)小于等于零。

2.若b≥0,則已求得最優(yōu)解，停止計算，否則進行下一步。

3.確定換出變量。計算

min{(B-1b)i|(B-1b)i<0}=(B-1b)l則xl為換出變量。

4.確定換入變量。若所有aij

≥0，則無可行解，停止計算；否則計算

θ=min{σj/alj|alj<0}=σk/alk則xk為換入變量。

5.以alk為主元素進行迭代。

6.重復(fù)2—5步。對偶單純形法的計算步驟：24例：例：25

-2-3-400-3-1-2-110-4-21-301-10-5/21/21-1/221-1/23/20-1/22/501-1/5-2/51/511/5107/51/5-2/5

0-4-10-1

00-3/5-8/5-1/5[][]

1-34/3/0

/8/5-202-2-326§7靈敏度分析

靈敏度分析的內(nèi)容：

1.當決定線性規(guī)劃問題的參數(shù)aij，bi，cj有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化。

2.當決定線性規(guī)劃問題的參數(shù)aij，bi，cj在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變?！?靈敏度分析靈敏度分析的內(nèi)容：27

7.1資源數(shù)量變化的分析

設(shè)b變化為b+Δb

，這時最終單純形表變?yōu)?/p>

當B-1(b+Δb)≥0時，最優(yōu)基不變;當B-1(b+Δb)中有負分量時，可利用對偶單純形法求解。7.1資源數(shù)量變化的分析28例：第一章例1中，若該廠又從別處抽出4臺時用于生產(chǎn)，求這時該廠生產(chǎn)的最優(yōu)方案。解：計算B-1Δb41001/40

2001-1/4-1/2

301001/4

-17000-1/2-3/4[]//3/4-1/40

+0-8+241001/40

400-21/21

2011/2-1/80

-1400-3/2-1/80

4-44例：第一章例1中，若該廠又從別處抽出4臺時29

例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)基不變。解：資源A的變化量Δb滿足下式時最優(yōu)基不變。例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)30

7.2目標函數(shù)中價值系數(shù)cj的變化

1.若cj是非基變量xj

的系數(shù)，則當CN變化ΔCN

后，最終單純形表的檢驗數(shù)行變?yōu)?

當CN+ΔCN

-CBB-1N≤0時，最優(yōu)解不變；當CN+ΔCN

-CBB-1N中有正分量時，可利用單純形法求解。7.2目標函數(shù)中價值系數(shù)cj的變化31

2.若cj是基變量xj

的系數(shù)，則當CB變化ΔCB后，最終單純形表的檢驗數(shù)行變?yōu)?當非基變量檢驗數(shù)≤0時，最優(yōu)解不變；當非基變量檢驗數(shù)中有正分量時，可利用單純形法求解。ΔCB2.若cj是基變量xj的系數(shù)，則當CB變32例：第一章例1中，基變量x2在目標函數(shù)中的系數(shù)c2在什么范圍內(nèi)變化最優(yōu)解不變。解：基變量x2在目標函數(shù)中的系數(shù)c2的變化量Δc2滿足下式時最優(yōu)解不變。41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

0

0-3/2--1/8+0Δc2/2Δc2/8Δc22+Δc2例：第一章例1中，基變量x2在目標函數(shù)中的系33

例：第一章例1中，出售資源A可獲利1/2元，這是最優(yōu)解發(fā)生什么變化。解：當Δc4=1/2時，單純形表為：41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

+1/2

3/8[]θ

168-1621020-1/2

800-412

30100-1/4

-170000-3/4例：第一章例1中，出售資源A可獲利1/2元，347.3技術(shù)系數(shù)aij的變化

1.增加一列Pn+1。則最終單純形表增加一列B-1Pn+1，檢驗數(shù)為σn+1=cn+1-CBB-1Pn+1例：第一章例1中，該廠開發(fā)一種新產(chǎn)品Ⅲ，已知生產(chǎn)新產(chǎn)品Ⅲ,每件需消耗原材料A，B各為6kg，3kg，使用設(shè)備2臺時;每件可獲利5元。問該廠是否應(yīng)該生產(chǎn)該產(chǎn)品和生產(chǎn)多少？解：計算7.3技術(shù)系數(shù)aij的變化3541001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

5/4[]

θ

8/3281103/2-1/8-3/40

200-11/41/21

3/2013/4-3/16-1/8

0-16.500-1/4-7/16-5/80

3/221/441036

2.改變一列Pj。若Pj變?yōu)镻j’，則最終單純形表增加一列B-1Pj’，檢驗數(shù)為σj=cj’

-CBB-1Pj’，刪除一列Pj。例：第一章例1中，該廠生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進，已知生產(chǎn)產(chǎn)品Ⅰ,每件需消耗原材料A，B各為5kg，2kg，使用設(shè)備2臺時;每件可獲利4元。試分析對原最優(yōu)計劃有什么影響？解：計算2.改變一列Pj。若Pj變?yōu)镻j’，則最3741001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

3/816/51001/5012/500-22/51

4/5011/2-1/50-15.200-3/2-1/5