對(duì)偶理論和靈敏度分析

對(duì)偶理論和靈敏度分析第1頁(yè)，共49頁(yè)，2023年，2月20日，星期一1.單純形的矩陣描述用矩陣語(yǔ)言描述單純形法的關(guān)鍵是寫(xiě)出兩個(gè)基本的表達(dá)式,設(shè)線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型為

maxz=CXAX=bX≥0C=(CB,CN)，X=(XB,XN)’，A=(B,N)由約束條件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基變量表示基變量的表達(dá)式:XB=B-1b-B-1NXN(1)第2頁(yè)，共49頁(yè)，2023年，2月20日，星期一將(1)式代入目標(biāo)函數(shù)的表達(dá)式,可以得到用非基變量表示目標(biāo)函數(shù)的表達(dá)式.Z=CX=(CB,CN)(XB,XN)’=CBXB+CNXN=CB(B-1-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XN=CBB-1b+σNXN另非基變量等于零，則Z=CBB-1b注意XB檢驗(yàn)數(shù)為零,實(shí)質(zhì)上是CB-CBB-1B=0Y=CBB-1為單純形乘子第3頁(yè)，共49頁(yè)，2023年，2月20日，星期一

cxbCBCNθ

XBXNXBB-1bB-1BB-1N-z-CBB-1b

0CN-CBB-1N第4頁(yè)，共49頁(yè)，2023年，2月20日，星期一注意:在初始單位矩陣的位置,在各運(yùn)算表中就是B-1的所在位置BI……IB-1第5頁(yè)，共49頁(yè)，2023年，2月20日，星期一2.改進(jìn)單純形法改進(jìn)單純形法又稱(chēng)為逆矩陣法或修正單純形法,是在原來(lái)單純形法基礎(chǔ)上加以改進(jìn)，關(guān)鍵在于求B-1,有了B-1,單純形算法的各個(gè)表中的數(shù)字都可以利用線(xiàn)性規(guī)劃中的原始數(shù)據(jù)計(jì)算出來(lái)。第6頁(yè)，共49頁(yè)，2023年，2月20日，星期一第7頁(yè)，共49頁(yè)，2023年，2月20日，星期一

3對(duì)偶理論某廠(chǎng)生產(chǎn)甲乙兩種產(chǎn)品，各自的零部件分別在A(yíng)、B車(chē)間生產(chǎn)，最后都需在C車(chē)間裝配，相關(guān)數(shù)據(jù)如表所示：?jiǎn)柸绾伟才偶住⒁覂僧a(chǎn)品的產(chǎn)量，使利潤(rùn)為最大。

產(chǎn)品車(chē)間工時(shí)單耗甲乙生產(chǎn)能力ABC

10023481236單位產(chǎn)品獲利

35maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.第8頁(yè)，共49頁(yè)，2023年，2月20日，星期一若上例中該廠(chǎng)的產(chǎn)品平銷(xiāo)，現(xiàn)有另一企業(yè)想租賃其設(shè)備。廠(chǎng)方為了在談判時(shí)心中有數(shù)，需掌握設(shè)備臺(tái)時(shí)費(fèi)用的最低價(jià)碼，以便衡量對(duì)方出價(jià)，對(duì)出租與否做出抉擇。在這個(gè)問(wèn)題上廠(chǎng)長(zhǎng)面臨著兩種選擇：自行生產(chǎn)或出租設(shè)備。首先要弄清兩個(gè)問(wèn)題：①合理安排生產(chǎn)能取得多大利潤(rùn)?②為保持利潤(rùn)水平不降低，資源轉(zhuǎn)讓的最低價(jià)格是多少？問(wèn)題①的最優(yōu)解：x1=4，x2=6，Z*=42。第9頁(yè)，共49頁(yè)，2023年，2月20日，星期一假設(shè)出讓A、B、C設(shè)備所得利潤(rùn)分別為y1、y2、y3原本用于生產(chǎn)甲產(chǎn)品的設(shè)備臺(tái)時(shí)，如若出讓?zhuān)粦?yīng)低于自行生產(chǎn)帶來(lái)的利潤(rùn)，否則寧愿自己生產(chǎn)。于是有

y1+0y2+3y3≥3同理，對(duì)乙產(chǎn)品而言，則有

0y1+2y2+4y3≥5設(shè)備臺(tái)時(shí)出讓的收益（希望出讓的收益最少值）

min=8y1+12y2+36y3顯然還有

y1，y2，y3≥0第10頁(yè)，共49頁(yè)，2023年，2月20日，星期一min=8y1+12y2+36y3

y1+0y2+3y3≥3

0y1+2y2+4y3≥5y1，y2，y3≥0S.t.maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.第11頁(yè)，共49頁(yè)，2023年，2月20日，星期一例

線(xiàn)性規(guī)劃問(wèn)題

maxz=3x1+5x2

stx1+3x2

10 7x1+4x2

20 xj0;j=1,2.

對(duì)偶問(wèn)題為：

ming=10y1+20y2 st y1+7y2

3 3y1+4y2

5 yi

0;i=1,2。第12頁(yè)，共49頁(yè)，2023年，2月20日，星期一

3.1對(duì)偶變換的規(guī)則第13頁(yè)，共49頁(yè)，2023年，2月20日，星期一

3.2對(duì)偶問(wèn)題的基本性質(zhì)為了便于討論，下面不妨總是假設(shè)(1)對(duì)稱(chēng)性：對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。(2)弱對(duì)偶性：對(duì)偶問(wèn)題(min)的任何可行解Y0，其目標(biāo)函數(shù)值總是不小于原問(wèn)題(max)任何可行解X0的目標(biāo)函數(shù)值，即CX0≤Yb0。弱對(duì)偶定理推論：原問(wèn)題的任何可行解目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下限；對(duì)偶問(wèn)題的任何可行解目標(biāo)函數(shù)值是原問(wèn)題目標(biāo)函數(shù)值的上限。第14頁(yè)，共49頁(yè)，2023年，2月20日，星期一

(3)無(wú)界性若原(對(duì)偶)問(wèn)題為無(wú)界解，則其對(duì)偶(原)問(wèn)題無(wú)可行解當(dāng)原問(wèn)題(對(duì)偶問(wèn)題)為無(wú)可行解,其對(duì)偶問(wèn)題(原問(wèn)題)或具有無(wú)界解或無(wú)可行解。如果原(對(duì)偶)問(wèn)題有可行解，其對(duì)偶(原)問(wèn)題無(wú)可行解，則原問(wèn)題為無(wú)界解。(4)強(qiáng)對(duì)偶性可行解是最優(yōu)解的性質(zhì)(最優(yōu)性準(zhǔn)則定理)若原問(wèn)題的某個(gè)可行解X0的目標(biāo)函數(shù)值與對(duì)偶問(wèn)題某個(gè)可行解Y0的目標(biāo)函數(shù)值相等，則X0,Y0分別是相應(yīng)問(wèn)題的最優(yōu)解（5）主對(duì)偶定理

若原問(wèn)題和對(duì)偶問(wèn)題兩者皆可行,則兩者均有最優(yōu)解,且此時(shí)目標(biāo)函數(shù)值相等。第15頁(yè)，共49頁(yè)，2023年，2月20日，星期一

綜上所述，一對(duì)對(duì)偶問(wèn)題的解必然是下列三種情況之一:原問(wèn)題和對(duì)偶問(wèn)題都有最優(yōu)解。一個(gè)問(wèn)題具有無(wú)界解，另一個(gè)問(wèn)題無(wú)可行解。原問(wèn)題和對(duì)偶問(wèn)題都無(wú)可行解。(6)互補(bǔ)松弛性設(shè)X0,Y0分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，Xs為原問(wèn)題的松弛變量的值、Ys為對(duì)偶問(wèn)題剩余變量的值。X0,Y0分別是原問(wèn)題和對(duì)偶問(wèn)題最優(yōu)解的充分必要條件是：Y0Xs

=

Ys

X0=0第16頁(yè)，共49頁(yè)，2023年，2月20日，星期一(7)原問(wèn)題單純形表檢驗(yàn)數(shù)行與對(duì)偶問(wèn)題解的關(guān)系原問(wèn)題單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基解.顯然,原問(wèn)題最終單純形表檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基可行解XBXNXS0CN-CBB-1N-CBB-1YS1-YS2-Y第17頁(yè)，共49頁(yè)，2023年，2月20日，星期一例已知線(xiàn)性規(guī)劃問(wèn)題：試用對(duì)偶理論證明此線(xiàn)性規(guī)劃問(wèn)題無(wú)最優(yōu)解。解：對(duì)偶問(wèn)題為：由第一約束條件顯見(jiàn)，對(duì)偶問(wèn)題無(wú)可行解因?yàn)椋?，0，0）為線(xiàn)性規(guī)劃問(wèn)題的可行解。而對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題為無(wú)界解或無(wú)可行解，故原問(wèn)題無(wú)最優(yōu)解。第18頁(yè)，共49頁(yè)，2023年，2月20日，星期一例5：線(xiàn)性規(guī)劃問(wèn)題最優(yōu)解為用對(duì)偶問(wèn)題求原問(wèn)題的最優(yōu)解。第19頁(yè)，共49頁(yè)，2023年，2月20日，星期一對(duì)偶問(wèn)題為：將對(duì)偶問(wèn)題的解代入上述約束條件，可知2、3、4式為嚴(yán)格不等式；由松弛互補(bǔ)性，可得x2=x3=x4=0,因y1,y2大于零，所以原問(wèn)題的兩個(gè)約束條件應(yīng)該取等式，故有：第20頁(yè)，共49頁(yè)，2023年，2月20日，星期一

4.影子價(jià)格（對(duì)偶價(jià)格）對(duì)偶變量yi(i=1,2,…,m)表示原問(wèn)題的第i個(gè)約束條件的影子價(jià)格，它表示：在其它條件不變的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。(1)影子價(jià)格能指示企業(yè)內(nèi)部挖潛的方向。影子價(jià)格越高的資源，它對(duì)目標(biāo)增益的影響越大，同時(shí)也表明這種資源越稀缺和貴重。企業(yè)的管理者要重視這種資源的管理，挖掘潛力，及時(shí)組織資源，由此可以給企業(yè)帶來(lái)較大的收益。(2)影子價(jià)格指導(dǎo)企業(yè)間的分工與協(xié)作。影子價(jià)格可以作為企業(yè)在接受外協(xié)加工任務(wù)時(shí)，對(duì)外協(xié)單位使用資源的收費(fèi)標(biāo)準(zhǔn)，按照影子價(jià)格收費(fèi)，保證了企業(yè)與外協(xié)單位雙方平等互利的格局，可以促進(jìn)雙方合作。第21頁(yè)，共49頁(yè)，2023年，2月20日，星期一

(3)影子價(jià)格在新產(chǎn)品開(kāi)發(fā)決策中的應(yīng)用。兩種新產(chǎn)品A,B的機(jī)會(huì)成本（萬(wàn)元）：A單位產(chǎn)品的機(jī)會(huì)成本=1×3/4+2×0+3×1/4=3/2B單位產(chǎn)品的機(jī)會(huì)成本=2×3/4+1×0+4×1/4=5/2產(chǎn)品資源AB影子價(jià)格(萬(wàn)元)鋼材煤機(jī)時(shí)1221343/401/4單位利潤(rùn)(萬(wàn)元)13第22頁(yè)，共49頁(yè)，2023年，2月20日，星期一

由于投產(chǎn)A產(chǎn)品所能提供的單位利潤(rùn)（1萬(wàn)元）不大于投產(chǎn)的機(jī)會(huì)成本（1.5萬(wàn)元），因此A產(chǎn)品不宜投產(chǎn)；而B(niǎo)產(chǎn)品的機(jī)會(huì)成本（2.5萬(wàn)元）小于該產(chǎn)品投產(chǎn)后所能提供的利潤(rùn)（3萬(wàn)元），因此投產(chǎn)B產(chǎn)品可以給工廠(chǎng)帶來(lái)較大的收益。如果新產(chǎn)品B確實(shí)為社會(huì)所歡迎,而在資源利用上與老產(chǎn)品發(fā)生沖突，工廠(chǎng)可以考慮用B產(chǎn)品去更換老產(chǎn)品，以獲得更大的經(jīng)濟(jì)效益。(4)影子價(jià)格在資源采購(gòu)決策中的應(yīng)用。當(dāng)資源的市場(chǎng)價(jià)格低于影子價(jià)格，企業(yè)買(mǎi)進(jìn)該資源，擴(kuò)大生產(chǎn)，當(dāng)資源的市場(chǎng)價(jià)格高于影子價(jià)格，企業(yè)應(yīng)設(shè)法轉(zhuǎn)讓該資源。第23頁(yè)，共49頁(yè)，2023年，2月20日，星期一

(5)利用影子價(jià)格分析工藝改變后對(duì)資源節(jié)約的收益。例如設(shè)工廠(chǎng)現(xiàn)有鋼材100噸，其影子價(jià)格為3/4，采用新工藝后，鋼材可以節(jié)約2%，則由此帶來(lái)的經(jīng)濟(jì)收益為：

100×3/4×2%=3/2(萬(wàn)元)第24頁(yè)，共49頁(yè)，2023年，2月20日，星期一5.對(duì)偶單純形法對(duì)偶單純形法是應(yīng)用對(duì)偶原理求解原問(wèn)題線(xiàn)性規(guī)劃的一種方法,采用的技術(shù)是在原問(wèn)題的單純形表格上進(jìn)行對(duì)偶處理。注意:對(duì)偶單純形法不是求解對(duì)偶問(wèn)題的單純形法。第25頁(yè)，共49頁(yè)，2023年，2月20日，星期一單純形法的求解過(guò)程是：在保持原始可行(b列保持≥０）的前提下，通過(guò)逐步迭代實(shí)現(xiàn)對(duì)偶可行（檢驗(yàn)數(shù)行≤０）。換個(gè)角度考慮線(xiàn)性規(guī)劃的求解過(guò)程：能否保持對(duì)偶可行（檢驗(yàn)數(shù)行保持≤０）的前提下，通過(guò)逐步迭代實(shí)現(xiàn)原始可行(b列≥０，從非可行解變成可行解）呢？答案是肯定的，這就是對(duì)偶單純形法的基本思想。第26頁(yè)，共49頁(yè)，2023年，2月20日，星期一步驟：（1）根據(jù)線(xiàn)性規(guī)劃問(wèn)題，列出初始單純形表。若b列數(shù)字還有負(fù)分量，檢驗(yàn)數(shù)保持非正，則（2）確定換出變量選min[(B-1b)i/(B-1b)i<0]對(duì)應(yīng)的變量xl為換出變量（3）確定換入變量θ=min[cj-zj/aij](aij<0)所對(duì)應(yīng)的非基變量xk為換入變量。（4）以alk為主元素進(jìn)行迭代運(yùn)算，并重復(fù)以上步驟第27頁(yè)，共49頁(yè)，2023年，2月20日，星期一利用對(duì)偶單純形法求解以下線(xiàn)性規(guī)劃問(wèn)題：第28頁(yè)，共49頁(yè)，2023年，2月20日，星期一cjCBXBbx1x2x3x4x5-1-3000-2-3-1-1-2-2100010解法001-3-4-1x3x4x5000-1-3000cj-zj1/33/2x3x1x50101/32/3-4/3100-2/3-1/3-1/3001cj-zj-1/34/31/30-7/30-1/301/20-10x4x1x5?3/21/2010-1/2?-3/2-3/2-1/2-1/21000010-10cj-zj0-5/2-1/200-3/2此時(shí)所有的B-1b均≥0，且所有的cj-zj均≤0，此時(shí)已得到最優(yōu)解為：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2第29頁(yè)，共49頁(yè)，2023年，2月20日，星期一總結(jié)：對(duì)偶單純形法與單純形法的比較最優(yōu)解時(shí)要求單純形法對(duì)偶單純形法保持B-1b≥0所有的cj-zj≤0所有的cj-zj≤0B-1b≥0第30頁(yè)，共49頁(yè)，2023年，2月20日，星期一特點(diǎn)：可以避免加人工變量，簡(jiǎn)化計(jì)算．靈敏度分析和整數(shù)規(guī)劃常借助于對(duì)偶單純形法分析．局限性在于初始單純形表的檢驗(yàn)數(shù)行很難滿(mǎn)足小于或等于零的要求，即滿(mǎn)足檢驗(yàn)數(shù)行對(duì)應(yīng)的對(duì)偶問(wèn)題的解是可行解．第31頁(yè)，共49頁(yè)，2023年，2月20日，星期一6.靈敏度分析靈敏度分析的意義

線(xiàn)性規(guī)劃研究的是一定條件下的最優(yōu)化問(wèn)題，采用優(yōu)化方案可以達(dá)到節(jié)約資源、提高效益的目的，但是對(duì)“優(yōu)化方案”必須要有全面的認(rèn)識(shí)，不可機(jī)械地對(duì)待。優(yōu)化方案是建立在特定的資源環(huán)境和技術(shù)條件之上的，而環(huán)境和條件總是處在不斷地變化之中，如產(chǎn)品價(jià)格、原材料成本、加工技術(shù)水平、資源消耗系數(shù)等時(shí)有波動(dòng)，所以?xún)?yōu)化方案是個(gè)相對(duì)穩(wěn)定的概念。當(dāng)基礎(chǔ)數(shù)據(jù)發(fā)生變化時(shí)，最優(yōu)方案也就變了。基礎(chǔ)數(shù)據(jù)往往是測(cè)算估計(jì)的數(shù)值，雖然在運(yùn)算過(guò)程中要求十分嚴(yán)格，但基礎(chǔ)數(shù)據(jù)的誤差是不可避免的。為了對(duì)優(yōu)化結(jié)果有更全面的了解和恰當(dāng)?shù)倪\(yùn)用，就需要進(jìn)行靈敏度分析。第32頁(yè)，共49頁(yè)，2023年，2月20日，星期一靈敏度分析所要解決的問(wèn)題：系數(shù)在什么范圍內(nèi)變化，不會(huì)影響已獲得的最優(yōu)基(即最優(yōu)解或最優(yōu)解結(jié)構(gòu)不變)。如果系數(shù)的變化超過(guò)以上范圍，如何在用最簡(jiǎn)便的方法在原來(lái)最優(yōu)解的基礎(chǔ)上求得新的最優(yōu)解當(dāng)線(xiàn)性規(guī)劃問(wèn)題增加一個(gè)新的變量或新的約束，如何在原來(lái)最優(yōu)解的基礎(chǔ)上獲得新的最優(yōu)解。第33頁(yè)，共49頁(yè)，2023年，2月20日，星期一6.1右端項(xiàng)bi變化的靈敏度分析bi變化到什么程度可以保持最優(yōu)基不變？用xB=B-1b≥0。第34頁(yè)，共49頁(yè)，2023年，2月20日，星期一例：求以下模型中第二個(gè)約束條件右端項(xiàng)b2的變化范圍。maxZ=70X1+120X29X1+4X2≤3604X1+5X2

≤2003X1+10X2

≤300X1≥0X2≥0第35頁(yè)，共49頁(yè)，2023年，2月20日，星期一

Cj70

120000CBXBbX1

X2

X3X4X5θi

000X3X4X5360200300

9410045010310001904030σj0

70120000

00120X3X4X22405030

7.8010-0.42.5001-0.50.31000.130.7620100σj3600

34000-12070120X3X1X2842024

001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.2第36頁(yè)，共49頁(yè)，2023年，2月20日，星期一解：從最優(yōu)單純形表得出：XB=(20,24,84)T最優(yōu)基為：注意：應(yīng)為初始數(shù)據(jù)。還可以從單純形表中找出B-1.第37頁(yè)，共49頁(yè)，2023年，2月20日，星期一設(shè)b2由200變?yōu)?00＋?b2，則b由

由此得到迭代后的單純形表：cj70120000CBXBbx1x2x3x4x5θi010001100-3.120.4-0.121.16-0.20.1684-3.12?b220+0.4?b224-0,12?b2x3x1x2070120σj4280+13.6?b2000-13.6-5.2第38頁(yè)，共49頁(yè)，2023年，2月20日，星期一上述解是最優(yōu)解，必須是可行解：即：解得：－50≤?b2≤26.9?？芍叶隧?xiàng)系數(shù)b2的變化范圍是:

（200－50）～（200＋26.9)第39頁(yè)，共49頁(yè)，2023年，2月20日，星期一在此范圍內(nèi)σj≤0，B-1b≥0，最優(yōu)解仍有效，即最優(yōu)解的基變量不變，最優(yōu)解為：最優(yōu)值為：Z*=4280+13.6?b2第40頁(yè)，共49頁(yè)，2023年，2月20日，星期一6.2目標(biāo)函數(shù)中價(jià)值系數(shù)cj的靈敏度分析分cj是非基變量的系數(shù)還是基變量的系數(shù)兩種情況來(lái)討論。①若cj是非基變量xj的系數(shù)，此時(shí)，當(dāng)cj變化?cj后，要保證最終表中這個(gè)檢驗(yàn)數(shù)仍小于或等于零即可。②若cj是基變量xj的系數(shù)，則引起的變化較大。第41頁(yè)，共49頁(yè)，2023年，2月20日，星期一例：在模型例1中，求基變量x2的系數(shù)變化范圍。解：本例的最優(yōu)單純形表如下：070120cjCBXBbx3x1x2842024x1x2x3x4x5θi70120000010001100-3.120.4-0.121.16-0.20.16σj4280000-13.6-5.2第42頁(yè)，共49頁(yè)，2023年，2月20日，星期一基變量系數(shù)c2由120變?yōu)?20＋?c2后，可以得到迭代后的單純形表。cjCBXBbx3x1x2842024x1x2x3x4x5θi70120＋?c2000010001100-3.120.4-0.121.16-0.20.16σj4280＋24?c2000-13.6+0.12