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

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

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

3、 > CjXjs. t ajjXj < bj j=iXj > 0 j =Min W = y 可達 = ££包詼訪> Cj 航之。i= 1,2,，m從而可以發(fā)現(xiàn)如下規(guī)律：1 .原問題目標函數(shù)系數(shù)是對偶問題約 束方程的右端項。2 .原問題約束方程的右端項是對偶問 題目標函數(shù)的系數(shù)。3 .原問題一個變量在所有約束方程中的系數(shù)是對偶問題一個約束方程中的所有 系數(shù)。三、對偶單純形法原理對偶單純形法是通過尋找原問題的對 偶問題的可行解來求解原問題的最優(yōu)解的 方法，它的應(yīng)用包括影子價格和靈敏度分析 等。為了理解對偶單純形法為什么能夠解出 原方程的最優(yōu)解，我們需要對

4、對偶理論的幾 個基本原理有所了解。1 .弱對偶性如果Xj( = L/n)是原問題的可行解，1,/m)是其對偶問題的可行解，則恒證明： 件是各行的2 b承 1=1由于對偶方程中原問題的約束條aj Xj之和小于等于V'的系數(shù)b)而對偶問題的約束條件是各行的 小于等于Xj的系數(shù)Cj ,aj V'之和故將ZJLi 9%x；和bi%分別和£目1£11居分比較)可得上述結(jié)論。2.最優(yōu)性如果=hJf，口)是原問題的可行解,%。工 草芳.啰某翻禺問題的可行解，且有j二i1=1則&是原問題的最優(yōu)解，i(i =是其對偶問題的最優(yōu)解。因”c b=-iyiiyiAb b c

5、m m電一 <->-可 與iyi一 b證IE .1可EKII故可知= LIH）是原問題的最優(yōu) 解，yi（i = L,m）是其對偶問題的最優(yōu)解。3 .強對偶性如果原問題有最優(yōu)解，那么其對偶問題 也有最優(yōu)解）且有maxz=minw.證明：設(shè) B為原問題式（1）的最優(yōu)基， 那么當(dāng)基為 B時的檢驗數(shù)為C cbb1a,其中CB為 由基變量的價值系數(shù)組成的價值向量。既然B為原問題式（1）的最優(yōu)基，那么有 C CBB1A 0 o令Y CbB那么有C YA 0 YA C ,從而Y OB是 對偶問題式（2）的可行解。這樣一來，Y CBB1是對偶問題的可行解， Xb ”是原問題的最優(yōu)基可行解。由于 C

6、X CbXb CnXn CbB 1b 而 Yb CbB 1b 從而有 CX Yb。根據(jù)最優(yōu)性，命題得鬲4 .線性規(guī)劃的問題原問題及對偶問題 之間存在一對互補的基解，其中原問題的松 弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量；這些相互對應(yīng)的 變量如果在一個問題中是基變量，則在另一 問題中是非基變量；將這對互補的基解分別 代入原問題和對偶問題的目標函數(shù)有Z=Wo四、對偶單純形算法流程在上述的理論基礎(chǔ)上，可知用單純形法 求解線性規(guī)劃問題時，在得到原問題的一個 基可行解問題同時，在檢驗數(shù)行得到對偶問 題的一個基解。單純形法的基本思想是保持 原問題為可行解的基礎(chǔ)上，通過迭代增大目 標函

7、數(shù)，當(dāng)其對偶問題也為可行解時，就達 到了目標函數(shù)的最優(yōu)值。而對偶單純形法的基本思想則是保持 對偶問題為可行解的前提下(即單純性表最 后一行檢驗數(shù)都小于零)，通過迭代減小目 標函數(shù)，當(dāng)原問題也是可行解時，就得到了 目標函數(shù)的最優(yōu)解。故我們可以得到對偶單純形法求解過 程如下：1 .將原問題化為標準型，找到一個檢驗 數(shù)都小于等于零的對偶問題的初始可行基。2 .確定換出基的變量對于小于零的 bi)找到最小的一個 br) 其對應(yīng)的Xr為換出基的變量3 .確定換入基的變量(1)為了使迭代后表中的第 r行基變 量為正值，因而只有對應(yīng) aj小于零的非基 變量才可以作為換入基的變量；(2)為了使迭代后表中對偶問

8、題仍為6可行的空叫口 |1。|二星二公J （沏J as稱ars為主元素）Xs為換入基的變量。4 .用換入變量替換換出變量，得到一個新的基。再次檢查是否所有的bi大于等于零。如果是，則找到了最優(yōu)解，如果否，則再次進行變換。對偶單純形法的算法流程圖:開始化原問題找出一個對偶問題的 初始可行等B）,計算 一. 上bi者B確定換出和換入的基變量：7換出最小的“右端項” b計算檢驗已找到"結(jié)束>五、對偶單純形法例題下面用一個例子來說明對偶單純形法 的解題過程。Min z=5x i+2x 2+4x3（3x1 + x2 + 2x3 > 45 .t.伯門一代二一, '.） xlf

9、x2,x3 > 01.化為標準型Max z ' =-5x i-2x 2-4x 3+0x4+0x5'-3x1 逐一2x3 + x4 = -4s.t. -6x1 - 3x2 5x3 +x5 = -1Oxl,x2Tx3Tx4*TxS > 02 .列出原始單純形表Cjf-5-2-400Cb基bXiX2X3X4X50x4-4-3-1-2100x5-10-6-3-501Cj-z j-5-2-4003 .找出最小的 bi ,即b5=-10.選擇x5作為再出變量J q I% 。1=4 =Q一也J aiiJ 3a22故選擇a22為主元素)x2為換入變量) 得到新的單純形表：Cjf-5

10、-2-400Cb基bXiX2X3X4X50X4 -2/3-2X210/3-10-1/31-1/3215/30-1/3Cj-z j-10-2/30-2/3再次換人換出：Cj 一-5-2-400Cb基bXiX2X3X4X5-5Xi2/3-2X22101/3-11/30112-1Cj-z j00-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ī) 劃問題具備卜面條件時，可以用

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

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