第二章對偶理念及靈敏度分析

第二章對偶理念及靈敏度分析第1頁，課件共86頁，創(chuàng)作于2023年2月一、問題的提出例一、資源的合理利用問題已知資料如表所示，問應(yīng)如何安排生產(chǎn)計劃使得既能充分利用現(xiàn)有資源有使總利潤最大？第2頁，課件共86頁，創(chuàng)作于2023年2月一、問題的提出1810單件利潤150（設(shè)備）51C100（煤炭）32B170（鋼材）25A資源限制乙甲單件產(chǎn)消耗品資源第3頁，課件共86頁，創(chuàng)作于2023年2月下面從另一個角度來討論這個問題：假定：該廠的決策者不是考慮自己生產(chǎn)甲、乙兩種產(chǎn)品，而是將廠里的現(xiàn)有資源用于接受外來加工任務(wù)，只收取加工費。試問該決策者應(yīng)制定怎樣的收費標準（收費的最底線）？第4頁，課件共86頁，創(chuàng)作于2023年2月第5頁，課件共86頁，創(chuàng)作于2023年2月一、問題的提出該問題的數(shù)學(xué)模型為：第6頁，課件共86頁，創(chuàng)作于2023年2月模型對比請總結(jié)規(guī)律第7頁，課件共86頁，創(chuàng)作于2023年2月1、對稱型對偶問題：已知

P，寫出D。（一）、對偶問題的形式

二、線性規(guī)劃的對偶理論第8頁，課件共86頁，創(chuàng)作于2023年2月原問題：maxz=2x1+3x2

s.t2x1+2x2≤12

x1+2x2≤8

4x1≤16

4x2≤12

x1≥0x2≥0

對偶問題：minw=12y1+8y2+16y2+12y4

s.t2y1+1y2+4y3+0y4≥2

2y1+2y2+0y3+4y4≥3

y1,y2,y3,y4≥0非對稱型對偶問題如何求解？第9頁，課件共86頁，創(chuàng)作于2023年2月對偶問題的其變換形式歸納如下原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)max目標函數(shù)min約束條件m個m個變量≤≥0≥≤0=無約束變量n個n個約束條件≥0≥≤0≤無約束=約束條件右端項目標函數(shù)變量的系數(shù)目標函數(shù)變量的系數(shù)約束條件右端項變向變向大約束，小變量第10頁，課件共86頁，創(chuàng)作于2023年2月例一、寫出線性規(guī)劃問題的對偶問題第11頁，課件共86頁，創(chuàng)作于2023年2月例二、原問題第12頁，課件共86頁，創(chuàng)作于2023年2月例三：第13頁，課件共86頁，創(chuàng)作于2023年2月例四、原問題第14頁，課件共86頁，創(chuàng)作于2023年2月對偶問題第15頁，課件共86頁，創(chuàng)作于2023年2月例五、線性規(guī)劃問題如下：第16頁，課件共86頁，創(chuàng)作于2023年2月第17頁，課件共86頁，創(chuàng)作于2023年2月練習(xí)：第18頁，課件共86頁，創(chuàng)作于2023年2月第19頁，課件共86頁，創(chuàng)作于2023年2月（二）、對偶問題的性質(zhì)1、對稱性定理：對偶問題的對偶是原問題。以下討論僅就“對稱形式”討論。因其他形式都可以轉(zhuǎn)化成“對稱形式”，故所有結(jié)論適用于所有形式。第20頁，課件共86頁，創(chuàng)作于2023年2月2、弱對偶原理（弱對偶性）：設(shè)和分別是問題（P）和（D）的可行解，則必有推論⑴.若和分別是問題（P）和（D）的可行解，則是（D）的目標函數(shù)最小值的一個下界；是（P）的目標函數(shù)最大值的一個上界。第21頁，課件共86頁，創(chuàng)作于2023年2月推論⑵.在一對對偶問題（P）和（D）中，若其中一個問題可行但目標函數(shù)無界，則另一個問題不可行；反之不成立。這也是對偶問題的無界性。關(guān)于無界性有如下結(jié)論：問題無界無可行解無可行解問題無界對偶問題原問題第22頁，課件共86頁，創(chuàng)作于2023年2月3、最優(yōu)性判別定理：

若X*

和Y*分別是P和D

的可行解且CX*=Y*b，則X*.Y*分別是問題P和D

的最優(yōu)解。下面來求原問題和對偶問題的最優(yōu)解：第23頁，課件共86頁，創(chuàng)作于2023年2月Cj

CBCN0系數(shù)基

XBXNXSCBXBB-1b

IB-1NB-1

Z=CBB-1b0

CN-CBB-1N

-CBB-1C

-CBB-1A≤0

最優(yōu)解的判定條件是：-CBB-1≤0

CBB-1≥0

令Y’=CBB-1-CBB-1≤0

由C

-CBB-1A≤0

則CBB-1A≥C即Y’A≥C即A’Y≥C’W=Y’b=CBB-1b=CBX=Z則Y’≥0

則Y≥0

第24頁，課件共86頁，創(chuàng)作于2023年2月4、對偶定理（強對偶性）：若一對對偶問題P和D

都有可行解，則它們都有最優(yōu)解，且目標函數(shù)的最優(yōu)值必相等。推論（3）.若P和D的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標函數(shù)的最優(yōu)值相等。推論（4）.在一對對偶問題（P）和（D）中，若一個可行，而另一個不可行，則該可行的問題無界。原問題有最優(yōu)解，則對偶問題只少有一個可行解。并且這一解即為對偶問題的最優(yōu)解。第25頁，課件共86頁，創(chuàng)作于2023年2月綜上所述，一對對偶問題的關(guān)系，只能有下面三種情況之一出現(xiàn)：①.都有可行解，都有最優(yōu)解，分別設(shè)為X*

和Y*，則必有CX*=Y*b；②.一個問題無界，則另一個問題無可行解；③.兩個都無可行解。第26頁，課件共86頁，創(chuàng)作于2023年2月5、互補松弛定理：在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；如果約束條件取嚴格不等式，則其對應(yīng)的對偶變量一定為零。嚴格不等式約束稱為松約束，而把嚴格等式約束稱為緊約束。第27頁，課件共86頁，創(chuàng)作于2023年2月例4、已知試通過求對偶問題的最優(yōu)解來求解原問題的最優(yōu)解。解：對偶問題為第28頁，課件共86頁，創(chuàng)作于2023年2月用圖解法求出：Y*=（1.3），W=11。將y*1=1，y*2=3代入對偶約束條件，（1）（2）（5）式為緊約束，（3）（4）為松約束。令原問題的最優(yōu)解為X*=（x1.x2.x3.x4.x5），則根據(jù)互補松弛條件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）第29頁，課件共86頁，創(chuàng)作于2023年2月又由于y*1＞0，y*2＞0，原問題的約束必為等式，即化簡為此方程組為無窮多解令x5=0,得到x1=1，x2=2

即X*1=（1.2.0.0.0）為原問題的一個最優(yōu)解，Z=11。

再令x5=2/3，得到x1=5/3，x2=0即X*2（5/3.0.0.0.2/3）也是原問題的一個最優(yōu)解，Z=11。第30頁，課件共86頁，創(chuàng)作于2023年2月例5、已知原問題的最優(yōu)解為X*=（0.0.4）試求對偶問題的最優(yōu)解。（最優(yōu)解與最優(yōu)值的區(qū)別）解：（1）（2）（3）第31頁，課件共86頁，創(chuàng)作于2023年2月將X*=（0.0.4）代入原問題中，有下式：所以，根據(jù)互補松弛條件，必有y*1=y*2=0，代入對偶問題（3）式，y3=3。因此，對偶問題的最優(yōu)解為

Y*=（0.0.3），W=12。第32頁，課件共86頁，創(chuàng)作于2023年2月6、對偶問題的解利用原問題的最優(yōu)單純形表和改進單純形表求解對偶問題的最優(yōu)解。設(shè)原問題為：maxZ=CXAX≤

bX≥0引入xs，構(gòu)建初始基變量，然后，用單純形法求解。當(dāng)檢驗數(shù)滿足σj≤0，則求得最優(yōu)解。此時，xs對應(yīng)的σjs

為-Y*，故求對偶Y*，只要將最優(yōu)單純形表上xs

對應(yīng)的檢驗數(shù)反號即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1第33頁，課件共86頁，創(chuàng)作于2023年2月例一、第34頁，課件共86頁，創(chuàng)作于2023年2月cj1018000cBxBbx1x2x3x4x50x3170521000x4100230100x515015001-Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最終表第35頁，課件共86頁，創(chuàng)作于2023年2月由上表可知：

X*=（50/7.200/7），Z=4100/7對偶問題的最優(yōu)解：

Y*=（0.32/7.6/7），W=4100/7第36頁，課件共86頁，創(chuàng)作于2023年2月例二、第37頁，課件共86頁，創(chuàng)作于2023年2月cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4111-211000-Mx63-4120-110-Mx71-2010001-Z3-6M-1+M-1+3M0-M00第38頁，課件共86頁，創(chuàng)作于2023年2月所以，X*=（4.1.9），Z=2∴y*1=(0－σ4)=1/3y*2=(－M－σ6)=－M－(1/3－M)=－1/3y*3=(－M－σ7)=－M－(2/3－M)=－2/3Y*=（1/3.－1/3.－2/3）W=2初始基變量的檢驗數(shù)σ4=－1/3，σ6=1/3－M,σ7=2/3－M第39頁，課件共86頁，創(chuàng)作于2023年2月定義：在一對P和D中，若P的某個約束條件的右端項常數(shù)bi增加一個單位時，所引起的目標函數(shù)最優(yōu)值Z*

的改變量y*i

稱為第i個約束條件的影子價格，又稱為邊際價格。三、對偶問題的經(jīng)濟解釋——影子價格

第40頁，課件共86頁，創(chuàng)作于2023年2月設(shè)：B是問題P的最優(yōu)基，由前式可知，

Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*Ibi+…+y*mbm

CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1即y*i

表示Z*對bi的變化率。第41頁，課件共86頁，創(chuàng)作于2023年2月其經(jīng)濟意義是：在其它條件不變的情況下，單位資源變化所引起的目標函數(shù)的最優(yōu)值的變化。即對偶變量yi就是第i個約束條件的影子價格。第42頁，課件共86頁，創(chuàng)作于2023年2月若第i種資源的單位市場價格為mi。當(dāng)yi>mi

時，企業(yè)愿意購進這種資源，單位純利為yi－mi，則有利可圖；如果yi<mi，則企業(yè)有償轉(zhuǎn)讓這種資源，，可獲單位純利mi－yi，否則，企業(yè)無利可圖，甚至虧損。第43頁，課件共86頁，創(chuàng)作于2023年2月012345678123456⑴⑵⑶⑷x2

x1(42)⑴′

X*=（4.2.0.0.0.4）Y*=（0.3/2.1/8.0）最優(yōu)值為14最優(yōu)值沒有發(fā)生變化即y1=0第44頁，課件共86頁，創(chuàng)作于2023年2月012345678123456⑴⑵⑶⑷x2

x1(45/2)⑵′最優(yōu)值為15.5，變化了3/2，即y2=3/2即b2增加一個單位，y2增加了3/2，即第二種資源的邊際價格為3/2第45頁，課件共86頁，創(chuàng)作于2023年2月生產(chǎn)過程中如果某種資源bi未得到充分利用時，該種資源的影子價格為零。當(dāng)資源的影子價格不為零時，表明該種資源生產(chǎn)過程已耗盡完畢。第46頁，課件共86頁，創(chuàng)作于2023年2月第47頁，課件共86頁，創(chuàng)作于2023年2月對偶單純形法是求解線性規(guī)劃的另一的基本方法。它是根據(jù)對偶原理和單純形法的原理而設(shè)計出來的，因此稱為對偶單純形法。對偶單純形法的基本思想：在保持對偶問題為可行解的基礎(chǔ)上（這時原問題一般為非可行解），通過迭代，當(dāng)原問題也達到可行解時，即得到目標函數(shù)最優(yōu)值。四、對偶單純形法W=Y’b=CBB-1b=CX=ZY’=CBB-1單位矩陣I行變換，即基變換與第48頁，課件共86頁，創(chuàng)作于2023年2月3、計算步驟：①建立初始單純形表，確定原問題或?qū)ε紗栴}的基（單位矩陣）。條件是檢驗數(shù)全部≤0。(原問題是不是可行解沒有關(guān)系）

基變換：先確定換出變量——b列中的負元素（一般選最小的負元素）對應(yīng)的基變量出基即第49頁，課件共86頁，創(chuàng)作于2023年2月

然后確定換入變量——原則是：在保持對偶可行的前提下，減少原始問題的不可行性。

如果存在（最小比值原則，保證所有的檢驗數(shù)<=0）則選為換入變量，相應(yīng)的列為主元列，主元行和主元列交叉處的元素為主元素。如果不存一個alj<0,則原問題無可行解，那么對偶問題就存在無界解。第50頁，課件共86頁，創(chuàng)作于2023年2月④按主元素進行換基迭代（旋轉(zhuǎn)運算、樞運算），將主元素變成1，主元列變成單位向量，得到新的單純形表。繼續(xù)以上步驟，直至求出最優(yōu)解。即所有的檢驗數(shù)小于等于零并且右端項大于等于零。跳出循環(huán)地方的有幾處？（保證原問題與對偶問題都有可行解，這時就得到兩問題的最優(yōu)解，為什么？？）第51頁，課件共86頁，創(chuàng)作于2023年2月例一、用對偶單純形法求解：解：將模型轉(zhuǎn)化為如果用單純形法如何求解？第52頁，課件共86頁，創(chuàng)作于2023年2月cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001(-9/-1.-12/-1.-15/-5)-Z′

0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5(-30/-9.-45/-14.-1/5/-3)-15x314/51/51/5100-1/5-Z′

42-6-9000-3第53頁，課件共86頁，創(chuàng)作于2023年2月cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9.-33/-1)-15x315/71/140101/14-3/14-Z′

501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z′

72000-1/3-3-7/3第54頁，課件共86頁，創(chuàng)作于2023年2月

所以，

X*=（2.2.2.0.0.0），Z′*=－72，

原問題Z*=72

其對偶問題的最優(yōu)解為：

Y*=(1/3.3.7/3)，W*=72第55頁，課件共86頁，創(chuàng)作于2023年2月練習(xí)：第56頁，課件共86頁，創(chuàng)作于2023年2月cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301-Z-2-3-400cj-2-3-400cBxBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z0-4-10-1第57頁，課件共86頁，創(chuàng)作于2023年2月cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z28/500-3/5-8/5-1/5Y=（8/5.1/5）X=（2/5.11/5.0）Z=28/5第58頁，課件共86頁，創(chuàng)作于2023年2月靈敏度分析的步驟：

1.將參數(shù)的改變通過矩陣計算反映到最終表中；

2.檢查原問題是否可行解；

3.檢查對偶問題是否可行解；

4.按以下原則得出結(jié)論或決定繼續(xù)計算的步驟。五、靈敏度分析第59頁，課件共86頁，創(chuàng)作于2023年2月σj=cj－CBB－1Pj=B－1Pj

=B－1b關(guān)鍵是求B-1即找單位矩陣I第60頁，課件共86頁，創(chuàng)作于2023年2月求下列LP問題第61頁，課件共86頁，創(chuàng)作于2023年2月Cj0-130-20CBXBbx1x2x3x4x5x60x1713-10200x4120-2[4]1000x6

100-43081σj

0-130-200x1101[5/2]01/4203x330-1/211/4000x6

10-5/20-3/481σj01/20-3/4-20-1x242/5101/104/503x351/5013/102/500x6

11100-1/2101σj-1/500-4/5-12/50第62頁，課件共86頁，創(chuàng)作于2023年2月B3=（P2，P3，P6）=B3－1=第63頁，課件共86頁，創(chuàng)作于2023年2月

求下列LP問題的最優(yōu)解

第64頁，課件共86頁，創(chuàng)作于2023年2月第65頁，課件共86頁，創(chuàng)作于2023年2月B4－1=B3=（P4，P2，P3）=B3－1=B4=（P1，P2，P3）=第66頁，課件共86頁，創(chuàng)作于2023年2月例：某企業(yè)利用三種資源生產(chǎn)兩種產(chǎn)品的最優(yōu)計劃問題歸結(jié)為下列線性規(guī)劃已知最優(yōu)表如下。（1）確定x2的系數(shù)c2的變化范圍，使原最優(yōu)解保持最優(yōu)；（2）若c2=6，求新的最優(yōu)計劃。一、價值系數(shù)cj的變化分析第67頁，課件共86頁，創(chuàng)作于2023年2月cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3第68頁，課件共86頁，創(chuàng)作于2023年2月σ4=c2－5≤0σ5=5－2c2≤05/2≤c2≤5cj5c2

000CBXBbx1x2x3x4x50x3250012-55x1351001-1c2

x2

10010-12000c2-55-2c2最優(yōu)解X*=（35，10，25，0，0）保持不變。（1）第69頁，課件共86頁，創(chuàng)作于2023年2月Cj56000CBXBbx1x2x3x4x50x325001[2]-55x1351001-16x2

10010-12σj

0001-70x425/2001/21-5/25x145/210-1/203/26x2

45/2011/20-1/2σj00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2（2）第70頁，課件共86頁，創(chuàng)作于2023年2月XB=B－1b例：對于上例中的線性規(guī)劃作下列分析：（1）b3在什么范圍內(nèi)變化，原最優(yōu)基不變？（2）若b3=55，求出新的最優(yōu)解。

二、右端常數(shù)bi的變化分析第71頁，課件共86頁，創(chuàng)作于2023年2月cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最優(yōu)基：B=（P3，P1，P2）B－1=第72頁，課件共86頁，創(chuàng)作于2023年2月（1）B－1==≥0解得40≤b3≤50，即當(dāng)b3∈[40，50]時，最優(yōu)基B不變z*=5×（80－b3）+4×（－80+2b3）=80+3b3=也可計算：B－1B－1見書上的P65例6第73頁，課件共86頁，創(chuàng)作于2023年2月（2）當(dāng)b3=55時

=x2

x1x50-11/5-3/500σj0-1/52/51020403/5-1/5013051-2/5-1/50050-32-1[-5]x50-1000σj

-101030x2

4100125x152100-25x30x4x3x2x1bXBCB0045Cj第74頁，課件共86頁，創(chuàng)作于2023年2月三、增加一個新變量的分析例2.10（續(xù)例2.8）設(shè)企業(yè)研制了一種新產(chǎn)品，對三種資源的消耗系數(shù)列向量以P6表示P6=。問它的價值系數(shù)c6符合什么條件才必須安排它的生產(chǎn)？設(shè)c6=3，新的最優(yōu)生產(chǎn)計劃是什么？第75頁，課件共86頁，創(chuàng)作于2023年2月σ6=c6－CBB－1P6=c6－（0，5，4）=c6－5/2=B－1P6==第76頁，課件共86頁，創(chuàng)作于2023年2月Cj540003CBXBbx1x2x3x4x5x60x3250012-5[1]5x1351001-11/26x2

10010-120σj

000-1-31/23x6250012-515x145/210-1/203/204x2

10010-120σj00-1/2-2-1/20第77頁，課件共86頁，創(chuàng)作于2023年2月四、增加新的約束條件的分析例2.11假設(shè)在例2.8中，還要考慮一個新的資源約束：4x1+2x2≤1504x1+2x2+x6=150X*=（35，10，25，0，0）T第78頁，課件共86頁，創(chuàng)作于2023年2月4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x2

10010-1200x6150420001000-1-30不管是單純形法還對偶單純形法都是從單位矩陣開始的，因此要先找單位矩陣第79頁，課件共86頁，創(chuàng)作于2023年2月Cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x210010-1200x6

150420001σj

000-1-300x3250012-505x1351001-104x210010-1200x6

-10000[-2]01σj000-1-300x3150010-515x1301000-11/24x21501002-1/20x4

500010-1/2σj0000-3-1/2第80頁，課件共86頁，創(chuàng)作于2023年2月五、