圖解法和單純形法求解線性規(guī)劃問題(共11頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上圖解法和單純形法求解以下線性規(guī)劃問題1.1 圖解法解線性規(guī)劃問題只含兩個(gè)變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解，步驟如下：(1) 以變量x1為橫坐標(biāo)軸，x2為縱坐標(biāo)軸，適當(dāng)選取單位坐標(biāo)長(zhǎng)度建立平面坐標(biāo)直角坐標(biāo)系。由變量的非負(fù)性約束性可知，滿足該約束條件的解均在第一象限內(nèi)。(2) 圖示約束條件，找出可行域（所有約束條件共同構(gòu)成的圖形）。(3) 畫出目標(biāo)函數(shù)等值線，并確定函數(shù)增大（或減小）的方向。(4) 可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的點(diǎn)即為最優(yōu)解。然而，由于圖解法不適用于求解大規(guī)模的線性規(guī)劃問題，其實(shí)用意義不大。1.2 單純形法解線性規(guī)劃問題它的理論根據(jù)是：線性

2、規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。如果問題無(wú)最優(yōu)解也可用此法判別。單純形法的一般解題步驟可歸納如下：把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。若基本可行解不存在，即約束條件有矛盾，則問題無(wú)解。若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)

3、性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問題的最優(yōu)解。若迭代過程中發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無(wú)界，則終止迭代。1.3 線性規(guī)劃問題的標(biāo)準(zhǔn)化使用單純形法求解線性規(guī)劃時(shí)，首先要化問題為標(biāo)準(zhǔn)形式所謂標(biāo)準(zhǔn)形式是指下列形式：當(dāng)實(shí)際模型非標(biāo)準(zhǔn)形式時(shí)，可以通過以下變換化為標(biāo)準(zhǔn)形式：當(dāng)目標(biāo)函數(shù)為時(shí)，可令Z=-Z，而將其寫成為求得最終解時(shí)，再求逆變換Z=-Z即可。當(dāng)s·t·中存在形式的約束條件時(shí)，可引進(jìn)變量便寫原條件成為其中的xn+1稱為松馳變量，其作用是化不等式約束為等式

4、約束。同理，若該約束不是用“”號(hào)連接，而是用“”連接，則可引進(jìn)松馳變量使原條件寫成2 單純形法2.1 單純形法的基本原理單純形法迭代原理：（1） 確定初始可行解 當(dāng)線性規(guī)劃問題的所有約束條件均為號(hào)時(shí)，松弛變量對(duì)應(yīng)的系數(shù)矩陣即為單位矩陣，以松弛變量為基變量可確定基可行解。 對(duì)約束條件含號(hào)或=號(hào)時(shí)，可構(gòu)造人工基，人為產(chǎn)生一個(gè)m×m單位矩陣用大M法或兩階段法獲得初始基可行解。（2） 最優(yōu)性檢驗(yàn)與解的判別（目標(biāo)函數(shù)極大型） 當(dāng)所有變量對(duì)應(yīng)的檢驗(yàn)數(shù)均非正時(shí)，現(xiàn)有的基可行解即為最優(yōu)解。若存在某個(gè)非基變量的檢驗(yàn)數(shù)為零時(shí)，線性規(guī)劃問題有無(wú)窮多最優(yōu)解；當(dāng)所有非基變量的檢驗(yàn)數(shù)均嚴(yán)格小于零時(shí)，線性規(guī)劃問題

5、具有唯一最優(yōu)解。 若存在某個(gè)非基變量的檢驗(yàn)數(shù)大于零，而該非基變量對(duì)應(yīng)的系數(shù)均非正，則該線性規(guī)劃問題具有無(wú)界解（無(wú)最優(yōu)解）。 當(dāng)存在某些非基變量的檢驗(yàn)數(shù)大于零，需要找一個(gè)新的基可行解，基要進(jìn)行基變換。2.1 確定初始可行解確定初始的基本可行解等價(jià)于確定初始的可行基，一旦初始的可行基確定了，那么對(duì)應(yīng)的初始基本可行解也就唯一確定，為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣中前m個(gè)系數(shù)列向量恰好構(gòu)成一個(gè)可行基，即=（），其中=（1，2，m）為基變量x1，x2，xm的系數(shù)列向量構(gòu)成的可行基，=(m+1，Pm+2， Pn)為非基變量xm+1，xm+2， xn的系數(shù)列向量構(gòu)成的矩陣。所以約束方程就可

6、以表示為用可行基的逆陣-1左乘等式兩端，再通過移項(xiàng)可推得：若令所有非基變量，則基變量由此可得初始的基本可行解2.2 最優(yōu)性檢驗(yàn)假如已求得一個(gè)基本可行解，將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值其中分別表示基變量和非基變量所對(duì)應(yīng)的價(jià)值系數(shù)子向量。要判定是否已經(jīng)達(dá)到最大值，只需將代入目標(biāo)函數(shù)，使目標(biāo)函數(shù)用非基變量表示，即： 其中稱為非基變量N的檢驗(yàn)向量，它的各個(gè)分量稱為檢驗(yàn)數(shù)。若N的每一個(gè)檢驗(yàn)數(shù)均小于等于0，即N0，那么現(xiàn)在的基本可行解就是最優(yōu)解。2.3 解的判別定理1：最優(yōu)解判別定理對(duì)于線性規(guī)劃問題，若某個(gè)基本可行解所對(duì)應(yīng)的檢驗(yàn)向量，則這個(gè)基本可行解就是最優(yōu)解。定理2：無(wú)窮多最優(yōu)解判

7、別定理 若是一個(gè)基本可行解，所對(duì)應(yīng)的檢驗(yàn)向量，其中存在一個(gè)檢驗(yàn)數(shù)m+k=0，則線性規(guī)劃問題有無(wú)窮多最優(yōu)解。定理3：無(wú)最優(yōu)解判別定理若是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)，但是，則該線性規(guī)劃問題無(wú)最優(yōu)解。2.4 基本可行解的改進(jìn)如果現(xiàn)行的基本可行解不是最優(yōu)解，即在檢驗(yàn)向量中存在正的檢驗(yàn)數(shù)，則需在原基本可行解的基礎(chǔ)上尋找一個(gè)新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：（1）先從檢驗(yàn)數(shù)為正的非基變量中確定一個(gè)換入變量，使它從非基變量變成基變量（將它的值從零增至正值）。（2）再?gòu)脑瓉?lái)的基變量中確定一個(gè)換出變量，使它從基變量變成非基變量（將它的值從正值減至零）。由此可得一個(gè)新的基本可行解，由可知，這樣

8、的變換一定能使目標(biāo)函數(shù)值有所增加。2.4.1 換入變量的確定-最大增加原則把基檢驗(yàn)數(shù)大于0的非基變量定為入基變量。若有兩個(gè)以上的j0，則選其中的j最大者的非基變量為入基變量。從最優(yōu)解判別定理知道，當(dāng)某個(gè)j0時(shí)，非基變量xj變?yōu)榛兞坎蝗×阒悼梢允鼓繕?biāo)函數(shù)值增大，故我們要選基檢驗(yàn)數(shù)大于0的非基變量換到基變量中去（稱之為入基變量）。若有兩個(gè)以上的j0，則為了使目標(biāo)函數(shù)增加得更大些，一般選其中的j最大者的非基變量為入基變量。2.4.2 換出變量的確定-最小比值原則把已確定的入基變量在各約束方程中的正的系數(shù)除以其所在約束方程中的常數(shù)項(xiàng)的值，把其中最小比值所在的約束方程中的原基變量確定為出基變量。即若則

9、應(yīng)令xl出基。其中bi是目前解的基變量取值，aik是進(jìn)基變量xk所在列的各個(gè)系數(shù)分量，要求僅對(duì)正分量做比，（這由前述作法可知，若aik0，則對(duì)應(yīng)的xi不會(huì)因xk的增加減值而成為出基變量）。2.5 表格單純形法在單純形法的求解過程中，有下列重要指標(biāo)：（1）每一個(gè)基本可行解的檢驗(yàn)向量，根據(jù)檢驗(yàn)向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過檢驗(yàn)向量確定合適的換入變量。（2）每一個(gè)基本可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值 ，通過目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地增加，直至求得最優(yōu)目標(biāo)函數(shù)為止。 在單純形法求解過程中，每一個(gè)基本可行解都以某個(gè)經(jīng)過初等行變換的約束方程組中

10、的單位矩陣為可行基。當(dāng)=時(shí)，-1=，易知：，可將這些重要結(jié)論的計(jì)算設(shè)計(jì)成如下一個(gè)簡(jiǎn)單的表格，即單純形表來(lái)完成： CCBCNCBXBbX1 X2 XmXm+1 Xm+2 XnC1C2CmX1X2Xmb1b2bmIN12mZCBb0C-CBN2.6 大M法大M法首先將線性規(guī)劃問題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換

11、出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。以后的計(jì)算與單純形表解法相同，只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解。2.7 單純形法程序設(shè)計(jì)完整的單純形法的計(jì)算程序設(shè)計(jì)框圖如下所示：圖1 單純形法程序框圖3 應(yīng)用實(shí)例3.1 有最優(yōu)解問題例1 求如下方程的最優(yōu)解在命令行輸入：>> A=1 2 2 1 0;3 4 1 0 1;b=8;7;c=5 2 3 -1 1;>>

12、simplemethod(A,b,c);即可得出結(jié)果：X = 1.2000 0 3.4000 0 0 0 0最大值為：z = 16.2000迭代次數(shù)：i = 4程序結(jié)果與例題結(jié)果一致。例2 求解下述線性規(guī)劃問題在命令窗口輸入：>> A=1 1;2 1;b=40;60;c=3 2;>> simplemethod(A,b,c);即可得到結(jié)果：已得到最優(yōu)解：X = 20 20 0 0最大值為：z = 100迭代次數(shù)：i = 4程序結(jié)果與例題結(jié)果一致。例3 利用大M法求解下述線性規(guī)劃問題在命令窗口輸入：>> A=1 1;-1 1;0 1;b=2;1;3;c=-1 2

13、;sign=1 1 -1;>> simplemethod(A,b,c,sign);結(jié)果如下：已得到最優(yōu)解：X = 0 3 1 2 0 0 0最大值為：z = 6迭代次數(shù)：i = 6與例題結(jié)果一致。3.2 無(wú)可行解問題通過大法或兩階段法求初始的基本可行解。但是如果在大法的最優(yōu)單純形表的基變量中仍含有人工變量，人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程，此時(shí)線性規(guī)劃問題也無(wú)最優(yōu)解。例4 利用大M法求解下述線性規(guī)劃問題在命令窗口輸入：>> A=1 1 1;1 0 -1;0 1 -1;b=6;4;3;c=-3 -2 -1;sign=-1

14、1 1;>> simplemethod(A,b,c,sign);結(jié)果輸出“此問題無(wú)可行解”。3.3 無(wú)最優(yōu)解問題無(wú)最優(yōu)解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達(dá)不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無(wú)窮大（或者無(wú)窮?。o(wú)最優(yōu)解也稱為有限最優(yōu)解，或無(wú)界解。判別方法：無(wú)最優(yōu)解判別定理在求解極大化的線性規(guī)劃問題過程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問題無(wú)最優(yōu)解。例5求解下述線性規(guī)劃問題在命令窗口輸入：>> A=1 -1;-3 2;b=1;6;c=1 1;>> simple