第3章線性規(guī)劃問題的對偶與靈敏度分析-課件

1、第三章 線性規(guī)劃問題的對偶與靈敏度分析1本章內(nèi)容重點線性規(guī)劃的對偶問題概念、理論及經(jīng)濟意義線性規(guī)劃的對偶單純形法線性規(guī)劃的靈敏度分析2線性規(guī)劃原問題 例2.1:某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示。求獲最大利潤的方案。產(chǎn)品甲產(chǎn)品乙設(shè)備能力（h）設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）150025003 對偶問題若上問題的設(shè)備都用于外協(xié)加工，工廠收取加工費。試問：設(shè)備 A、B、C 每工時各如何收費才最有競爭力？ 設(shè) y1, y2, y3 分別為每工時設(shè)備 A、B、C

2、的收取費用。4原問題 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0對偶問題Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1500 （不少于甲產(chǎn)品的利潤） 2y1+y2+3y3 2500 （不少于乙產(chǎn)品的利潤） y1, y2 , y3 05 2、對偶定義 對稱形式： 互為對偶 (LP) Max z = cTx (DP) Min f =bTy s.t. Ax b s.t. AT yc x 0 y 0 “Max - ” “Min- ”6 一對對稱形式的對偶規(guī)劃之間具有下面

3、的對應(yīng)關(guān)系。 (1)若一個模型為目標求“極大”，約束為“小于等于”的不等式，則它的對偶模型為目標求“極小”，約束是“大于等于”的不等式。即“max，”和“min，”相對應(yīng)。7 (2)從約束系數(shù)矩陣看：一個模型中為，則另一個模型中為AT。一個模型是m個約束，n個變量，則它的對偶模型為n個約束，m個變量。 (3)從數(shù)據(jù)b、C的位置看：在兩個規(guī)劃模型中，b和C的位置對換。 (4)兩個規(guī)劃模型中的變量皆非負。8非對稱形式的對偶規(guī)劃 一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃。 對于非對稱形式的規(guī)劃，可以按照下面 的對應(yīng)關(guān)系直接給出其對偶規(guī)劃。 （1）將模型統(tǒng)一為“max，”或“min，”

4、 的形式，對于其中的等式約束按下面（2）、（3）中的方法處理； （2）若原規(guī)劃的某個約束條件為等式約束，則在對偶規(guī)劃中與此約束對應(yīng)的那個變量取值沒有非負限制；9（3）若原規(guī)劃的某個變量的值沒有非負限 制，則在對偶問題中與此變量對應(yīng)的那個 約束為等式 下面對關(guān)系（2）作一說明。對于關(guān)系（3） 可以給出類似的解釋。 設(shè)原規(guī)劃中第一個約束為等式： a11x1 + + a1nxn = b1 那么，這個等式與下面兩個不等式等價10這樣，原規(guī)劃模型可以寫成11 此時已轉(zhuǎn)化為對稱形式，直接寫出對偶規(guī)劃這里，把 y1看作是 y1=y1-y1，于是 y1 沒有非負限制，關(guān)系（2）的說明完畢。12 例 寫出下面線

5、性規(guī)劃的對偶規(guī)劃模型解 先將約束條件變形為“”形式13 再根據(jù)非對稱形式的對應(yīng)關(guān)系，直接寫出對偶規(guī)劃1415對偶性定理設(shè)有一對互為對偶的線性規(guī)劃A為mn階矩陣，A的秩為m16引入松弛變量xs，得到原規(guī)劃(P)的標準型為(P1)其中01和I分別為m維的零向量和m維的單位矩陣 17則上面的標準型可以表示為(P2)其中02為m+n維零向量18設(shè)B為一可行基得到模型P2的另一表達形式19記 為非基變量檢驗數(shù)的向量表達式由于基變量的檢驗數(shù)為零，所以全部檢驗數(shù)的向量形式可記為20可行基B對應(yīng)的基本可行解為x0的目標函數(shù)值為21定理3-1(弱對偶定理)設(shè) 分別為原規(guī)劃(P)和對偶規(guī)劃(D)的可行解，則 證：

6、因為 是原規(guī)劃可行解，且 所以有又因為 是對偶規(guī)劃的可行解，且 所以有所以這一性質(zhì)說明了兩個線性規(guī)劃互為對偶時，求最大值的線性規(guī)劃的任意目標值都不會大于求最小值的線性規(guī)劃的任一目標值，不能理解為原問題的目標值不超過對偶問題的目標值22推論1設(shè) 分別為原規(guī)劃(P)和對偶規(guī)劃(D)的可解，當(dāng) 時， 分別是兩個問題的最優(yōu)解證明，由定理3.1可知，對于線性規(guī)劃(D)的任一可行解y。都有 ，因此 是線性規(guī)劃(D)的最優(yōu)解， 類似的，可以證明 是線性規(guī)劃(P)的最優(yōu)解2324例3.4 試用對偶理論判斷下面線性規(guī)劃是否有最優(yōu)解25解 此線性規(guī)劃存在可行解 ,其對偶規(guī)劃為 此線性規(guī)劃沒有可行解，因此原規(guī)劃沒有

7、最優(yōu)解2627解 此線性規(guī)劃存在可行解 ,其對偶規(guī)劃為 此線性規(guī)劃存在可行解 因此原規(guī)劃存在最優(yōu)解28定理3.2 若原規(guī)劃(P)有最優(yōu)解，則對偶規(guī)劃(D)也有最優(yōu)解，反之亦然，并且兩者的目標函數(shù)值相等證明: 考慮原規(guī)劃(P)的標準型(P2)設(shè) B為模型P2 的最優(yōu)解，現(xiàn)在證明對偶規(guī)劃D也有最優(yōu)解。由單純形法可知，此時29令 ，則有因此， 為對偶規(guī)劃(D)的可行解。另一方面其中 為原規(guī)劃的最優(yōu)解。由推論1可知 為對偶規(guī)劃(D)的最優(yōu)解30類似的，若對偶規(guī)劃(D)有最優(yōu)解，則原規(guī)劃(P)也有最優(yōu)解從定理3.2可以看到，對偶規(guī)劃(D)的最優(yōu)解 可以在原規(guī)劃(P)的檢驗數(shù) 中得到 由于 的后m列為單位

8、矩陣， 的后m個分量為031對偶規(guī)劃(D)的最優(yōu)解是原規(guī)劃(P)的最優(yōu)解的檢驗數(shù)中松弛變量對應(yīng)檢驗數(shù)的相反數(shù)。3233基變量解 引入松弛變量x4, x5將模型化為標準型，經(jīng)求解后得到其最優(yōu)單純形表34由此表可知，原問題的最優(yōu)解為x*=(0,25,25)T 最優(yōu)值為250.表中兩個松弛變量的檢驗數(shù)分別為-1/2, -2, 由上面的分析可知，對偶問題的最優(yōu)解為 (1/2, 2)T35影子價格363738 影子價格的經(jīng)濟含義 (1)影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價 企業(yè)可以根據(jù)現(xiàn)有資源的影子價格，對資源的使用有兩種考慮： 第一，是否將設(shè)備用于外加工或出租，若租費高于某設(shè)備的影子價格，可考

9、慮出租該設(shè)備，否則不宜出租 第二，是否將投資用于購買設(shè)備，以擴大生產(chǎn)能力，若市價低于某設(shè)備的影子價格，可考慮買進該設(shè)備，否則不宜買進39 （2） 影子價格表明資源增加對總效益產(chǎn)生的影響。根據(jù)推論“設(shè)x0和y0分別為原規(guī)劃P和對偶規(guī)劃D的可行解，當(dāng)cx0=bTy0時，x0、y0分別是兩個問題的最優(yōu)解”可知，在最優(yōu)解的情況下，有關(guān)系 因此，可以將z*看作是bi,i=1,2， ,m的函數(shù)，對bi求偏導(dǎo)數(shù)可得到 這說明，如果右端常數(shù)增加一個單位，則目標函數(shù)值的增量將是4041 影子價格反映了不同的局部或個體的增量可以獲得不同的整體經(jīng)濟效益。 如果為了擴大生產(chǎn)能力，考慮增加設(shè)備，就應(yīng)該從影子價格高的設(shè)備

10、入手。這樣可以用較少的局部努力，獲得較大的整體效益。 要指出，影子價格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。另外，影子價格的經(jīng)濟含義(2)，是指資源在一定范圍內(nèi)增加時的情況，當(dāng)某種資源的增加超過了這個“一定的范圍”時，總利潤的增加量則不是按照影子價格給出的數(shù)值線性地增加。這個問題還將在靈敏度分析一節(jié)中討論。424344現(xiàn)在公司有另外一筆資金585元，進行投資，利用影子價格分析，應(yīng)如何進行投資使公司獲得更多利潤？ 由上表可知，倉庫的影子價格y2=1/9，即為增加1m3的倉庫空間，可獲利潤1/9元。 現(xiàn)在已知增加1m3的倉庫需要0.8元，即每投資0.8元，可多

11、獲利1/9元。也就是每投資一元，可多獲利潤10/72元。 45倉庫的影子價格y1=11/45，即為增加1元的購買產(chǎn)品，可獲利潤11/45元。通過比較分析，應(yīng)該將投資用于購買產(chǎn)品A1，A2 將585元進行投資，最大利潤為 588* 11/45=143元46這一增量值，我們可以對改變條件的新模型的求解結(jié)果得到，新模型為最優(yōu)解為總利潤為533，利潤增量為533-390=143元47 對偶單純形法的基本思想 對偶單純形法的基本思想是：從原規(guī)劃的一個基本解出發(fā)，此基本解不一定可行，但它對應(yīng)著一個對偶可行解（檢驗數(shù)非正），所以也可以說是從一個對偶可行解出發(fā)；然后檢驗原規(guī)劃的基本解是否可行，即是否有負的分量

12、，如果有小于零的分量，則進行迭代，求另一個基本解，此基本解對應(yīng)著另一個對偶可行解（檢驗數(shù)非正）。對偶單純形法48 如果得到的基本解的分量皆非負則該基本解為最優(yōu)解。也就是說，對偶單純形法在迭代過程中始終保持對偶解的可行性(即檢驗數(shù)非正)，使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時得到對偶規(guī)劃與原規(guī)劃的可行解時，便得到原規(guī)劃的最優(yōu)解。49 對偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個基，其對應(yīng)的基滿足: 單純形表的檢驗數(shù)行全部非正（對偶可行）； 變量取值可有負數(shù)（非可行解）。 注：通過矩陣行變換運算，使所有相應(yīng)變量取值均為非負數(shù)即得到最優(yōu)單純形表。501.建立初始對偶單純形表,對應(yīng)一個基本

13、解,所有檢驗數(shù)均非正,轉(zhuǎn)2； 2.若基本解所有分量皆非負,則得到最優(yōu)解,停止;否則,若有bk0則選k行的基變量為出基變量,轉(zhuǎn)3 3.若所有akj0( j = 1,2,n )，則原問題無可行解,停止;否則,若有akj0 則選 =minj / akjakj0=r/akr那么 xr為進基變量,轉(zhuǎn)4； 4.以akr為轉(zhuǎn)軸元,作矩陣行變換使其變?yōu)?,該列其他元變?yōu)?,轉(zhuǎn)2。對偶單純形法求解線性規(guī)劃問題過程：51單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優(yōu)解計算計算典式對應(yīng)原規(guī)劃的基本解是可行的典式對應(yīng)原規(guī)劃的基本解的檢驗數(shù)所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優(yōu)解

14、沒有最優(yōu)解單純形法對偶單純形法52例3.8 用對偶單純形法求解下面線性規(guī)劃解: (1) 引入松弛變量x3, x4 , x5化為標準型，并在約束等式兩側(cè)同乘以-1得到：53x3, x4 , x5化為基變量，此式為典式形式，并且檢驗數(shù)均為非正，因此可構(gòu)造初始對偶單純形表為54 初始表中基本解的三個分量小于零，不是可行解，需要迭代求解新的基本解 (2) 定x4 為出基變量，按對偶 規(guī)則計算取x2為進基變量55(3) 以a22=-3為中心元素，進行迭代，迭代后的檢驗數(shù)仍保持非正(4) 經(jīng)檢驗，上表仍需迭代，取x3 為出基變量56x1 為出基變量，以a11=-5/3為中心進行迭代，這樣就可以得到原規(guī)劃的

15、最優(yōu)解 (3/5, 6/5, 0, 0, 11/5)T57例3.9 用對偶單純形法求解下面線性規(guī)劃58解：59對偶單純形法的適用范圍 適合于解如下形式的線性規(guī)劃問題在引入松弛變量化為標準型之后，約束等式兩側(cè)同乘-1，能夠立即得到檢驗數(shù)全部非正的原規(guī)劃基本解，可以直接建立初始對偶單純形表進行求解，非常方便。60 對于有些線性規(guī)劃模型，如果在開始求解時不能很快使所有檢驗數(shù)非正，最好還是采用單純形法求解。 因為，這樣可以免去為使檢驗數(shù)全部非正而作的許多工作。從這個意義上看，可以說，對偶單純形法是單純形法的一個補充。除此之外，在對線性規(guī)劃進行靈敏度分析中有時也要用到對偶單純形方法，可以簡化計算。61靈

16、敏度分析以前討論線性規(guī)劃問題時，假定系數(shù)都是常數(shù)。但實際上這些系數(shù)往往是估計值和預(yù)測值。因此提出這樣兩個問題：(1)當(dāng)這些系數(shù)有一個或幾個發(fā)生變化時，已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化；(2)這些系數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的最優(yōu)解或最優(yōu)基不變。62顯然，當(dāng)線性規(guī)劃問題中某一個或幾個系數(shù)發(fā)生變化后，原來已得結(jié)果一般會發(fā)生變化。當(dāng)然可以用單純形法從頭計算，以便得到新的最優(yōu)解。這樣做很麻煩，而且也沒有必要。在靈敏度分析采用的辦法，是從已得到的最優(yōu)解出發(fā)，通過對數(shù)據(jù)進行一些簡單的計算，便可迅速得到所需要的結(jié)果以及變化后的最優(yōu)解。因此，靈敏度分析也稱優(yōu)化后分析63考慮下面的線性規(guī)劃模型其

17、向量形式為64我們先給出一些矩陣的表達式： 1.檢驗數(shù)的向量表示 B為可行基 為系數(shù)矩陣A的第j列向量 cB, cB分別為基變量和非基變量的目標函數(shù)系數(shù)向量65 的展開形式為檢驗數(shù)的向量表示令662.基本解的矩陣表示 B對應(yīng)的典式基本解的矩陣表示對應(yīng)的目標函數(shù)的值為67研究最優(yōu)解受數(shù)據(jù)變化的影響情況主要考慮兩個方面： 1.是解的最優(yōu)性，即檢驗數(shù)是否仍然非正 2.是解的可行性，即基本解的各個分量是否非負68目標函數(shù)系數(shù)的變化 設(shè)只有一個系數(shù)cj變化，其它系數(shù)均保持不變，僅僅影響到檢驗數(shù)的變化1. ck是非基變量的系數(shù)2. ck是基變量的系數(shù)691. ck是非基變量的系數(shù)根據(jù)檢驗數(shù)的向量表示 非基

18、變量的系數(shù)ck的變化只影響與ck有關(guān)的檢驗數(shù)，所以只考慮 設(shè)ck的變化為ck，此時 的改變量為 70為了保持最優(yōu)解不變， 必須滿足 即為 為ck的變化上限 當(dāng)ck的變化超過此上限時，最優(yōu)解發(fā)生變化，應(yīng)求出新的檢驗數(shù)的值，繼續(xù)迭代求新的最優(yōu)解712.若 cl 是基變量的系數(shù)： 設(shè)cl變化為cl + cl那么，引入m維向量 72其中 為構(gòu)成 的第l個分量 為了使最優(yōu)解保持不變，要保證n-m個 ，則需要為了保持最優(yōu)解不變的 的變化范圍73當(dāng) 超過此范圍，應(yīng)該求出n-m個新檢驗數(shù) ，繼續(xù)迭代求新的最優(yōu)解747576解 (1) c3 是非基變量的目標系數(shù)當(dāng) 時，最優(yōu)解保持不變也就是說，當(dāng)?shù)谌N產(chǎn)品的單位

19、利潤小于等于19.2時，不宜安排生產(chǎn)，只有在利潤大于19.2元時候，生產(chǎn)第三種產(chǎn)品才有利潤 時，此時 77以x3為進基變量進行迭代，求最優(yōu)解最優(yōu)解為(0,1000/9,200/9)T, 最優(yōu)值為1777.7878這說明，當(dāng)c3變?yōu)?0后，應(yīng)生產(chǎn)第二和第三種產(chǎn)品，并且最大利潤增加了17元(2) c1是基變量系數(shù)為了保持最優(yōu)解不變，應(yīng)使下列不等式成立79解出由于c1=20，為了保持最優(yōu)解不變，應(yīng)該有 當(dāng) 超過此范圍，就會使檢驗數(shù) 中的某一個大于零，此時要取相應(yīng)的變量進行迭代，求最優(yōu)解 例如當(dāng)80 ，不滿足最優(yōu)性準則，所以，應(yīng)將所求的檢驗數(shù)去替換原檢驗數(shù)，并以x5為進基變量迭代，求新的最優(yōu)解81新的最優(yōu)解為(75,0,0)T, 最優(yōu)值為1875.這說明當(dāng)c1變?yōu)?5后，只生產(chǎn)第一種產(chǎn)品，最大利潤為1875元8283848586解:最優(yōu)解xB和B-1的值為設(shè) ，為了保持最優(yōu)解不變，應(yīng)使下式成立87整理后得 在此范圍內(nèi)，最優(yōu)基保持不變當(dāng) ，最優(yōu)基不變新的最優(yōu)解為88當(dāng) ，最優(yōu)基將發(fā)生變化，所以進行新的迭代求最優(yōu)解，基變量的值變?yōu)?其中出現(xiàn)了負分量，破壞了解的可行性 需要用新的解替換原來的解，用對偶單純形法迭代89得到的新最優(yōu)解為(400, 0, 0)T90約束條件中的系數(shù)變