基于單純形法的線性規(guī)劃模型研究

基于單純形法的線性規(guī)劃模型研究

線性平面問題是在一定的約束條件下計算目標函數(shù)的最佳（最大或最?。┲档膯栴}。求解線性規(guī)劃問題有圖解法,單純形法,橢球法及投影尺度法。其中以單純性法最常用,應用范圍也更廣泛。一、可行解和實際效果函數(shù)的確定單純形法是從一個初始解開始,不斷地改進現(xiàn)有的解,直到所要求的目標函數(shù)值被滿足為止。即是進行反復的迭代,直到得到需要的最優(yōu)解。這即是單純形法的基本思想。它的主要步驟我們通過一個例子說明。例1:解線性規(guī)劃問題:x2≤3解:(1)先將線性規(guī)劃問題化為標準形式。須在約束方程中加入松弛變量x2,x3,x4,得到標準形式如下(2)選擇一個初始可行解。由約束方程組的系數(shù)矩陣,選擇x3,x4,x5為基變量,x1,x2為非基變量。將基變量由非基變量表示,同時令非基變量x1,x2為0,便得到一個基本可行解(0,0,4,3,8)T,此時目標函數(shù)值為z=0(3)檢驗是否是最有解。檢驗的方法是非基變量在目標函數(shù)中的系數(shù)是否有正值。本例求出的基本可行解(0,0,4,3,8)不是最優(yōu)解。因為從目標函數(shù)表達式2x1+5x2中可以看出,當可行解中非基變量x1=x2=0,目標函數(shù)值為0,但只要x1或x2之一取正值,則目標函數(shù)值應增加,所以它不是最優(yōu)解。從一般情況而言,當目標函數(shù)表達式中還存在正系數(shù)的非基變量時,就表示目標函數(shù)值還有可能增加,此時將非基變量與基變量進行對換,就可以使目標函數(shù)值繼續(xù)增加。對于本例,就是將x3,x4或x5之一置成0,而x1或x2之一的值可以取為大于0,目標函數(shù)值不再是0,而是大于0。欲置0的基變量被稱為離基變量。而允許目標函數(shù)中系數(shù)大于0非基變量被稱為進基變量。那么如何選擇進基與離基變量呢?(4)進基變量的選擇。進基變量的選擇方法是取非基變量在目標函數(shù)的正系數(shù)中的最大的數(shù)所對應的變量為進基變量。在目標函數(shù)方程中選取正系數(shù)最大的非基變量作為進基變量。非基變量的正系數(shù)意味著相應變量的增加,這種增加將使目標值增大,所以只有使具有正系數(shù)的非基變量進基才有可能使目標函數(shù)值得到改善。在本例中目標函數(shù)方程中x2的系數(shù)具有最大值5,因此,x2將進入下一個基本可行解的基。(5)離基變量的選擇。離基變量的選擇的原則是,求出每一個約束方程中的右端常數(shù)與進基變量在約束方程中的系數(shù)的比值,最小非負比值所在方程中的基變量應是離基變量。本例中考慮每一個約束方程右邊的常數(shù)與該方程中進基變量x2的系數(shù)的比值,找出最小非負比值,把這個方程中的基作為離基變量。本例記其中“-”表示進基變量約束條件的系數(shù)為0或為負數(shù)。下面求以x2,x3,x4為進基變量時的基本可行解。(6)轉(zhuǎn)軸計算。先選主元,令進基變量所在列為主元列,離基變量所在的行為主元行,主元行與主元列交叉位置的元素為主元。然后用高斯消元法進行消元運算,即將主元位置的數(shù)變?yōu)?,主元列中其余元素變?yōu)?。本例中x2進基,x4離基,所以第2行為主元行,第2列為主元列,其主元為第2列與第2行交叉的元素,將該位置的數(shù)變?yōu)?,該列的其余系數(shù)變?yōu)?。即可得到從而得到目標函數(shù)z=2x1-5x4+15。(7)確定新的基本可行解。由上一步得到的等價約束條件方程組和等價的目標函數(shù)式,可得到本例另一基本可行解(0,3,4,0,2)T。此時得到目標函數(shù)值z=15。(8)求出最優(yōu)解。經(jīng)過這一系列運算,我們從一個基本可行解(0,0,4,3,8)T達到另一基本可行解,目標函數(shù)值也從0增加到15。因此第二個基本可行解是改進的基本可行解。下面再從基本可行解(0,3,4,0,2)T出發(fā),尋找最優(yōu)解。仍須重復(4)——(7)的步驟,直至找到最優(yōu)解:目標函數(shù)值z=19。以上就是單純形法的基本思路及運算過程。這些運算可簡寫成矩陣,行列式的形式,這便是下面要介紹的求解一般線性規(guī)劃問題的單純形法。二、一般單純度法的原理1、約束方程的增廣矩陣的確定(1)先找出一個初始可行解。(2)進行最優(yōu)性檢驗。就是盡興迭代運算,首先應建立一個判別準則。如最優(yōu)解判別定理:若x(0)=(b1′,b2′,bm′,0,…,0)T為對應于基矩陣B的基本可行解,且對于一切j=m+1,m+2,…,n,有σ≤0,則x(0)為最優(yōu)解(3)進基變量(主元列)的確定。為使目標函數(shù)值增加得快,一般選σj大于0的非基變量中的最大者為進基變量。即σk=max[σjσj≥0],所對應的xk為進基變量。(4)離基變量(主元行)的確定。按最小比值原則或θ原則取約束方程組的右端項和進基變量的對應約束條件的比值的最小值所在行的基變量x1作為離基變量。(5)轉(zhuǎn)軸計算。假設(shè)約束方程組有x1,x2,…,xm個基變量,其系數(shù)列向量構(gòu)成一個m階單位矩陣是可行基,令非基變量xm+1,…,xk,…,xn為零,便可得一個基本可行解。若它不是最優(yōu)解,則要找另一個基本可行解。即可假定xk為進基變量,x1為離基變量,對主元αlk作轉(zhuǎn)軸運算,即以αlk為主元的增廣矩陣作Gauss-Jordan消元法。(6)重復上述過程,直至找到最優(yōu)解。三、基變量對應關(guān)系對于標準的線性規(guī)劃問題,用單純形表方法求解最優(yōu)解一般分為兩個步驟:1、找出基變量,確定初始基本可行解,列初始的單純形表。2、從初始單純形表開始,逐步求出最優(yōu)解。(1)基變量對應的列經(jīng)過適當?shù)奈恢米儞Q后能變成一個單位矩陣。(2)在檢驗數(shù)這一行中,對應的基變量的檢驗數(shù)要全為0。(3)表格中常數(shù)b這一列(除去最后一行)的元素應全為非負數(shù)。如果上述3個條件都被滿足,則所得到的表格就是問題的初始單純形表。以下通過例1說明單純形法求解最優(yōu)解。(方法同三中所述各步)解:(1)列初始單純形表(2)利用單純形表求最優(yōu)解:列第二張單純形表從上表中可看到,得到一組新的基本可行解x(2)=(2,3,2,0,2)T,此時z=19。在最后的檢驗數(shù)行中已無正值,說明已求出最優(yōu)解。四、關(guān)于單純度法的進一步討論1、線性規(guī)劃的最優(yōu)解只有當矩陣A中存在單位矩陣或約束條件為Ax≤b時,加上松馳變量生成單位矩陣,即Ax+Ixs=b。如果約束條件非上述兩種情況,又將如何處理呢?有兩種方法處理:一——大法;二——兩階段法。所謂大M法,就是在確定離基變量時,即如何是基變量xa=0,就是采用懲罰的方法:在xa的前面乘上一個很大的數(shù)M,一旦xa的某個分量大于0,目標函數(shù)值就會下降。這樣就得到一個與M有關(guān)的問題,簡記為P(M),即記原線性規(guī)劃問題為P,相應的大M問題為P(M)。設(shè)x=0,xa=b是P(M)的一個基本可行解,從基本可行解出發(fā),對P(M)求解,分以下情況進行討論。(1)P(M)有最優(yōu)解,其解為(x*,xa*,且xa*=0,則x*是P的最優(yōu)解。若x是p的可行解,則(x,0)是P(M)的可行解,因此有cTx-0≤cTx*-0,所以x*是P的最優(yōu)解。(2)P(M)有最優(yōu)解,其解為(x*,xa*),且xa*≠0(某些分量大于0),則p無可行解。若p存在可行解x,則(x.0)是P(M)的可行解,則有cTx*-MeTxa*≥cTx,這與M可以充分大矛盾。(3)P(M)無有限最優(yōu)解。若存在并且σk>0,B-1Pk≤0,并且人工變量xa*≠0,則P無有限最優(yōu)解。(4)P(M)無有限最優(yōu)解。若存在σk>0,B-1Pk≤0并且人工變量xa*≠0(某些分量大于0),則P無可行解。下面以(2)為例,說明大M法的迭代過程。例2:用大M法求解線性規(guī)劃問題列出單純形表,并進行迭代,具體迭代過程如下表所示:從表中的檢驗數(shù)可看出:檢驗數(shù)已符合最優(yōu)解的要求,得到唯一最優(yōu)解x=(0,2,0,0,4)T,最優(yōu)解為4-4M。但現(xiàn)在的最優(yōu)解包含人工變量,說明該解對于原問題而言是不可行的。因此原問題無解。2、兩階段法算法用大M法手工計算時很實用。但用計算機求解時,對M就要附一個機器最大字長的數(shù),因此在迭代過程中很容易溢出。有可能使計算結(jié)果產(chǎn)生錯誤。為了解決這個問題,可以對增加人工變量后的規(guī)劃問題分兩個階段來計算,稱為兩階段法。下面通過例子來說明兩階段法的算法。例3:解線性規(guī)劃問題解:第一階段要增加新的人工變量x6,x7,x8,所得輔助問題為由原問題及輔助問題作單純形表:將表中第一行,第二行,第三行加到關(guān)于g的檢驗行中,使基變量的x6,x7,x8檢驗數(shù)為0,得到輔助問題的第一張單純形表:按單純形法迭代,得關(guān)于目標函數(shù)g的檢驗數(shù)都是負數(shù),所以輔助線性規(guī)劃問題的最優(yōu)解是其最優(yōu)解,所以原問題無解。從迭代過程可以發(fā)現(xiàn),無論是大M法還是兩階段法,目的都是盡快地使人工變量離基,從而得到原問題的初始基本可行解,再由此進行迭代,得到原問題的最優(yōu)解。五、線性規(guī)劃問題的算法需要改良單純形法是解線性規(guī)劃問題的一種有效的方法,它需要一個已知的基本可行解,并需把原始線性規(guī)劃問題化為標準式,而在一般情況下線性規(guī)劃問題并無明顯的基本可行解,則需增加人工變量以獲得基本可行解,這樣可能增加計算量,因而需要改進算法;同時,實際生活中的線性規(guī)劃問題規(guī)模較大,即變量個數(shù)和約束條件都多,當用計算機進行計算時會占據(jù)大量的內(nèi)存空間,在迭代過程中,實際上有很多計算是多余的,當?shù)螖?shù)增多時,累計誤差就會增加,進而會影響計算精度。針對這一問題,算法也需改進。因此,單純形法解線性規(guī)劃問題的算法仍需更進一步的探究與改良,這將對解決線性規(guī)劃問題非常有意義。其中,