第二節(jié)單純形法329

單純形表的計算步驟

①將線性規(guī)劃數(shù)學(xué)模型化成標(biāo)準(zhǔn)型②構(gòu)造初始可行基-找單位陣③列初始單純形表④計算檢驗數(shù)，進行最優(yōu)性檢驗⑤基變換：選擇正檢驗數(shù)大的對應(yīng)變量進基，選最小的檢驗比θ對應(yīng)的行變量出基。一進一出完成基變換。

⑥選擇主元，以主元行為中心進行迭代運算（初等行變換）⑦重復(fù)④、⑤、⑥，直至得到最優(yōu)解

單純形法的進一步討論人工變量法：前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。例用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)型系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。故添加人工變量x6,x7，得到人工變量單純形法數(shù)學(xué)模型：像這樣，為了構(gòu)造初始可行基得到初始基可行解，把人工變量強行的加到原來的約束條件中，由于約束條件在添加人工變量前已是等式，因此在最優(yōu)解中人工變量取值必須為0。為此令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的負值，用-M表示。這個方法稱為大M法，M叫罰因子。其中：M是一個很大的抽象的數(shù)，可以理解為它是足夠大的一個正數(shù)，再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。

-431-1010-1201002-2[1]0001410104513-2M

2+M

-1+2M

–M000-6[5]0-101-1-33001002-2100015-6M

5M

0

-M0003/58/3—4101380141001410-6/510-1/503/5003/51-2/501-2/505000031/3——3/531/511/53/531/531/519/31331/30101210015/300102/3000-5-25/3總結(jié)：基變量不含人工變量—為原問題的最優(yōu)解。基變量含有人工變量

(1)若人工變量大于0，則原問題無可行解。(2)若人工變量等于0，則將人工變量作為入基變量繼續(xù)迭代，可將人工變量換出基。總結(jié)兩階段法：如果線性規(guī)劃問題中的aij、bi或cj等參數(shù)值與這個代表M的數(shù)相對比較接近，或遠遠小于這個數(shù)字，由于計算機計算時取值上的誤差，有可能使計算結(jié)果發(fā)生錯誤。為了克服這個困難，可以對添加人工變量后的線性規(guī)劃問題分兩個階段來計算，稱兩階段法。第一階段第一階段最優(yōu)解中:

如果w<0,則原問題沒有可行解;

如果w=0,則若人工變量全為非基變量,則得到了原問題的基可行解.否則基可行解退化,繼續(xù)迭代就可以得到基可行解.第一階段第二階段以第一階段最優(yōu)基作為初始基可行解,繼續(xù)迭代。例用兩階段法解下列線性規(guī)劃解：做輔助線性規(guī)劃問題：00000-1-1CBXBB-1bx1x2x3x4x5x6x7θ-1x64-431-101040x5101-1201005-1x712-2[1]00011-212-1000-1x63-6[5]0-101-13/50x58-330010-28/30x312-210001—-650-100-20x23/5-6/510-1/501/5-1/50x531/53/5003/51-3/5-7/50x311/5-2/501-2/502/53/500000-1-1總結(jié)：在第一階段，只有當(dāng)人工變量取值為0，目標(biāo)函數(shù)值才為0時，這時候的最優(yōu)解是原線性規(guī)劃問題的可行解，若目標(biāo)函數(shù)值不為0，說明有不為0的人工變量，則原問題無可行解。總結(jié)再從上表中的最后一個表出發(fā)，繼續(xù)用單純形法計算。32-100CBXBB-1bx1x2x3x4x5θ2x23/5－6/510－1/50—0x531/53/5003/5131/3-1x311/5－2/501－2/50—500002x213010123x131/310015/3-1x319/300112/3000-5-25/3

通過大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極大值小于零，則該線性規(guī)劃問題就不存在可行解。

無可行解

解的幾種特殊情況

-3-2-1000-M-M

CB

XB

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-10100[1]-100-101

6/1-3/1

-3+M-2+M-1-2M0-M-M00

0-M-2

x4x7x2

343

[1]021010-110-10-101001-100-101

3/14/1-

-3+M0-3-M0-M-202-M

-3-M-2

x1x7x2

313

1021010-100-3-1-1-11101-100-101

003-3M3-M-M1-M0-1運算到檢驗數(shù)全負為止，基變量里仍含有非0的人工變量，所以原問題無可行解。

無界解

無界解也稱無最優(yōu)解，無界解與無可行解時兩個不同的概念?！餆o可行解是指原規(guī)劃不存在可行解，從幾何的角度解釋是指線性規(guī)劃問題的可行域為空集；★無界解則是指線性規(guī)劃問題存在可行解，但是可行解的目標(biāo)函數(shù)達不到最優(yōu)值，即目標(biāo)函數(shù)在可行域內(nèi)可以趨于無窮大（或者無窮?。o界解判別方法：

在求解極大化的線性規(guī)劃問題過程中，若某單純形表的非基變量的檢驗數(shù)大于0，但是該非基變量的系數(shù)列都為負數(shù)或零，則該線性規(guī)劃問題為無界解。例用單純形法求解下列LP問題2200θ

CBXB

B-1bx1

x2

x3

x4

0x3

1-11100x4

2-1/21012200因但所以原問題無界解。為什么呢？顯然這是線性規(guī)劃問題的可行解，此時目標(biāo)函數(shù)值當(dāng)M無限增大，目標(biāo)函數(shù)值也無限增大。因此此線性規(guī)劃問題有無界解。

退化

即計算出的θ（用于確定換出變量）存在有兩個以上相同的最小比值，會造成下一次迭代中由一個或幾個基變量等于零，這就是退化（會產(chǎn)生退化解）。退化會出現(xiàn)循環(huán)。但是一般情況下還是能夠把最優(yōu)解找出來。但不是所有的退化情況都能得到最優(yōu)解，也就是出現(xiàn)了死循環(huán)。為避免出現(xiàn)死循環(huán)，勃蘭特(Bland)提出一個簡便有效的規(guī)則（攝動法原理）：⑴當(dāng)存在多個時，選下標(biāo)最小的非基變量為換入變量；(2)當(dāng)θ值出現(xiàn)兩個以上相同的最小值時，選下標(biāo)最小的基變量為換出變量。這樣就避免了死循環(huán)。平時仍然用原來的方法做，只有發(fā)現(xiàn)出現(xiàn)死循環(huán)，才用這種辦法。

無窮多最優(yōu)解

若線性規(guī)劃問題某個非基變量檢驗數(shù)等于零，那么該線性規(guī)劃問題有無窮多最優(yōu)解。例：用單純形法求解下面的線性規(guī)劃

例：用單純形法求解下面的線性規(guī)劃

直觀上有什么特點？——目標(biāo)與某約束斜率相同會出現(xiàn)什么情況呢?zé)o窮多最優(yōu)解[]問題：本題的單純形終表檢驗數(shù)有何特點？

——非基變量x2的檢驗數(shù)等于零。無窮多最優(yōu)解0110[]0110[]011012.5000

解的判別：1）唯一最優(yōu)解判別：終表非基變量檢驗數(shù)均小于零。2）無窮多最優(yōu)解判別：終表某非基變量的檢驗數(shù)等于零。3）無界解判別：任意表有正檢驗數(shù)相應(yīng)的系數(shù)列均非正。4）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解存在某人工變量>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基可行解。關(guān)于單純形法的一點注：min型單純形表與max型的區(qū)別僅在于：檢驗數(shù)反號，即

-令負檢驗數(shù)中最小的對應(yīng)的變量進基；

-當(dāng)檢驗數(shù)均大于等于零時為最優(yōu)。建立模型個數(shù)取值右端項等式或不等式極大或極小新加變量系數(shù)兩個三個以上