1、16:07,第三 講 線性規(guī)劃：靈敏度分析與對(duì)偶,李勇建 博士,主要內(nèi)容,線性規(guī)劃的對(duì)偶問題 線性規(guī)劃的靈敏度分析問題,16:07,16:07,線性規(guī)劃的對(duì)偶問題,對(duì)偶問題的來源 對(duì)偶問題的應(yīng)用和經(jīng)濟(jì)解釋 對(duì)偶問題的轉(zhuǎn)化,16:07,原問題,約束：,對(duì)偶問題,最優(yōu)解：x1=50, x2=250；Z*=27500,16:07,如果把三種資源分別以價(jià)格 出租或買出， 那么出讓相對(duì)于生產(chǎn)一單位第 j 種產(chǎn)品的資源消耗的價(jià)值應(yīng)不低于第 j 種產(chǎn)品的單位利潤(rùn)價(jià)值 因此有 但是買方會(huì)把價(jià)格壓到最低 ：,y1：,y2：,y3：,16:07,對(duì)偶問題,決策變量：yi 收買該公司一單位 i 種資源時(shí)付給的價(jià)格,

2、目標(biāo)函數(shù)：,約束：,此極小問題稱為原問題的對(duì)偶問題，解是,分別稱為原料1，2，3的影子價(jià)格或?qū)ε純r(jià)格.,.,16:07,y1,y2,y3,16:07,舉例,原問題 Max 50 x1+30 x2 S.t. 4x1+3x2120 2x1+x250 x1,x20,對(duì)偶問題 Min 120y1+50y2 S.t. 4y1+2y250 3y1+y2 30 y1,y20,16:07,對(duì)偶規(guī)劃的應(yīng)用,一般來說，線性規(guī)劃問題是確定資源的最優(yōu)分配方案；對(duì)偶問題則是確定對(duì)資源的恰當(dāng)估價(jià)，以確定資源的最有效利用； 可借助資源的影子價(jià)格確定一些內(nèi)部結(jié)算價(jià)格，以便控制有限資源的使用和考核下屬企業(yè)經(jīng)營(yíng)的好壞； 對(duì)于一些

3、緊缺資源，可以借助于影子價(jià)格機(jī)制規(guī)定上交的利潤(rùn)額，控制一些經(jīng)濟(jì)效益低的公司自覺地節(jié)約使用緊缺資源。,影子價(jià)值的內(nèi)涵,影子價(jià)格不是資源的實(shí)際價(jià)格，反映了資源配置結(jié)構(gòu)， 其它數(shù)據(jù)固定，某資源增加一單位導(dǎo)致目標(biāo)函數(shù)的增量。 對(duì)資源i總存量的評(píng)估：購(gòu)進(jìn) or 出讓 對(duì)資源i當(dāng)前分配量的評(píng)估：增加 or 減少 第一，影子利潤(rùn)說明增加哪種資源對(duì)經(jīng)濟(jì)效益最有利 第二，影子價(jià)格告知以怎樣的代價(jià)去取得緊缺資源 第三，影子價(jià)格是機(jī)會(huì)成本，提示資源出租/轉(zhuǎn)讓的基價(jià) 第四，利用影子價(jià)格分析新品的資源效果：定價(jià)決策 第五，利用影子價(jià)格分析現(xiàn)有產(chǎn)品價(jià)格變動(dòng)的資源緊性 第六，可以幫助分析工藝改變后對(duì)資源節(jié)約的收益 第七，可

4、以預(yù)知哪些資源是稀缺資源而哪些資源不稀缺,資源定價(jià)的決策方案,例：某廠生產(chǎn)甲乙產(chǎn)品，（1）如何安排每周的利潤(rùn)為最大? （2）如果企業(yè)可以不生產(chǎn)，那資源出讓如何定價(jià)？,1、最優(yōu)生產(chǎn)決策,資源定價(jià)的決策方案,2、資源獲利決策,如果決策者考慮自己不生產(chǎn)甲乙兩種產(chǎn)品，而把原擬用于生產(chǎn)這兩種產(chǎn)品的原材料、設(shè)備工時(shí)、電量資源全部出售給外單位，或者做代加工，則應(yīng)如何確定這三種資源的價(jià)格。,設(shè)原材料的單位出讓獲利為y1，設(shè)備工時(shí)的單位出讓獲利為y2，電量的單位出讓獲利為y3 。 出讓決策的線性規(guī)劃模型：,16:07,閱讀和自學(xué)： 參考書 P60-61，第3.3.4節(jié),16:07,想一想,產(chǎn)品的機(jī)會(huì)成本是什么:

5、 表示減少一件產(chǎn)品 j 所節(jié)省的資源可以增加的利潤(rùn). 產(chǎn)品的差額成本是什么:,16:07,如果 則用這些資源來生產(chǎn)這種產(chǎn)品更為有利可圖. 如果 表明已經(jīng)在其他地方以更為有利可圖的方式使用這些資源，沒有必 要生產(chǎn)產(chǎn)品j . 其經(jīng)濟(jì)解釋是:在利潤(rùn)最大化的生產(chǎn)計(jì)劃中 (1)邊際利潤(rùn)大于0的資源沒有剩余; (2)有剩余的資源邊際利潤(rùn)等于0; (3)安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本小于等于利潤(rùn); (4)機(jī)會(huì)成本大于利潤(rùn)的產(chǎn)品不安排生產(chǎn).,對(duì)偶問題的經(jīng)濟(jì)解釋,16:07,對(duì)偶的一般形式,16:07,16:07,例1：寫出下面線性規(guī)劃的對(duì)偶規(guī)劃,16:07,1，建立對(duì)偶表,16:07,y1 y2 y3,2，寫出對(duì)偶規(guī)

6、劃,16:07,閱讀和自學(xué)： 參考書 P56-59，第3.3.1和3.3.2節(jié),16:07,線性規(guī)劃的敏感性分析,什么是敏感性分析 偉恩德公司案例研究 目標(biāo)函數(shù)系數(shù)分析 右端項(xiàng)的影子價(jià)格分析,16:07,自己動(dòng)手,16:07,如果桌子的利潤(rùn)是$35，最優(yōu)解會(huì)怎樣變化呢？ 如果又有一個(gè)額外的大塊，會(huì)增加總利潤(rùn)嗎？ 如果桌子和椅子構(gòu)成改變，最優(yōu)解會(huì)變化嗎？ 如果還有一些原材料，你愿意以多大的代價(jià)購(gòu)買呢？,拼裝玩具生產(chǎn),自己動(dòng)手,你怎么來分析這些問題？,16:07,什么是敏感性分析,定義：建立數(shù)學(xué)模型和求得最優(yōu)解后，研究線性規(guī)劃的一個(gè)或多個(gè)參數(shù)（系數(shù)）ci , aij , bj 變化時(shí)，對(duì)最優(yōu)解產(chǎn)生

7、的影響 數(shù)學(xué)模型只是實(shí)際問題的一個(gè)粗略的抽象 最優(yōu)解一般只是針對(duì)某一特定的數(shù)學(xué)模型 管理者要對(duì)未來做各種假設(shè)，在這些假設(shè)下，測(cè)試可能產(chǎn)生的結(jié)果，通過對(duì)各種結(jié)果深入分析來指導(dǎo)決策 通常，在取得最初版本模型的最優(yōu)解之后，進(jìn)行分析才能取得對(duì)問題深入的認(rèn)識(shí) 這種分析稱為what-if分析或敏感性分析（Sensitivity Analysis） 意義： what-if分析可以表明改變這些決策對(duì)結(jié)果的影響，從而有效指導(dǎo)管理者作出最終的決策,16:07,偉恩德公司案例研究,實(shí)際舉例,16:07,偉恩德公司案例研究,修正的偉恩德例子，門的單位利潤(rùn)PD=$300降到PD=$200，而最優(yōu)解不變,實(shí)際舉例,16:

8、07,偉恩德公司案例研究,修正的偉恩德例子，門的單位利潤(rùn)PD=$300增加到PD=$500，而最優(yōu)解不變,實(shí)際舉例,16:07,偉恩德公司案例研究,修正的偉恩德例子，門的單位利潤(rùn)從PD=$300增加到PD=$1000，最優(yōu)解改變,實(shí)際舉例,16:07,偉恩德公司案例研究,在偉恩德的例子中系統(tǒng)改變門的單位利潤(rùn)得到數(shù)據(jù)表,實(shí)際舉例,16:07,偉恩德公司案例研究,其中最后三欄表示了門窗單位利潤(rùn)的最優(yōu)域。,實(shí)際舉例,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALL

9、OWABLE COEF INCREASE DECREASE X1 300.000000 450.000000 300.000000 X2 500.000000 INFINITY 300.000000,16:07,最優(yōu)域敏感性分析,如何在不重新求解模型的條件下，確定如果目標(biāo)函數(shù)的幾個(gè)系數(shù)同時(shí)變化，可能造成對(duì)最優(yōu)解的影響,如果偉恩德公司兩種新產(chǎn)品單位利潤(rùn)的估計(jì)值都是不精確的，將會(huì)對(duì)結(jié)果產(chǎn)生怎樣的影響？,16:07,偉恩德公司案例研究,修正的偉恩德問題模型，其中門，窗的單位利潤(rùn)分別被改為PD=$450,PW$400，但是最優(yōu)解不變,實(shí)際舉例,16:07,偉恩德公司案例研究,修正的偉恩德問題模型，其中

10、門，窗的單位利潤(rùn)分別被改為PD=$600,PW$300，從而最優(yōu)解改變,實(shí)際舉例,16:07,偉恩德公司案例研究,偉恩德例子中系統(tǒng)改變門，窗單位利潤(rùn)得到的數(shù)據(jù)表,實(shí)際舉例,16:07,百分之百法則,目標(biāo)函數(shù)系數(shù)同時(shí)變動(dòng)的百分之百法則(The 100 percent rule for simultaneous changes in objective function coefficients)： 如果目標(biāo)函數(shù)的系數(shù)同時(shí)變動(dòng)，計(jì)算出每一系數(shù)變動(dòng)量占該系數(shù)最優(yōu)域允許變動(dòng)量的百分比，而后，將各個(gè)系數(shù)的變動(dòng)百分比相加，如果所得的和不超過百分之一百，最優(yōu)解不會(huì)改變，如果超過百分之一百，則不能確定最優(yōu)解是

11、否改變。,16:07,可用于確定在保持最優(yōu)解不變的條件下，目標(biāo)函 數(shù)系數(shù)的變動(dòng)范圍 百分百法則通過將允許的增加或減少值在各個(gè)系數(shù)之間分?jǐn)偅瑥亩梢灾苯语@示出每個(gè)系數(shù)的允許變動(dòng)值 線性規(guī)劃研究結(jié)束以后，如果將來?xiàng)l件變 化，致使目標(biāo)函數(shù)中一部分或所有系數(shù)都發(fā)生變動(dòng)，百分百法則可以直接表明最初最優(yōu)解是否保持不變,百分之百法則的作用,16:07,右端項(xiàng)的影子價(jià)格分析,分析函數(shù)約束右端值變動(dòng)的原因也是不能得到模型的參數(shù)的精確值，只能對(duì)其作大略的估計(jì)。因此要知道萬一這些估計(jì)不準(zhǔn)確產(chǎn)生的后果 更主要的理由是因?yàn)檫@些常數(shù)往往不是由外界決定的而是管理層的政策決策。在建模并求解后，管理者想要知道如果改變這些決策是

12、否會(huì)提高最終收益 影子價(jià)格分析就是為管理者提供這方面的信息,16:07,影子價(jià)格,在給定線性規(guī)劃模型的最優(yōu)解和目標(biāo)函數(shù)相應(yīng)值的條件下，影子價(jià)格（shadow price）就是約束常數(shù)增加微小的量，使得目標(biāo)函數(shù)值增加的量。,16:07,Max z=20A+30B S.t. 工序1: 2A+B40 工序2: A+2B40 工序3: A+B25 非負(fù)約束：A0, B0 最優(yōu)解：A=10, B=15, Z=650 影子價(jià)格：工序1的為0；工序2的為10；工序3的為10,實(shí)際舉例,16:07,Max z=20A+30B S.t. 工序1: 2A+B 4041 工序2: A+2B40 工序3: A+B25

13、 非負(fù)約束：A0, B0 最優(yōu)解： A=15, B=10, Z=650 沒有變化，工序1的影子價(jià)格是0,16:07,Max z=20A+30B S.t. 工序1: 2A+B40 工序2: A+2B4041 工序3: A+B25 非負(fù)約束：A0, B0 最優(yōu)解：A=9, B=16, Z=650 660 增加了10元，工序2的影子價(jià)格是10 但是若增加太多，例如增加100小時(shí)，該約束不再是限制約束了，增加的價(jià)值反而不是1000元。也就是說存在上限。,16:07,Max z=20A+30B S.t. 工序1: 2A+B40 工序2: A+2B40 工序3: A+B2526 非負(fù)約束：A0, B0 最

14、優(yōu)解：A=12, B=14, Z=650 660 增加了10元，工序3的影子價(jià)格是10 同工序2，只有在生產(chǎn)能力有較小的變動(dòng)時(shí)適用,16:07,同時(shí)改變右端項(xiàng),如果，多個(gè)約束右端值同時(shí)變動(dòng)，那么管理層又 該如何來評(píng)估可能造成的影響呢？,這種問題很常見！,16:07,同時(shí)改變幾個(gè)或所有函數(shù)約束的約束右端值，如果這些變動(dòng)的幅度不大，那么可以用影子價(jià)格預(yù)測(cè)變動(dòng)產(chǎn)生的影響。如果所有的百分比之和不超過百分之一百，那么，影子價(jià)格還是有效的，如果所有的百分比之和超過百分之一百，那就無法確定影子價(jià)格是否有效,The 100 percent rule 百分之百法則,16:07,修正的偉恩德問題，其中一個(gè)小時(shí)的工

15、作時(shí)間從工廠3 移到工廠2，模型的求解。,實(shí)際舉例,Wyndor Case Study 偉恩德公司案例研究,16:07,不斷將工廠3的工作時(shí)間轉(zhuǎn)移到工廠2，從而生成數(shù)據(jù)表,實(shí)際舉例,Wyndor Case Study 偉恩德公司案例研究,16:07,百分之百法則,設(shè)參數(shù)a變化的最優(yōu)范圍的上下限分別為a,a，若參數(shù)a變化增加到a*，則可行增加的百分比(a*-a)/(a-a)；若參數(shù)a變化減少到a*，則可行減少的百分比(a -a*)/(a-a)。注意：不是(a -a*)/(a”-a)。 對(duì)所有變化的目標(biāo)函數(shù)系數(shù)，求其占可行增加和可行減少的百分比的絕對(duì)值之和。若絕對(duì)值之和不超過100%，則最優(yōu)解不變； 對(duì)所有變化的約束條件右側(cè)的值系數(shù)，求其占可行增加和可行減少的百分比的絕對(duì)值之和。若絕對(duì)值之和不超過100%，則影子價(jià)格起作用； 注意： 當(dāng)允許增加（減少）的量為無窮大時(shí)，則對(duì)任意增加（減少）的量，其允許增減（減少）的百分比均看做0； 百分百法則是充分條