兩階段法分析與實現(xiàn)

1、最 優(yōu) 化 方 法課 程 設(shè) 計題 目： 兩階段法分析與實現(xiàn) 院 系： 數(shù)學(xué)與計算科學(xué)學(xué)院 專 業(yè)： 統(tǒng)計學(xué) 姓名學(xué)號： 張雨坤 1200720216 指導(dǎo)教師： 李豐兵 日 期： 2015 年 01 月 22 日摘 要常用的解線性規(guī)劃問題的方法有圖解法，單純形法，對偶單純形法，解乘數(shù)法，橢球法等。而本論文即主要闡述的是從屬于單純形法的兩階段法。兩階段法第一階段是先求解一個目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，當(dāng)?shù)谝浑A段求解結(jié)果表明問題有可行解時，第二階段是從第一階段的最終單純形表出發(fā)，去掉人工變量，并按問題原來的目標(biāo)函數(shù)，繼續(xù)尋找問題的最優(yōu)解，即是一種為使人工變量被替換出成為非基變量的方法

2、。與大M法同時被廣為使用，但相較于大M法，兩階段法能夠求的更準(zhǔn)確地結(jié)果。關(guān)鍵詞：線性規(guī)劃；單純形法；兩階段法；大M法Abstract We usually solve the linear programming problems with graphic method, simplex method and dual simplex method, the multiplier method, ellipsoid method and so on.This paper mainly expounds the two stage method which belongs to simplex

3、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 of the final simplex

4、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 widely used at the same tim

5、e, 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、兩階段法描述12.1 基本可行解12.2 兩階段法概述12.3 兩階段法第一階段22.4 兩階段法第二階段.33、兩階段法求解引例43.1 兩階段法計算步驟43.

6、2 例153.3 例283.4 引例分析94、算法比較94.1 大M法94.2 算法比較104.3 特殊情況115、總結(jié)125.1 總結(jié)概括125.2 個人感言126、參考文獻(xiàn)：131、引言在各種優(yōu)化算法中，兩階段法（Two stage method）是非常重要的一種。即如果線性規(guī)劃模型中的約束條件系數(shù)矩陣不存在單位向量組，階梯式應(yīng)先加入人工變量，人工構(gòu)成一個單位向量組，其只起過渡作用，不應(yīng)影響決策變量的取值，兩階段法即可控制人工變量取值。尋找線性規(guī)劃問題初始基可行解的一種方法.把增加人工變量的線性規(guī)劃問題分為兩個階段去求解.第一階段是構(gòu)造一個輔助的人工目標(biāo)函數(shù),即或。若原

7、問題有可行解,則在本階段的最終單純形表中,必有和,并使人工變量均為非基變量.此時,劃去人工變量所在的列與人工目標(biāo)函數(shù)所在的行,就得到原問題的初始可行基對應(yīng)的單純形表,進(jìn)入第二階段.2、兩階段法描述2.1 基本可行解當(dāng)線性規(guī)劃問題的玉樹條件全部為“”時，可按下述方法比較方便的尋找可行解：設(shè)給定線性規(guī)劃問題為在第個約束條件上加上松弛變量，化為標(biāo)準(zhǔn)形式由于這個系數(shù)矩陣中含一個單位矩陣，只要以這個單位矩陣作為基，就可以立即解除基變量值，因為有，由此就是一個基可行解。當(dāng)線性規(guī)劃中約束條件為“”、“ ”時，化為標(biāo)準(zhǔn)形式后，一般約束條件的系數(shù)矩陣中不包括有單位矩陣。這是為能方便地找出一個初始的基可行解，可添

8、加人工變量來人為地構(gòu)造一個單位矩陣作為基，稱作人工基。先在不等式左端減去一個大于等于零的剩余變量（也稱為松弛變量）化為等式，然后再添加一個人工變量。2.2 解線性規(guī)劃概述兩階段法第一階段是先求解一個目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中其他變量的系數(shù)取0，人工便靈的系數(shù)取某個正的常數(shù)，（一般取1），在保持原問題約束條件不變的情況下求這歌目標(biāo)函數(shù)極小化的解。顯然在第一階段中，當(dāng)人工變量取值為0的時候，目標(biāo)函數(shù)值也為0。這時候的最優(yōu)解就是原線性規(guī)劃問題的一個可行解，。如果第一階段求解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為0，也即最優(yōu)解的基變量中含有人工基變量，表明原線性規(guī)劃問題無可行解。當(dāng)?shù)谝?/p>

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

10、第一個LP。首先我們可以知道，原LP的表達(dá)式為其可行域為而我們需要一個輔助的LP，其表達(dá)式為其可行域為我們計算以上輔助LP有三種可能結(jié)果：1)、最優(yōu)值，且人工變量皆為非基變量。從第一階段的最優(yōu)解中去掉人工變量后即為原LP的一個基本可行解。作為原LP的一個初始基本可行解，再求原問題，從而進(jìn)入第二階段。2)、最優(yōu)值，且存在人工變量皆為基變量，取值為。把某個非基變量與該人工變量進(jìn)行調(diào)換。 3)、最優(yōu)值，說明至少有一個人工變量不為。原LP無可行解，不需要再做第二階段計算。兩階段法第一階段目的就是判斷原LP有無可行解，若有，則可得原LP的一個初始基本可行解，再對原LP進(jìn)行第二階段的計算。2.4 兩階段法

11、第二階段以第一階段求得最優(yōu)解作為初始基本可行解，再用第一階段求得最優(yōu)解時的約束條件和原問題的目標(biāo)函數(shù)進(jìn)行迭代，直到求出最優(yōu)解。3、兩階段法求解引例3.1、兩階段法計算步驟兩階段法具體計算步驟：第一步：求出線性規(guī)劃的初始基可行解，列出初始單純形表。第二步：進(jìn)行最優(yōu)性檢驗。第三步;從一個基可行解轉(zhuǎn)換到另一個目標(biāo)函數(shù)值更大的基可行解，列出新的單純形表。第四步：重復(fù)第二、三步一直到計算終止。第五步：去除人工變量。根據(jù)求得初始基本可行解，求得最優(yōu)解。 其中第三步具體方法如下：1)、確定換入基變量。只要檢驗數(shù)，對應(yīng)的變量就可作為換入基的變量，當(dāng)有一個以上檢驗數(shù)大于零時，一般從中找出最大的一個其對應(yīng)變量作為

12、換入基的變量（簡稱換入變量）。2)、確定換出基的變量，確定確定為換出基的變量（簡稱出基變量）。元素決定了從一個基本可行解到另一個可行解的轉(zhuǎn)移去向，取名主元素。3)、用換入變量替換基變量中的換出變量，得到一個新的基。對應(yīng)這個基可以找出一個新的基本可行解。并可劃出一個新的單純形表。進(jìn)行如下計算:a、將主元素所在的行數(shù)字除以主元素，即有b、為使列變換成單位向量，將單純形表的第行數(shù)字乘上，加到單純形表第行數(shù)字上，計入其相應(yīng)行。即有c、計算單純形表中各檢驗數(shù)，如下由上可看出，檢驗數(shù)計算同樣因基變量后，其檢驗數(shù)應(yīng)為零，故將單純形表中第行數(shù)字乘上加到該表的檢驗數(shù)上，得新的變量的檢驗數(shù)。 接下來在引例中用以上

13、步驟實際求解3.2、例一：用兩階段法求以下問題最優(yōu)解首先第一階段是將此問題化為標(biāo)準(zhǔn)形式，在約束條件中加入松弛變量后得先用單純形法解一階段問題，迭代如下：其中，時目標(biāo)函數(shù)中基變量的系數(shù)構(gòu)成的維行向量，是上表中的第列，是上表中的右端列。求解過程如下單純形表3-1表3-1單純形表00000-1-1基041211000-11-2-10-110-190310001-2400-10003 30211-1001-21-10-110-1660403-3160403-4000000103010000110000000-1-1所有判別級數(shù)，因此達(dá)到最優(yōu)解，在第一階段問題最優(yōu)解中，人工變量、都是非基變量。因此我們可

14、得到初始基可行解第二階段是將表3-1中的人工變量去除，目標(biāo)函數(shù)改為：再從表3-1最后一個表出發(fā)，繼續(xù)迭代，求解過程的單純形表如下表3-2表3-2單純形表-30100基000001030100-31100003000000101001010000得到其最優(yōu)解，所以目標(biāo)函數(shù)最優(yōu)值3.3、例二：用兩階段法求解以下問題首先第一階段是將此問題化為標(biāo)準(zhǔn)形式，在約束條件中加入松弛變量后得先用單純形法解一階段問題，迭代如下其中，時目標(biāo)函數(shù)中基變量的系數(shù)構(gòu)成的維行向量，是上表中的第列，是上表中的右端列。求解過程如下單純形表3-3表3-3單純形表000011基041000136130-11011010001240

15、-1000010016-200-11-3010110001-20010-4所有判別級數(shù)，但此時，說明至少有一個人工變量不為0，原問題無可行解，不需要進(jìn)入第二階段計算。3.4、引例分析根據(jù)引例一和引例二的求解過程計算可知，第一階段使用單純形法可以得到一般的最優(yōu)解，而使用兩階段法能在第二階段找到更精確更優(yōu)化的最優(yōu)解。4、算法比較4.1 大M算法單純形法從一個初始可行基開始，要求標(biāo)準(zhǔn)型對應(yīng)的單純形表滿足兩個條件，其一是中心部位具有階單位子塊，其二是右列元素非負(fù)。對于線性規(guī)劃問題 （4.1.1）若，且對應(yīng)的廚師單純形表條件二滿足條件一不滿足，那么應(yīng)引入人工變量，構(gòu)造新的線性規(guī)劃問題 （4.1.2）其中

16、，且為無限大的數(shù)，令，則相性規(guī)劃問題可表示為 （4.1.3）設(shè)是（4.1.3）的最優(yōu)解，若，則是（4.1.2）的最優(yōu)解，若，則（4. 1.2）無可行解。反之，若是（4.1.2）的最優(yōu)解，則是（4.1.3）的最優(yōu)解。故其求解方法步驟為1）、經(jīng)初等行變換通常使，使右列元素非負(fù)。2）、在中心部位人工的添加一個階單位子塊，即引入人工變量，得到新的約束方程組。3）、講目標(biāo)函數(shù)修改為，其中為足夠大的正常數(shù)，從而得到新的LP模型。4）、用單純形法求解新的LP模型，試圖將變成自由變量，最終有兩種結(jié)果如下a、設(shè)球的新的LP模型最優(yōu)解為，若，則是原LP問題的最優(yōu)解。若，則原LP問題無最優(yōu)解。b、新LP無界（無最優(yōu)

17、解），則原LP問題也無最優(yōu)解。4.2 算法比較如果線性規(guī)劃模型中約束條件系數(shù)矩陣中不存在單位向量組，解題時應(yīng)先加入人工變量，人工地構(gòu)成一個單位向量組。而兩階段法和大M法都是可以控制人工變量取值的方法，并且兩種方法都是在單純形法的基礎(chǔ)上進(jìn)一步求解最優(yōu)解的方法，兩種方法的用法相似，各有優(yōu)缺點。通過設(shè)置新的變量得到初始基本變量，并通過在目標(biāo)函數(shù)中設(shè)置新變量的價格系數(shù)為M使得在優(yōu)化過程中，新變量的值優(yōu)化為0在計算機(jī)求解過程中，由于計算機(jī)只能對M設(shè)置有限大的數(shù)值，所以在計算過程中可能會產(chǎn)生誤差，為了解決這個問題，產(chǎn)生了兩階段法。所以大M法雖然簡單直觀，在單純形表上的計算步驟與普通單純形法相同，但是大M到

18、底取值多大不能確定，M取值過大也將增加數(shù)值計算困難。用大M法處理人工變量，用手工計算求解時不會碰到麻煩。但用電子計算機(jī)求解時，對M就只能在計算機(jī)內(nèi)輸入一個機(jī)器最大字長的數(shù)字。如果線性規(guī)劃問題中的參數(shù)值與這個代表M的數(shù)相對比較接近，或遠(yuǎn)遠(yuǎn)小于這個數(shù)字，由于計算機(jī)計算時取值上的誤差，可能使計算結(jié)果發(fā)生錯誤。而兩階段法通過對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，從而可以克服這個困難。4.3 特殊情況1）、無可行解：線性規(guī)劃最優(yōu)解中出現(xiàn)人工變量大于零的情況，則此線性規(guī)劃無可行解。2）、無界解：在求目標(biāo)函數(shù)最大值等問題中，在某次迭代的單純形表中，如果存在這一個不滿足符號條件的檢驗數(shù)，并且該列的系

19、數(shù)向量的每個元素都小于或等于令，則此線性規(guī)劃無界。3）、無窮多最優(yōu)解:對于某個最優(yōu)的基本可行解，如果存在某個非基變量的檢驗數(shù)為零，則此線性規(guī)劃問題有無窮多最優(yōu)解。4）、退化：在單純形法計算過程中，基變量有事存在兩個以上相同的最小比值，這樣在下一次迭代中就有一個或幾個基變量等于零，稱之為退化。而退化就容易產(chǎn)生循環(huán)迭代，為避免如此，應(yīng)遵守以下兩條原則：a、在所有不滿足符號條件的檢驗數(shù)對應(yīng)的非基變量中，選一個下標(biāo)最小的作為調(diào)入變量。b、若存在兩個以上的最小比值，選一個下表最小的作為調(diào)出變量。5、總結(jié)5.1 總結(jié)概括求解最優(yōu)問題是一個艱難而具有挑戰(zhàn)性的過程，最優(yōu)化方法是近幾十年形成的一門運用數(shù)學(xué)方法研

20、究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)的學(xué)科，它涵蓋了無約束最優(yōu)化問題、凸集與凸函數(shù)、等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題等知識點。通過本課程教學(xué)，使學(xué)生掌握最優(yōu)化計算方法的基本概念和基本理論，初步學(xué)會處理應(yīng)用最優(yōu)化方法解決實際中的碰到的各個問題，培養(yǎng)解決實際問題的能力。而本次課程設(shè)計，我選擇了兩階段法這一課題對之進(jìn)行了一定程度上的研究。兩階段法是當(dāng)線性規(guī)劃模型中約束條件系數(shù)矩陣不存在單位向量組時，加入人工變量，人工構(gòu)造一個單位向量組的方法。在兩階段法中，第一階段不考慮原問題是否存在基可行解，給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量目標(biāo)函數(shù)和要求實現(xiàn)最小化。然后用單純形法求解上述模型，若得到，說明原問題存在基可行解，可以進(jìn)行第二階段的計算，否則原問題無可行解，應(yīng)停止計算。在第二階段中，將第