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

單純形表的計(jì)算步驟

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

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

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

-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é)：基變量不含人工變量—為原問(wèn)題的最優(yōu)解?；兞亢腥斯ぷ兞?/p>

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

如果w<0,則原問(wèn)題沒(méi)有可行解;

如果w=0,則若人工變量全為非基變量,則得到了原問(wèn)題的基可行解.否則基可行解退化,繼續(xù)迭代就可以得到基可行解.第一階段第二階段以第一階段最優(yōu)基作為初始基可行解,繼續(xù)迭代。例用兩階段法解下列線性規(guī)劃解：做輔助線性規(guī)劃問(wèn)題：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時(shí)，這時(shí)候的最優(yōu)解是原線性規(guī)劃問(wèn)題的可行解，若目標(biāo)函數(shù)值不為0，說(shuō)明有不為0的人工變量，則原問(wèn)題無(wú)可行解?？偨Y(jié)再?gòu)纳媳碇械淖詈笠粋€(gè)表出發(fā)，繼續(xù)用單純形法計(jì)算。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

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

無(wú)可行解

解的幾種特殊情況

-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運(yùn)算到檢驗(yàn)數(shù)全負(fù)為止，基變量里仍含有非0的人工變量，所以原問(wèn)題無(wú)可行解。

無(wú)界解

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

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

CBXB

B-1bx1

x2

x3

x4

0x3

1-11100x4

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

退化

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

無(wú)窮多最優(yōu)解

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

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

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

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

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

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

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