1、第二章線性規(guī)劃的對偶理論及其應用,窗含西嶺千秋雪，門泊東吳萬里船 對偶是一種普遍現(xiàn)象,2,2.1 線性規(guī)劃的對偶理論 2.1.1 線性規(guī)劃原問題與對偶問題的表達形式,任何線性規(guī)劃問題都有其對偶問題 對偶問題有其明顯的經(jīng)濟含義,假設有商人要向廠方購買資源A和B，問他們談判原料 價格的模型是怎樣的？,3,例2.1.1,設A、B資源的出售價格分別為 y1 和 y2 顯然商人希望總的收購價越小越好 工廠希望出售資源后所得不應比生產(chǎn)產(chǎn)品所得少,目標函數(shù) min g(y)=25y1+15y2,4,2.1.1 線性規(guī)劃原問題與對偶問題的表達形式,5,2.1.1 線性規(guī)劃原問題與對偶問題的表達形式,6,2.1

2、.2 (max,)標準型的對偶變換,目標函數(shù)由 max 型變?yōu)?min 型 對應原問題每個約束行有一個對偶變量 yi，i=1,2,m 對偶問題約束為 型，有 n 行 原問題的價值系數(shù) C 變換為對偶問題的右端項 原問題的右端項 b 變換為對偶問題的價值系數(shù) 原問題的技術(shù)系數(shù)矩陣 A 轉(zhuǎn)置后成為對偶問題的技術(shù)系數(shù)矩陣矩陣 原問題與對偶問題互為對偶 對偶問題可能比原問題容易求解 對偶問題還有很多理論和實際應用的意義,7,2.1.3 非標準型的對偶變換,8,表2.1.1 對偶變換的規(guī)則,約束條件的類型與非負條件對偶 非標準的約束條件類型對應非正常的非負條件 對偶變換是一一對應的,9,弱對偶定理推論,

3、max問題的任何可行解目標函數(shù)值是其對偶min問題目標函數(shù)值的下限； min問題的任何可行解目標函數(shù)值是其對偶max問題目標函數(shù)值的上限 如果原max(min)問題為無界解，則其對偶min (max)問題無可行解 如果原max(min)問題有可行解，其對偶min (max)問題無可行解，則原問題為無界解,10,2.2.2 最優(yōu)解判別定理,定理 若原問題的某個可行解X0的目標函數(shù)值與對偶問題某個可行解Y0的目標函數(shù)值相等，則X0, Y0分別是相應問題的最優(yōu)解 證：由弱對偶定理推論1，結(jié)論是顯然的。 即CX0 = Y0b CX, Y0b = CX0 Yb 。 證畢。,2.2.3 主對偶定理 定理

4、如果原問題和對偶問題都有可行解，則它們都有最優(yōu)解，且它們的最優(yōu)解的目標函數(shù)值相等。 證：由弱對偶定理推論1可知，原問題和對偶問題的目標函數(shù)有界，故一定存在最優(yōu)解。 現(xiàn)證明定理的后一句話。,11,主對偶定理的證明,證：現(xiàn)證明定理的后一句話。 設 X0 為原問題的最優(yōu)解，它所對應的基矩陣是 B， X0= B1 b，則其檢驗數(shù)滿足 C CBB1A 0 令 Y0= CBB1，則有 Y0 A C。 顯然Y0為對偶問題的可行解。因此有對偶問題目標函數(shù)值， g(Y0)=Y0b= CBB1 b 而原問題最優(yōu)解的目標函數(shù)值為 f(X0)=CX0= CBB1 b 故由最優(yōu)解判別定理可知Y0 為對偶問題的最優(yōu)解。證

5、畢。 該定理的證明告訴我們一個非常重要的概念：對偶變量的最優(yōu)解等于原問題松弛變量的機會成本。 即對偶變量的最優(yōu)解是原問題資源的影子價格,12,2.2.4 互補松弛定理,定理 設X0, Y0分別是原問題和對偶問題的可行解，U0為原問題的松弛變量的值、V0為對偶問題剩余變量的值。X0, Y0分別是原問題和對偶問題最優(yōu)解的充分必要條件是 Y0 U0 + V0 X0 = 0 證：由定理所設，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2) 分別以Y0左乘(1)式，以X0右乘(2)式后，兩式相減，得 Y0 U0 + V0 X0 = Y0 b

6、C X0 若 Y0 U0 + V0 X0 = 0，根據(jù)最優(yōu)解判別定理， X0, Y0分別是原問題和對偶問題最優(yōu)解。反之亦然。 證畢。,13,2.2.5 原問題檢驗數(shù)與對偶問題的解,在主對偶定理的證明中我們有：對偶(min型)變量的最優(yōu)解等于原問題松弛變量的機會成本，或者說原問題松弛變量檢驗數(shù)的絕對值 容易證明，對偶問題最優(yōu)解的剩余變量解值等于原問題對應變量的檢驗數(shù)的絕對值 由于原問題和對偶問題是相互對偶的，因此對偶問題的檢驗數(shù)與原問題的解也有類似上述關(guān)系。 更一般地講，不管原問題是否標準，在最優(yōu)解的單純型表中，都有原問題虛變量(松弛或剩余) 的檢驗數(shù)對應其對偶問題實變量 (對偶變量)的最優(yōu)解，

7、原問題實變量(決策變量) 的檢驗數(shù)對應其對偶問題虛變量 (松弛或剩余變量)的最優(yōu)解。因此，原問題或?qū)ε紗栴}只需要求解其中之一就可以了。,14,例2.2.3 原問題檢驗數(shù)與對偶問題的解,15,16,17,2.3 對偶單純型算法,2.3.1 基本思路 原單純型迭代要求每步都是基礎(chǔ)可行解 達到最優(yōu)解時，檢驗數(shù) cjzj 0 (max) 或 cjzj 0 (min) 但對于(min, )型所加的剩余變量無法構(gòu)成初始基礎(chǔ)可行解，因此通過加人工變量來解決 大M法和二階段法較繁 能否從剩余變量構(gòu)成的初始基礎(chǔ)非可行解出發(fā)迭代，但保證檢驗數(shù)滿足最優(yōu)條件， cjzj 0 (max) 或 cjzj 0 (min)

8、每步迭代保持檢驗數(shù)滿足最優(yōu)條件，但減少非可行度 如何判斷達到最優(yōu)解 如何保證初始基礎(chǔ)解滿足最優(yōu)條件 為什么叫對偶單純型法,18,2.3.2 迭代步驟,確定出變量 找非可行解中最小者，即 min bi | bi0，設第 i*行的最負，則i*行稱為主行，該行對應的基變量為出變量，xi* 確定入變量 最大比例原則,設 j* 列滿足(2.3.1)式， j* 列稱為主列，xj* 為出變量 以主元 ai*j* 為中心迭代 檢查當前基礎(chǔ)解是否為可行解 若是，則當前解即為最優(yōu)解 否則，返回步驟 1,19,例2.3.1 對偶單純型解法,解：化原問題為適合對偶解法的標準型,20,表2.3.1 對偶單純型法的單純型

9、表(min),答：最優(yōu)解為x1=14, x3=8, x2=x4=0, OBJ=14,2.4 靈敏度分析,靈敏度分析又稱為后優(yōu)化分析,22,2.4 線性規(guī)劃的靈敏度分析,線性規(guī)劃是靜態(tài)模型 參數(shù)發(fā)生變化，原問題的最優(yōu)解還是不是最優(yōu) 哪些參數(shù)容易發(fā)生變化 C, b, A 每個參數(shù)發(fā)生多大的變化不會破壞最優(yōu)解 靈敏度越小，解的穩(wěn)定性越好,23,2.4.1 邊際值(影子價) qi,以(max,)為例 邊際值(影子價)qi 是指在最優(yōu)解的基礎(chǔ)上，當?shù)?i 個約束行的右端項 bi 減少一個單位時，目標函數(shù)的變化量,24,例2.4.2,25,關(guān)于影子價的一些說明,影子價是資源最優(yōu)配置下資源的理想價格，資源的

10、影子價與資源的緊缺度有關(guān) 松弛變量增加一個單位等于資源減少一個單位 剩余變量增加一個單位等于資源增加一個單位 資源有剩余，在最優(yōu)解中就有對應松弛變量存在，且其影子價為 0 影子價為 0，資源并不一定有剩余 應用，郵電產(chǎn)品的影子價格,26,2.4.2 價值系數(shù) cj 的靈敏度分析,cj 變動可能由于市場價格的波動，或生產(chǎn)成本的變動 cj 的靈敏度分析是在保證最優(yōu)解的基變量不變的情況下，分析cj 允許的變動范圍cj cj 的變化會引起檢驗數(shù)的變化，有兩種情況 非基變量對應的價值系數(shù)變化，不影響其它檢驗數(shù) 基變量對應的價值系數(shù)變化，影響所有非基變量檢驗數(shù) 1、非基變量對應的價值系數(shù)的靈敏度分析,27

11、,例2.4.2,28,2、基變量對應的價值系數(shù)的靈敏度分析,由于基變量對應的價值系數(shù)在CB中出現(xiàn)，因此它會影響所有非基變量的檢驗數(shù) 只有一個基變量的 cj 發(fā)生變化，變化量為 cj 令 cj 在CB中的第k行，研究非基變量xj 機會成本的變化,29,設x4的價值系數(shù)增加c4，對應k=2，,有一邊為空集如何處理,為什么akj=0不出現(xiàn)在任何一邊的集合中,與對偶單純型法找入變量的公式一樣,30,2.4.3 右端項 bi 的靈敏度分析,設XB=B1b是最優(yōu)解，則有XB=B1b0 b的變化不會影響檢驗數(shù) b的變化量b可能導致原最優(yōu)解變?yōu)榉强尚薪?31,2.4.3 右端項 bi 的靈敏度分析,32,以b

12、2為例, x6是對應的初始基變量，所以有,33,2.4.4 技術(shù)系數(shù) aij 的靈敏度分析,技術(shù)系數(shù)aij變化的影響比較復雜 對應基變量的 aij ，且資源bi已全部用完 對應基變量的 aij ，但資源bi未用完 對應非基變量的 aij ，且資源bi全用完或未用完 1、對應基變量的 aij ，且資源bi已全部用完 aij=0 2、對應基變量的 aij ，但資源bi未用完 aijxn+i /xj 上述兩個公式不充分，為什么？ B1發(fā)生變化，從而引起非基變量檢驗數(shù) cj zj 的變化 3、對應非基變量的 aij 只影響對應非基變量xj的檢驗數(shù) cj zj 若 aij 0，不會破壞最優(yōu)解 若 aij

13、 0，必須保證 cj zj 0,34,35,x1, x3為非基變量， q1= 0, q2= 0.25, q3= 1, 故有,x2, x4為基變量，x5=100, b1有剩余， 故有,36,2.4.5 新增決策變量的分析,例2.4.2中，若新增產(chǎn)品 x8，問是否生產(chǎn)？ 已知 c8=9, a18=5, a28=4, a38=3 計算 x8 的檢驗數(shù)可知生產(chǎn)是否有利,結(jié)論：生產(chǎn)x8有利。 將B1P8加入最優(yōu)單純型表中，以x8為入變量進行迭代,37,2.4.6 新增約束條件的分析,1、將最優(yōu)解代入新的約束條件，若滿足，則最優(yōu)解不變 2、若不滿足，則當前最優(yōu)解要發(fā)生變化；將新增約束條件加入最優(yōu)單純型表，

14、并變換為標準型 3、利用對偶單純型法繼續(xù)迭代 為什么可以利用對偶單純型法,例2.4.2 第2步,38,39,注意：最優(yōu)解的目標函數(shù)減少了25個單位,40,2.4.7 靈敏度分析舉例,例2.4.3 某工廠生產(chǎn)三種產(chǎn)品A, B, C，有五種生產(chǎn)組合方案。下兩表給出有關(guān)數(shù)據(jù)。規(guī)定每天供應A產(chǎn)品至少110 個，求收益最大的生產(chǎn)方案。,41,例2.4.3,解：設xj為已選定各種組合方案的組數(shù)(j=1,2,5)， x6為A產(chǎn)品的剩余變量， x7，x8分別為工人工時和機器工時的松弛變量。,42,例2.4.3,最優(yōu)解的B1是什么 產(chǎn)品A的影子價為多少 第II組方案的生產(chǎn)費用提高2元，是否要調(diào)整生產(chǎn)組別 若工人加班費為1元/小時，是否要采取加班措施 若通過租借機器增加工時，租費的上限應為多少 A產(chǎn)品的訂購合同是否有利 若要選用第IV組方案，該組的生產(chǎn)費用應降低多少 若工人加班費為0.3元/小時，最多允許加班時間多少 若機器租費低于44元/小時，問租幾部機器才合適(每天8小時計) 若第III組方案使機器工時減少0.5小時，能否被選入,43,2.5 參數(shù)線性規(guī)劃,2.4 節(jié)中 aij, bi, cj 只有一個發(fā)生變化，多個同時發(fā)生變化則很難解析 但在一些特殊情