對偶理論和靈敏度分析

1、運(yùn)運(yùn) 籌 籌 帷 帷 幄 幄 之 之 中 中 決決 勝 勝 千 千 里 里 之 之 外 外 對偶理論和靈敏對偶理論和靈敏 度分析度分析 對偶問題的提出 對偶是什么：對同一事物（或問題 ），從不同的角度（或立場）提出 對立的兩種不同的表述。 例如 在平面內(nèi)，矩形的面積與其周長之間的 關(guān)系，有兩種不同的表述方法。 （1）周長一定，面積最大的矩形是正 方形。 （2）面積一定，周長最短的矩形是正 方形。 這是互為對偶關(guān)系的表述。 這種表述有利于加深對事物的認(rèn)識 和理解。 線性規(guī)劃問題也有對偶關(guān)系。 例 工廠生產(chǎn)i，ii兩種餅干，這兩產(chǎn)品分別要在A，B，C三 種不同的設(shè)備上加工，每生產(chǎn)i產(chǎn)品要用各設(shè)備分

2、別為 3h，2h，2h；生產(chǎn)ii產(chǎn)品為5h，1h，2h； 設(shè)備的生產(chǎn)能力分別為： 15h，5h，11h 每生產(chǎn)一件i產(chǎn)品可以獲得利潤為5元， 每生產(chǎn)一件ii產(chǎn)品可以獲得利潤為4元，問企業(yè)應(yīng)安排生 產(chǎn)兩種產(chǎn)品各多少件，使總的利潤最大。 第1章例1的不同表述 現(xiàn)從另一角度來討論這個問題。 假設(shè)該工廠的決策者決定不生產(chǎn)產(chǎn)品、，而 將其所有資源出租或外售。這時工廠的決策者就 要考慮給每種資源如何定價的問題。設(shè)用y1，y2 ，y3分別表示出租單位設(shè)備臺時的租金。他在做 定價決策時，做如下比較：若用3個單位A設(shè)備 臺時和2個單位B設(shè)備臺以及2個單位C設(shè)備臺時 時可以生產(chǎn)一件產(chǎn)品，可獲利5元，那么生產(chǎn) 每件

3、產(chǎn)品的設(shè)備臺時出租或出讓的所有收入應(yīng) 不低于生產(chǎn)一件產(chǎn)品的利潤，這就有 3y1+2y2+2y35 1.1對偶問題的形式 12 12 12 12 12 max z = 5x + 4x s.t 3x + 5x15 2x + x5 (1) 2x +2x11 x ,x0 123 123 123 123 min 15511 . . 3225 (2) 524 ,0 wyyy styyy yyy y yy (1),( ) ( )( ) ( ) (2) ( )( )( )( ) 一是求最大值 函數(shù)約束都是不等式.而 2 是 求最小值,函數(shù)約束都是不等式 二 2 中函數(shù)約束的系數(shù)矩陣是 1 中函數(shù)約束的系數(shù) 矩

4、陣的轉(zhuǎn)置 三 (2)中目標(biāo)函數(shù)的系數(shù)是 1 中函數(shù)約束右端的元素, 反之,(1)中目標(biāo)函數(shù)的系數(shù)是中函數(shù)約束右端的 元素 把與 1 具有上述關(guān)系的 2 稱為1 的對偶問題,而將 1 稱為原問題,對偶問題中 maxz=, . .,0 (3) min, . .,0 (4) TTT cx st Axb x wb y st A ycy 的決策變量稱為對偶變量 min bTY s.t.ATYc Y 0 max cX s.t. Xb X 0 min cT AT bT bA cT max n m n m 12 12 12 12 12 max = 5 + 4 s.t 3+ 515 2 + 5 2 + 211

5、,0 zxx xx xx xx x x 123 123 123 123 min = 15 + 511 s.t 3+ 225 5 + 4 ,0 wyyy yyy yyy x xy 例2-1-1寫出下述問題的對偶問題 123 123 123 123 123 min 567 . . 2351 6232 3483 ,0 (1) zxxx stxxx xxx xxx x x x 123 123 123 123 123 max . . 233 231 33 ,0 (2) zxxx stxxx xxx xxx x xx 綜合上述，線性規(guī)劃的原問題與對偶問題 的關(guān)系， 其變換形式歸納為下表中所示的對應(yīng)關(guān)系 。

6、 RHS RHS 0 0 0 0 m n 0 0 n minzmax 約束條件的目標(biāo)函數(shù)變量系數(shù) 目標(biāo)函數(shù)變量的系數(shù)約束條件 量 變 無約束 個個 件 條 束 約 件 條 束 約個 無約束 個 量 變 目標(biāo)函數(shù)目標(biāo)函數(shù) 對偶問題原問題 m 例3 試求下述線性規(guī)劃原問題的對偶問題 無約束 4321 3432 2431 14321 4321 00 36 2422 153 532 x,x ,x,x yxxx yxxx yxxxx xxxxzmin 則由表中原問題和對偶問題的對應(yīng)關(guān)系，可以 直接寫出上述問題的對偶問題， 無約束 321 321 321 31 21 321 00 1 523 3 22 6

7、45 y,y,y yyy yyy yy yy yyyzmax 1.2對偶問題的解 12123 u u uxx 23 1 77 15 1 77 24 1 77 2 1 3 x x u 15 7 10 7 27 7 右端 z 110 - 7 3 7 13 7 12312 yyyvv w 1 2 y y 0 1 4 7 2 7 5 7 1 7 3 7 2 7 13 7 0 1 3 7 27 7 10 7 15 7 110 7 例2.3-1用對偶單純形法解下述問題 123 123 123 123 min 15511 . . 3225 (1) 524 ,0 wyyy styyy yyy y yy 123

8、 1231 1232 12312 min 15511 . . -322 5 (2) -52 4 ,0 wyyy styyyS yyyS y yy S S 12312 y y S Sy 1 2 S S 右 端 比 w 例2.3-1對偶單純形表(1-2) 3 5 2 1 2 2 1 1 5 4 155 11 w 2 2 y S 3 2 7 2 11 1 1 2 1 2 1 5 2 3 2 15 2 6 5 2 25 2 12312 y y S Sy 2 1 y y 右 端 比 w 例2.3-1對偶單純形表(3) 1 1 4 7 2 7 5 7 1 7 3 7 2 7 13 7 3 7 27 7 1

9、0 7 15 7 110 7 * 12312 313 :,0 77 yyySS最優(yōu)解為 對偶單純形法的一般步驟 1) LP 2) 0,. ) 0, ). ). 5) , i b 1 1 把所給的問題化為標(biāo)準(zhǔn)形. 找出一個滿足一切檢驗(yàn)數(shù)的初始基做其單純形表 3 若表中一切則 已是最優(yōu)基 求出最優(yōu)解和最優(yōu)值, 計算終止.否則,轉(zhuǎn)4 4 換基,換基后得新基 對 的單純形表進(jìn)行單純形變換 便得到 的單純形表. 以前討論線性規(guī)劃問題時，假定ij，bi,cj都是常數(shù)。 但實(shí)際上這些系數(shù)往往是估計值和預(yù)測值。 如市場條件一變，cj值就會變化；ij往往是因工藝條 件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果

10、決 定的一種決策選擇。 因此提出這樣兩個問題： (1)當(dāng)這些系數(shù)有一個或幾個發(fā)生變化時，已求得的線性 規(guī)劃問題的最優(yōu)解會有什么變化； (2)或者這些系數(shù)在什么范圍內(nèi)變化時，線性規(guī)劃問題的 最優(yōu)解或最優(yōu)基不變。 線性規(guī)劃問題中某一個或幾個系數(shù)發(fā)生變化 顯然，當(dāng)線性規(guī)劃問題中某一個或幾個系數(shù)發(fā)生 變化后，原來已得結(jié)果一般會發(fā)生變化。當(dāng)然可 以用單純形法從頭計算，以便得到新的最優(yōu)解。 這樣做很麻煩，而且也沒有必要。因在單純形法 迭代時，每次運(yùn)算都和基變量的系數(shù)矩陣B有關(guān) ，因此可以把發(fā)生變化的個別系數(shù)，經(jīng)過一定計 算后直接填入最終計算表中，并進(jìn)行檢查和分析 ，可按表2-9中的幾種情況 進(jìn)行處理。 表

11、 2-9 原問題原問題 對偶問題對偶問題 結(jié)論或繼續(xù)計算的步驟結(jié)論或繼續(xù)計算的步驟 可行解 可行解 表中的解仍為最優(yōu)解 可行解 非可行解 用單純形法繼續(xù)迭代求最優(yōu)解 非可行解 可行解用 對偶單純形法繼續(xù)迭代求最優(yōu)解 非可行解 非可行解 引進(jìn)人工變量，編制新的單純形表，求最優(yōu)解 下面就各種情況分別按節(jié)進(jìn)行討論。 1.目標(biāo)函數(shù)的系數(shù)發(fā)生變化 12 123 124 125 12345 max z = 5x +4x s.t 3x + 5xx 15 2x + x + x 5 2x +2x x11 x ,x ,x ,x ,x0 2 討論下述問題當(dāng)x 在目標(biāo)函數(shù)中的系數(shù) 發(fā)生微小擾動q時對最優(yōu)解的影響 12

12、345 xxxxx 5 4+qp 351 211 221 3 4 5 x x x 15 5 11 右端 z 12123 u u uxx 23 1 77 15 1 77 24 1 77 2 1 3 x x u 15 7 10 7 27 7 右端 z 110 - 7 3 7 13 7 12312 yyyvv w 1 2 y y 0 1 4 7 2 7 5 7 1 7 3 7 2 7 13 7 0 1 3 7 27 7 10 7 15 7 110 7 12345 xxxxx 23 1 77 15 1 77 24 1 77 2 1 5 x x x 15 7 10 7 27 7 右端 z 110 - 7

13、 3 7 13 7 q p 12345 xxxxx 23 1 77 15 1 77 24 1 77 2 1 5 x x x 15 7 10 7 27 7 右端 z 1510 77 qp * 110 z =- 7 3 321 777 qp 4 1335 777 qp 12345 xxxxx 5 4 351 211 221 3 4 5 x x x 15 5 11 右端 z 2.約束條件右端的常數(shù)發(fā)生變化 1 t 1 一個發(fā)生變化的情形 12345 xxxxx 23 1 77 15 1 77 24 1 77 2 1 5 x x x 15 7 10 7 27 7 右端 z 110 - 7 3 7 13

14、 7 1 t 2 7 1 7 2 7 3 7 211151 152101272 , 777777 xt xt xt 11 110315 , 10 772 ztt 12345 xxxxx 5 4 351 211 221 3 4 5 x x x 15 5 11 右端 z 123 t t t 1 多個發(fā)生變化的情形 1 1 12345 xxxxx 23 1 77 15 1 77 24 1 77 2 1 5 x x x 1 5 7 1 0 7 2 7 7 右端 z 123 ttt 1 2 7 1 7 2 7 3 7 5 7 4 7 2121125123 152310152724 , 777777777

15、 xttxttxttt 110 7 1 3 7 t 2 13 7 t 3 7 1 3 7 12345 xxxxx 323 1 777 515 1 777 424 1 777 q q q 2 1 5 x x x 15 7 10 7 27 7 右端 z 110 - 7 3 7 13 7 3.約束條件左端的常數(shù)發(fā)生變化 13 7 q 4.新變量的引入 126 1236 1246 1256 123456 max z = 5x +4x7 s.t 3x + 5xx 215 2x + x + x 35 2x +2x x511 x ,x ,x ,x ,x ,0 x x x x x 12345 xxxxx 23 1 77 15 1 77 24 1 77 2 1 5 x x x 1 5 7 1 0 7 2 7 7 右端 z 1 2 7 1 7 2 7 3 7 5 7 4 7 3 7 1 3 7 6