第5節(jié) 單純形法的進(jìn)一步討論

第5節(jié)單純形法的進(jìn)一步討論

借助人工變量求初始的基本可行解單純形表與線性規(guī)劃問(wèn)題的討論改進(jìn)單純形法

1借助人工變量求初始的基本可行解

若約束方程組含有“≥”不等式，那么在化標(biāo)準(zhǔn)形時(shí)除了在方程式左端減去剩余變量，還必須在左端加上一個(gè)非負(fù)的人工變量。因?yàn)槿斯ぷ兞渴窃诩s束方程已為等式的基礎(chǔ)上，人為的加上去的一個(gè)新變量，因此加入人工變量后的約束方程組與原約束方程組是不等價(jià)的。加上人工變量以后，線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問(wèn)題的基本可行解。只有當(dāng)基本可行解中所有人工變量都為取零值的非基變量時(shí)，該基本可行解對(duì)原線性規(guī)劃才有意義。因?yàn)榇藭r(shí)只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規(guī)劃的一個(gè)基本可行解．而這正是我們引入人工變量的主要目的。2考慮線性規(guī)劃問(wèn)題：為了在約束方程組的系數(shù)矩陣中得到一個(gè)m階單位矩陣作為初始可行基，在每個(gè)約束方程組的左端加上一個(gè)人工變量

可得到：

3————————————————————————

添加了m個(gè)人工變量以后，在系數(shù)矩陣中得到一個(gè)m階單位矩陣，以該單位矩陣對(duì)應(yīng)的人工變量為基變量，即可得到一個(gè)初始的基本可行解這樣的基本可行解對(duì)原線性規(guī)劃沒(méi)有意義的。但是我們可以從X(0)出發(fā)進(jìn)行迭代，一旦所有的人工變量都從基變量迭代出來(lái)，變成只能取零值的非基變量，那么我們實(shí)際上已經(jīng)求得了原線性規(guī)劃問(wèn)題的一個(gè)初始的基本可行解。此時(shí)可以把所有人工變量剔除，開(kāi)始正式進(jìn)入求原線性規(guī)劃最優(yōu)解的過(guò)程。4大M法

大M法首先將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個(gè)單位矩陣I，那么已經(jīng)得到了一個(gè)初始可行基。否則在約束方程組的左邊加上若干個(gè)非負(fù)的人工變量，使人工變量對(duì)應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個(gè)單位矩陣。以單位矩陣為初始基，即可求得一個(gè)初始的基本可行解。為了求得原問(wèn)題的初始基本可行解，必須盡快通過(guò)迭代過(guò)程把人工變量從基變量中替換出來(lái)成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個(gè)絕對(duì)值很大的負(fù)系數(shù)-Ｍ。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。以后的計(jì)算與單純形表解法相同，Ｍ只需認(rèn)定是一個(gè)很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說(shuō)明原問(wèn)題無(wú)可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問(wèn)題的初始基本可行解。5例4、用大M法求解下面的線性規(guī)劃問(wèn)題:解：首先將原問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量，并在目標(biāo)函數(shù)中分別賦予-Ｍ

6-01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M001/23/20-1/2-M-3/2-M5/2Z001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50-12+2M-M-M000-3MZ3/101001003X50X1x2x3x4x5x6x7bXBCBθ-12000-M-MC701001003X22100110-12X4011-100102X2220-1101-11X40-01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50001/23/20-1/2-M-3/2-M5/2Z3/2/1/2001/21/21-1/2-1/23/2X50X1x2x3x4x5x6x7bXBCBθ-12000-M-MC最優(yōu)解最優(yōu)值8兩階段法

兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。兩階段法的步驟：求解一個(gè)輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化；約束條件為原問(wèn)題中引入人工變量后包含一個(gè)單位矩陣的標(biāo)準(zhǔn)型的約束條件。如果輔助線性規(guī)劃存在一個(gè)基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問(wèn)題已經(jīng)得了一個(gè)初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計(jì)算；否則說(shuō)明原問(wèn)題沒(méi)有可行解，可停止計(jì)算。求原問(wèn)題的最優(yōu)解。在第一階段已求得原問(wèn)題的一個(gè)初始基本可行解的基礎(chǔ)上，繼續(xù)用單純形法求原問(wèn)題的最優(yōu)解9例5、用兩階段法求解例4中的線性規(guī)劃問(wèn)題。解：首先將問(wèn)題化為標(biāo)準(zhǔn)型添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：由于輔助線性規(guī)劃的目標(biāo)函數(shù)是極小化，因此最優(yōu)解的判別準(zhǔn)則應(yīng)為：1001-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10--110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110W001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X500-2110003W3/101001003X50x1x2x3x4x5x6x7bXBCBθ0000011C輔助規(guī)劃所有檢驗(yàn)數(shù)：原問(wèn)題已得一個(gè)初始基本可行解，11由上表可知，通過(guò)若干次旋轉(zhuǎn)變換，原問(wèn)題的約束方程組已變換成包含一個(gè)單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問(wèn)題的目標(biāo)函數(shù)，可繼續(xù)利用單純形表求解。12-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020001/23/205/2Z1/2/1/2-3/2/1/210-1/21/2001-1/2-1/20001/21/211/23/23/2X1X2X5-120x1x2x3x4x5

bXBCBθ-12000C可得最優(yōu)解，目標(biāo)函數(shù)值maxZ=6，與用大M法的結(jié)果完全相同。13單純形表與線性規(guī)劃問(wèn)題的討論

無(wú)可行解

通過(guò)大Ｍ法或兩階段法求初始的基本可行解。但是如果在大Ｍ法的最優(yōu)單純形表的基變量中仍含有人工變量，或者兩階段法的輔助線性規(guī)劃的目標(biāo)函數(shù)的極小值大于零，那么該線性規(guī)劃就不存在可行解。人工變量的值不能取零，說(shuō)明了原線性規(guī)劃的數(shù)學(xué)模型的約束條件出現(xiàn)了相互矛盾的約束方程。此時(shí)線性規(guī)劃問(wèn)題的可行域?yàn)榭占?4例6、求解下列線性規(guī)劃問(wèn)題解：首先將問(wèn)題化為標(biāo)準(zhǔn)型令，則

故引入人工變量，并利用大M法求解15C

-3-2-1000-M-M

CB

XB

b

x1x2x3x4x5x6x7x8

θ

0-M-M

x4x7x8

643

1111000010-10-101001-100-101

6/1-3/1

Z’

-7M

-6-4M

-15-M

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

0-M-2

x4x7x2

343

1021010-110-10-101001-100-101

3/14/1-

Z’

Z’

-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ōu)單純形表中，所有非基變量檢驗(yàn)數(shù)都小于零，但在該表中人工變量x7=1為基變量，所以原線性規(guī)劃不存在可行解。16無(wú)最優(yōu)解

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

判別方法：無(wú)最優(yōu)解判別定理在求解極大化的線性規(guī)劃問(wèn)題過(guò)程中，若某單純形表的檢驗(yàn)行存在某個(gè)大于零的檢驗(yàn)數(shù)，但是該檢驗(yàn)數(shù)所對(duì)應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則該線性規(guī)劃問(wèn)題無(wú)最優(yōu)解，可以可以17例7、試用單純形法求解下列線性規(guī)劃問(wèn)題：解：引入松弛變量x3,x4化為標(biāo)準(zhǔn)型C2200θ

CXB

B

x1

x2

x3

x4

0X3

1-11100X4

2-1/2101Z02200因但所以原問(wèn)題無(wú)最優(yōu)解18

退化解

當(dāng)線性規(guī)劃問(wèn)題的基本可行解中有一個(gè)或多個(gè)基變量取零值時(shí)，稱(chēng)此基本可行解為退化解。產(chǎn)生的原因：在單純形法計(jì)算中用最小比值原則確定換出變量時(shí)，有時(shí)存在兩個(gè)或兩個(gè)以上相同的最小比值θ，那么在下次迭代中就會(huì)出現(xiàn)一個(gè)甚至多個(gè)基變量等于零。遇到的問(wèn)題：當(dāng)某個(gè)基變量為零，且下次迭代以該基變量作為換出變量時(shí)，目標(biāo)函數(shù)并不能因此得到任何改變（由旋轉(zhuǎn)變換性質(zhì)可知，任何一個(gè)換入變量只能仍取零值，其它基變量的取值保持不變）。通過(guò)基變換以后的前后兩個(gè)退化的基本可行解的坐標(biāo)形式完全相同。從幾何角度來(lái)解釋?zhuān)@兩個(gè)退化的基本可行解對(duì)應(yīng)線性規(guī)劃可行域的同一個(gè)頂點(diǎn)，解決的辦法：最小比值原則計(jì)算時(shí)存在兩個(gè)及其以上相同的最小比值時(shí)，選取下標(biāo)最大的基變量為換出變量，按此方法進(jìn)行迭代一定能避免循環(huán)現(xiàn)象的產(chǎn)生（攝動(dòng)法原理）。19例8、求解下述線性規(guī)劃問(wèn)題：解：引入松弛變量化標(biāo)準(zhǔn)型20000-242-8030Z-5-60-420-805Z10001001x3

212060-2411x1

3321300-803x5

00-30-425-800Z11001001x7

00106-1-2410x1

30-1130-3-800x5

0-11001001x7

000106-1-2410x6

0000136-4-3210x5

0x7

x6

x5

x4

x3

x2

x1

b

XB

CB

000-242-803C

θ

第一次迭代中使用了攝動(dòng)法原理，選擇下標(biāo)為6的基變量x6離基?？傻米顑?yōu)解，目標(biāo)函數(shù)值maxZ=５，21無(wú)窮多最優(yōu)解

無(wú)窮多最優(yōu)解判別原理：若線性規(guī)劃問(wèn)題某個(gè)基本可行解所有的非基變量檢驗(yàn)數(shù)都小于等于零，但其中存在一個(gè)檢驗(yàn)數(shù)等于零，那么該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。例３：最優(yōu)表：非基變量檢驗(yàn)數(shù)，

所以有無(wú)窮多最優(yōu)解。最優(yōu)解集為可行域兩個(gè)頂點(diǎn)的凸組合：C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-122改進(jìn)單純形法的特點(diǎn)

利用單純形表求解線性規(guī)劃時(shí)，每一次迭代都把整個(gè)單純形表計(jì)算一遍，事實(shí)上我們關(guān)心的只是以下一些數(shù)據(jù)：基本可行解，其相應(yīng)的目標(biāo)函數(shù)值，非基變量檢驗(yàn)數(shù)，及其換入變量，

設(shè)主元列元素，及其換出變量，設(shè)

利用它們可得到一組新的基變量以及新的可行基Ｂ1。改進(jìn)單純形法為基變量下標(biāo)為非基變量下標(biāo)23

對(duì)任一基本可行解Ｘ，只要知道，上述關(guān)鍵數(shù)據(jù)都可以從線性規(guī)劃問(wèn)題的初始數(shù)據(jù)直接計(jì)算出來(lái)。因此如何計(jì)算基本可行解Ｘ對(duì)應(yīng)的可行基Ｂ的逆陣成為改進(jìn)單純形法的關(guān)鍵．改進(jìn)單純形法推導(dǎo)出從可行基Ｂ變換到Ｂ1時(shí)，到的變換公式。當(dāng)初始可行基為單位矩陣Ι時(shí)，變換公式將更具有優(yōu)越性，因?yàn)檫@樣可以避免矩陣求逆的麻煩以下推導(dǎo)從到的變換公式：24假設(shè)當(dāng)前基，

基變換中用非基變量取代基變量可得新基前后二個(gè)基相比僅相差一列，且比較以上二式，可得其中表示第個(gè)元素為1，其它元素均為零的單位列向量，為主元列元素。25假設(shè)，則第列（換出變量對(duì)應(yīng)列）第行所以由主元素26改進(jìn)單純形法的步驟（1）根據(jù)給出的線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型，確定初始基變量和初始可行基Ｂ。求初始可行基B的逆陣Ｂ-1，得初始基本可行解。

（2）計(jì)算單純形乘子，得目標(biāo)函數(shù)當(dāng)前值（3）

計(jì)算非基變量檢驗(yàn)數(shù)，若σN≤0，則當(dāng)前解已是最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)下一步。（4）

根據(jù)，確定非基變量為換入變量，計(jì)算,若≤0，則問(wèn)題沒(méi)有有限最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)下一步。27（5）根據(jù)，確定基變量

為換出變量。（6）用替代得新基Ｂ1，由變換公式計(jì)算新基的逆陣Ｂ1-1，求出新的基本可行解其