第3章 北理工運籌學課件_第1頁
第3章 北理工運籌學課件_第2頁
第3章 北理工運籌學課件_第3頁
第3章 北理工運籌學課件_第4頁
第3章 北理工運籌學課件_第5頁
已閱讀5頁,還剩47頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、1第三章 線性規劃問題的對偶與靈敏度分析w線性規劃的對偶問題概念、理論及經濟意義w線性規劃的對偶單純形法w線性規劃的靈敏度分析本章內容重點21.1.線性規劃對偶問題線性規劃對偶問題 對偶原理 對偶問題定義 線性規劃問題寫出其對偶問題,要掌握在對稱形式和非對稱情況下由原問題寫出對偶問題的方法。 對偶定理 只需了解原問題與對偶問題解的關系,證明從略。3 1.對偶問題: 若第二章例2.1問題的設備都用于外協加工,工廠收取加工費。試問:設備 A、B、C 每工時各如何收費才最有競爭力? 設 y1 ,y2 ,y3 分別為每工時設備 A、B、C 的收取費用。1.1.線性規劃對偶問題線性規劃對偶問題4線性規劃

2、原問題線性規劃原問題 例2.1:某工廠擁有A、B、C三種類型的設備,生產甲、乙兩種產品。每件產品在生產中需要占用的設備機時數,每件產品可以獲得的利潤以及三種設備可利用的時數如下表所示。求獲最大利潤的方案。 產品甲產品乙設備能力(h)設備A3 32 26565設備B2 21 14040設備C0 03 37575利潤(元/件)1500150025002500 5 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原問題原問題 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 + 75y3 s.t. 3y1+2y2 1

3、500 (不少于甲產品的利潤) 2y1+y2+3y3 2500 對偶問題對偶問題 (不少于乙產品的利潤) y1, y2 , y3 01.1.線性規劃對偶問題線性規劃對偶問題6 2、對偶定義 對稱形式: 互為對偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”1.1.線性規劃對偶問題線性規劃對偶問題7 一對對稱形式的對偶規劃之間具有下面的對應關系。 (1)若一個模型為目標求“極大”,約束為“小于等于”的不等式,則它的對偶模型為目標求“極小”,約束是“大于等于”的不等式。即“max

4、,”和“min,”相對應。1.1.線性規劃對偶問題線性規劃對偶問題8 (2)從約束系數矩陣看:一個模型中為,則另一個模型中為AT。一個模型是m個約束,n個變量,則它的對偶模型為n個約束,m個變量。 (3)從數據b、C的位置看:在兩個規劃模型中,b和C的位置對換。 (4)兩個規劃模型中的變量皆非負。1.1.線性規劃對偶問題線性規劃對偶問題9 非對稱形式的對偶規劃 一般稱不具有對稱形式的一對線性規劃為非對稱形式的對偶規劃。 對于非對稱形式的規劃,可以按照下面 的對應關系直接給出其對偶規劃。 (1)將模型統一為“max,”或“min,” 的形式,對于其中的等式約束按下面(2)、(3)中的方法處理;

5、(2)若原規劃的某個約束條件為等式約束,則在對偶規劃中與此約束對應的那個變量取值沒有非負限制;1.1.線性規劃對偶問題線性規劃對偶問題1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c1x2x3x0jx1y11a12a13a1b2y21a22a23a2b3y31a32a33a3b4y41a42a43a4b0jy1c2c3c10 (3)若原規劃的某個變量的值沒有非負限

6、制,則在對偶問題中與此變量對應的那個 約束為等式。 下面對關系(2)作一說明。對于關系(3) 可以給出類似的解釋。 設原規劃中第一個約束為等式: a11x1 + + a1nxn = b1 那么,這個等式與下面兩個不等式等價1.1.線性規劃對偶問題線性規劃對偶問題111.1.線性規劃對偶問題線性規劃對偶問題1111111111.bxaxabxaxannnn這樣,原規劃模型可以寫成mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn, 2 , 1, 0max11111111111111121.1.線性規劃對偶問題線性規劃對偶問題 此時已轉化為對稱形式,直接寫出對偶規劃沒有非負限制

7、121111112211211211111111221111,0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm這里,把 y1 看作是 y1 = y1 - y1,于是 y1 沒有非負限制,關系(2)的說明完畢。131.1.線性規劃對偶問題線性規劃對偶問題 例3.1 寫出下面線性規劃的對偶規劃模型解 先將約束條件變形為“”形式沒有非負限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ141.1.線性規劃對偶問題線性規劃對偶問題沒有非負限制432144321

8、4314321,0,051030422602722523xxxxxxxxxxxxxxxx 再根據非對稱形式的對應關系,直接寫出對偶規劃151.1.線性規劃對偶問題線性規劃對偶問題0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf沒有非負限制16 3.對偶定理(原問題與對偶問題解的關系)考慮(LP)和(DP) 定理3-1 (弱對偶定理) 若 x, y 分別為(LP) 和(DP)的可行解,那么cTx bTy。 推論 若(LP)可行,那么(LP)無有限最優解的充分必要條件是(LD)無可行解。1.1.線性規劃對

9、偶問題線性規劃對偶問題17 定理3-2 (最優性準則定理) 若x,y分別(LP),(DP)的可行解,且cTx=bTy ,那么x,y分別為(LP)和(DP)的最優解。 定理3-3 (主對偶定理) 若(LP)和(DP)均可行 那么(LP)和(DP)均有最優解,且最優值相等。 以上定理、推論對任意形式的相應性規劃的對偶均有效1.1.線性規劃對偶問題線性規劃對偶問題18 4. 4.影子價格影子價格 是一個向量,它的分量表示最優目標值隨相應資源數量變化的變化率。 若x*,y* 分別為(LP)和(DP)的最優解, 那么, cT x* = bT y* 。 根據 f = bTy*=b1y1*+b2y2*+bm

10、ym* 可知 f / bi = yi* yi* 表示 bi 變化1個單位對目標 f 產生的影響,稱 yi* 為 bi的影子價格。 注意:注意:若 B 是最優基, y* = (BT)-1 cB 為影子價格向量。1.1.線性規劃對偶問題線性規劃對偶問題19 影子價格的經濟含義 (1)影子價格是對現有資源實現最大效益時的一種估價 企業可以根據現有資源的影子價格,對資源的使用有兩種考慮:第一,是否將設備用于外加工或出租,若租費高于某設備的影子價格,可考慮出租該設備,否則不宜出租。第二,是否將投資用于購買設備,以擴大生產能力,若市價低于某設備的影子價格,可考慮買進該設備,否則不宜買進。1.1.線性規劃對

11、偶問題線性規劃對偶問題201.1.線性規劃對偶問題線性規劃對偶問題 (2) 影子價格表明資源增加對總效益產生的影響。根據推論推論“設x0和y0分別為原規劃(P)和對偶規劃(D)的可行解,當cx0=bTy0時,x0、y0分別是兩個問題的最優解”可知,在最優解的情況下,有關系 因此,可以將z*看作是bi,i=1,2, ,m的函數,對bi求偏導數可得到 這說明,如果右端常數增加一個單位,則目標函數值的增量將是*22*11*mmybybybfZmiybZii,2,1,*miyi,2,1,*21 影子價格反映了不同的局部或個體的增量可以獲得不同的整體經濟效益。如果為了擴大生產能力,考慮增加設備,就應該從

12、影子價格高的設備入手。這樣可以用較少的局部努力,獲得較大的整體效益。1.1.線性規劃對偶問題線性規劃對偶問題22 需要指出,影子價格不是固定不變的,當約束條件、產品利潤等發生變化時,有可能使影子價格發生變化。另外,影子價格的經濟含義(2),是指資源在一定范圍內增加時的情況,當某種資源的增加超過了這個“一定的范圍”時,總利潤的增加量則不是按照影子價格給出的數值線性地增加。這個問題還將在靈敏度分析一節中討論。1.1.線性規劃對偶問題線性規劃對偶問題23 5.由最優單純形表求對偶問題最優解 標準形式: Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x

13、1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 01.1.線性規劃對偶問題線性規劃對偶問題2450100000CBXBx1x2x3x4x5i0 x3300111003000 x4400210104000 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-c-cB BT TB B-1-1I IB B=(

14、p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最優解 x1 = 50 x2 = 250 x4 = 50影子價格影子價格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-1-1對應的檢驗數對應的檢驗數 T T = = c cB BT TB B-1-1 。 1. 1.線性規劃對偶問題線性規劃對偶問題25 對偶單純形法的基本思想 對偶單純形法的基本思想是:從原規劃的一個基本解基本解出發,此基本解不一定可行,但它對應著一個對偶對偶可行解可行解(檢驗數非正),所以也可以說是從一個對偶可行解出發;然后檢驗原規劃的基本解是

15、否可行,即是否有負的分量,如果有小于零的分量,則進行迭代,求另一個基本解,此基本解對應著另一個對偶可行解(檢驗數非正)。2.2.對偶單純形法對偶單純形法26 如果得到的基本解的分量皆非負則該基本解為最優解。也就是說,對偶單純形法在迭代過程中始終保持對偶解的可行性(即檢驗數非正),使原規劃的基本解由不可行逐步變為可行,當同時得到對偶規劃與原 規劃的可行解時,便 得到原規劃的最優解。2.2.對偶單純形法對偶單純形法27 對偶單純形法在什么情況下使用 : 應用前提:有一個基,其對應的基滿足: 單純形表的檢驗數行全部非正(對偶可行); 變量取值可有負數(非可行解)。 注:通過矩陣行變換運算,使所有相應

16、變量取值均為非負數即得到最優單純形表。2.2.對偶單純形法對偶單純形法28w 1.建立初始對偶單純形表,對應一個基本解,所有檢驗數均非正,轉2; 2.若b0,則得到最優解,停止;否則,若有bk0則選k行的基變量為出基變量,轉3 3.若所有akj0( j = 1,2,n ),則原問題無可行解,停止;否則,若有akj0 則選 =minj / akjakj0=r/akr那么 xr為進基變量,轉4; 4.以akr為轉軸元,作矩陣行變換使其變為1,該列其他元變為0,轉2。 對偶單純形法求解線性規劃問題對偶單純形法求解線性規劃問題過程:過程:2.2.對偶單純形法對偶單純形法29例3.2:求解線性規劃問題:

17、求解線性規劃問題: 標準化:標準化: Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0 2.2.對偶單純形法對偶單純形法30w表格對偶單純形法CI-2-3-400CBXBbX1X2X3X4X50 X4-3-1-2-1100 X5-4-21-301j-2-3-4000 X4-10-5/21/21-1/2-2 X121-1/23/2

18、0-1/2j0-4-10-1-3 X22/501-1/5-2/51/5-2 X111/5107/5-1/5-2/5j00-9/5-8/5-1/52.2.對偶單純形法對偶單純形法31單純形法和對偶單純形法步驟是是是是否否否否所有所有得到最優解計算計算典式對應原規劃的基本解是可行的典式對應原規劃的基本解的檢驗數所有所有計算計算以為中心元素進行迭代以為中心元素進行迭代停沒有最優解沒有最優解單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0brMin-bi/airair03.3.

19、靈敏度分析靈敏度分析46 例3.5: 上例最優單純形表如下 C i23000CBX BBX 1X 2X 3X 4X 52 X 141001/400 X 5400-21/213 X 22011/2-1/80j00-1.5-1/803.3.靈敏度分析靈敏度分析47 0 0.25 0 這里 B B-1 = -2 0.5 1 0.5 -0.125 0 各列分別對應 b1、b2、b3 的單一變化因此,設 b1 增加 4,則 x1 ,x5 ,x2分別變為:4+04=4, 4+(-2)4=-40, 2+0.54=4用對偶單純形法進一步求解,可得:x* = ( 4, 3, 2, 0, 0 )T f* = 173.3.靈敏度分析靈敏度分析48 增加一個變量 增加變量 xn+1 則有相應的pn+1 ,cn+1 。 那么 計算出B B-1pn+1 , n+1=cn+1-cri ari n+1 填入最優單純形表, 若 n+1 0 則 最優解不變; 否則,進一步用單純形法求解。3.3.靈敏度分析靈敏度分析49例3.6:例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 計算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論