《管理運(yùn)籌學(xué)》02-4兩階段法和大m法ppt課件

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

2、X=(x1,x2,xn)T引進(jìn)人工變量Xa=(xn+1,xn+2,xn+m)T根底可行解X=0,Xa=b非原問題的根底可行解兩階段法和大兩階段法和大M M法法為非基變量，那么闡明原為非基變量，那么闡明原LP問題無可行解。問題無可行解。兩階段法和大兩階段法和大M M法法兩階段法兩階段法 階段階段 求解輔助問題求解輔助問題 構(gòu)造輔助問題 (1)假設(shè)輔助問題的最優(yōu)基B全部在A中，即Xa全部是非基變量min z=0，那么B為原問題的一個(gè)可行基。轉(zhuǎn)階段; (2)假設(shè)輔助問題的最優(yōu)目的函數(shù)值min z0，那么至少有一個(gè)人工變量留在第一階段問題最優(yōu)解的基變量中，這時(shí)原問題無可行解。兩階段法和大兩階段法和大M

3、 M法法 階段階段 求解原問題求解原問題 以階段以階段的最優(yōu)基的最優(yōu)基B B作為原問題的初始可作為原問題的初始可行基，求解原問題，得到原問題的最優(yōu)基和最優(yōu)行基，求解原問題，得到原問題的最優(yōu)基和最優(yōu)解。解。例1 求解以下線性規(guī)劃問題。兩階段法和大兩階段法和大M M法法引進(jìn)松弛變量x3，x4，x50，得到添加人工變量x6，x70，構(gòu)造輔助問題，并進(jìn)入第一階段求解。兩階段法和大兩階段法和大M M法法規(guī)范化并寫出輔助問題的系數(shù)矩陣表：消去目的函數(shù)中基變量x6、x7的系數(shù)，得到初始單純形表并進(jìn)展單純形變換：x2進(jìn)基21/11/ X7離基31/Cj 0 0 0 0 0 1 1兩階段法和大兩階段法和大M M

4、法法x1進(jìn)基12/ X6離基21/第一階段最優(yōu)，z=0Cj 0 0 0 0 0 1 1- -兩階段法和大兩階段法和大M M法法在第一階段最優(yōu)單純形表換入原問題的目的函數(shù)，去掉人工變量x6、x7以及相應(yīng)的列，得到第二階段的系數(shù)矩陣表：消去基變量x1、x2在目的函數(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法法

5、OABCD012123x1x2 第一階段：在原問題的可行域外部進(jìn)展基變換，第一階段終了后進(jìn)入可行域 第二階段：從可行域內(nèi)部的的一個(gè)極點(diǎn)B原問題的一個(gè)可行基開場，在可行域內(nèi)部進(jìn)展基變換基迭代道路基迭代道路兩階段法和大兩階段法和大M M法法 大大M法的根本步驟如下：法的根本步驟如下： 1引進(jìn)松弛變量，使約束條件成為等式；引進(jìn)松弛變量，使約束條件成為等式； 2假設(shè)約束條件的系數(shù)矩陣中不存在一個(gè)單位矩假設(shè)約束條件的系數(shù)矩陣中不存在一個(gè)單位矩陣，那么引進(jìn)人工變量；陣，那么引進(jìn)人工變量； 3在原目的函數(shù)中，加上人工變量，每個(gè)人工變量在原目的函數(shù)中，加上人工變量，每個(gè)人工變量的系數(shù)為一個(gè)充分大的正數(shù)的系數(shù)為

6、一個(gè)充分大的正數(shù)M； 4用單純形表求解以上問題，假設(shè)這個(gè)問題的最優(yōu)用單純形表求解以上問題，假設(shè)這個(gè)問題的最優(yōu)解中有人工變量是基變量，那么原問題無可行解。假設(shè)最解中有人工變量是基變量，那么原問題無可行解。假設(shè)最優(yōu)解中一切人工變量都離基，那么得到原問題的最優(yōu)解。優(yōu)解中一切人工變量都離基，那么得到原問題的最優(yōu)解。兩階段法和大兩階段法和大M M法法例2 求解以下線性規(guī)劃問題。引進(jìn)松弛變量x4，x5并規(guī)范化兩階段法和大兩階段法和大M M法法引進(jìn)人工變量x6，x70，在目的函數(shù)中添加人工變量列出系數(shù)矩陣表兩階段法和大兩階段法和大M M法法消去基變量x6、x7在目的函數(shù)中的系數(shù)x1進(jìn)基 X6離基1 64/2

7、 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è)設(shè)B是線性規(guī)劃的一個(gè)可行基，是線性規(guī)劃的一個(gè)可行基， XB=B-1b=(xB1,xB2,xBi,xBm)T 是這個(gè)根底解中的基變量。假設(shè)其中至少有一個(gè)分量是這個(gè)根底解中的基變量。假設(shè)其中至少有一個(gè)分量xBi=0(i=1,2,m)，那么稱此根底可行解是退化的。，那么稱此根

8、底可行解是退化的。 退化的構(gòu)造對單純形迭代會有不利的影響。當(dāng)?shù)M(jìn)入一個(gè)退化極點(diǎn)時(shí)，能夠出現(xiàn)以下情況： (1)進(jìn)展進(jìn)基、離基變換后，雖然改動了基，但沒有改動極點(diǎn)，目的函數(shù)當(dāng)然也不會改良。進(jìn)展假設(shè)干次基變換后，才脫離退化極點(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)基變量時(shí)不再思索檢驗(yàn)數(shù)zj-cj絕對值的大小，將會導(dǎo)致收斂速度的降低。需