1、卜二 GUILIN UNIVERSITV OF ELECTRONIC TECKHOLO<>Y最優化方法課程設計題目兩階段法分析與實現院系：數學與計算科學學院專 業：統計學姓名學號：張雨坤 16指導教師：李豐兵日 期：2015 年01 月22 日摘要常用的解線性規劃問題的方法有圖解法， 單純形法，對偶單純形法，解乘數 法，橢球法等。而本論文即主要闡述的是從屬于單純形法的兩階段法。 兩階段法 第一階段是先求解一個目標函數中只包含人工變量的線性規劃問題， 當第一階段 求解結果表明問題有可行解時，第二階段是從第一階段的最終單純形表出發， 去 掉人工變量，并按問題原來的目標函數，繼續尋找問題

2、的最優解，即是一種為使 人工變量被替換出成為非基變量的方法。與大M法同時被廣為使用，但相較于大 M法，兩階段法能夠求的更準確地結果。關鍵詞：線性規劃；單純形法；兩階段法；大 M法AbstractWe usually solve the linear programming problems with graphic method, simplex method and dual simplex method, the multiplier method, ellipsoid method and so paper mainly expounds the two stage method whi

3、ch belongs to simplex method. The first stage of two stage method is used to solve a objective function which only contains artificial variables linear programming problem. When the first phase of solving results show that the problem has a feasible solution, the second stage is from the first stage

4、 of the final simplex tableau, remove artificial variables, and according to the problems of the original objective function, continue to look for the optimal solution of the problem. It is a kind of way to make artificial variables substituted the non variable method. The big M method is also widel

5、y used at the same time, but compared with the big M method ,two-phase method can more accurate results.Key words: ;Linear programming；Simplex method;Two stage method;The big M method;目錄1、引言 12、兩階段法描述 1基本可行解 1兩階段法概述 1兩階段法第一階段 2兩階段法第二階 段33、兩階段法求解引例 4兩階段法計算步驟 4例 1 5例 2 8引例分析 94、算法比較 9大M法 9算法比較 10特殊情況

6、115、總結 錯誤 !未定義書簽。總結概括 12個人感言 126、參考文獻： 131、引言在各種優化算法中，兩階段法(Two stage method)是非常重要的一種。即如果 線性規劃模型中的約束條件系數矩陣不存在單位向量組，階梯式應先加入人工變量，人 工構成一個單位向量組，其只起過渡作用，不應影響決策變量的取值，兩階段法即可控 制人工變量取值。尋找線性規劃問題初始基可行解的一種方法 . 把增加人工變量的線性規劃問題分為 Ax x b 兩個階段去求解. 第一階段是構造一個輔助的人工目標函數, 即a 或x 0,xa 0 maxZ ( yi) 。 若原問題 有可行 解, 則在本階 段的最 終單

7、純形表中 , 必有 Z 0和 yi 0(i 1,2,L ,m), 并使人工變量均為非基變量 . 此時,劃去人工變量所在的列與人工目 標函數所在的行 , 就得到原問題的初始可行基對應的單純形表 , 進入第二階段 .2、兩階段法描述基本可行解 設給定線性規劃問題為當線性規劃問題的玉樹條件全部為時，可按下述方法比較方便的尋找可行解：nmax z cj xj j1naij xj bi(i 1,L ,m)s.t. j 1xj 0 ( j 1,L ,n)在第 i 個約束條件上加上松弛變量 xsi(i 1,L ,m) ，化為標準形式nmmax z cj xj 0xsij 1 i 1naij xj xsi b

8、i(i 1,L ,m)s.t. j 1xj 0 ( j 1,L ,n)a11a12 La1n10L0a21a22 La2n01L0MMMMMMam1am2 Lamn00L1由于這個系數矩陣中含一個單位矩陣(Ps1,L , Psm ) ，只要以這個單位矩陣作為基，就可以立即解除基變量值 xsi bi(i 1,L ,m) ，因為有 bi 0(i 1,L ,m) ，由此X (0,L ,0, b1,L ,bm)T 就是一個基可行解。當線性規劃中約束條件為“ ”、“ ”時，化為標準形式后，一般約束條件的系 數矩陣中不包括有單位矩陣。這是為能方便地找出一個初始的基可行解，可添加人工變 量來人為地構造一個單

9、位矩陣作為基，稱作人工基。先在不等式左端減去一個大于等于 零的剩余變量(也稱為松弛變量)化為等式，然后再添加一個人工變量。解線性規劃概述 兩階段法第一階段是先求解一個目標函數中只包含人工變量的線性規劃問題， 即令 目標函數中其他變量的系數取 0，人工便靈的系數取某個正的常數，(一般取 1)，在 保持原問題約束條件不變的情況下求這歌目標函數極小化的解。顯然在第一階段中，當 人工變量取值為 0 的時候，目標函數值也為 0。這時候的最優解就是原線性規劃問題的 一個可行解，。如果第一階段求解結果最優解的目標函數值不為0，也即最優解的基變量中含有人工基變量，表明原線性規劃問題無可行解。當第一階段求解結果

10、表明問題有可行解時， 第二階段是從第一階段的最終單純性表 出發，去掉人工變量，并按問題原來的目標函數，繼續尋找問題的最優解。兩階段法第一階段 兩階段法第一階段是先求解一個目標函數中只包含人工變量的線性規劃問題， 即令目標函數 中其他變量的系數取 0，人工便靈的系數取某個正的常數，(一般取 1)，在保持原問題約束條 件不變的情況下求這歌目標函數極小化的解。顯然在第一階段中，當人工變量取值為 0 的時候， 目標函數值也為 0。這時候的最優解就是原線性規劃問題的一個可行解。如果第一階段求解結果 最優解的目標函數值不為 0，也即最優解的基變量中含有人工基變量，表明原線性規劃問題無可行解兩階段法第一階段

11、是求解第一個 LP。首先我們可以知道，原LP的表達式為nmin zcj xjj1Ax bs.t.x0其可行域為xxD:x D Da0而我們需要一個輔助的LP,其表達式為mmin waii1Ax a bs.t.x 0,a 0其可行域為xD : D min w 00我們計算以上輔助LP有三種可能結果：1) 、最優值 w 0 ，且人工變量皆為非基變量。從第一階段的最優解中去掉人工變量后即為原LP的一個基本可行解。作為原LP的一個初始基本可行解，再求原問題，從 而進入第二階段。2) 、最優值 w 0，且存在人工變量皆為基變量，取值為 0 。把某個非基變量與該人工變量進行調換。3) 、最優值w 0，說明

12、至少有一個人工變量不為0。原LP無可行解，不需要再做第二階段計算。兩階段法第一階段目的就是判斷原 LP有無可行解，若有，則可得原LP的一個初始基本可行解，再對原LP進行第二階段的計算。兩階段法第二階段以第一階段求得最優解作為初始基本可行解，再用第一階段求得最優解時的約束條 件和原問題的目標函數進行迭代，直到求出最優解。3、兩階段法求解引例、兩階段法計算步驟兩階段法具體計算步驟：第一步：求出線性規劃的初始基可行解，列出初始單純形表。第二步：進行最優性檢驗。第三步;從一個基可行解轉換到另一個目標函數值更大的基可行解，列出新的單純形表。第四步：重復第二、三步一直到計算終止。第五步：去除人工變量。根據

13、求得初始基本可行解，求得最優解。其中第三步具體方法如下：1）、確定換入基變量。只要檢驗數 j 0，對應的變量Xj就可作為換入基的變量，當有一個以上檢驗數大于零時，一般從中找出最大的一個kk max j j 0其對應變量Xk作為換入基的變量（簡稱換入變量）2）、確定換出基的變量，確定baikbimin aikaik確定Xi為換出基的變量（簡稱出基變量）元素aik決定了從一個基本可行解到另一個可行解的轉移去向，取名主元素3）、用換入變量Xk替換基變量中的換出變量，得到一個新的基（,L ,P|1,Pk,P1,L ,Pm,Pm1,L ,Pmn）。對應這個基可以找出一個新的基本可行解。并可 劃出一個新的

14、單純形表。進行如下計算bia、將主元素所在的I行數字除以主元素aik，即有 aakb、為使Pk列變換成單位向量，將單純形表的第I行數字乘上（a”），加到單純aIk形表第i行數字上，計入其相應行。即有bibiaIj aIjbIgaik (i bkaIj g ( gaik (i aIkI)I)c、計算單純形表中各檢驗數，如下Zi)Ci1 I1mCi akCkCi aikaI ki1i I 1Ck1 m1(CkZk)Ci aika IkaIk i 1a Ik1 1mmmCi aijCi aijCi aikCkCiaiki 1iI 1a Iki 1i I 1ma Ijma IjCi aijCkGaik

15、(CjZj)(Ck1a Iki 1a Ik(CiIZk)其檢驗數（CkiiCj(Cj Zj) Cj由上可看出，檢驗數計算同樣因Xk基變量后,Zk）應為零，故將單純形表中第I行數字乘上（ 衣）加到該表的檢驗數上，得新的變量的檢驗數。 aI k接下來在引例中用以上步驟實際求解、例一：用兩階段法求以下問題最優解max z3x(X3X1X2X342x-iX2X31s.t3x2X39Xj 0(j1,2,3)首先第一階段是將此問題化為標準形式，在約束條件中加入松弛變量x4, x5, x6, x7后min w x6 x7x-ix2x3x442為x2x3X5X61s.t3x2 x3X79Xj 0( j 1,L

16、 ,7)先用單純形法解一階段問題，迭代如下：1ZjCjCbB PjCjCBYjCjZjCjCbB 1PjCjCsYjCj其中，cb時目標函數中基變量的系數構成的維行向量，yj是上表中的第j列，b是上表中的右端列。求解過程如下單純形表3-1表3-1單純形表Cj00000-1-1Cb基bX1X2X3X4X5X6X70X441211000-1X61-21-10-110-1X790310001CjZj-2400-1000X4330211-100X21-21-10-110-1X7660403-31CjZj60403-400X4000011212120X230113000130X1110230121216

17、CjZj00000-1-1所有判別級數Cj Zj 0，因此達到最優解，在第一階段問題最優解中，人工變量X6、X7都是非基變量。因此我們可得到初始基可行解Xi，X2，X3，X4，x1,3,0,0,0第二階段是將表3-1中的人工變量X6,X7去除，目標函數改為：max z3x1 0x2 x3 0x4 0x5再從表3-1最后一個表出發，繼續迭代，求解過程的單純形表如下表3-2表3-2單純形表Cj-30100Cb基bXX2X3X4X50X400001120X2301100321-3X1110032CjZj0030320X40000120511X21002241330103X322493CjZj0002

18、45 3得到其最優解Xi,X2,X30,-,3 ,所以目標函數最優值嗨2 2、例二：用兩階段法求解以下問題min z 2x1 3x211XiX2424S.tXi3x236XiX210Xi,X20首先第一階段是將此問題化為標準形式，在約束條件中加入松弛變量x3, x4, x5, x6后minz2x1 3x211X7X2X3424s.tX13x2x4 x536X1X2X6 10Xi,X2,X3,X4,X5,X60先用單純形法解一階段問題，迭代如下1ZjCjcbbPjCjCb yjCj1ZjCjCBb PjCjCB yj Cj其中，Cb時目標函數中基變量的系數構成的維行向量，Yj是上表中的第j列，b

19、是上表中的右端列。求解過程如下單純形表3-3表3-3單純形表Cj000011Cb基bX1X2X3X4X5X60X34121410001X536130-1101X610110001CjZj240-1000X332140100141X56-200-11-30X210110001CjZj-20010-4所有判別級數Cj Zj 0 ,但此時w 6，說明至少有一個人工變量不為 0,原問題 無可行解，不需要進入第二階段計算。、引例分析根據引例一和引例二的求解過程計算可知，第一階段使用單純形法可以得到一般的 最優解，而使用兩階段法能在第二階段找到更精確更優化的最優解。4、算法比較大M算法單純形法從一個初始可

20、行基開始，要求標準型對應的單純形表滿足兩個條件，其是中心部位具有m階單位子塊，其二是右列元素非負。對于線性規劃問題nmin z CjXjj i()naijxjbi, i 1,2.L ,mS.t j 1Xj0, j 1,2.L , n若r(A) m，且對應的廚師單純形表條件二滿足條件一不滿足，那么應引入人工變量Xn 1 , Xn 2 ,LXn m ，構造新的線性規劃問題min zcj xj M xjj 1 j n1naij xj xn 1 bi,i 1,2.L ,m s.t. j 1xj 0, j 1,2.L ,n,n 1,L ,n m其中， M 0 且為無限大的數，令 yxn 1,xn 2,L

21、xnmT,E1,1,L 1 T ，則相性規劃問題可表示為min z CTx MET yAx y b （） s.t.x, y 0設（x ,y ）T是（）的最優解，若y0，則X是（）的最優解，若y0 ，則（ 4. ）無可行解。反之，若x是（）的最優解，貝U （x ,0）T是（）的最優解故其求解方法步驟為1）、經初等行變換通常使 ri （ 1） ，使右列元素非負2）、在中心部位人工的添加一個 m階單位子塊，即引入人工變量 力2丄，ym，得到新 的約束方程組。m3） 、講目標函數修改為 z z M yj ，其中 M 0為足夠大的正常數，從而得到新的j1LP模型。4）、用單純形法求解新的LP模型，試圖將

22、yi, y2,L ,ym變成自由變量，最終有兩種結 果如下a、設球的新的LP模型最優解為（x , y ）T，若y g ,y丄，ym ）0，則x % x丄，Xn）是原lp問題的最優解。若y （yi , y2丄，ym ） 0，則原LP問題無最優解。b、新LP無界（無最優解），則原LP問題也無最優解。算法比較如果線性規劃模型中約束條件系數矩陣中不存在單位向量組，解題時應先加入人工 變量，人工地構成一個單位向量組。而兩階段法和大 M法都是可以控制人工變量取值的 方法，并且兩種方法都是在單純形法的基礎上進一步求解最優解的方法，兩種方法的用 法相似，各有優缺點。通過設置新的變量得到初始基本變量，并通過在目

23、標函數中設置 新變量的價格系數為M使得在優化過程中，新變量的值優化為 0在計算機求解過程中， 由于計算機只能對M設置有限大的數值，所以在計算過程中可能會產生誤差，為了解決 這個問題，產生了兩階段法。所以大 M法雖然簡單直觀，在單純形表上的計算步驟與普 通單純形法相同，但是大M到底取值多大不能確定，M取值過大也將增加數值計算困難。用大M法處理人工變量，用手工計算求解時不會碰到麻煩。但用電子計算機求解時, 對M就只能在計算機內輸入一個機器最大字長的數字。 如果線性規劃問題中的參數值與 這個代表M的數相對比較接近，或遠遠小于這個數字，由于計算機計算時取值上的誤差， 可能使計算結果發生錯誤。 而兩階段

24、法通過對添加人工變量后的線性規劃問題分兩個階 段來計算，從而可以克服這個困難。特殊情況1）、無可行解：線性規劃最優解中出現人工變量大于零的情況，則此線性規劃無 可行解。2）、無界解：在求目標函數最大值等問題中，在某次迭代的單純形表中，如果存 在這一個不滿足符號條件的檢驗數，并且該列的系數向量的每個元素都小于或等于令， 則此線性規劃無界。3）、無窮多最優解 : 對于某個最優的基本可行解，如果存在某個非基變量的檢驗 數為零，則此線性規劃問題有無窮多最優解。4）、退化：在單純形法計算過程中，基變量有事存在兩個以上相同的最小比值， 這樣在下一次迭代中就有一個或幾個基變量等于零，稱之為退化。而退化就容易

25、產生循 環迭代，為避免如此，應遵守以下兩條原則：a、在所有不滿足符號條件的檢驗數對應的非基變量中，選一個下標最小的作 為調入變量。b、若存在兩個以上的最小比值，選一個下表最小的作為調出變量5、總結總結概括求解最優問題是一個艱難而具有挑戰性的過程， 最優化方法是近幾十年形成的一門 運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據的學科， 它涵蓋了無約束最優化問題、凸集與凸函數、等式約束最優化問題和不等式約束最優化 問題等知識點。通過本課程教學，使學生掌握最優化計算方法的基本概念和基本理論， 初步學會處理應用最優化方法解決實際中的碰到的各個問題，培養解決實際問題的能 力。而本次課程設計，我選擇了兩階段法這一課題對之進行了一定程