管理運(yùn)籌學(xué)第3章 對偶規(guī)劃ppt課件

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

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

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

4、2210. .8(1),0zxxxxstxxx x設(shè)：兩種設(shè)備單位臺時(shí)租金分別為設(shè)：兩種設(shè)備單位臺時(shí)租金分別為 y1,y2由于承租方是理智的，會把租金壓至最由于承租方是理智的，會把租金壓至最低。故出租方在滿足上述二約束情況下，低。故出租方在滿足上述二約束情況下，至少出租總收入目標(biāo)函數(shù)為至少出租總收入目標(biāo)函數(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ù)學(xué)模型對偶問題的數(shù)學(xué)模型1 111 1111 11max,.,.,. .,.,.,0nnnnmmnnmnzc xc xa xa xbsta xaxbxx1111111111min,.,.,. .,.,.,0mnmmmnmnmnmzb yb ya ya ysta yayyycc（1對稱形式對偶問題對稱形式對偶問題 原問題原問題 對偶問題對偶問題3.1.2 對偶問題的數(shù)學(xué)模型對偶問題的數(shù)學(xué)模型（2非對稱形式對偶問題非對稱形式對偶問題1212121212m

6、ax22135. .280,zxxxxxxstxxxx無符號約束【例【例3.1】 寫出下列線性規(guī)劃的對偶規(guī)劃。寫出下列線性規(guī)劃的對偶規(guī)劃。對偶模型：對偶模型：123123123123min5822. .32wyyyyyystyyyyyy無約束,10,0123yyy3.1.3 對偶問題的基本性質(zhì)對偶問題的基本性質(zhì) 3.2 對偶單純形法簡介對偶單純形法簡介3.2 對偶單純形法簡介對偶單純形法簡介標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化（假設(shè)（假設(shè)乘乘-1）計(jì)算檢驗(yàn)數(shù)計(jì)算檢驗(yàn)數(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 解解 標(biāo)準(zhǔn)化標(biāo)準(zhǔn)化初始單純形表初始單純形表第第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 影子價(jià)格影子價(jià)格導(dǎo)入案例原問題的解如圖導(dǎo)入案例原問題的解如圖.12121212max32210. .8,0zxxxxstxxx x23,2186zCX 101,1188TwY b對偶問題的解對偶問題的解3.3 影子價(jià)格影子價(jià)格原問題原問題1 111max(1,.,). .0(1,., )njnijjijjzc xa xbimstxjn11min(1,., ). .0(1,.,)miiimjiijiizb ya ycjnstyim bi代表第i種資源擁有量 yi

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

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

11、058223cc 10230cc 3/ 21c 即即c2的允許變化范圍：的允許變化范圍：2.5, 53.4.2 右端項(xiàng)右端項(xiàng)bi的變化分析的變化分析設(shè)設(shè) 由式由式3-8，假設(shè)，假設(shè) 則最優(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 增加一個(gè)新變量的分析增加一個(gè)新變量的分析3.4.3 增加一個(gè)新變量的分析增加一個(gè)新變量的分析在操作上：由在操作上：由 若大于若大于0應(yīng)安排生產(chǎn)。應(yīng)安排生產(chǎn)。 【例【例3.6】 在例在例3.4 中增加一個(gè)新產(chǎn)品是否可行。其消耗系數(shù)列向量中增加一個(gè)新產(chǎn)品是否可行。其消耗系數(shù)列向量p6=（3/2，1，1/2及價(jià)值系數(shù)及價(jià)值系數(shù)c6=3.1*kkBkkkcC BpcY p161253/ 201110121

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

14、弛變量引入松弛變量 添加到最終單純形表中。添加到最終單純形表中。1242150 xx12642150 xxx將基向量變成單位向量。將基向量變成單位向量。3.5 如何看計(jì)算機(jī)求解報(bào)告如何看計(jì)算機(jī)求解報(bào)告【例【例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） 指在資源總量不變的情況下，指在資源總量不變的情況下，某一個(gè)變量在最優(yōu)解的基礎(chǔ)某一個(gè)變量在最優(yōu)解的基礎(chǔ)上增加上增加1個(gè)單位時(shí)，目標(biāo)成個(gè)單位時(shí)，目標(biāo)成本增加量。由求解結(jié)果可見，本增加量。由求解結(jié)果可見，X(2)=0，其縮減成本為，其縮減成本為2，表示如果表示如果X(2)入基后，每增入基后，每增加加1個(gè)

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

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

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