兩階段法分析與實(shí)現(xiàn)[運(yùn)用分享]

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

2、人工變量，并按問(wèn)題原來(lái)的目標(biāo)函數(shù)，繼續(xù)尋找問(wèn)題的最優(yōu)解，即 是一種為使人工變量被替換出成為非基變量的方法。與大 M 法同時(shí)被廣為使用， 但相較于大 M 法，兩階段法能夠求的更準(zhǔn)確地結(jié)果。 關(guān)鍵詞關(guān)鍵詞：線性規(guī)劃；單純形法；兩階段法；大 M 法 教資 c 類 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.Th

3、is paper mainly expounds the two stage method which 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 s

4、olution, the second stage is from the first stage 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 no

5、n variable method. The big M method is also widely 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; 教資 c 類 目目 錄錄 1、引言引言.1 2、兩階段法描述兩階段法描述.1 2.1 基本可行解.1 2.2 兩階段法概述.1 2

6、.3 兩階段法第一階段.2 2.4 兩階段法第二階段.3 3、兩階段法求解引例兩階段法求解引例.4 3.1 兩階段法計(jì)算步驟.4 3.2 例 1.5 3.3 例 2.8 3.4 引例分析.9 4、算法比較算法比較.9 4.1 大 M 法.9 4.2 算法比較.10 4.3 特殊情況.11 5、總結(jié)總結(jié).12 5.1 總結(jié)概括.12 5.2 個(gè)人感言.12 6、參考文獻(xiàn)、參考文獻(xiàn)：.13 教資 c 類 1 1、引言引言 在各種優(yōu)化算法中，兩階段法（Two stage method）是非常重要的一種。即如果線 性規(guī)劃模型中的約束條件系數(shù)矩陣不存在單位向量組，階梯式應(yīng)先加入人工變量，人 工構(gòu)成一個(gè)單

7、位向量組，其只起過(guò)渡作用，不應(yīng)影響決策變量的取值，兩階段法即可 控制人工變量取值。 尋找線性規(guī)劃問(wèn)題初始基可行解的一種方法.把增加人工變量的線性規(guī)劃問(wèn)題分為 兩個(gè)階段去求解.第一階段是構(gòu)造一個(gè)輔助的人工目標(biāo)函數(shù),即或 0,0 a a Axxb xx 。若原問(wèn)題有可行解,則在本階段的最終單純形表中,必有和max() i Zy 0Z ,并使人工變量均為非基變量.此時(shí),劃去人工變量所在的列與人工目0(1,2,) i yim 標(biāo)函數(shù)所在的行,就得到原問(wèn)題的初始可行基對(duì)應(yīng)的單純形表,進(jìn)入第二階段. 2 2、兩階段法描述兩階段法描述 2.1 基本可行解基本可行解 當(dāng)線性規(guī)劃問(wèn)題的玉樹條件全部為“”時(shí)，可按

8、下述方法比較方便的尋找可行 解： 設(shè)給定線性規(guī)劃問(wèn)題為 1 1 max (1,) . . 0(1, ) n jj j n ijji j j zc x a xb im st xjn 在第 個(gè)約束條件上加上松弛變量，化為標(biāo)準(zhǔn)形式 i (1,) si xim 教資 c 類 11 1 max0 (1,) . . 0(1, ) nm jjsi ji n ijjsii j j zc xx a xxb im st xjn 11121 21222 12 1 00 0 10 0 01 n n mmmn aaa aaa aaa 由于這個(gè)系數(shù)矩陣中含一個(gè)單位矩陣，只要以這個(gè)單位矩陣作為基， 1 (,) ssm PP

9、 就可以立即解除基變量值，因?yàn)橛?，由?1,) sii xb im0(1,) i bim 就是一個(gè)基可行解。 1 (0,0,)T m Xbb 當(dāng)線性規(guī)劃中約束條件為“”、“ ”時(shí)，化為標(biāo)準(zhǔn)形式后，一般約束條件的 系數(shù)矩陣中不包括有單位矩陣。這是為能方便地找出一個(gè)初始的基可行解，可添加人 工變量來(lái)人為地構(gòu)造一個(gè)單位矩陣作為基，稱作人工基。先在不等式左端減去一個(gè)大 于等于零的剩余變量（也稱為松弛變量）化為等式，然后再添加一個(gè)人工變量。 2.2 解線性規(guī)劃概述解線性規(guī)劃概述 兩階段法第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問(wèn)題，即 令目標(biāo)函數(shù)中其他變量的系數(shù)取 0，人工便靈的系數(shù)取某個(gè)

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

11、數(shù)中其他變量的系數(shù)取 0，人工便靈的系數(shù)取某個(gè)正的常數(shù)，（一般取 1），在保持原問(wèn)題約束 條件不變的情況下求這歌目標(biāo)函數(shù)極小化的解。顯然在第一階段中，當(dāng)人工變量取值為 0 的時(shí) 候，目標(biāo)函數(shù)值也為 0。這時(shí)候的最優(yōu)解就是原線性規(guī)劃問(wèn)題的一個(gè)可行解。如果第一階段求 解結(jié)果最優(yōu)解的目標(biāo)函數(shù)值不為 0，也即最優(yōu)解的基變量中含有人工基變量，表明原線性規(guī)劃 問(wèn)題無(wú)可行解。 兩階段法第一階段是求解第一個(gè) LP。首先我們可以知道，原 LP 的表達(dá)式為 1 min . . 0 n jj j zc x Axb st x 其可行域?yàn)?: 0 xx D xDD a 而我們需要一個(gè)輔助的 LP，其表達(dá)式為 1 min

12、 . . 0,0 m i i wa Axab st xa 其可行域?yàn)?:min0 0 x DDw 我們計(jì)算以上輔助 LP 有三種可能結(jié)果： 1)、最優(yōu)值，且人工變量皆為非基變量。從第一階段的最優(yōu)解中去掉人工變0w 量后即為原 LP 的一個(gè)基本可行解。作為原 LP 的一個(gè)初始基本可行解，再求原問(wèn)題， 從而進(jìn)入第二階段。 2)、最優(yōu)值，且存在人工變量皆為基變量，取值為。把某個(gè)非基變量與該0w0 人工變量進(jìn)行調(diào)換。 3)、最優(yōu)值，說(shuō)明至少有一個(gè)人工變量不為。原 LP 無(wú)可行解，不需要再0w0 教資 c 類 做第二階段計(jì)算。 兩階段法第一階段目的就是判斷原 LP 有無(wú)可行解，若有，則可得原 LP 的一

13、個(gè)初 始基本可行解，再對(duì)原 LP 進(jìn)行第二階段的計(jì)算。 2.4 兩階段法第二階段兩階段法第二階段 以第一階段求得最優(yōu)解作為初始基本可行解，再用第一階段求得最優(yōu)解時(shí)的約束 條件和原問(wèn)題的目標(biāo)函數(shù)進(jìn)行迭代，直到求出最優(yōu)解。 3 3、兩階段法求解引例、兩階段法求解引例 3.1、兩階段法計(jì)算步驟、兩階段法計(jì)算步驟 兩階段法具體計(jì)算步驟： 第一步：求出線性規(guī)劃的初始基可行解，列出初始單純形表。 第二步：進(jìn)行最優(yōu)性檢驗(yàn)。 第三步;從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解，列出新的單純 形表。 第四步：重復(fù)第二、三步一直到計(jì)算終止。 第五步：去除人工變量。根據(jù)求得初始基本可行解，求得最優(yōu)解。 其中

14、第三步具體方法如下： 1)、確定換入基變量。只要檢驗(yàn)數(shù)，對(duì)應(yīng)的變量就可作為換入基的變量，0 j j x 當(dāng)有一個(gè)以上檢驗(yàn)數(shù)大于零時(shí)，一般從中找出最大的一個(gè) k max0 kjj 其對(duì)應(yīng)變量作為換入基的變量（簡(jiǎn)稱換入變量）。 k x 2)、確定換出基的變量，確定 min0 il ik iklk bb a aa 教資 c 類 確定為換出基的變量（簡(jiǎn)稱出基變量）。元素決定了從一個(gè)基本可行解到另一個(gè) l x lk a 可行解的轉(zhuǎn)移去向，取名主元素。 3)、用換入變量替換基變量中的換出變量，得到一個(gè)新的基 k x 。對(duì)應(yīng)這個(gè)基可以找出一個(gè)新的基本可行解。并 1111 ( ,) lklmmm n PPP

15、PppP 可劃出一個(gè)新的單純形表。進(jìn)行如下計(jì)算: a、將主元素所在的 行數(shù)字除以主元素，即有l(wèi) lk a lj l llj lklk a b ba aa b、為使列變換成單位向量，將單純形表的第 行數(shù)字乘上，加到單 k Pl() lj lk a a 純形表第 行數(shù)字上，計(jì)入其相應(yīng)行。即有i () () l iiik lk lj ljljik lk b bbail b a aaail a c、計(jì)算單純形表中各檢驗(yàn)數(shù)，如下 1 11 1 1 () 11 () lm llliikkiik ii l lk m k iikkk i lklklk czcc acc a a c c acz aaa 1 11

16、11 11 () ()() lmmm lj jjjiijiijiikkiik ii lii l lk mm ljlj jiijkiikjjkk ii lklk a czcc ac ac acc a a aa cc acc aczcz aa 由上可看出，檢驗(yàn)數(shù)計(jì)算同樣因基變量后，其檢驗(yàn)數(shù)應(yīng)為零，故將單純形表 k x() kk cz 中第 行數(shù)字乘上加到該表的檢驗(yàn)數(shù)上，得新的變量的檢驗(yàn)數(shù)。l () () kk lk cz a 接下來(lái)在引例中用以上步驟實(shí)際求解 教資 c 類 3.2、例一：、例一： 用兩階段法求以下問(wèn)題最優(yōu)解 13 123 123 23 max3 4 21 . . 39 0(1,2,

17、3) j zxx xxx xxx st xx xj 首先第一階段是將此問(wèn)題化為標(biāo)準(zhǔn)形式，在約束條件中加入松弛變量 后得 4567 ,x x x x 67 1234 12356 237 min 4 21 . 39 0(1,7) j wxx xxxx xxxxx st xxx xj 先用單純形法解一階段問(wèn)題，迭代如下： 1 jjBjjBjj zcc B Pcc yc 1 jjBjjBjj zcc B Pcc yc 其中，時(shí)目標(biāo)函數(shù)中基變量的系數(shù)構(gòu)成的維行向量，是上表中的第列，是上 B c j yjb 表中的右端列。 求解過(guò)程如下單純形表 3-1 表 3-1 單純形表 j c 00000-1-1 B

18、 c 基 b1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x41211000 -1 6 x1-21-10-110 -1 7 x90310001 教資 c 類 jj cz -2400-100 0 4 x3 30211-10 0 2 x1-21-10-110 -1 7 x660403-31 jj cz 60403-40 0 4 x00001 1 2 1 2 1 2 0 2 x301 1 3 000 1 3 0 1 x110 2 3 0 1 2 1 2 1 6 jj cz 00000-1-1 所有判別級(jí)數(shù)，因此達(dá)到最優(yōu)解，在第一階段問(wèn)題最優(yōu)解中，人工變量0 jj cz 、都是非基變

19、量。因此我們可得到初始基可行解 6 x 7 x 12345 ,1,3,0,0,0 x x x x x 第二階段是將表 3-1 中的人工變量去除，目標(biāo)函數(shù)改為： 67 ,x x 12345 max3000zxxxxx 再?gòu)谋?3-1 最后一個(gè)表出發(fā)，繼續(xù)迭代，求解過(guò)程的單純形表如下表 3-2 表 3-2 單純形表 j c -30100 B c基 b1 x 2 x 3 x 4 x 5 x 04 x0 0001 1 2 02 x3 01 1 3 00 教資 c 類 -31 x1 10 2 3 0 1 2 jj cz 0030 3 2 04 x 00001 1 2 02 x 5 2 1 2 100 1

20、 4 13 x 3 2 3 2 010 3 4 jj cz 9 2 000 3 4 得到其最優(yōu)解，所以目標(biāo)函數(shù)最優(yōu)值 123 5 3 ,0, 2 2 x x x max 3 2 f 3.3、例二：、例二： 用兩階段法求解以下問(wèn)題 12 12 12 12 12 min23 11 4 24 336 . . 10 ,0 zxx xx xx st xx x x 首先第一階段是將此問(wèn)題化為標(biāo)準(zhǔn)形式，在約束條件中加入松弛變量后 3456 ,x x x x 得 12 123 1245 126 123456 min23 11 4 24 336 . . 10 ,0 zxx xxx xxxx st xxx x x

21、 x x x x 先用單純形法解一階段問(wèn)題，迭代如下 1 jjBjjBjj zcc B Pcc yc 1 jjBjjBjj zcc B Pcc yc 教資 c 類 其中，時(shí)目標(biāo)函數(shù)中基變量的系數(shù)構(gòu)成的維行向量，是上表中的第列，是上 B c j yjb 表中的右端列。 求解過(guò)程如下單純形表 3-3 表 3-3 單純形表 j c 000011 B c基 b1 x 2 x 3 x 4 x 5 x 6 x 03 x 4 1 2 1 4 1000 15 x 36130-110 16 x 101 1 0001 jj cz 240-100 03 x 3 2 1 4 0100 1 4 15 x 6-200-1

22、1-3 02 x 10110001 jj cz -20010-4 所有判別級(jí)數(shù)，但此時(shí)，說(shuō)明至少有一個(gè)人工變量不為 0，原問(wèn)題0 jj cz6w 無(wú)可行解，不需要進(jìn)入第二階段計(jì)算。 3.4、引例分析、引例分析 根據(jù)引例一和引例二的求解過(guò)程計(jì)算可知，第一階段使用單純形法可以得到一般 的最優(yōu)解，而使用兩階段法能在第二階段找到更精確更優(yōu)化的最優(yōu)解。 4 4、算法比較、算法比較 4.14.1 大大 M M 算法算法 教資 c 類 單純形法從一個(gè)初始可行基開始，要求標(biāo)準(zhǔn)型對(duì)應(yīng)的單純形表滿足兩個(gè)條件，其 一是中心部位具有階單位子塊，其二是右列元素非負(fù)。對(duì)于線性規(guī)劃問(wèn)題 m （4.1.1） 1 1 min

23、,1,2., . . 0,1,2., n jj j n ijji j j zc x a xb im st xjn 若，且對(duì)應(yīng)的廚師單純形表?xiàng)l件二滿足條件一不滿足，那么應(yīng)引入人工變量( )r Am ，構(gòu)造新的線性規(guī)劃問(wèn)題 12 , nnn m xxx （4.1.2） 11 1 1 min ,1,2., . . 0,1,2., ,1, nn m jjj jj n n ijjni j j zc xMx a xxb im st xjn nnm 其中，且為無(wú)限大的數(shù)，令，則相性規(guī)劃問(wèn)0M 12 ,1,1,1 TT nnn m yxxxE 題可表示為 （4.1.3） min . . ,0 TT zC xM

24、E y Axyb st x y 設(shè)是（4.1.3）的最優(yōu)解，若，則是（4.1.2）的最優(yōu)解，若，則(,)Txy 0y x 0y （4. 1.2）無(wú)可行解。反之，若是（4.1.2）的最優(yōu)解，則是（4.1.3）的最優(yōu)解。x(,0)Tx 故其求解方法步驟為 1）、經(jīng)初等行變換通常使，使右列元素非負(fù)。( 1) i r 2）、在中心部位人工的添加一個(gè)階單位子塊，即引入人工變量，得到新m 12 , m y yy 的約束方程組。 教資 c 類 3）、講目標(biāo)函數(shù)修改為，其中為足夠大的正常數(shù)，從而得到新 1 m j j zzMy 0M 的 LP 模型。 4）、用單純形法求解新的 LP 模型，試圖將變成自由變量，

25、最終有兩種 12 , m y yy 結(jié)果如下 a、設(shè)球的新的 LP 模型最優(yōu)解為，若，則(,)Txy 12 (,)0 m yyyy 是原 LP 問(wèn)題的最優(yōu)解。若，則原 LP 問(wèn)題 12 (,) n xxxx 12 (,)0 m yyyy 無(wú)最優(yōu)解。 b、新 LP 無(wú)界（無(wú)最優(yōu)解），則原 LP 問(wèn)題也無(wú)最優(yōu)解。 4.24.2 算法比較算法比較 如果線性規(guī)劃模型中約束條件系數(shù)矩陣中不存在單位向量組，解題時(shí)應(yīng)先加入人 工變量，人工地構(gòu)成一個(gè)單位向量組。而兩階段法和大 M 法都是可以控制人工變量取 值的方法，并且兩種方法都是在單純形法的基礎(chǔ)上進(jìn)一步求解最優(yōu)解的方法，兩種方 法的用法相似，各有優(yōu)缺點(diǎn)。通

26、過(guò)設(shè)置新的變量得到初始基本變量，并通過(guò)在目標(biāo)函 數(shù)中設(shè)置新變量的價(jià)格系數(shù)為 M 使得在優(yōu)化過(guò)程中，新變量的值優(yōu)化為 0 在計(jì)算機(jī)求 解過(guò)程中，由于計(jì)算機(jī)只能對(duì) M 設(shè)置有限大的數(shù)值，所以在計(jì)算過(guò)程中可能會(huì)產(chǎn)生誤 差，為了解決這個(gè)問(wèn)題，產(chǎn)生了兩階段法。所以大 M 法雖然簡(jiǎn)單直觀，在單純形表上 的計(jì)算步驟與普通單純形法相同，但是大 M 到底取值多大不能確定，M 取值過(guò)大也將 增加數(shù)值計(jì)算困難。 用大 M 法處理人工變量，用手工計(jì)算求解時(shí)不會(huì)碰到麻煩。但用電子計(jì)算機(jī)求解 時(shí)，對(duì) M 就只能在計(jì)算機(jī)內(nèi)輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字。如果線性規(guī)劃問(wèn)題中的參 數(shù)值與這個(gè)代表 M 的數(shù)相對(duì)比較接近，或遠(yuǎn)遠(yuǎn)小于這

27、個(gè)數(shù)字，由于計(jì)算機(jī)計(jì)算時(shí)取值 上的誤差，可能使計(jì)算結(jié)果發(fā)生錯(cuò)誤。而兩階段法通過(guò)對(duì)添加人工變量后的線性規(guī)劃 問(wèn)題分兩個(gè)階段來(lái)計(jì)算，從而可以克服這個(gè)困難。 4.34.3 特殊情況特殊情況 1）、無(wú)可行解：線性規(guī)劃最優(yōu)解中出現(xiàn)人工變量大于零的情況，則此線性規(guī)劃 教資 c 類 無(wú)可行解。 2）、無(wú)界解：在求目標(biāo)函數(shù)最大值等問(wèn)題中，在某次迭代的單純形表中，如果 存在這一個(gè)不滿足符號(hào)條件的檢驗(yàn)數(shù)，并且該列的系數(shù)向量的每個(gè)元素都小于或等于 令，則此線性規(guī)劃無(wú)界。 3）、無(wú)窮多最優(yōu)解:對(duì)于某個(gè)最優(yōu)的基本可行解，如果存在某個(gè)非基變量的檢驗(yàn) 數(shù)為零，則此線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。 4）、退化：在單純形法計(jì)算過(guò)程

28、中，基變量有事存在兩個(gè)以上相同的最小比值， 這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，稱之為退化。而退化就容易產(chǎn)生 循環(huán)迭代，為避免如此，應(yīng)遵守以下兩條原則： a、在所有不滿足符號(hào)條件的檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量中，選一個(gè)下標(biāo)最小的 作為調(diào)入變量。 b、若存在兩個(gè)以上的最小比值，選一個(gè)下表最小的作為調(diào)出變量。 5 5、總結(jié)、總結(jié) 5.15.1 總結(jié)概括總結(jié)概括 求解最優(yōu)問(wèn)題是一個(gè)艱難而具有挑戰(zhàn)性的過(guò)程，最優(yōu)化方法是近幾十年形成的一 門運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)的學(xué) 科，它涵蓋了無(wú)約束最優(yōu)化問(wèn)題、凸集與凸函數(shù)、等式約束最優(yōu)化問(wèn)題和不等式約束 最優(yōu)化問(wèn)題等知識(shí)點(diǎn)。通過(guò)本課程教學(xué)，使學(xué)生掌握最優(yōu)