管理運(yùn)籌學(xué)024兩階段法和大m法

1、一、單純形法原理及步驟一、單純形法原理及步驟二、用向量矩陣描述單純形法原理二、用向量矩陣描述單純形法原理三、單純形表三、單純形表四、兩階段法和大四、兩階段法和大m法法五、退化和循環(huán)五、退化和循環(huán)兩階段法和大兩階段法和大m m法法 當(dāng)不能通過轉(zhuǎn)化標(biāo)準(zhǔn)形式使約束方程系數(shù)矩陣中出現(xiàn)單位矩陣時(shí)，此時(shí)可以通過添加人工變量添加人工變量的方法，人為地使系數(shù)矩陣中出現(xiàn)一個(gè)單位矩陣，以它作為初始可行基。 例如例如: 設(shè)一線性規(guī)劃問題的約束為設(shè)一線性規(guī)劃問題的約束為 人工變量法有兩種方法：兩階段法和大兩階段法和大m法法。引進(jìn)變量x4,x5基中不包含單位矩陣，因此無法直接獲得初始可行基?；胁话瑔挝痪仃嚕虼藷o法

2、直接獲得初始可行基。兩階段法和大兩階段法和大m m法法x=(x1,x2,xn)t引進(jìn)人工變量xa=(xn+1,xn+2,xn+m)t基礎(chǔ)可行解x=0,xa=b非原問題的基礎(chǔ)可行解兩階段法和大兩階段法和大m m法法 人造解人造解 x0 不是原不是原問題的基本可行解。問題的基本可行解。 但若能通過單純形法的迭代步驟，將虛擬但若能通過單純形法的迭代步驟，將虛擬 的人工變量都替換出去，都變?yōu)榉腔兞浚吹娜斯ぷ兞慷继鎿Q出去，都變?yōu)榉腔兞浚?人工變量人工變量xn+ +1 = xn+ +2 = = xn+ +m = 0），則），則x0的的 前前n個(gè)分量就構(gòu)成原個(gè)分量就構(gòu)成原問題的一個(gè)基本可行解。問題的

3、一個(gè)基本可行解。 反之，若經(jīng)過迭代，不能把人工變量都變反之，若經(jīng)過迭代，不能把人工變量都變 為非基變量，則表明原為非基變量，則表明原問題問題無可行解無可行解。兩階段法和大兩階段法和大m m法法兩階段法兩階段法 階段階段 求解求解輔助問題輔助問題 構(gòu)造輔助問題 (1)若輔助問題的最優(yōu)基b全部在a中，即xa全部是非基變量（min z=0），則b為原問題的一個(gè)可行基。轉(zhuǎn)階段; ; (2)若輔助問題的最優(yōu)目標(biāo)函數(shù)值min z0，則至少有一個(gè)人工變量留在第一階段問題最優(yōu)解的基變量中，這時(shí)原問題無可行解。兩階段法和大兩階段法和大m m法法 階段階段 求解求解原問題原問題 以階段的最優(yōu)基b作為原問題的初始可

4、行基，求解原問題，得到原問題的最優(yōu)基和最優(yōu)解。例1 求解以下線性規(guī)劃問題。兩階段法和大兩階段法和大m m法法引進(jìn)松弛變量x3，x4，x50，得到增加人工變量x6，x70，構(gòu)造輔助問題，并進(jìn)入第一階段求解。兩階段法和大兩階段法和大m m法法標(biāo)準(zhǔn)化并寫出輔助問題的系數(shù)矩陣表：消去目標(biāo)函數(shù)中基變量x6、x7的系數(shù)，得到初始單純形表并進(jìn)行單純形變換：x2進(jìn)基21/11/ x7離基31/cj 0 0 0 0 0 1 1兩階段法和大兩階段法和大m m法法x1進(jìn)基12/ x6離基21/第一階段最優(yōu)，z=0cj 0 0 0 0 0 1 1- -兩階段法和大兩階段法和大m m法法在第一階段最優(yōu)單純形表換入原問題

5、的目標(biāo)函數(shù)，去掉人工變量x6、x7以及相應(yīng)的列，得到第二階段的系數(shù)矩陣表：消去基變量x1、x2在目標(biāo)函數(shù)中的系數(shù)，得到第二階段問題的單純形表：x4進(jìn)基1212/ x1離基3212/cj -1 2 0 0 0兩階段法和大兩階段法和大m m法法x3進(jìn)基 x5離基11/問題的最優(yōu)解為x=(x1,x2,x3,x4,x5)t=(0,3,1,2,0)t，max z=6 ，即min z=-6。cj -1 2 0 0 0兩階段法和大兩階段法和大m m法法oabcd012123x1x2 第一階段：在原問題的可行域外部進(jìn)行基變換，第一階段結(jié)束后進(jìn)入可行域 第二階段：從可行域內(nèi)部的的一個(gè)極點(diǎn)b（原問題的一個(gè)可行基）

6、開始，在可行域內(nèi)部進(jìn)行基變換基迭代路線基迭代路線兩階段法和大兩階段法和大m m法法 大大m法法的基本步驟如下： （1）引進(jìn)松弛變量，使約束條件成為等式； （2）如果約束條件的系數(shù)矩陣中不存在一個(gè)單位矩陣，則引進(jìn)人工變量； （3）在原目標(biāo)函數(shù)中，加上人工變量，每個(gè)人工變量的系數(shù)為一個(gè)充分大的正數(shù)m； （4）用單純形表求解以上問題，如果這個(gè)問題的最優(yōu)解中有人工變量是基變量，則原問題無可行解。如果最優(yōu)解中所有人工變量都離基，則得到原問題的最優(yōu)解。兩階段法和大兩階段法和大m m法法例2 求解以下線性規(guī)劃問題。引進(jìn)松弛變量x4，x5并標(biāo)準(zhǔn)化兩階段法和大兩階段法和大m m法法引進(jìn)人工變量x6，x70，在目

7、標(biāo)函數(shù)中增加人工變量列出系數(shù)矩陣表兩階段法和大兩階段法和大m m法法消去基變量x6、x7在目標(biāo)函數(shù)中的系數(shù)x1進(jìn)基 x6離基1 64/2 41/x3進(jìn)基 x7離基2 054/cj -2 -3 -1 0 0 -m -m兩階段法和大兩階段法和大m m法法已獲得最優(yōu)解，最優(yōu)解為：（x1，x2，x3，x4，x5，x6，x7）(8，0，16，0，0，0，0)，max z=-32，即min z=32cj -2 -3 -1 0 0 -m -m退化和循環(huán)退化和循環(huán)定義定義2-6 設(shè)b是線性規(guī)劃的一個(gè)可行基， xb=b-1b=(xb1,xb2,xbi,xbm)t 是這個(gè)基礎(chǔ)解中的基變量。如果其中至少有一個(gè)分量x

8、bi=0(i=1,2,m)，則稱此基礎(chǔ)可行解是退化的。 退化的結(jié)構(gòu)對單純形迭代會有不利的影響。當(dāng)?shù)M(jìn)入一個(gè)退化極點(diǎn)時(shí)，可能出現(xiàn)以下情況： (1)進(jìn)行進(jìn)基、離基變換后，雖然改變了基，但沒有改變極點(diǎn)，目標(biāo)函數(shù)當(dāng)然也不會改進(jìn)。進(jìn)行若干次基變換后，才脫離退化極點(diǎn)，進(jìn)入其他極點(diǎn)。這種情況會增加疊代次數(shù)，使單純形法收斂的速度減慢。 (2)在十分特殊的情況下，退化會出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形疊代將永遠(yuǎn)停留在同一極點(diǎn)上，因而無法求得最優(yōu)解。退化和循環(huán)退化和循環(huán) 對此，bland提出了一個(gè)避免循環(huán)的方法，在選擇進(jìn)基變量和離基變量時(shí)作了以下規(guī)定： （1）在選擇進(jìn)基變量時(shí)，在所有檢驗(yàn)數(shù)zj-cj0的非基變量中選取下標(biāo)最小的進(jìn)基； （2）當(dāng)有多個(gè)變量同時(shí)可作為離基變量時(shí)，選擇下標(biāo)最小的那個(gè)變量離基。這樣就可以避免出現(xiàn)循環(huán)。 當(dāng)然，用bland的方法，由于選取進(jìn)基變量