哈工大運籌學(xué)大作業(yè)-對偶單純形法對比

1、精選優(yōu)質(zhì)文檔-傾情為你奉上運籌學(xué)課程運籌學(xué)對偶單純形法與單純形法對比分析大作業(yè) 哈爾濱工業(yè)大學(xué)工業(yè)工程系 學(xué) 生 姓 名: 學(xué) 號： 指 導(dǎo) 教 師： 成 績：評 語：運籌學(xué)對偶單純形法與單純形法對比分析摘要：這篇論文主要介紹了對偶單純形法的實質(zhì)、原理、流程和適用條件等。將對偶單純形法與單純形法的基本思想進行對比分析，從而說明對偶單純形法的優(yōu)點和適用范圍。關(guān)鍵詞：對偶單純形法；對偶理論；單純形法；基本思想在線性規(guī)劃早期發(fā)展階段的眾多重要發(fā)現(xiàn)中，對偶的概念及其分支是其中最重要的內(nèi)容之一。這個發(fā)現(xiàn)指出，對于任何一個線性規(guī)劃問題都具有對應(yīng)的稱為對偶問題的線性規(guī)劃問題。對偶問題與原問題的關(guān)系在眾多領(lǐng)域

2、都非常有用。（一）教學(xué)目標：通過對偶單純形法的學(xué)習(xí)，加深對對偶問題的理解。掌握對偶單純形法的解題過程，理解對偶理論的其原理，了解對偶單純形法的作用和應(yīng)用范圍（二）教學(xué)內(nèi)容：1） 對偶單純形法的思想來源2） 對偶單純形法原理3） 對偶理論的實質(zhì)4） 單純形法和對偶單純形法的比較（三）教學(xué)進程：一、對偶單純形法的思想來源所謂對偶單純形法，就是將單純形法應(yīng)用于對偶問題的計算，該方法是由美國數(shù)學(xué)家C.萊姆基于1954年提出的，它并不是求解對偶問題解的方法，而是利用對偶理論求解原問題的解的方法。二、對偶問題的實質(zhì)下面是原問題的標準形式以及其對應(yīng)的對偶問題：原問題對偶問題Max Z=j=1ncjxjs.t

3、. j=1naijxjbi i=1,2,mxj0 j=1,2,nMin W=j=1mbiyis.t. j=1naijyicj j=1,2,nyi0 i=1,2,m從而可以發(fā)現(xiàn)如下規(guī)律：1.原問題目標函數(shù)系數(shù)是對偶問題約束方程的右端項。2.原問題約束方程的右端項是對偶問題目標函數(shù)的系數(shù)。3.原問題一個變量在所有約束方程中的系數(shù)是對偶問題一個約束方程中的所有系數(shù)。三、對偶單純形法原理對偶單純形法是通過尋找原問題的對偶問題的可行解來求解原問題的最優(yōu)解的方法，它的應(yīng)用包括影子價格和靈敏度分析等。為了理解對偶單純形法為什么能夠解出原方程的最優(yōu)解，我們需要對對偶理論的幾個基本原理有所了解。1.弱對偶性如果

4、xj(j=1,n)是原問題的可行解，yi(i=1,m)是其對偶問題的可行解，則恒有j=1ncjxji=1mbiyi證明：由于對偶方程中原問題的約束條件是各行的aijxj之和小于等于yi的系數(shù)bi，而對偶問題的約束條件是各行的aijyi之和小于等于xj的系數(shù)cj，故將j=1ncjxj和i=1mbiyi分別和i=1mj=1nxjaijyi比較，可得上述結(jié)論。2.最優(yōu)性如果xj(j=1,n)是原問題的可行解，yi(i=1,m)是其對偶問題的可行解，且有j=1ncjxj=i=1mbiyi則xj(j=1,n)是原問題的最優(yōu)解，yi(i=1,m)是其對偶問題的最優(yōu)解。證明：由j=1ncjxji=1mbiy

5、i可得j=1ncjxji=1mbiyi=j=1ncjxji=1mbiyij=1ncjxj=i=1mbiyi故可知xj(j=1,n)是原問題的最優(yōu)解，yi(i=1,m)是其對偶問題的最優(yōu)解。3.強對偶性如果原問題有最優(yōu)解，那么其對偶問題也有最優(yōu)解，且有maxz=minw.證明：設(shè)B為原問題式(1)的最優(yōu)基，那么當(dāng)基為B時的檢驗數(shù)為，其中為由基變量的價值系數(shù)組成的價值向量。既然B為原問題式(1)的最優(yōu)基，那么有。令，那么有，從而是對偶問題式(2)的可行解。這樣一來，是對偶問題的可行解，是原問題的最優(yōu)基可行解。由于，而，從而有。根據(jù)最優(yōu)性，命題得證。4.線性規(guī)劃的問題原問題及對偶問題之間存在一對互補

6、的基解，其中原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量；這些相互對應(yīng)的變量如果在一個問題中是基變量，則在另一問題中是非基變量；將這對互補的基解分別代入原問題和對偶問題的目標函數(shù)有z=w。四、對偶單純形算法流程在上述的理論基礎(chǔ)上，可知用單純形法求解線性規(guī)劃問題時，在得到原問題的一個基可行解問題同時，在檢驗數(shù)行得到對偶問題的一個基解。單純形法的基本思想是保持原問題為可行解的基礎(chǔ)上，通過迭代增大目標函數(shù)，當(dāng)其對偶問題也為可行解時，就達到了目標函數(shù)的最優(yōu)值。而對偶單純形法的基本思想則是保持對偶問題為可行解的前提下（即單純性表最后一行檢驗數(shù)都小于零），通過迭代減小目標函數(shù)，當(dāng)

7、原問題也是可行解時，就得到了目標函數(shù)的最優(yōu)解。故我們可以得到對偶單純形法求解過程如下： 1.將原問題化為標準型，找到一個檢驗數(shù)都小于等于零的對偶問題的初始可行基。2.確定換出基的變量對于小于零的bi，找到最小的一個br，其對應(yīng)的xr為換出基的變量3.確定換入基的變量（1）為了使迭代后表中的第r行基變量為正值，因而只有對應(yīng)aij小于零的非基變量才可以作為換入基的變量；（2）為了使迭代后表中對偶問題仍為可行解，令=minjcj-zjaijari<0=cs-zsars稱ars為主元素，xs為換入基的變量。4.用換入變量替換換出變量，得到一個新的基。再次檢查是否所有的bi大于等于零。如果是，則找

8、到了最優(yōu)解，如果否，則再次進行變換。對偶單純形法的算法流程圖開始化原問題為標準型找出一個對偶問題的初始可行基B0，計算非基變量檢驗數(shù)（全部檢驗數(shù)j  0）并列出初始單純形表是bi 都0？否確定換出和換入的基變量： 換出最小的“右端項”bi所對應(yīng)的基變量； 按公式=minj/aij ，aij 0=s/aij  計算最小比值，所對應(yīng)的基變量為換入計算檢驗數(shù)，列出新的單純形表已找到最優(yōu)解結(jié)束五、對偶單純形法例題下面用一個例子來說明對偶單純形法的解題過程。Min z=5x1+2x2+4x3s.t.3x1+x2+2x346x1+3x2+5x31

9、0x1,x2,x301.化為標準型Max z=-5x1-2x2-4x3+0x4+0x5s.t.-3x1-x2-2x3+x4=-4-6x1-3x2-5x3+x5=-10x1,x2,x3,x4,x502.列出原始單純形表cj-5-2-400CB 基 bx1x2x3x4x50 x4 -40 x5 -10-3-1-210-6-3-501cj-zj-5-2-4003.找出最小的bi，即b5=-10.選擇x5作為換出變量。=minjcj-zjaijari<0=23=c2-z2a22故選擇a22為主元素，x2為換入變量，得到新的單純形表：cj-5-2-400CB 基 bx1x2x3x4x50 x4 -

10、2/3-2 x2 10/3-10-1/31-1/3215/30-1/3cj-zj-10-2/30-2/3再次換入換出：cj-5-2-400CB 基 bx1x2x3x4x5-5 x1 2/3-2 x2 2101/3-11/30112-1cj-zj00-1/3-1-1/34.所有的bi都大于零，說明找到了最優(yōu)解。X=（2/3,2,0）TMax z=-10/3-4=-22/3Min z= 22/3.但是，對偶單純形法并不是一種普遍算法，它有一定的局限性，不是任何線性規(guī)劃問題都能用對偶單純形法計算的。當(dāng)線性規(guī)劃問題具備下面條件時，可以用對偶單純形法求解：問題標準化后，價值系數(shù)全非正；所有約束全是不等式

11、。 六、對偶單純形法的應(yīng)用1.從上面的例題可以看出，原問題是求最小值，并且目標函數(shù)各項系數(shù)都不小于零。所以在轉(zhuǎn)化成標準型后各項系數(shù)不大于零，從而以松弛變量為基列出的單純形表滿足檢驗數(shù)都不大于零，是其對偶問題的一個可行解。如果原問題的標準形式中各項系數(shù)不都小于零，則不容易找到對偶問題的一個初始可行解，就不適合使用對偶單純形法求解。所以對偶單純形法適用于不易找到原方程的可行解而容易找到其對偶問題的可行解的線性規(guī)劃問題。2.我們知道，約束方程的數(shù)量對單純形法的計算過程要遠遠大于變量個數(shù)的影響。如果m>n，那么對偶問題有n個約束方程，而原問題有m個約束方程，所以對偶問題有更少的約束方程數(shù)量，那么

12、通過對偶單純形法的運用比起直接只用單純形法將會顯著的減少計算量。3.弱對偶性和強對偶性是對偶理論的關(guān)鍵原理。對偶問題可以用來對原問題的計劃方案進行評價。我們可以用一個對偶問題的可行解和目前原問題的計劃方案進行比較，如果兩個目標函數(shù)值相等或比較接近，則可以說明原問題的計劃方案已經(jīng)是可以看做最優(yōu)了。4.對偶理論在靈敏度分析和影子價格計算中有著重要的作用。七、單純形法和對偶單純形法的基本思想比較通過以上的分析可知，對偶單純形法其實相當(dāng)于單純形法的一種變形，只不過在運用對偶單純形法解線性規(guī)劃時需要將單純形表旋轉(zhuǎn)一下。單純形表中的b列實際上是對偶問題的非基變量的檢驗數(shù), 而原單純形表的檢驗數(shù)為對偶問題的基解, 這樣可以理解為通過旋轉(zhuǎn)90°運用單純形法