運(yùn)籌學(xué)大作業(yè)單純性法與對偶單純性法比較

1、對偶單 純形法 與單純 形法對 比分析1 .教學(xué)目標(biāo)：通過對偶單純形法的學(xué)習(xí)，加深對對偶問題的理解2 .教學(xué)內(nèi)容：1）對偶單純形法的思想來源2）對偶單純形法原理3 .教學(xué)進(jìn)程：1）講述對偶單純形法解法的來源：所謂對偶單純形法，就是將單純形法應(yīng)用于對偶問題的計(jì)算，該方法是由美國數(shù)學(xué)家C.萊姆基于1954年提出的，它并不是求解對偶問題解的方法，而是利用對偶理論求解原問題 的解的方法。2）為什么要引入對偶單純形法：單純形法是解線性規(guī)劃的主要方法，對偶單純形法則提高了求解線性規(guī)劃問題的效率，因?yàn)樗哂幸韵聝?yōu)點(diǎn)：（1）初始基解可以是非可行解，當(dāng)檢驗(yàn)數(shù)都為負(fù)值時，就可以進(jìn)行基的變換，不需加入 人工變量，從

2、而簡化計(jì)算；（2）對于變量多于約束條件的線性規(guī)劃問題，用對偶單純形法可以減少計(jì)算量，在靈敏度 分析及求解整數(shù)規(guī)劃的割平面法中，有時適宜用對偶規(guī)劃單純形法。由對偶問題的基本性質(zhì)可以知道，線性規(guī)劃的原問題及其對偶問題之間存在一組互補(bǔ)的 基解，其中原問題的松弛變量對應(yīng)對偶問題的變量， 對偶問題的剩余變量對應(yīng)原問題的變量； 這些互相對應(yīng)的變量如果在一個問題的解中是基變量，則在另一問題的解中是非基變量； 將這對互補(bǔ)的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有z=w。據(jù)此可知，用單純形法求解線性規(guī)劃問題時，在得到原問題的一個基可行解的同時， 在檢驗(yàn)數(shù)行得到對偶問題的一個基 解，并且將兩個解分別代入各自的目標(biāo)

3、函數(shù)時其值相等。我們知道，單純形法計(jì)算的基本思路是保持原問題為可行解（這時一般其對偶問題為非 可行解）的基礎(chǔ)上，通過迭代，增大目標(biāo)函數(shù)，當(dāng)其對偶問題的解也為可行解時，就達(dá)到了 目標(biāo)函數(shù)的最優(yōu)值。那么對偶單純形法的基本思想可以理解為保持對偶問題為可行解（這時一般原問題為非可行解）的基礎(chǔ)上，通過迭代，減小目標(biāo)函數(shù)，當(dāng)原問題也達(dá)到可行解時， 即達(dá)到了目標(biāo)函數(shù)的最優(yōu)值。其實(shí)對偶單純形法本質(zhì)上就是單純形法，只不過在運(yùn)用時需要 將單純形表旋轉(zhuǎn)一下而已。一.單純形法和對偶單純性法單純形法是求解線性規(guī)劃的主要方法，單純形表則是單純形法和對偶單純形法的運(yùn)算 工具。設(shè)線性規(guī)劃問題為nMax ZCj Xjj 1n,

4、ajXj b(i 1，,m)s.t. j 1Xj0( j 1,.,n)將其化為標(biāo)準(zhǔn)形式，得Max Z= CXs.t.AX Xs bX,Xs 0其中 C (Cb，Cn)，Cn0 (0,0，,0), A (B,N), xXB,則其對應(yīng)的線性約束轉(zhuǎn)換Xn為 Xb B1XN B1Xs 0 ,Xb B1b B 1XN B1Xs，代入目標(biāo)函數(shù)得1八B b，Xn 0，111 A Z CbB b (Cn CbB)Xn CbB Xs，相應(yīng)的一個基解為 Xb一1一11一 Xs 0。顯然，右 B b。，且（Cn CbB N） 0， CbB Xs 0，則基斛 X為該線性規(guī)劃的最優(yōu)解，此時檢驗(yàn)數(shù)均大于零，見表1。通過上

5、面的分析，我們知道單純形表的檢驗(yàn)數(shù)實(shí)際上是目標(biāo)函數(shù)中基變量、 非基變量的 價值系數(shù)，又由對偶理論知道它們是相應(yīng)對偶問題的一個 （加一個負(fù)號）基解。那么表中b 列的數(shù)字僅僅表示的是 XB的取值嗎？我們可以猜想B 1b很可能是對偶問題的檢驗(yàn)數(shù)。這 里首先給出問題（1）的對偶問題的一般形式Min wm1biymaij yi 。( j 1,n)s.t. i 1 Jyi 0（i 1,.,m）將問題（3）化為標(biāo)準(zhǔn)形式，得Min w YBs.t.YA Ys Cy，Ys 0由 C （Cb，Cn），A (B, N) , Ys為松弛變量,Ys相應(yīng)分解為Ysb、YsN，其中 s s Ds s INYsB (ym1,

6、ym1,.，y2m)0，YsNZm 12m 2，¥2/ 0。得:YB YsB CbYN YsN Cn由式得到11/ Y CbB YsbB通過令YsB 0，由式得對偶問題的基解y cbB 1,代入式(6)得YsN CBB 1 n CN, 將式 對偶問題的目標(biāo)函數(shù)得 w CB B 1b YsB B 1b。顯然若目標(biāo)函數(shù)達(dá)到最小,非基變 量YsB的價值系數(shù)要求大于等于零，單純形表b列B 1b 0,即B1b 0實(shí)際上是對偶問題的 非基變量檢驗(yàn)數(shù)。二.對偶單純形法的算法步驟(1)確定換出基的變量設(shè)原問題為(1),對偶問題為(3)。由A (B,N),C (CB，CN),不等式Y(jié)A C則可分解為Y

7、B Cb,YN Cn（8）進(jìn)一步添加松弛變量有等式（5）、（6）,對等式（5）兩端同時左乘B 1有_ _11-Y YsbB CbB將YsBB 1移至等式右端得-11Y YsbB CbB（10）由不等式（8）得Cb yb 0（11）Cn YN 0（12）將式（10）代入不等式（11）、（12）得 1 _1 _Cb YB Cb CbB b YsbB b 0（13）11-Cn YN Cn CbB N Y，bB N 0（14）將（13）、（14）合并得 ,、一、，、，11_（Cb，Cn）Y（B，N） （Cb，Cn）（CbB YsbB ）（B，N） 0（15）整理得 _11_C CbB A YsbB a

8、 0（16）11其中C cbB a是單純形表中x變量的檢驗(yàn)數(shù)，記c CBB a （ j），1'd(j=1,2,.,n), B A(aJmxn矩陣，顯然，若Y為基可行解，而若 B b 0,則對偶問題一 一r一一“111 一 一 ，一 一111的目標(biāo)函數(shù) w CbB b YsBB b未取得最小值，取 min (B b)i |(B b)i 0 (B b)l ,確定單純形表的換出基變量 m,即(在單純形表中的)對偶問題相應(yīng)的換入基變量v ，xly m l令Ysb其余分量為零，即Ysb (V , V ,., V ) (0,0,y ,.,0)，V 可能取大，使對I sBI sB ym 1 y m

9、2 y2mymlyml偶問題的目標(biāo)函數(shù)值下降，由 Y為基可行解，則要求滿足式（16）,即對于任意的j ,均有j ymiaj°,得ymi'min 一| j0, aij 0 T上，從而確止單純形表中換入基變ajak量Yi同時確定對偶問題（在單純形表中）換出基變量 y o這與單純形法確定換出基變 Xm kk里的規(guī)則是完全一樣的。3）例題講解下面舉例說明對偶單純形法的算法步驟：【例題】用對偶單純形法求解線性規(guī)劃問題：min w 15 y24 y2 5 y3解：i）將問題改寫為:2）算法步驟第一步：建立一個初始單純形表，使表中檢驗(yàn)行的j值全部大于或等于零,即對其對偶問題而言是一基本可行

10、解。約束條件兩端乘-1 ,得：根據(jù)原問題和對偶問題之間的對稱關(guān)系，這時單純形表中原基變量列數(shù)字相當(dāng)于對偶問題解的非基變量的檢驗(yàn)數(shù)。第二步：由于對偶問題的求解是使目標(biāo)函數(shù)達(dá)到最小值，所以最優(yōu)判別準(zhǔn)則是當(dāng)所有檢驗(yàn)數(shù)大于或等于零時為最優(yōu)（也即這時原問題是可行解）。如果不滿足這個條件，找出絕對值最大的負(fù)檢驗(yàn)數(shù)，設(shè)為 -bi,其對應(yīng)的原問題的基變量x即為對偶問題的換入變量 xl第三步：將j行數(shù)字與表中第l行對應(yīng)的數(shù)字對比，令min |O|aij 0 Cj,alk即為主元素，xk為對偶問題的換出變 aijak量。第四步：用換入變量替換對偶問題中的換出變量（在單純形表中反映為用替原問題的基變量），得到一個新

11、的單純形表。表中數(shù)字計(jì)算同用單純形法時完全一樣。新表中對偶問題仍保持基本可行解，原問題基變量列數(shù)字列數(shù)字相當(dāng)于對偶問題的檢驗(yàn)數(shù)。據(jù)此可以完成對這個對偶問題的求解。4.總結(jié)。1）對比單純形法&M偶單純形法單純性法基本思想2）對偶單純形法優(yōu)點(diǎn)這里我們需要對單純形法和對偶單純形法做一個詳細(xì)的對比：1 ,單純形法中的b對應(yīng)于對偶單純形法中的；2 ,單純形法中的 作為檢驗(yàn)數(shù)，對偶單純形法中的b#為檢驗(yàn)數(shù)；3 ,單純形法中的b 0,對偶單純形法中的0;4,單純形法中當(dāng)0時得到最優(yōu)解，對偶單純形法中當(dāng)b 0時得到最優(yōu)解；5,單純形法的可行解為X b 1b,對偶單純形法的可行解為 Y CBB 1;（由

12、于松弛變量 xs對應(yīng)的檢驗(yàn)數(shù)為 cbb 1,由于xs與Y對應(yīng)，又由于 11CbB °，可行y CbB 0）。對于單純形法和對偶單純形法，我們建立了使用單純形法解決線性規(guī)劃問題 的依據(jù)：1 ,表中有單位矩陣I ,當(dāng)b 0時用單純形法；2 ,表中有單位矩陣I ,當(dāng)0時用單純形法；3 ,兩者都不滿足時，使用人工變量法或兩階段法。接下來需要說明在哪些場合下使用對偶單純形法解決線性規(guī)劃問題較為便捷，我將通過下面的例子來說明：minZ 12x1 8X2 16X3 12X4令Z z ,則問題可變?yōu)閙axZ12X1 8X2 16X3 12X4M b （p5, p6）為初始基，易見所有檢驗(yàn)數(shù)j 0,從而建立單純形表，計(jì)算結(jié)果如下：本例如果用單純形法計(jì)算，確定初始基可行解時需引入兩個人工變量，計(jì)算量要多于對偶單純形法。一般情況下，如果問題能夠用對偶單純形法計(jì)算，計(jì)算量會少于單純形法。但是，對偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線性規(guī)劃問題都能用對偶單純形法計(jì)算的。當(dāng)線