管理運籌學第3章 對偶規(guī)劃ppt課件

1、第第3章章 對偶規(guī)劃對偶規(guī)劃教學目標與要求教學目標與要求n【教學目標】n通過對本章的學習，理解對偶定義和性質及影子價格的含義；了解對偶單純形法；會根據(jù)最終單純形表對于資源項、目標系數(shù)變動進行敏感性分析。n【知識結構】本章主要內容本章主要內容 n3.1 線性規(guī)劃的對偶模型線性規(guī)劃的對偶模型n3.1.1 對偶問題對偶問題n3.1.2 線性規(guī)劃對偶模型線性規(guī)劃對偶模型n3.1.3 對偶問題的基本性質對偶問題的基本性質n3.2 對偶單純形法簡介對偶單純形法簡介n3.3 影子價格影子價格n3.4 靈敏度分析靈敏度分析n3.4.1 價值系數(shù)的變化分析價值系數(shù)的變化分析n3.4.2 右端常數(shù)的變化分析右端常

2、數(shù)的變化分析n3.4.3 增加一個新變量的分析增加一個新變量的分析n3.4.4 增加新的約束條件的分析增加新的約束條件的分析n3.5 如何看計算機求解報告如何看計算機求解報告n本章小結本章小結導入案例導入案例出租還是自己組織生產(chǎn)？出租還是自己組織生產(chǎn)？第第2章導入案例中的數(shù)學模型章導入案例中的數(shù)學模型任何一個線性規(guī)劃問題都存在一任何一個線性規(guī)劃問題都存在一個伴生的線性規(guī)劃問題，我們稱個伴生的線性規(guī)劃問題，我們稱之為之為“對偶對偶”。本章將討論對偶。本章將討論對偶問題模型的建立、影子價格及敏問題模型的建立、影子價格及敏感性分析。感性分析。12121212max32210. .8,0zxxxxst

3、xxx x現(xiàn)在換個角度討論這個問題?，F(xiàn)在換個角度討論這個問題。假若由于某種原因，該企業(yè)打算放棄生產(chǎn)產(chǎn)品的項目，而將所有設備出租，假若由于某種原因，該企業(yè)打算放棄生產(chǎn)產(chǎn)品的項目，而將所有設備出租，收取租金。那么，在考慮到設備出租市場競爭條件下，如何確定三種設備收取租金。那么，在考慮到設備出租市場競爭條件下，如何確定三種設備單位臺時的租金，才能使企業(yè)不至于蝕本。單位臺時的租金，才能使企業(yè)不至于蝕本。問題：問題：1. 如何建立該問題的數(shù)學模型？如何建立該問題的數(shù)學模型？ 3. 用什么方法對該問題模型求解？用什么方法對該問題模型求解？3.1.1 對偶問題對偶問題原始規(guī)劃原始規(guī)劃12121212max3

4、2210. .8(1),0zxxxxstxxx x設：兩種設備單位臺時租金分別為設：兩種設備單位臺時租金分別為 y1,y2由于承租方是理智的，會把租金壓至最由于承租方是理智的，會把租金壓至最低。故出租方在滿足上述二約束情況下，低。故出租方在滿足上述二約束情況下，至少出租總收入目標函數(shù)為至少出租總收入目標函數(shù)為12min810wyy約束一：生產(chǎn)甲產(chǎn)品的利潤不大于放棄生約束一：生產(chǎn)甲產(chǎn)品的利潤不大于放棄生產(chǎn)而出租的租金收入產(chǎn)而出租的租金收入1223yy約束二：生產(chǎn)乙產(chǎn)品的利潤不大于放棄生約束二：生產(chǎn)乙產(chǎn)品的利潤不大于放棄生產(chǎn)而出租的租金收入產(chǎn)而出租的租金收入122yy對偶規(guī)劃對偶規(guī)劃1212121

5、2min810210. .8(2),0wyyyystyyy y稱稱2為為1的對偶，也稱的對偶，也稱1為為2的對偶。的對偶。3.1.2 對偶問題的數(shù)學模型對偶問題的數(shù)學模型1 111 1111 11max,.,.,. .,.,.,0nnnnmmnnmnzc xc xa xa xbsta xaxbxx1111111111min,.,.,. .,.,.,0mnmmmnmnmnmzb yb ya ya ysta yayyycc（1對稱形式對偶問題對稱形式對偶問題 原問題原問題 對偶問題對偶問題3.1.2 對偶問題的數(shù)學模型對偶問題的數(shù)學模型（2非對稱形式對偶問題非對稱形式對偶問題1212121212m

6、ax22135. .280,zxxxxxxstxxxx無符號約束【例【例3.1】 寫出下列線性規(guī)劃的對偶規(guī)劃。寫出下列線性規(guī)劃的對偶規(guī)劃。對偶模型：對偶模型：123123123123min5822. .32wyyyyyystyyyyyy無約束,10,0123yyy3.1.3 對偶問題的基本性質對偶問題的基本性質 3.2 對偶單純形法簡介對偶單純形法簡介3.2 對偶單純形法簡介對偶單純形法簡介標準化標準化（假設（假設乘乘-1）計算檢驗數(shù)計算檢驗數(shù)所有所有0?Yes所有所有b0?不符合對偶單純形法不符合對偶單純形法條件，改用大條件，改用大M法法No完畢完畢Yes找到最找到最優(yōu)解優(yōu)解No找出最小找出

7、最小bkxk為離去變量為離去變量所有所有akj0?s=minakj/j|j0，xs入基，迭代得新單純形表No無可無可行解行解Yes3.2 對偶單純形法簡介對偶單純形法簡介【例【例3.2】用對偶單純形法解】用對偶單純形法解12323123123min1524562521. .,0wyyyyyyyysty yy1232341235max1524562. .5210(1,2,.,5)jzyyyyyystyyyyyj 解解 標準化標準化初始單純形表初始單純形表第第1次迭代次迭代第第2次迭代次迭代最優(yōu)解最優(yōu)解最優(yōu)值最優(yōu)值203.2 對偶單純形法簡介對偶單純形法簡介【例【例3.3】用對偶單純形法解】用對偶

8、單純形法解12123124max221. .120(1,2,3,4)jzxxxxxstxxxxj B20A2j0無可行解無可行解3.3 影子價格影子價格導入案例原問題的解如圖導入案例原問題的解如圖.12121212max32210. .8,0zxxxxstxxx x23,2186zCX 101,1188TwY b對偶問題的解對偶問題的解3.3 影子價格影子價格原問題原問題1 111max(1,.,). .0(1,., )njnijjijjzc xa xbimstxjn11min(1,., ). .0(1,.,)miiimjiijiizb ya ycjnstyim bi代表第i種資源擁有量 yi

9、 代表第i種資源的估價，該估價并非市價格，而是在生產(chǎn)中的單位貢獻所做的估價,稱為影子價格。其含義：（1資源的市場價格由供求關系決定，而它的影子價格則有賴于資源的利用情況。（2影子價格是一種邊際價格。（3資源的影子價格實際上又是一種機會成本。（4當影子價格為0時，表明該種資源未得到充分利用；當影子價格不為0時，表明該種資源已耗費完畢。（5在一個大公司內部，可借助資源的影子價格確定一些內部結算價格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營的好壞。/iiywb 對偶問題對偶問題3.4 靈敏度分析靈敏度分析n線性規(guī)劃的各個參數(shù)A，C，b往往是根據(jù)統(tǒng)計數(shù)據(jù)測算的，不可能完全準確，而且隨著實際情況變化。靈

10、敏度分析是指各參數(shù)變化對最優(yōu)解的影響。3.4.1 價值系數(shù)價值系數(shù)cj的變化分析的變化分析由式由式3-7 可知，可知，cj變化僅影響檢驗數(shù)。敏感性分析是求變化僅影響檢驗數(shù)。敏感性分析是求檢驗數(shù)符號不變最優(yōu)基不變時檢驗數(shù)符號不變最優(yōu)基不變時cj的允許變化范圍。的允許變化范圍?！纠纠?.4】 由下述模型的最終單純形表求最優(yōu)基不變的由下述模型的最終單純形表求最優(yōu)基不變的c2允許變化范圍。允許變化范圍。1jjBjCC B p1212121212max54390280. .45,0zxxxxxxstxxx x令令c2=4+c，有：，有：若保持檢驗數(shù)非正，要求：若保持檢驗數(shù)非正，要求：40541cc 5

11、058223cc 10230cc 3/ 21c 即即c2的允許變化范圍：的允許變化范圍：2.5, 53.4.2 右端項右端項bi的變化分析的變化分析設設 由式由式3-8，假設，假設 則最優(yōu)基保持不變則最優(yōu)基保持不變. 【例【例3.5】 由由例例3.4最終單純形表求最優(yōu)基不變的最終單純形表求最優(yōu)基不變的b3允許變化范圍。允許變化范圍。bbb 10bB b1212121212max54390280. .45,0zxxxxxxstxxx xbbb 1212121212max54390280. .45,0zxxxxxxstxxx x312345113100021010011001pppppp10bB

12、bbbb 1|E B初始基初始基|B E最優(yōu)基最優(yōu)基333255350102bbb 13125900118001245B bb355b 即即b3的允許變化范圍：的允許變化范圍：40, 503.4.3 增加一個新變量的分析增加一個新變量的分析3.4.3 增加一個新變量的分析增加一個新變量的分析在操作上：由在操作上：由 若大于若大于0應安排生產(chǎn)。應安排生產(chǎn)。 【例【例3.6】 在例在例3.4 中增加一個新產(chǎn)品是否可行。其消耗系數(shù)列向量中增加一個新產(chǎn)品是否可行。其消耗系數(shù)列向量p6=（3/2，1，1/2及價值系數(shù)及價值系數(shù)c6=3.1*kkBkkkcC BpcY p161253/ 201110121

13、/ 2B p1*kkBkkkcC BpcY p65/ 2c11/ 201666BcC Bp663,1/ 2,c時值得安排6(0,5,4) 1,1/ 2,0Tc3.4.4 增加一個新的約束分析增加一個新的約束分析增加一個新的約束后，線性規(guī)劃的可行域只會變小，不會變大，最優(yōu)值增加一個新的約束后，線性規(guī)劃的可行域只會變小，不會變大，最優(yōu)值只能變差，不會變的更好。因此如果原最優(yōu)解只能變差，不會變的更好。因此如果原最優(yōu)解X*滿足新的約束條件，則滿足新的約束條件，則X*仍然是最優(yōu)解；否則繼續(xù)進行迭代。仍然是最優(yōu)解；否則繼續(xù)進行迭代?！纠纠?.7】 在例在例3.4中增加一個新的約束中增加一個新的約束引入松

14、弛變量引入松弛變量 添加到最終單純形表中。添加到最終單純形表中。1242150 xx12642150 xxx將基向量變成單位向量。將基向量變成單位向量。3.5 如何看計算機求解報告如何看計算機求解報告【例【例3.8】Global optimal solution found.Objective value:35.00000Total solver iterations: 2Variable ValueReduced CostX( 1) 5.0000000.000000X( 2) 0.000000 2.000000X( 3)5.000000 0.000000RowSlack or Surplus

15、 Dual Price135.000001.00000020.0000000.200000030.0000000.6000000Ranges in which the basis is unchanged: Objective Coefficient RangesCurrent Allowable AllowableVariable CoefficientIncreaseDecreaseX( 1) 3.000000 1.8000000.6000000X( 2) 1.0000002.000000INFINITYX( 3) 4.0000001.0000001.500000 Righthand Si

16、de RangesRow CurrentAllowableAllowableRHSIncrease Decrease255.0000025.0000015.000003 40.0000015.0000012.50000最優(yōu)值最優(yōu)值迭代次數(shù)迭代次數(shù)最優(yōu)解最優(yōu)解縮減成本縮減成本Reduced Cost） 指在資源總量不變的情況下，指在資源總量不變的情況下，某一個變量在最優(yōu)解的基礎某一個變量在最優(yōu)解的基礎上增加上增加1個單位時，目標成個單位時，目標成本增加量。由求解結果可見，本增加量。由求解結果可見，X(2)=0，其縮減成本為，其縮減成本為2，表示如果表示如果X(2)入基后，每增入基后，每增加加1個

17、單位，成本將增加個單位，成本將增加2個個單位。單位。松弛或剩余變量松弛或剩余變量Slack or Surplus） 反映了資源的利用情反映了資源的利用情況。若松弛變量為況。若松弛變量為0，表示該資源，表示該資源已耗費完畢，若大于已耗費完畢，若大于0，表示尚有，表示尚有剩余。本例剩余。本例2個約束的松弛變量個約束的松弛變量第第2、3行均為行均為0，表示兩種資，表示兩種資源均已耗費完畢。而第源均已耗費完畢。而第1行是生產(chǎn)行是生產(chǎn)一個單位產(chǎn)品所消耗的各項資源一個單位產(chǎn)品所消耗的各項資源的影子價格的總和，稱為產(chǎn)品的的影子價格的總和，稱為產(chǎn)品的隱含成本。隱含成本。影子價格影子價格Dual Price的含

18、義的含義見節(jié)見節(jié)3.3。當松弛變量為。當松弛變量為0時，影時，影子價格大于子價格大于0。目標系數(shù)當前值目標系數(shù)當前值保持最優(yōu)基不變時允許增量保持最優(yōu)基不變時允許增量保持最優(yōu)基不變時允許減量保持最優(yōu)基不變時允許減量1232.44.8-2.5ccc35本章小結本章小結n 本章主要內容包括線性規(guī)劃對偶問題；線性規(guī)劃原模型與對偶模型本章主要內容包括線性規(guī)劃對偶問題；線性規(guī)劃原模型與對偶模型之間的結構關系；基于線性規(guī)劃對偶問題的資源影子價格的含義；之間的結構關系；基于線性規(guī)劃對偶問題的資源影子價格的含義；各參數(shù)變化的敏感性分析；對偶單純形法。各參數(shù)變化的敏感性分析；對偶單純形法。 n原始規(guī)劃的解與對偶規(guī)

19、劃的解之間有一些重要的關系，這些基本性原始規(guī)劃的解與對偶規(guī)劃的解之間有一些重要的關系，這些基本性質統(tǒng)稱為對偶定理，包括對稱性定理，弱對偶定理，最優(yōu)性準則定質統(tǒng)稱為對偶定理，包括對稱性定理，弱對偶定理，最優(yōu)性準則定理，主對偶定理。理，主對偶定理。n對偶變量表示一個單位第對偶變量表示一個單位第i種資源的估價，這種估價不是資源的市場種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，價格，而是根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價，為區(qū)別起見，稱為影子價格稱為影子價格Shadow price），），n線性規(guī)劃的靈敏度分析就是研究參數(shù)變化時對最優(yōu)解的影響。具體