1、運運 籌籌 學學Operations Research管理學院管理學院 饒慧饒慧電話：電話Q：1224414457工作地點：思齊工作地點：思齊107運運 籌籌 學學廣東白云學院廣東白云學院第三講第三講 對偶理論及靈敏度分析對偶理論及靈敏度分析對偶問題的概念對偶問題的概念1影子價格問題影子價格問題2對偶理論的應用對偶理論的應用3 3靈敏度分析靈敏度分析4 4運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶理論的概念對偶理論的概念【引例引例】某工廠決策者如何安排生產獲利最多？某工廠決策者如何安排生產獲利最多？ 項目項目產品產品I I產品產品II II可用能力可

2、用能力設備設備/ /臺時臺時1 13 38080原料原料/kg/kg2 21 16060利潤利潤4 45 5maxZ=4x1+5x2 s.tx1+3x280 2x1+x260 x1,x20 列出該問題的線性規劃模型為：列出該問題的線性規劃模型為：解得：解得：x1=x2=20 Z=180運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念【引例引例】若決策者決定不生產產品若決策者決定不生產產品I、II而決定將設備和而決定將設備和原料出售或出租，則應如何定價？原料出售或出租，則應如何定價？ 項目項目產品產品I I產品產品II II可用能力可用能力設備設備/ /臺時臺

3、時1 13 38080原料原料/kg/kg2 21 16060利潤利潤4 45 5y1+2y24 設設y1和和y2分別為設備和生產原料出售或出租的價格分別為設備和生產原料出售或出租的價格用用1 1臺時的設備和臺時的設備和2kg2kg原料可生產原料可生產1 1個產品個產品I I，獲利，獲利4 4元，故元，故 用用3 3臺時的設備和臺時的設備和1kg1kg原料可生產原料可生產1 1個產品個產品IIII，獲利，獲利5 5元，故元，故 3y1+y25 運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念【引例引例】若決策者決定不生產產品若決策者決定不生產產品I、II而決

4、定將設備和而決定將設備和原料出售或出租，則應如何定價？原料出售或出租，則應如何定價？ 項目項目產品產品I I產品產品II II可用能力可用能力設備設備/ /臺時臺時1 13 38080原料原料/kg/kg2 21 16060利潤利潤4 45 5設設y1和和y2分別為設備和生產原料出售或出租的價格分別為設備和生產原料出售或出租的價格所有設備和原料出租或出售的總收入所有設備和原料出租或出售的總收入 W=80y1+60y2決策者提出的是最低價格方案，因此此問題的目標函數為決策者提出的是最低價格方案，因此此問題的目標函數為 minW=80y1+60y2運運 籌籌 學學廣東白云學院廣東白云學院3.1 3

5、.1 對偶問題的概念對偶問題的概念綜合以上，得到以下線性規劃模型：綜合以上，得到以下線性規劃模型：minW=80y1+60y2s.t.y1+2y24 3y1+y25y1,y20 maxZ=4x1+5x2 s.t. x1+3x280 2x1+ x260 x1,x20 觀察可發現兩個問題的對稱性：觀察可發現兩個問題的對稱性：（1）求極大值和極小值）求極大值和極小值 （2）約束常數與價值系數）約束常數與價值系數（3）不等號）不等號（4）約束系數矩陣）約束系數矩陣運運 籌籌 學學廣東白云學院廣東白云學院從上面的例題我們可以以肴出，線性規劃有一個很有意思的特性：就是在形式上，可以形成一對對稱的問題。 對

6、任何求最大的線性規劃問題，都有一個與之對應的求最小值的問題，與這兩個問題有關的約束條件的系數矩陣具有相同的數據，僅在形式上互為轉置，并且目標函數系數與約束右端項互換，其目標函數的最優解雖然不同單最優值彼此相等。我們把線性規劃這一對稱問題成為對偶問題。3.1 3.1 對偶問題的概念對偶問題的概念3.1.1 對偶問題的概念 運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.2 對偶問題的標準形式 目標求最大值問題 所有的約束都是同向的“”決策變量非負原問題對偶問題目標求最小問題 所有的約束都是同向的 “”決策變量非負運運 籌籌 學學廣東白云學院廣東白云學院

7、3.1 3.1 對偶問題的概念對偶問題的概念3.1.2 對偶問題的標準形式 對偶問題 minW=bY YAC Y0項目項目原問題 maxZ=CX AXb X0原問題原問題對偶問題對偶問題目標函數系數目標函數系數c1,c2,cnb1,b2,bm限制常數限制常數b1,b2,bmc1,c2,cn限制方向限制方向約束系數約束系數a11,a12,a1na21,a22,a2nam1,am2,amna11,a21,am1a12,a22,am2a1n,a2n,amnAm nAn m運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.2 對偶問題的標準形式 【例題3-1】

8、 試寫出下列線性規劃問題的對偶問題maxZ=32x1+24x2+42x30.03x1+0.05x2+0.14x30.040.3x10.150.2x20.10.15x1+0.1x2+0.07x30.13s.t.x1，x2，x30minW=0.04y1+0.15y2+0.1y3+0.13y40.03y1+0.3y2+0.15y4320.05y1+0.2y3+0.1y4 240.14y1+0.07y4 42s.t.y1,y2,y3,y40運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.3 一般線性規劃問題的對偶模型 1.當當max線性規劃模型中有線性規劃模

9、型中有“”時的處理方法時的處理方法若第若第i i個約束條件的不等號為個約束條件的不等號為“”號，號，則其對偶的第則其對偶的第i i個變量小于個變量小于0 02.當當max線性規劃模型中有線性規劃模型中有“=”時的處理方法時的處理方法若第若第i i個約束條件的為個約束條件的為“= =”號時，號時，則其對偶的第則其對偶的第i i個變量為自由取值個變量為自由取值運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.3 一般線性規劃問題的對偶模型 原問題（或對偶問題）對偶問題（或原問題）目標函數maxZ目標函數minWn個00無約束n個=變量約束條件約束條件m個=

10、m個00無約束變量約束條件右端項目標函數變量的系數目標函數變量的系數約束條件右端項運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.3 一般線性規劃問題的對偶模型 【例題例題3-23-2】求下列線性規劃模型的對偶規劃求下列線性規劃模型的對偶規劃maxZ=4x1+5x2-7x3+2x42x1+x2-3x3+x45x1+2x3-x44x2+x3+x4=6x10，x2,x30，x4無約束無約束minW=5y1+4y2+6y32y1+y2y1+y3-3y1+2y2+y3y1-y2+y345-72=y10，y20，y3無約束無約束第一步：由對稱形式的對應關系寫出

11、對偶的部分第二步：將對偶約束條件的限制符號填入第三步：將對偶變量的限制符號填入對偶約束條件限制符號的方向與原問題變量限制符號對偶約束條件限制符號的方向與原問題變量限制符號相同相同對偶變量限制符號的方向與原問題約束條件限制符號對偶變量限制符號的方向與原問題約束條件限制符號相反相反運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.3 一般線性規劃問題的對偶模型 【課堂練習課堂練習】求下列線性規劃模型的對偶規劃求下列線性規劃模型的對偶規劃maxZ=x1+2x2+3x3+4x4-x1+x2-x3+3x456x1+7x2+3x3-5x4812x1-9x2-9x3

12、+9x420 x1,x2,x3,x40minW=5y1+8y2+20y3-y1+6y2+12y31y1+7y2-9y32-y1+3y2-9y333y1-5y2+9y34y1無約束，無約束，y20，y30大變小，變量同，約束反運運 籌籌 學學廣東白云學院廣東白云學院3.1 3.1 對偶問題的概念對偶問題的概念3.1.3 一般線性規劃問題的對偶模型 【課堂練習課堂練習】求下列線性規劃模型的對偶規劃求下列線性規劃模型的對偶規劃minZ=2x1+2x2+4x32x1+3x2+5x323x1+x2+7x33x1+4x2+6x35x1,x2,x30maxW=2y1+3y2+5y32y1+3y2+1y323

13、y1+y2+4y3 25y1+7y2+6y3 4y1，y20，y30小變大，約束同，變量反運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格【引例引例】企業管理者如何決策？企業管理者如何決策？項目項目產品產品I I產品產品II II可用能力可用能力設備設備/ /臺時臺時1 13 38080原料原料/kg/kg2 21 16060利潤利潤4 45 5maxZ=4x1+5x2 x1+3x280 2x1+x260 x1,x20 方案一：生產產品方案一：生產產品I和產品和產品IIx1=x2=20；Z=180方案二：出租或出售設備原料方案二：出租或出售設備原料 minW=80y1+

14、60y2y1+2y24 3y1+y25 y1,y20 y1=1.2 y2=1.4；W=180運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格從案例可以看出，采用方案一和方案二所獲得的利潤是等同的。從案例可以看出，采用方案一和方案二所獲得的利潤是等同的。也就是說，當達到最優解時，原問題域對偶問題的目標函數值相等也就是說，當達到最優解時，原問題域對偶問題的目標函數值相等,即即Z0=cx0=y0b=y10b1+y20b2+ym0bm 式式x0,y0分別為原問題與對偶問題的最優解分別為原問題與對偶問題的最優解 y0=（y10,y20,ym0）將將Z0對對bi求導，得到求導，得到

15、上式表明若原問題某一個約束條件的右端項上式表明若原問題某一個約束條件的右端項bibi每增加一個單位，每增加一個單位，則由此引起的最優目標函數值的增加量就等于與該條件相對應則由此引起的最優目標函數值的增加量就等于與該條件相對應的對偶變量的最優解值，稱之為影子價格。的對偶變量的最優解值，稱之為影子價格。(1,2,.,)im00iiZyb運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格影子價格的經濟含義影子價格的經濟含義方案一：生產產品方案一：生產產品I和產品和產品IImaxZ=4x1+5x2 x1+3x280 2x1+x260 x1,x20 x1=x2=20；Z=180若決

16、策者希望設備多工作若決策者希望設備多工作1 1個小時，個小時，能多獲得多少利潤呢？能多獲得多少利潤呢？x1=19.8, x2=20.4Z=181.2，Z=1.2=y1若決策者希望多用若決策者希望多用1kg1kg原材料，原材料，能多獲得多少利潤呢？能多獲得多少利潤呢？x1=20.6, x2=19.8Z=181.4，Z=1.4=y2運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格影子價格的經濟含義影子價格的經濟含義G對現有資源實現最大效益時的一種估價對現有資源實現最大效益時的一種估價生產產品？or 出租設備？若出租費高于設備的影子價格，可考慮出租購買設備擴大產能？or 維持

17、現狀？設備的市價低于其影子價格時可考慮購置運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格影子價格的經濟含義影子價格的經濟含義G資源量的變化對總效益的影響資源量的變化對總效益的影響購置設備擴大產能？購買原料？選擇影子價格高者運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格影子價格的經濟含義影子價格的經濟含義以教材第以教材第6464頁第頁第8 8題為例題為例建模建模：設設I,II,III三種產品在三種產品在A設備上生產的量分別為：設備上生產的量分別為：x11,x12,x13 在在B設備上生產的量分別為：設備上生產的量分別為：x21,x22,x23

18、在在C設備上生產的量分別為：設備上生產的量分別為：x31,x32,x33 總利潤為總利潤為ZmaxZ=2（x11+x21+x31）+2（x12+x22+x32）+2.9（x13+x23+x33）8x11+2x12+10 x1330010 x21+5x22+8x234002x31+13x32+10 x33420 xij0（i=1，2，3 j=1，2，3）求解求解: （1 1）確定最優生產規模）確定最優生產規模x12=150, x22=80, x31=210, Z=880運運 籌籌 學學廣東白云學院廣東白云學院3.2 3.2 影子價格影子價格影子價格的經濟含義影子價格的經濟含義以教材第以教材第64

19、64頁第頁第8 8題為例題為例討論討論：根據題意，租用設備根據題意，租用設備B需要需要1.8萬元，增加生產時間萬元，增加生產時間60臺時，臺時，問題即轉換為求設備問題即轉換為求設備B的影子價格。的影子價格。minW=300y1+400y2+420y3y11（2 2）租用設備）租用設備B B以擴大產能，是否劃算？以擴大產能，是否劃算？列出原問題的對偶形式并求解列出原問題的對偶形式并求解y22/5y31y1,y2,y30y1=1,y2=0.4,y3=1,Z=880B設備的影子價格對應設備的影子價格對應y2=0.4，亦即增加，亦即增加B設備設備1臺時可增加收入臺時可增加收入0.4元，元，增加增加60

20、臺時共可增加利潤：臺時共可增加利潤：0.460=2.4萬元，因此用萬元，因此用1.8萬元租用萬元租用B設備設備60臺時臺時是劃算的。是劃算的。運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析引入案例引入案例 Par公司是一家生產高爾夫器材的小型公司，它決定進入中高等價位的公司是一家生產高爾夫器材的小型公司，它決定進入中高等價位的高爾夫袋市場。分銷商對新產品十分感興趣，且同意買進高爾夫袋市場。分銷商對新產品十分感興趣，且同意買進ParPar公司未來三個月公司未來三個月內的全部新產品。內的全部新產品。 在對整個高爾夫袋生產步驟進行了調查以后，管理層明確了高爾夫袋的在對整

21、個高爾夫袋生產步驟進行了調查以后，管理層明確了高爾夫袋的生產過程包括：（生產過程包括：（1 1）切割與印染原材料；（）切割與印染原材料；（2 2）縫合；（）縫合；（3 3）成型（插入支撐）成型（插入支撐架、球棒分離裝置等）；（架、球棒分離裝置等）；（4 4）檢查與包裝。）檢查與包裝。 生產部門主管詳細分析了生產過程的每一步，得到不同產品的生產時間生產部門主管詳細分析了生產過程的每一步，得到不同產品的生產時間以及各部門生產時間的限制如表以及各部門生產時間的限制如表1 1所示。所示。 財務部門經過計算得到以下結論：生產一個標準袋的利潤為財務部門經過計算得到以下結論：生產一個標準袋的利潤為9 9元，

22、生產元，生產一個高級袋的利潤是一個高級袋的利潤是1010元。元。 請你給出一份詳細生產計劃報告。請你給出一份詳細生產計劃報告。 運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析引入案例引入案例部門部門切割與印染切割與印染縫合縫合成型成型檢查與包裝檢查與包裝生產時間（小時）生產時間（小時）最大生產時間最大生產時間（小時）（小時）標準袋標準袋高級袋高級袋7/101/211/1015/62/31/4630600708135表表1 運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析建模并求解建模并求解 假設假設S為生產標準袋的數量，為生產標準袋的數

23、量，D為生產高級袋的數量，為生產高級袋的數量，Z Z為總利潤。為總利潤。 maxZ=9S+10D7/10S+1D6301/2S+5/6D600S+2/3D7081/10S+1/4D135S,D0S=540D=252Z=7668J高爾夫袋銷售價格下降，會影響此最優生產組合嗎？J公司決定增加某個部門的生產能力，會影響此最優生產組合嗎？運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析 假設假設S為生產標準袋的數量，為生產標準袋的數量，D為生產高級袋的數量，為生產高級袋的數量，Z Z為總利潤。為總利潤。 maxZ=9S+10D7/10S+1D6301/2S+5/6D600S

24、+2/3D7081/10S+1/4D135S,D0S=540D=252Z=7668J高爾夫袋銷售價格下降，會影響此最優生產組合嗎？05001000150050010001500SD：7/10S+1D=6301/2S+5/6D=600：S+2/3D=708：1/10S+1/4D=135Z=10S+9D直線直線B的斜率的斜率目標函數線的斜率目標函數線的斜率直線直線A的斜率的斜率直線直線A直線直線B目標函數線逆時針旋轉，最優解不改變，目標函數線逆時針旋轉，最優解不改變，直至旋轉到直線直至旋轉到直線A處，出現多重解處，出現多重解目標函數線順時針旋轉，最優解不改變，目標函數線順時針旋轉，最優解不改變，直

25、至旋轉到直線直至旋轉到直線B處，出現多重解處，出現多重解運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析05001000150050010001500SD7/10S+D=6301/2S+5/6D=600S+2/3D=7081/10S+1/4/D=135Z=10S+9D運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析05001000150050010001500SD：7/10S+1D=6301/2S+5/6D=600：S+2/3D=708：1/10S+1/4D=135Z=10S+9D直線直線A直線直線B線段線段A的斜率的斜率KA=-7/10

26、，在，在D軸的截距是軸的截距是630線段線段B的斜率的斜率KB=-3/2，在，在D軸上的截距是軸上的截距是1062令目標函數直線方程為：令目標函數直線方程為：Z=CSS+CDD則目標函數的斜率則目標函數的斜率K=-CS/CDKAKKB-3/2-CS/CD-7/10假如高級袋的利潤不變，即假如高級袋的利潤不變，即CD=96.3CS13.5結果表明：在其他系數不變的情況下，只要標準袋的利潤在6.3元與 13.5元之間，540個標準袋和252個高級袋的生產組合總是 最優生產組合。運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析05001000150050010001500

27、SD：7/10S+1D=6301/2S+5/6D=600：S+2/3D=708：1/10S+1/4D=135Z=10S+9D直線直線A直線直線B同理在同理在CS不變的情況下，可計算得到：不變的情況下，可計算得到：6.67CD14.29結果表明：在其他系數不變的情況下，只要高級袋的利潤在6.67元至 14.29元之間，540個標準袋和252個高級袋的生產組合總是 最優生產組合。運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析-3/2-CS/CD-7/10結果表明：標準袋和高級袋利潤變化的比值不超過此范圍，最優生產 組合便不會發生變化。思考：如果標準袋和高級袋的利潤都發

28、生的變化，最優產量組合會怎樣變化呢？運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析 假設假設S為生產標準袋的數量，為生產標準袋的數量，D為生產高級袋的數量，為生產高級袋的數量，Z Z為總利潤。為總利潤。 maxZ=9S+10D7/10S+1D6301/2S+5/6D600S+2/3D7081/10S+1/4D135S,D0J公司決定增加某個部門的生產能力，會影響此最優生產組合嗎？約束條件約束條件限制值限制值實際值實際值差異值差異值7/10S+1D630在最優生產組合時各部門的工時利用情況在最優生產組合時各部門的工時利用情況（S=540，D=252）63001/2S

29、+5/6D600480120S+2/3D70870801/10S+1/4D13511718結果表明：切割印染部門和成型部門的資源充分利用，增加這兩個部門 的生產能力會影響最優生產組合。切割切割縫合縫合成型成型檢查檢查運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析J公司決定增加某個部門的生產能力，會影響此最優生產組合嗎？結論：1.增加切割和成型兩個部門的生產能力以增加利潤。 2.合理利用縫合部門剩余的工時（120小時）和檢查部門剩余 的工時（18小時）以免造成成本浪費。運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析靈敏度分析（敏感性分析）主要研究和分析線性規劃問題中各參數波動對最優解的影響程度。利用靈敏度分析可以在不改變既有模型的基礎上，為分析問題和決策提供相關的信息。運運 籌籌 學學廣東白云學院廣東白云學院3.3 3.3 靈敏度分析靈敏度分析靈敏度分析報告運運 籌籌 學學廣東白云學院廣東