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

第二章對(duì)偶理論和靈敏度分析第一頁，共七十頁，2022年，8月28日矩陣的加法相加的兩個(gè)矩陣必須具有相同的行數(shù)和列數(shù)預(yù)備知識(shí)第二頁，共七十頁，2022年，8月28日矩陣的數(shù)量乘法用數(shù)乘一個(gè)矩陣，需要把矩陣中的每個(gè)元素都乘上k預(yù)備知識(shí)第三頁，共七十頁，2022年，8月28日矩陣的乘法左矩陣A的列數(shù)必須等于右矩陣B的行數(shù)不滿足交換律預(yù)備知識(shí)第四頁，共七十頁，2022年，8月28日矩陣的轉(zhuǎn)置可逆矩陣A-1A=AA-1=I預(yù)備知識(shí)第五頁，共七十頁，2022年，8月28日2.1單純形法的矩陣描述對(duì)于線性規(guī)劃問題：令：第六頁，共七十頁，2022年，8月28日2.1單純形法的矩陣描述將原問題化為標(biāo)準(zhǔn)型（加入松弛變量），得第七頁，共七十頁，2022年，8月28日得到初始的單純形表：此時(shí)前m列可以湊成一個(gè)基，用B表示：2.1單純形法的矩陣描述第八頁，共七十頁，2022年，8月28日得到初始的單純形表：第m+1列至n列為非基變量，用N表示：2.1單純形法的矩陣描述第九頁，共七十頁，2022年，8月28日得到初始的單純形表：第n+1列至n+m列為松弛變量，用S表示：2.1單純形法的矩陣描述第十頁，共七十頁，2022年，8月28日因此，原單純形表可分解為：用B-1左乘系數(shù)矩陣用－CB左乘系數(shù)矩陣，再加到最后一行2.1單純形法的矩陣描述非基變量是什么？非基變量的檢驗(yàn)數(shù)是什么？第十一頁，共七十頁，2022年，8月28日用矩陣運(yùn)算的方法也可以求解線性規(guī)劃問題，其本質(zhì)與單純形法一樣，非基變量檢驗(yàn)數(shù)的判斷方法也與單純形法相同。用矩陣運(yùn)算的方法求解例1：2.2改進(jìn)單純形法第十二頁，共七十頁，2022年，8月28日2.2改進(jìn)單純形法通過觀察檢驗(yàn)數(shù)，發(fā)現(xiàn)未達(dá)到最優(yōu)，需要換基，x2入基，x5出基第十三頁，共七十頁，2022年，8月28日2.2改進(jìn)單純形法由于p3,p4,p2為基向量而p1,p5為非基向量則原單純形表變?yōu)榈谑捻?，共七十頁?022年，8月28日2.2改進(jìn)單純形法通過觀察檢驗(yàn)數(shù)，發(fā)現(xiàn)未達(dá)到最優(yōu)，需要換基，x1入基，x3出基第十五頁，共七十頁，2022年，8月28日2.2改進(jìn)單純形法由于p1,p4,p2為基向量而p3,p5為非基向量則原單純形表變?yōu)榈谑摚财呤摚?022年，8月28日2.2改進(jìn)單純形法通過觀察檢驗(yàn)數(shù)，發(fā)現(xiàn)未達(dá)到最優(yōu)，需要換基，x5入基，x4出基第十七頁，共七十頁，2022年，8月28日求出最終的單純形表為：2.2改進(jìn)單純形法第十八頁，共七十頁，2022年，8月28日B-1練習(xí)題第十九頁，共七十頁，2022年，8月28日對(duì)偶是指同一事物（問題）從不同的角度（立場(chǎng)）觀察，有兩種相對(duì)的表述。每一個(gè)線性規(guī)劃問題，都存在一個(gè)與它密切相關(guān)的另一個(gè)線性規(guī)劃問題，我們稱其中任意一個(gè)為原問題，另一個(gè)則稱為它的對(duì)偶問題。

2.3對(duì)偶問題的提出第二十頁，共七十頁，2022年，8月28日例

某工廠在計(jì)劃期內(nèi)安排Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如表所示。該工廠每生產(chǎn)一單位產(chǎn)品I可獲利50元，每生產(chǎn)一單位產(chǎn)品II可獲利100元，問工廠應(yīng)分別生產(chǎn)多少I產(chǎn)品和II產(chǎn)品，才能使工廠獲利最多？

解：設(shè)工廠生產(chǎn)I產(chǎn)品x1件，生產(chǎn)II產(chǎn)品x2件，建模如下：假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、C，那么每臺(tái)時(shí)設(shè)備的租金應(yīng)該定多少，才不至于虧損？2.3對(duì)偶問題的提出第二十一頁，共七十頁，2022年，8月28日解：設(shè)設(shè)備A、B、C每臺(tái)時(shí)的租金分別為y1，y2，y3元，建模如下：比較原問題和對(duì)偶問題：原問題對(duì)偶問題2.3對(duì)偶問題的提出第二十二頁，共七十頁，2022年，8月28日原關(guān)系對(duì)偶關(guān)系2.3對(duì)偶問題的提出第二十三頁，共七十頁，2022年，8月28日用矩陣形式表示原問題和對(duì)偶問題的關(guān)系：原問題對(duì)偶問題原問題對(duì)偶問題2.3對(duì)偶問題的提出第二十四頁，共七十頁，2022年，8月28日寫出下列線性規(guī)劃問題的對(duì)偶問題：練習(xí)題第二十五頁，共七十頁，2022年，8月28日對(duì)于線性規(guī)劃問題：基B對(duì)應(yīng)的單純形表如下：當(dāng)非基變量的檢驗(yàn)數(shù)均小于或等于0的時(shí)候，該線性規(guī)劃問題可以得到最優(yōu)解，即2.4對(duì)偶問題的基本性質(zhì)第二十六頁，共七十頁，2022年，8月28日上式中均含有乘子

CBB-1

,稱它為單純形乘子，并令則有Y≥0包括基變量在內(nèi)的所有檢驗(yàn)數(shù)可以表示為：原先性規(guī)劃問題的最優(yōu)值為2.4對(duì)偶問題的基本性質(zhì)第二十七頁，共七十頁，2022年，8月28日這樣，即可得到原線性規(guī)劃的對(duì)偶問題:2.4對(duì)偶問題的基本性質(zhì)第二十八頁，共七十頁，2022年，8月28日對(duì)稱性對(duì)偶問題的對(duì)偶是原問題2.4對(duì)偶問題的基本性質(zhì)-1原問題對(duì)偶問題第二十九頁，共七十頁，2022年，8月28日弱對(duì)偶性若X0

是原問題的可行解，Y0

是對(duì)偶問題的可行解，則存在CX0≤Y0b。2.4對(duì)偶問題的基本性質(zhì)-2原問題對(duì)偶問題第三十頁，共七十頁，2022年，8月28日無界性若原問題存在無界解，則其對(duì)偶問題無可行解。反證法：若對(duì)偶問題存在可行解Y0，根據(jù)弱對(duì)偶性，可知CX≤Y0b而Y0b是一個(gè)定數(shù)，這與原問題無界相矛盾。推論：若對(duì)偶問題存在無界解，則其原問題無可行解。2.4對(duì)偶問題的基本性質(zhì)-3為什么？第三十一頁，共七十頁，2022年，8月28日若X0

是原問題的可行解，Y0

是對(duì)偶問題的可行解，當(dāng)CX0=Y0b時(shí)，X0，Y0分別是原問題和其對(duì)偶問題的最優(yōu)解。根據(jù)弱對(duì)偶性可知，對(duì)原問題的任一可行解X，均有CX≤Y0b由于CX0=Y0b，可知CX≤CX0從而可知X0是原問題的最優(yōu)解。同理，可證Y0是其對(duì)偶問題的最優(yōu)解。2.4對(duì)偶問題的基本性質(zhì)-4第三十二頁，共七十頁，2022年，8月28日對(duì)偶定理若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。令X*為原問題的最優(yōu)解，則同時(shí)，檢驗(yàn)數(shù)要滿足令

可知Y*是其對(duì)偶問題的一個(gè)可行解。又根據(jù)性質(zhì)4，可知Y*是其對(duì)偶問題的最優(yōu)解。2.4對(duì)偶問題的基本性質(zhì)-5第三十三頁，共七十頁，2022年，8月28日互補(bǔ)松弛性若X*和Y*分別為原問題和對(duì)偶問題的可行解，那么

其中Xs*和Ys*分別為松弛變量和剩余變量解的集合。2.4對(duì)偶問題的基本性質(zhì)-6第三十四頁，共七十頁，2022年，8月28日例題：已知線性規(guī)劃問題：已知其對(duì)偶問題的最優(yōu)解為y1*=4/5，y2*=3/5；z=5。試用對(duì)偶理論找出原問題的最優(yōu)解。2.4對(duì)偶問題的基本性質(zhì)-6第三十五頁，共七十頁，2022年，8月28日基解的互補(bǔ)性原問題的一個(gè)基解，對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解，并且該對(duì)互補(bǔ)基解的目標(biāo)函數(shù)值相等；當(dāng)求得原問題在基B下的單純形表后，表中檢驗(yàn)數(shù)行相反的數(shù)（即－σ），就是其對(duì)偶問題的一個(gè)基解。2.4對(duì)偶問題的基本性質(zhì)-7第三十六頁，共七十頁，2022年，8月28日將下列線性規(guī)劃模型（例1）轉(zhuǎn)化為對(duì)偶問題

2.5對(duì)偶問題的經(jīng)濟(jì)解釋—影子價(jià)格用大M法求解第三十七頁，共七十頁，2022年，8月28日最終單純形表為：

2.5對(duì)偶問題的經(jīng)濟(jì)解釋—影子價(jià)格第三十八頁，共七十頁，2022年，8月28日由例1可知：

2.5對(duì)偶問題的經(jīng)濟(jì)解釋—影子價(jià)格設(shè)備增加1臺(tái)時(shí)，總利潤增加1.5元原料A的供應(yīng)增加1kg，總利潤增加0.125元原料B的供應(yīng)增加1kg，總利潤沒有變化第三十九頁，共七十頁，2022年，8月28日將例1中設(shè)備限制增加1臺(tái)時(shí)，則原線性規(guī)劃問題變?yōu)椋?/p>

2.5對(duì)偶問題的經(jīng)濟(jì)解釋—影子價(jià)格用圖解法求解第四十頁，共七十頁，2022年，8月28日將例1中原料B的供應(yīng)量增加到20kg，則原線性規(guī)劃問題變?yōu)椋?/p>

2.5對(duì)偶問題的經(jīng)濟(jì)解釋—影子價(jià)格用圖解法求解第四十一頁，共七十頁，2022年，8月28日對(duì)偶問題的最優(yōu)解往往代表對(duì)第i種資源的估價(jià)，這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格，稱它為“影子價(jià)格”。影子價(jià)格隨具體情況而異，在完全市場(chǎng)經(jīng)濟(jì)的條件下，當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，企業(yè)應(yīng)買進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí)，則企業(yè)的決策者應(yīng)把已有資源賣掉。2.5對(duì)偶問題的經(jīng)濟(jì)解釋—影子價(jià)格第四十二頁，共七十頁，2022年，8月28日解決線性規(guī)劃問題的另一種方法。對(duì)偶單純形法與單純形法的區(qū)別：2.6對(duì)偶單純形法單純形法對(duì)偶單純形法前提保持所有約束條件的常數(shù)b≥0保持所有的檢驗(yàn)數(shù)σ符合目標(biāo)函數(shù)的要求思路使所有的檢驗(yàn)數(shù)σ符合目標(biāo)函數(shù)的要求使所有約束條件的常數(shù)b≥0出發(fā)點(diǎn)不同第四十三頁，共七十頁，2022年，8月28日在以下的情況中，用對(duì)偶單純形法能更好地解決線性規(guī)劃問題：變量較少，而約束條件比較多的線性規(guī)劃問題，可先變換成它的對(duì)偶問題，然后用對(duì)偶單純形法求解；目標(biāo)函數(shù)最小化，且約束條件中含有“≥”的線性規(guī)劃問題。2.6對(duì)偶單純形法第四十四頁，共七十頁，2022年，8月28日解題步驟：（針對(duì)求目標(biāo)函數(shù)最大值的情況）根據(jù)線性規(guī)劃問題，列出初始單純形表。檢查b列的數(shù)字，如果b≥0，且σ≤0，則得到最優(yōu)解；若b列的數(shù)字至少還有一個(gè)bi≤0，且σ≤0，則進(jìn)行以下計(jì)算。2.6對(duì)偶單純形法第四十五頁，共七十頁，2022年，8月28日確定出基變量在b列中找到最小的一個(gè)負(fù)數(shù)，這個(gè)負(fù)數(shù)所在行的基變量定為出基變量xk。確定入基變量檢查xk所在行的各系數(shù)akj(j=1,…,n)：若所有akj≥0，則無可行解，停止計(jì)算；若存在akj＜0，計(jì)算：

最小比值所對(duì)應(yīng)的xt

為入基變量。2.6對(duì)偶單純形法為什么？第四十六頁，共七十頁，2022年，8月28日以akt

為主元進(jìn)行迭代運(yùn)算，得到新的單純形表。重復(fù)步驟1~4，直到能夠判斷出解的形式。用對(duì)偶單純形法求解例1的對(duì)偶問題：2.6對(duì)偶單純形法第四十七頁，共七十頁，2022年，8月28日在約束條件的兩邊同時(shí)乘以（-1），且變?yōu)樽畲蠡?，?.6對(duì)偶單純形法加入松弛變量第四十八頁，共七十頁，2022年，8月28日建立初始單純形表：2.6對(duì)偶單純形法意味著這一行所對(duì)應(yīng)的原基變量為出基變量此行存在akj＜0，取第四十九頁，共七十頁，2022年，8月28日進(jìn)行迭代：2.6對(duì)偶單純形法第五十頁，共七十頁，2022年，8月28日2.6對(duì)偶單純形法第五十一頁，共七十頁，2022年，8月28日2.6對(duì)偶單純形法第五十二頁，共七十頁，2022年，8月28日比較原問題和對(duì)偶問題（第一步）原問題對(duì)偶問題第五十三頁，共七十頁，2022年，8月28日比較原問題和對(duì)偶問題（第二步）原問題對(duì)偶問題第五十四頁，共七十頁，2022年，8月28日比較原問題和對(duì)偶問題（第三步）原問題對(duì)偶問題第五十五頁，共七十頁，2022年，8月28日比較原問題和對(duì)偶問題（第四步）原問題對(duì)偶問題第五十六頁，共七十頁，2022年，8月28日性質(zhì)2：弱對(duì)偶性

若X0

是原問題的可行解，Y0

是對(duì)偶問題的可行解，則存在CX0≤Y0b。性質(zhì)4：若X0

是原問題的可行解，Y0

是對(duì)偶問題的可行解，當(dāng)CX0=Y0b時(shí)，X0，Y0分別是原問題和其對(duì)偶問題的最優(yōu)解。性質(zhì)5：對(duì)偶定理若原問題有最優(yōu)解，則對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。對(duì)照對(duì)偶問題的基本性質(zhì)第五十七頁，共七十頁，2022年，8月28日互補(bǔ)松弛性若X*和Y*分別為原問題和對(duì)偶問題的可行解，那么其中Xs*和Ys*分別為松弛變量和剩余變量解的集合。對(duì)照對(duì)偶問題的基本性質(zhì)（性質(zhì)6）第五十八頁，共七十頁，2022年，8月28日基解的互補(bǔ)性原問題的一個(gè)基解，對(duì)應(yīng)其對(duì)偶問題的一個(gè)基解，并且該對(duì)互補(bǔ)基解的目標(biāo)函數(shù)值相等；當(dāng)求得原問題在基B下的單純形表后，表中檢驗(yàn)數(shù)行相反的數(shù)（即－σ），就是其對(duì)偶問題的一個(gè)基解。對(duì)照對(duì)偶問題的基本性質(zhì)（性質(zhì)7）第五十九頁，共七十頁，2022年，8月28日2.7靈敏度分析解決兩個(gè)問題：當(dāng)bi、cj、aij

發(fā)生變化時(shí)，對(duì)已求得的最優(yōu)解有什么影響；當(dāng)bi、cj、aij

在什么范圍內(nèi)變化時(shí)，最優(yōu)解或最優(yōu)基不變。解決方法：用單純形法從頭計(jì)算，得到新的最優(yōu)解；靈敏度分析計(jì)算量大，沒有必要第六十頁，共七十頁，2022年，8月28日1.約束條件中常數(shù)項(xiàng)b的靈敏度分析假設(shè)約束條件中某一常數(shù)發(fā)生變化（其他常數(shù)不變），即：這樣，最終單純形表中原問題的解變?yōu)椋喝绻鸛B’≥0，因檢驗(yàn)數(shù)不變，故最優(yōu)基不變，但最優(yōu)解發(fā)生了變化，XB’成為新的最優(yōu)解；如果XB’＜0，則可用對(duì)偶單純形法在最終單純形表的基礎(chǔ)上繼續(xù)迭代。第六十一頁，共七十頁，2022年，8月28日以例1為例，討論使最優(yōu)基不變的b2

的變化范圍△b2。此時(shí)的最優(yōu)解變?yōu)槎嗌?？第六十二頁，共七十頁?022年，8月28日以例1為例，如果b1

的取值由8變?yōu)?0，請(qǐng)求出最優(yōu)解。例1的最終單純形表如下：練習(xí)題第六十三頁，共七十頁，2022年，8月28日2.目標(biāo)函數(shù)中變量系數(shù)C的靈敏度分析若目標(biāo)函數(shù)中的系數(shù)cr

發(fā)生變化，可能會(huì)引起CN或CB的變化，即：這樣，最終單純形表中非基變量所對(duì)應(yīng)的檢驗(yàn)數(shù)變?yōu)椋喝绻襧‘≤0，最優(yōu)解不變；如果σj‘中存在某個(gè)檢驗(yàn)數(shù)＞0，則需要在最終單純形表的基礎(chǔ)上繼續(xù)迭代。思考：如果基變量在目標(biāo)函數(shù)中的系數(shù)發(fā)生變化，基變量對(duì)應(yīng)的檢驗(yàn)數(shù)是否會(huì)有變化？第六十四頁，共七十頁，2022年，8月28日以例1為例，討論使最優(yōu)解不變的c2

的變化范圍△c2。x2為基變量，因此，代入公式因此，當(dāng)σ3‘≤0且

σ4‘≤0時(shí)，即－3≤△