第三章對(duì)偶理論與靈敏度分析

第三章對(duì)偶理論與靈敏度分析第一頁(yè)，共四十一頁(yè)，2022年，8月28日§1單純形法的矩陣描述設(shè)線性規(guī)劃問(wèn)題設(shè)B是一個(gè)可行基，令（A，I）=（B，N，I），則：第二頁(yè)，共四十一頁(yè)，2022年，8月28日1.檢驗(yàn)數(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)lXBbXBXNXsθB-1bIB-1NB-1(B-1b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.單純形表的矩陣描述：σ=C-CBB-1A2.θ的矩陣描述：第三頁(yè)，共四十一頁(yè)，2022年，8月28日§2改進(jìn)單純形法用改進(jìn)單純形法求解線性規(guī)劃問(wèn)題的計(jì)算步驟：1.確定初始可行基B1。求出B1-1；2.計(jì)算非基變量的檢驗(yàn)數(shù)σN。若σN≤0已求的最優(yōu)解，停止計(jì)算,否則進(jìn)行下一步；3.確定換入變量xk；4.計(jì)算B1-1b，B1-1

Pk及θ；若θ≤0那么無(wú)最優(yōu)解，停止計(jì)算，否則進(jìn)行下一步；5.確定換出變量xl;6.計(jì)算B2-1；7.重復(fù)2—7步。第四頁(yè)，共四十一頁(yè)，2022年，8月28日

第五頁(yè)，共四十一頁(yè)，2022年，8月28日例：用改進(jìn)單純形法求解第六頁(yè)，共四十一頁(yè)，2022年，8月28日解：[]第七頁(yè)，共四十一頁(yè)，2022年，8月28日[][]第八頁(yè)，共四十一頁(yè)，2022年，8月28日[][]第九頁(yè)，共四十一頁(yè)，2022年，8月28日[][]第十頁(yè)，共四十一頁(yè)，2022年，8月28日§3對(duì)偶問(wèn)題的提出例：

ⅠⅡ設(shè)備原材料A原材料B1402048臺(tái)時(shí)16kg12kg利潤(rùn)23x1minx2x1x2y1y2y3第十一頁(yè)，共四十一頁(yè)，2022年，8月28日當(dāng)該問(wèn)題達(dá)到最優(yōu)時(shí)有：

z的上界為無(wú)限大，所以只存在最小值。于是得到另一個(gè)線性規(guī)劃問(wèn)題對(duì)線性規(guī)劃問(wèn)題對(duì)偶問(wèn)題原問(wèn)題第十二頁(yè)，共四十一頁(yè)，2022年，8月28日§4線性規(guī)劃的對(duì)偶理論4.1原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系第十三頁(yè)，共四十一頁(yè)，2022年，8月28日原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）例：23-51第十四頁(yè)，共四十一頁(yè)，2022年，8月28日第十五頁(yè)，共四十一頁(yè)，2022年，8月28日第十六頁(yè)，共四十一頁(yè)，2022年，8月28日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*≤Y*b證設(shè)原問(wèn)題及對(duì)偶問(wèn)題為maxz=CX，AX≤b，X≥0minω=Yb，YA≥CY≥0∵若X*是原問(wèn)題的可行解，Y*是對(duì)偶問(wèn)題的可行解∴AX*≤bY*A≥C∴Y*AX*≤Y*bY*AX*≥CX*∴CX*≤Y*AX*≤Y*bCX*Y*b第十七頁(yè)，共四十一頁(yè)，2022年，8月28日3.無(wú)界性若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。4.可行解是最優(yōu)解的性質(zhì)設(shè)X^是原問(wèn)題的可行解，Y^是對(duì)偶問(wèn)題的可行解，當(dāng)CX^=

Y^b時(shí)，X^，

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

X^=0，當(dāng)且僅當(dāng)X^，

Y^為最優(yōu)解。第十八頁(yè)，共四十一頁(yè)，2022年，8月28日6.互補(bǔ)松馳性若X^是原問(wèn)題的可行解，Y^是對(duì)偶問(wèn)題的可行解，那么Y^Xs=0，Ys

X^=0，但且僅當(dāng)X^，

Y^為最優(yōu)解。證：設(shè)原問(wèn)題及對(duì)偶問(wèn)題的標(biāo)準(zhǔn)型是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^是原問(wèn)題的可行解，Y^是對(duì)偶問(wèn)題的可行解∴z^=Y^AX^—YSX^ω^=Y^AX^+Y^XS當(dāng)Y^Xs=0，Ys

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

X^=0第十九頁(yè)，共四十一頁(yè)，2022年，8月28日例：已知線性規(guī)劃問(wèn)題max其對(duì)偶問(wèn)題的最優(yōu)解為試用對(duì)偶理論求原問(wèn)題的最優(yōu)解解：max∵∴∴∴第二十頁(yè)，共四十一頁(yè)，2022年，8月28日7.設(shè)原問(wèn)題及對(duì)偶問(wèn)題的標(biāo)準(zhǔn)型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA－YS=CY，YS≥0則原問(wèn)題單純形表的檢驗(yàn)數(shù)行對(duì)應(yīng)其對(duì)偶問(wèn)題的一個(gè)基解，對(duì)應(yīng)關(guān)系如下表：XBXNXs0CN－CBB-1N－CBB-1－Ys1－Ys2－Y證:CBB-1A－(0，－CN+CBB-1N)=CBB-1(B，N)－(0，－CN+CBB-1N)=(CB，CN)=C第二十一頁(yè)，共四十一頁(yè)，2022年，8月28日§5對(duì)偶問(wèn)題的經(jīng)濟(jì)解釋

——影子價(jià)格

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

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

yi的值代表對(duì)第i種資源的估價(jià)。這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱(chēng)它為“影子價(jià)格”。第二十二頁(yè)，共四十一頁(yè)，2022年，8月28日Q2(4,2)X2X10123454321Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3**A增加4，利潤(rùn)增加4×1/8=1/2設(shè)備增加2，利潤(rùn)增加2×3/2=3Q

(5,3/2)Q

(4,3)第二十三頁(yè)，共四十一頁(yè)，2022年，8月28日§6對(duì)偶單純形法bXBXNXsθXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1≤0變?yōu)椤?變?yōu)椤?/p>

0≥0θ單純形法對(duì)偶單純形法第二十四頁(yè)，共四十一頁(yè)，2022年，8月28日對(duì)偶單純形法的計(jì)算步驟：1.確定初始的基，使非基變量的檢驗(yàn)數(shù)小于等于零。2.若b≥0,則已求得最優(yōu)解，停止計(jì)算，否則進(jìn)行下一步。3.確定換出變量。計(jì)算

min{(B-1b)i|(B-1b)i<0}=(B-1b)l則xl為換出變量。4.確定換入變量。若所有aij

≥0，則無(wú)可行解，停止計(jì)算；否則計(jì)算

θ=min{σj/alj|alj<0}=σk/alk則xk為換入變量。5.以alk為主元素進(jìn)行迭代。6.重復(fù)2—5步。第二十五頁(yè)，共四十一頁(yè)，2022年，8月28日例：第二十六頁(yè)，共四十一頁(yè)，2022年，8月28日

-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第二十七頁(yè)，共四十一頁(yè)，2022年，8月28日§7靈敏度分析

靈敏度分析的內(nèi)容：1.當(dāng)決定線性規(guī)劃問(wèn)題的參數(shù)aij，bi，cj有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問(wèn)題的最優(yōu)解會(huì)有什么變化。2.當(dāng)決定線性規(guī)劃問(wèn)題的參數(shù)aij，bi，cj在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問(wèn)題的最優(yōu)解或最優(yōu)基不變。第二十八頁(yè)，共四十一頁(yè)，2022年，8月28日

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

設(shè)b變化為b+Δb，這時(shí)最終單純形表變?yōu)閄BbXBXNXsθB-1b+B-1ΔbIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1

當(dāng)B-1(b+Δb)≥0時(shí)，最優(yōu)基不變;當(dāng)B-1(b+Δb)中有負(fù)分量時(shí)，可利用對(duì)偶單純形法求解。第二十九頁(yè)，共四十一頁(yè)，2022年，8月28日例：第一章例1中，若該廠又從別處抽出4臺(tái)時(shí)用于生產(chǎn)，求這時(shí)該廠生產(chǎn)的最優(yōu)方案。解：計(jì)算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第三十頁(yè)，共四十一頁(yè)，2022年，8月28日

例：第一章例1中，資源A在什么范圍內(nèi)變化最優(yōu)基不變。解：資源A的變化量Δb滿足下式時(shí)最優(yōu)基不變。第三十一頁(yè)，共四十一頁(yè)，2022年，8月28日

7.2目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化1.若cj是非基變量xj的系數(shù)，則當(dāng)CN變化ΔCN后，最終單純形表的檢驗(yàn)數(shù)行變?yōu)?XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN+ΔCN-CBB-1N-CBB-1

當(dāng)CN+ΔCN

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

-CBB-1N中有正分量時(shí)，可利用單純形法求解。第三十二頁(yè)，共四十一頁(yè)，2022年，8月28日2.若cj是基變量xj的系數(shù)，則當(dāng)CB變化ΔCB后，最終單純形表的檢驗(yàn)數(shù)行變?yōu)?XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1當(dāng)非基變量檢驗(yàn)數(shù)≤0時(shí)，最優(yōu)解不變；當(dāng)非基變量檢驗(yàn)數(shù)中有正分量時(shí)，可利用單純形法求解。-zCBB-1b-

ΔCBB-1b0CN-CBB-1N-

ΔCBB-1N-CBB-1-ΔCBB-1ΔCB第三十三頁(yè)，共四十一頁(yè)，2022年，8月28日例：第一章例1中，基變量x2在目標(biāo)函數(shù)中的系數(shù)c2在什么范圍內(nèi)變化最優(yōu)解不變。解：基變量x2在目標(biāo)函數(shù)中的系數(shù)c2的變化量Δc2滿足下式時(shí)最優(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第三十四頁(yè)，共四十一頁(yè)，2022年，8月28日

例：第一章例1中，出售資源A可獲利1/2元，這是最優(yōu)解發(fā)生什么變化。解：當(dāng)Δc4=1/2時(shí)，單純形表為：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第三十五頁(yè)，共四十一頁(yè)，2022年，8月28日7.3技術(shù)系數(shù)aij的變化1.增加一列Pn+1。則最終單純形表增加一列B-1Pn+1，檢驗(yàn)數(shù)為σn+1=cn+1-CBB-1Pn+1例：第一章例1中，該廠開(kāi)發(fā)一種新產(chǎn)品Ⅲ，已知生產(chǎn)新產(chǎn)品Ⅲ,每件需消耗原材料A，B各為6kg，3kg，使用設(shè)備2臺(tái)時(shí);每件可獲利5元。問(wèn)該廠是否應(yīng)該生產(chǎn)該產(chǎn)品和生產(chǎn)多少？解：計(jì)算第三十六頁(yè)，共四十一頁(yè)，2022年，8月28日41001/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/4第三十七頁(yè)，共四十一頁(yè)，2022年，8月28日

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

-CBB-1Pj’，刪除一列Pj。例：第一章例1中，該廠生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進(jìn)，已知生產(chǎn)產(chǎn)品Ⅰ,每件需消耗原材料A，B各為5kg，2kg，使用設(shè)備2臺(tái)時(shí);每件可獲利4元。試分析對(duì)原最優(yōu)計(jì)劃有什么影響？解：計(jì)算第三十八頁(yè)，共四十一頁(yè)，2022年，8月28日41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

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

4/5011/2