第3章對(duì)偶理論與靈敏度分析

1、北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！第三章對(duì)偶理論與靈敏度分析3.1 對(duì)偶理論問(wèn)題的提出（1 學(xué)時(shí)）3.1.1 對(duì)偶線性規(guī)劃問(wèn)題的導(dǎo)出對(duì)一個(gè)問(wèn)題可以從不同的角度去看，解決一個(gè)問(wèn)題也可以有多種。例 3.6 一個(gè)工廠生產(chǎn)三種怎么生產(chǎn)獲得最大利潤(rùn)。表 3-3所用工時(shí)和材料以及利潤(rùn)如下表所示，決策應(yīng)該其線性規(guī)劃模型為maxìïz = 2x1 + 3x2 + 3x3£ 33£ 9³ 0s.t.í3ïî3æ x1 öz = (2, 3, 3) ç x

2、47;max或ç2 ÷ç x ÷è 3 øìæ x1 ö1 öç÷ïæ114æ3öïç1÷ x£ ç ÷7÷29ïèøç xè ø÷ïè 3 øs.t.íïïïïîæ x öæ 0

3、öç1 ÷ç ÷ç x2 ÷ ³ ç 0÷ç x ÷ç 0÷è 3 øè ø從另一個(gè)角度去思考這個(gè)問(wèn)題，就是當(dāng)另外一個(gè)工廠提出購(gòu)買這個(gè)廠的所有工時(shí)和材料時(shí)，工廠應(yīng)該怎么做決策才會(huì)使得這樣一個(gè)出現(xiàn)雙贏的局面。簡(jiǎn)要的雙贏的原理：價(jià)格盡量低，使得其具有競(jìng)爭(zhēng)力，同時(shí)希望客戶能出更高的價(jià)格，這樣企業(yè)就可以獲得的利潤(rùn)。亦即，生產(chǎn)一件 A 的工時(shí)和材料的銷售收入應(yīng)該不少于 A 生產(chǎn)一件 B 的工時(shí)和材料的銷售收入應(yīng)該不少于 B 生

4、產(chǎn)一件 C 的工時(shí)和材料的銷售收入應(yīng)該不少于 C的的的利潤(rùn)； 利潤(rùn)； 利潤(rùn)。定義工時(shí)和材料分別為 y1,y2，于是有æ y1 öminW = 3y1 + 9 y2minW = (3,9)ç÷yè 2 ø消耗總量工時(shí)1113材料1479利潤(rùn)233北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！ìæ11 öæ 2öïç÷æ y1 öç ÷ì y1 + y2³ 24

5、7;ç y ÷ ³ ç 2÷ïç1ï y+ 4 y ³ 3s t ïïç17 ÷è 2 øç3 ÷12. .í ys.t.íèïïøè ø或+ 7 y ³ 3ï12æ y öï y³ 0, y ³ 0ç 1 ÷ ³ 0î 12ïy

6、è 2 øî上述兩個(gè)線性規(guī)劃模型是在同一企業(yè)的資源狀況和生產(chǎn)技術(shù)條件下產(chǎn)生的，是同一個(gè)問(wèn)題從不同角度來(lái)觀察所產(chǎn)生的，因此兩者是密切相關(guān)的，我們稱這兩個(gè)線性規(guī)劃問(wèn)題是互為對(duì)偶的兩個(gè)線性規(guī)劃問(wèn)題，其中一個(gè)問(wèn)題是另一問(wèn)題的對(duì)偶問(wèn)題。3.1.2對(duì)偶問(wèn)題的定義max z = c1x1 + c2 x2+ " +cn xnìæ a11a12""a1n öæ x1 öæ b1 ö÷çx÷ç÷bïç aaa

7、9;ç2n ÷ç2 ÷ £ ç÷21222s t ïç÷ç#÷ç#÷. .íç #（3-5）÷ç÷ç÷ïç a÷ç x ÷ç b ÷a"aïè m1ïîmn øè n øè m øm 2³ 0nmin z =

8、b1y1 + b2 y2+" +bm ymìæ a11am1 öæ y1öæ c1 öa21""ïç a÷ç÷ç÷ycaam 2 ÷ç 2÷ ³ ç 2 ÷ïç1222s t ïç÷ç#÷ç# ÷. .íç #（3-6 ）÷ç÷&

9、#231;÷ïç a÷ç y ÷ç c ÷a"aïè 1nmn øè m øè n ø2nïî y1 , y2 ,", ym ³ 0用矩陣的形式表示對(duì)偶問(wèn)題max Z = CXmin W = bT Y Tì AT Y T ³ CT£ bìAXs.t.íXs.t.í與寫法正確嗎？³ 0îY³ 0Tî原

10、問(wèn)題模型與對(duì)偶問(wèn)題在結(jié)構(gòu)上的對(duì)應(yīng)如表 3-4表 3-4北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！3.2 線性規(guī)劃的對(duì)偶理論（3 學(xué)時(shí)）對(duì)于對(duì)偶問(wèn)題，有下面幾個(gè)重要的定理定理 3.1 弱對(duì)偶定理若互為對(duì)偶的線性規(guī)劃（3-5）與（3-6）分別有可行解2 ,", xn ) 和Y = ( y1 , y2 ,", ym )T則其相應(yīng)的目標(biāo)函數(shù)值滿足：Z = c1 x1 + c2 x2 + "+ cn xn £ b1 y1 + b2 y2 + "+ bm ym = W證明 由 X ,Y 分別為（3-5）和（3-6）的可行

11、解，（3-5）與（3-6）互為對(duì)偶問(wèn)題，因此下面的證明是最嗎？是不是有點(diǎn)繁瑣？！mm當(dāng) x j ³ 0 時(shí)，有å aij yi ³ c j ，則c j x ji=1當(dāng) x j £ 0 時(shí)，有å aij yi £ c j ，則c j x j£ å x j aij yi i=1mm£ å x j aij yii=1i=1mm當(dāng) x j 符號(hào)不限時(shí)，有å aij yi = c j ，則c j x j i=1= å x j aij yi i=1nnmZ = åcj x j&

12、#163; åå x j aij yi(3-7)j =1j =1 i=1nn同理，當(dāng) yi ³ 0 時(shí)，有å aij x j £ bi ，則å x j aij yi £ bi yij =1j =1nn當(dāng) yi £ 0 時(shí)，有å aij x j ³ bi ，則å x j aij yi £ bi yij =1j =1nn當(dāng) yi 符號(hào)不限時(shí)， å aij x j = bi ，則å x j aij yi £ bi yij =1j =1原問(wèn)題（或?qū)ε紗?wèn)題

13、）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù) maxZ目標(biāo)函數(shù) minW約束條件： m 個(gè)第 i 個(gè)約束條件類型為“” 第 i 個(gè)約束條件類型為“” 第 i 個(gè)約束條件類型為“”變量數(shù)：m 個(gè)第 i 個(gè)變量“” 第 i 個(gè)變量“”第 i 個(gè)變量是變量變量數(shù)：n 個(gè)第 j 個(gè)變量0 第 j 個(gè)變量0第 j 個(gè)變量是變量約束條件數(shù)：n 個(gè)第 j 個(gè)約束條件類型為“” 第 j 個(gè)約束條件類型為“” 第 j 個(gè)約束條件類型為“”目標(biāo)函數(shù)系數(shù) 約束條件右端項(xiàng)約束條件右端項(xiàng)目標(biāo)函數(shù)系數(shù)北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！mm nW = åbi yi³ 

14、29;å x j aij yi(3-8)i=1i=1 j =1結(jié)合（3-7）與（3-8）立即可得定理的結(jié)論mnåbi yii=1³ åcj x j j =1推論 1極大化問(wèn)題的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)下界。推論 2極小化問(wèn)題的任意一個(gè)可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題最優(yōu)目標(biāo)函數(shù)值的一個(gè)上界。推論 3若原始問(wèn)題可行，則其目標(biāo)函數(shù)的充要條件是對(duì)偶問(wèn)題沒(méi)有可行解。定理 3.2 最優(yōu)性準(zhǔn)若 X 和Y 分別為互為對(duì)偶問(wèn)題的線性規(guī)劃（3-5）與（3-6）的可行解，且使CX = bT Y T ， 則 X 和Y 分別是相應(yīng)線性

15、規(guī)劃的最優(yōu)解。CX £ bT Y T證明 對(duì)于 X 和Y 將分別有CX £ bT Y TCX £ bT Y TCX = bT Y T ，故有又由于bT Y T£ bT Y TCX £ CX由于 X 與Y 分別是（3-5）與（3-6）的可行解，而 X 與 Y 分別是（3-5）與（3-6）的任意可行解，根據(jù)最優(yōu)解的概念知 X 與Y 是（3-5）與（3-6）的最優(yōu)解。定理 3.3 對(duì)偶定理若原始問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解；且目標(biāo)函數(shù)值相同。證明 設(shè)原問(wèn)題的最優(yōu)解X ，對(duì)應(yīng)的基 B 是最優(yōu)基，則必有對(duì)應(yīng)B 的檢驗(yàn)數(shù)滿足s N = CN - C

16、B B N £ 0 。即得到Y(jié)A ³ C ，其中Y = C B ，若這時(shí)Y = C B 是對(duì)偶問(wèn)-1-1-1BB題的一個(gè)可行解，對(duì)應(yīng)的目標(biāo)函數(shù)值為W = Yb = CB B b-1X因?yàn)樵瓎?wèn)題的最優(yōu)，使得目標(biāo)函數(shù)取值Z* = CX = CB B b-1由此，得到Y(jié) b = CB B b = CX-1可知Y 是對(duì)偶規(guī)劃的最優(yōu)解。定理 3.4 互補(bǔ)松弛定理ÙÙÙÙÙ若X ，Y 分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，那么Y Xi = 0 和 Yi X = 0 ，當(dāng)且僅當(dāng)X ，ÙY 為最優(yōu)解。Xi 這樣的符號(hào)前面用過(guò)嗎？能知道是

17、什么含義嗎？證明 設(shè)原問(wèn)題和對(duì)偶問(wèn)題的原問(wèn)題是對(duì)偶問(wèn)題北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（max z = CX和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢min w = Yb講解！AX + Xi = b X, Xi ³ 0將原問(wèn)題目標(biāo)函數(shù)中的系數(shù)YA - Yi = C Y, Yi ³ 0C 用 C=YA-Y，代替后，得到z = (YA - Yi )X = YAX - Yi X（3-9）將對(duì)偶問(wèn)題的目標(biāo)函數(shù)中系數(shù)，用b = AX + Xi 代替后，得到w = Y(AX + Xi ) = YAX + YXi（3-10）ÙÙÙÙÙ

18、7;ÙÙ若Y Xi = 0 ， Yi X = 0 ；則Yb = YAX = C X 由定理 3.10 可知X ， Y 是最優(yōu)解。ÙÙ又若X ， Y 分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解，根據(jù)定理 3.10，則有ÙÙÙÙCX = Y A X = Y bÙÙ由（3-9）和（3-10）可知，必有Y Xi = 0 ， Yi X = 0 。例 3.7 已知線性規(guī)劃max z =ì3 + 4x4x3 + 3x4 £ 20ï2x+ 2x £ 20ï34í&

19、#239;x - x £ 134ï, x ³ 0î34的最優(yōu)X * =（0，0，4，4） T 。試?yán)没パa(bǔ)松弛原理求對(duì)偶問(wèn)題的最優(yōu)解。解 對(duì)偶問(wèn)題為Min w=20y 1 +20y 2 +y 3ì y1 + 2 y2 + y3 ³ 1ï 2y + y - y ³ 2123ïí2y1 + 3y2 + y3 ³ 3ï3y + 2 y - y ³ 4ï123ïîy1, y2 , y3 ³ 0*由于 x 3 =x 4 =4>0，

20、故對(duì)偶問(wèn)題約束方程式（3）、（4）是等式約束，即對(duì) Y 成立等式ì2y + 3y+ y =3*ï123í3y + 2 y- y= 4*ïî123把 X * 代入原問(wèn)題 3 個(gè)約束中可知原問(wèn)題式（3）是不等式，故 y * =0，然后解方程組3ì 2y + 3y =3*ï12í3y + 2 y= 4ï*î12得到ì*y =6/5ï1íy= 1/ 5*ïî 2故對(duì)偶最優(yōu)Y * =(6/5,1/5,0), z * =w * =28.例 3.8考慮線性規(guī)劃

21、max z3x3北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！x2 +ìïxïíïïî2=1³ 0已知它的最優(yōu)X * =（4，1，9） T ，求對(duì)偶問(wèn)題的最優(yōu)解。解 對(duì)偶問(wèn)題是min w = 11y1 + 3y2 + y3ì y1 - 4 y2 - 2 y3 ³ 3ï- 2y + y ³ -1ï12íy+ 2 y + y ³ -1ï123ïy³ 0, y £ 0, y 無(wú)約束

22、î 123由于 x * >0,x * >0, x * >0，故上面 3 個(gè)技術(shù)約束應(yīng)是等式，即123ì y * - 4 y * - 2 y * = 3123ï- 2y * + y * = -1í12ïy * + 2 y * + y * = -1î123從中解得ì y * = 1/31ïy= -*í1 /32ï y * = -2 / 3î3z * =w * =23.3對(duì)偶問(wèn)題的解釋價(jià)格（1 學(xué)時(shí)）在對(duì)偶問(wèn)題導(dǎo)出的例中，生產(chǎn)計(jì)劃問(wèn)題的對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)

23、解所代表是企業(yè)在當(dāng)前的資源狀況 b，技術(shù)狀況 A 和市場(chǎng)狀況 C 已知的情況下， 源對(duì)企業(yè)的價(jià)值。資3.3.1價(jià)格的原理* ,", x* )T和對(duì)于的線性規(guī)劃問(wèn)題（3-5）和其對(duì)偶問(wèn)題（3-6），若2nY * = ( y* , y* ,", y* ) 分別是式（3-5）和式（3-6）的最優(yōu)解，則據(jù)定理 3.3 知其最優(yōu)值相等，12n即Z* = c x* + c x* + " + c= W * = b y* + b y* + " + bx*y*1 12 2n n1 12 2m m由此可知原線性規(guī)劃問(wèn)題（3-5）的最優(yōu)值與右端常數(shù)之間的為Z* = b y*

24、+ b y* + "+ by *(3-11)1 12 2m m因此， y * 代表著當(dāng)?shù)?i 個(gè)右端常數(shù)b 增加一個(gè)時(shí)，最優(yōu)目標(biāo)函數(shù)值的相應(yīng)增量。ii若把 Z * 看作b ,", b 的函數(shù)，則由 ¶Z * = y* ，可知 y * 是資源b 的價(jià)值的一種度量，1m¶biiii北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！稱為bi 的價(jià)格，其含義是在目前已給定的情況下，最優(yōu)目標(biāo)值隨資源數(shù)量變化的變化率，其含義是為約束條件所付出的代價(jià)。-1值得注意的是，當(dāng) B 是原問(wèn)題的最優(yōu)基時(shí)，Y* = CB B就是價(jià)格，可見(jiàn)價(jià)格只是對(duì)資

25、源價(jià)值的邊際度量，當(dāng) A，b 或C 改變時(shí)， 例 3.9用線性規(guī)劃的對(duì)偶問(wèn)題進(jìn)行求解max z = 2x1 + 3x2 + 3x3價(jià)格也會(huì)發(fā)生相應(yīng)的改變。£ 3£ 9³ 0ì3s t ï. .í3ïî3解 線性規(guī)劃的對(duì)偶問(wèn)題為min w = 3y1 + 9y2ì y1 + y2³ 2ï y+ 4 y ³ 3s t ï12. .í y+ 7 y ³ 3ï12ïî y1 ³ 0, y2 ³ 0求解可得

26、5151y1 = 3 , y2 = 3 ，即工時(shí)的價(jià)格為 ，材料的3價(jià)格為 。31如果目前市場(chǎng)上材料的價(jià)格低于 ，則企業(yè)可以購(gòu)進(jìn)一部分材料來(lái)擴(kuò)大生產(chǎn)，反之若31市場(chǎng)價(jià)高于 ，則企業(yè)可以賣掉部分材料。35如果有客戶以高于 的價(jià)格購(gòu)買該企業(yè)的工時(shí)，則可以出售一些工時(shí)，反之若客戶出35價(jià)低于 則不應(yīng)出售工時(shí)，若企業(yè)能夠通過(guò)加班或租用別人的3來(lái)擴(kuò)大工時(shí)，則當(dāng)所獲5得的額外工時(shí)的成本低 時(shí)，企業(yè)可以增3時(shí)，否則不應(yīng)增時(shí)。在這兩個(gè)互為對(duì)偶的線性規(guī)劃問(wèn)題中，生產(chǎn)計(jì)劃問(wèn)題的對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解所代表的是企業(yè)在當(dāng)前的資源狀況 b，技術(shù)狀況 A 和市場(chǎng)狀況 C 已知的情況下資源對(duì)企業(yè)的價(jià)值。因

27、此， y * 代表著當(dāng)?shù)?i 個(gè)右端常數(shù)b 增加一個(gè)時(shí)，最優(yōu)目標(biāo)函數(shù)值的相應(yīng)增量。ii在這兩個(gè)互為對(duì)偶的線性規(guī)劃問(wèn)題中，生產(chǎn)計(jì)劃問(wèn)題的對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解所代表是企業(yè)在當(dāng)前資源對(duì)企業(yè)的價(jià)值。的資源狀況 b，技術(shù)狀況 A 和市場(chǎng)狀況 C 已知的情況下3.3.2 對(duì)偶理論的應(yīng)用若 B 是線性規(guī)劃的最優(yōu)基，則p = C B -1 是對(duì)偶問(wèn)題的最優(yōu)解。由檢驗(yàn)數(shù)的計(jì)算B子矩陣，不妨設(shè) A 的前 m 列為可知：s = C - pA 。若 A 中有矩陣，則在最優(yōu)表中有s i = ci - p ip i = ci - s ii = 1,2,", mi = 1,2,",

28、m可知北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！其中， ci 為目標(biāo)函數(shù)中 xi 的系數(shù)， s i 為最優(yōu)表中 xi 的檢驗(yàn)數(shù)。3.4對(duì)偶單純形法（1 學(xué)時(shí)）對(duì)偶單純型法就是利用對(duì)偶理論來(lái)求解線性規(guī)劃問(wèn)題的，而不是求解線性規(guī)劃對(duì)偶問(wèn)題的。設(shè)線性規(guī)劃問(wèn)題為max z = CX= bìAXs.t.íx ³ 0î線性規(guī)劃解的概念可知，當(dāng) B 對(duì)應(yīng)的基本若 B 是 A 中的一個(gè)基，回顧第二是可行解時(shí)，我們稱 B 為可行基，當(dāng) B 對(duì)應(yīng)的基本可行解是最優(yōu)解時(shí)，我們稱 B 為最優(yōu)基，在此我們定義如下概念：若C B -1 是對(duì)偶問(wèn)題

29、的可行解，則稱 B 為對(duì)偶可行基，且使單純形乘子p = CB -1 成BB為對(duì)偶問(wèn)題的可行解，即滿足pA ³ C 。結(jié)合最優(yōu)性判別定理，最優(yōu)基既應(yīng)該是可行基，也應(yīng)該使檢驗(yàn)數(shù)s N £ 0 ，而這就意味著 B 也是對(duì)偶可行基。反之當(dāng) B 是可行基，且也是對(duì)偶可行基時(shí)，對(duì)應(yīng)于 B 的基本可行解的檢驗(yàn)數(shù)s N £ 0（ CB B A ³ C ），因此 B 也是最優(yōu)基。-1于是有如下定理。定理 3.5B 是線性規(guī)劃的最優(yōu)基的充要條件是，B 是可行基，而且也是對(duì)偶可行基。我們已經(jīng)了解了對(duì)偶問(wèn)題的基本概念和基本定理，這一節(jié)中著重來(lái)討論對(duì)偶單純型法。線性規(guī)劃以為例，對(duì)

30、于線性規(guī)劃max z = CX= bìAXs.t.íx ³ 0î若 B 是 A 中的一個(gè)基，回顧線性規(guī)劃解的概念可知，當(dāng) B 對(duì)應(yīng)的基本是可行解時(shí)，我們稱 B 為可行基，當(dāng) B 對(duì)應(yīng)的基本可行解是最優(yōu)解時(shí)，我們稱 B 為最優(yōu)基， 用對(duì)偶單純形法求解原問(wèn)題，它有應(yīng)用的前提條件，有一個(gè)基，其對(duì)應(yīng)的基本解滿足以下兩條：（1） 單純形表的檢驗(yàn)數(shù)行全部非正（保證它是對(duì)偶可行基）；（2） 變量取值有負(fù)數(shù)（對(duì)于原問(wèn)題來(lái)說(shuō)是不可行）。表 3-4c j ®-3-9000qCBXBb0x3-20x4-30x5-3x1x2x3x4x5-1-1100-1-4010-1

31、-7001-Zcj - zj-3-9000北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！對(duì)偶單純形法的步驟步驟 1 求一個(gè)滿足最優(yōu)檢驗(yàn)條件的初始基本解，列出初始單純形表；步驟 2 可行性檢驗(yàn)，若所有的右端系數(shù)均大于等于 0，即b j ³ 0, i = 1,2,", m ,則已得到最優(yōu)解，停止運(yùn)算，否則，轉(zhuǎn)到步驟 3；步驟 3 求另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。bi < 0 ，設(shè)第 l 行的最小，確定換出變量 找非可行解中最小者，即minbi則 l 行成為主行，該行對(duì)應(yīng)的基變量為換出變量；（1）（2）確定換入變量 最小比例原

32、則（設(shè)目標(biāo)函數(shù)為 max 型，檢驗(yàn)數(shù)為 cj zj），若é cjù- z jc- z¢ê a< 0 ú =kk=minê則第 k 列為主列，第 k 列的變量úûk¢lj¢a lja lkjëxk 為換入變量。若找不到主列或換入變量，則原線性規(guī)劃的運(yùn)算，否則轉(zhuǎn)到步驟（3）；以主元 alk為中心迭代得到另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。即將主元 alk變換為 1，主元 alk所在列的其他技術(shù)系數(shù)變換為 0，并用換入變量及其價(jià)值系數(shù)置換出變量及其價(jià)值系數(shù)，得到新的單純形表與

33、另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。再轉(zhuǎn)到步驟 2。解，停止（3）例 3.10 用對(duì)偶單純形法求解如下線性規(guī)劃問(wèn)題+ 3 x 4min f (ì2+ x 4³ 6³ 4³ 03s.t.ï - 2+ xí34ï, xî34解 將上述線性規(guī)劃變換為如下適合對(duì)偶單純形法的形式- 3 x 4min g (ì -2- x 4+ x 5= -6= -4³ 03s.t. ï 2Max- x+ xí346ï,î其中，g(x) = -f (x)，變量 x5 和 x

34、6 為剩余變量。36表 3-5用對(duì)偶單純形法求解例 3.10 的單純形表過(guò)程cj ®-1-50-300序號(hào)CBXBbx1x2x3x4x5x6-1-21-11021-4-10100x5 x6-6-4-Z= 0cj - zj-1-50-300比值-3/-1=3-9/-1=9北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！= X 2 = (= (14 , 0 , 8 , 0 , 0 , 0 ) TX *,) T36最優(yōu)解時(shí)的目標(biāo)函數(shù)值為 f (X *) = - g (X*) = 14。例 3.11 用對(duì)偶單純形法求解下列線性規(guī)劃問(wèn)題。Min w = 15 y1

35、 + 24 y2 + 5 y3ì6 y2 + y3 ³ 2ïí5 y1 + 2 y2 + y3 ³ 1ï y , y , y ³ 0î 123解 先標(biāo)準(zhǔn)化得Max w = -15 y - 24 y - 5 y + 0 y + 0 y'12345ì6 y2 + y3 - y4 = 2ïí5 y1 + 2 y2 + y3 - y5 = 1ï y³ 0î約束條件兩邊乘-1，得iMax w = -15 y - 24 y - 5 y + 0 y + 0 y&

36、#39;12345ì-6 y2 - y3 + y4 = -2ï-5 y - 2 y - y + y = -1í1235³ 0ï yî i列出單純形表，按照上述步驟計(jì)算，計(jì)算過(guò)程見(jiàn)表 3-6。表 3-6cj ®-15-24-500序號(hào)CBYBby1y2y3y4y50-b-110-5-2-10100y4y5-2-1-15-24-500-24y21/3011/6-1/60-10x1 x66-1612-11-100-3-2-321-Z=- 6cj - zj0-3-1-2-10-10x1 x3148017/215/2-2-1/203/

37、23/2-1-1/2-Z=-14cj - zj0-3/20-1/-2-2-1/2北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！3.4對(duì)偶單純形法（1 學(xué)時(shí)）對(duì)偶單純型法就是利用對(duì)偶理論來(lái)求解線性規(guī)劃問(wèn)題的，而不是求解線性規(guī)劃對(duì)偶問(wèn)題的。設(shè)線性規(guī)劃問(wèn)題為max z = CX= bì AXs.t.íx ³ 0î線性規(guī)劃解的概念可知，當(dāng) B 對(duì)應(yīng)的基本若 B 是 A 中的一個(gè)基，回顧第二是可行解時(shí)，我們稱 B 為可行基，當(dāng) B 對(duì)應(yīng)的基本可行解是最優(yōu)解時(shí)，我們稱 B 為最優(yōu)基，在此我們定義如下概念：若C B -1 是對(duì)偶問(wèn)題的可

38、行解，則稱 B 為對(duì)偶可行基，且使單純形乘子p = CB -1 成BB為對(duì)偶問(wèn)題的可行解，即滿足pA ³ C 。結(jié)合最優(yōu)性判別定理，最優(yōu)基既應(yīng)該是可行基，也應(yīng)該使檢驗(yàn)數(shù)s N £ 0 ，而這就意味著 B 也是對(duì)偶可行基。反之當(dāng) B 是可行基，且也是對(duì)偶可行基時(shí)，對(duì)應(yīng)于 B 的基本可行解的檢驗(yàn)數(shù)s N £ 0（ CB B A ³ C ），因此 B 也是最優(yōu)基。-1于是有如下定理。定理 3.5B 是線性規(guī)劃的最優(yōu)基的充要條件是，B 是可行基，而且也是對(duì)偶可行基。我們已經(jīng)了解了對(duì)偶問(wèn)題的基本概念和基本定理，這一節(jié)中著重來(lái)討論對(duì)偶單純型法。線性規(guī)劃以為例，對(duì)于線

39、性規(guī)劃max z = CX= bì AXs.t.íx ³ 0î若 B 是 A 中的一個(gè)基，回顧線性規(guī)劃解的概念可知，當(dāng) B 對(duì)應(yīng)的基本是可行解時(shí)，我們稱 B 為可行基，當(dāng) B 對(duì)應(yīng)的基本可行解是最優(yōu)解時(shí)，我們稱 B 為最優(yōu)基， 用對(duì)偶單純形法求解原問(wèn)題，它有應(yīng)用的前提條件，有一個(gè)基，其對(duì)應(yīng)的基本解滿足以下兩條：（1） 單純形表的檢驗(yàn)數(shù)行全部非正（保證它是對(duì)偶可行基）；（2） 變量取值有負(fù)數(shù)（對(duì)于原問(wèn)題來(lái)說(shuō)是不可行）。表 3-4c j ®-3-9000q0y5-1/3-50-2/3-1/31-150-1-40-24-5y2y31/41/2-5/4

40、101/41/415/2011/2-3/2-17/2-15/200-7/2-3/2北交大管理運(yùn)籌學(xué)考研詳見(jiàn)，網(wǎng)學(xué)天地（和資料，、考點(diǎn)、命題規(guī)律獨(dú)家）；咨詢講解！對(duì)偶單純形法的步驟步驟 1 求一個(gè)滿足最優(yōu)檢驗(yàn)條件的初始基本解，列出初始單純形表；步驟 2 可行性檢驗(yàn)，若所有的右端系數(shù)均大于等于 0，即b j ³ 0, i = 1,2,", m ,則已得到最優(yōu)解，停止運(yùn)算，否則，轉(zhuǎn)到步驟 3；步驟 3 求另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。bi < 0 ，設(shè)第 l 行的最小，確定換出變量 找非可行解中最小者，即minbi則 l 行成為主行，該行對(duì)應(yīng)的基變量為換出變

41、量；（4）（5）確定換入變量 最小比例原則（設(shè)目標(biāo)函數(shù)為 max 型，檢驗(yàn)數(shù)為 cj zj），若é cjù- z j- zc¢ê a< 0 ú =kk=minê則第 k 列為主列，第 k 列的變量¢úû¢klja lja lkjëxk 為換入變量。若找不到主列或換入變量，則原線性規(guī)劃的運(yùn)算，否則轉(zhuǎn)到步驟（3）；解，停止（6）以主元 alk為中心迭代得到另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。即將主元 alk變換為 1，主元 alk所在列的其他技術(shù)系數(shù)變換為 0，并用換入變量及其價(jià)值系數(shù)置換出變量及其價(jià)值系數(shù)，得到新的單純形表與另一個(gè)滿足最優(yōu)檢驗(yàn)條件且更接近可行解的基本解。再轉(zhuǎn)到步驟 2。例 3.10 用對(duì)偶單純形法求解如下線性規(guī)