運籌學(xué)第4講：單純形法的進一步討論

1、第4講：單純形法的進一步討論1一、LP問題的標(biāo)準(zhǔn)化LP模型的標(biāo)準(zhǔn)形式運籌學(xué) 第4講：單純形法的進一步討論max Z = CXs.t. AX = b X 0 目標(biāo)函數(shù)為max型 X 0 b 0! 單純形法僅適于LP標(biāo)準(zhǔn)模型的求解2非標(biāo)準(zhǔn)型LP模型的標(biāo)準(zhǔn)化（P10）一、若目標(biāo)函數(shù)為：min Z = CX 令Z = -Z，則原目標(biāo)函數(shù)轉(zhuǎn)化為 max Z = -CX二、若存在bi 0 將bi所在的約束條件式兩邊同乘（1）三、若約束條件不等式為“” 左式加入松弛變量xj，xj0運籌學(xué) 第4講：單純形法的進一步討論3五、若存在xj無約束 可令xj = xj - xj, xj, xj0六、若存在xj 0時，

2、說明模型中存在多余的約束，使多個基可行解對應(yīng)同一頂點。當(dāng)模型存在退化解時，處理方法如下： 最小比值相同時，取下標(biāo)值最大的變量為換出變量 j最大值相同時，取下標(biāo)值最小的變量為換入變量運籌學(xué) 第4講：單純形法的進一步討論8 大M法的問題在于：采用手工計算求解不會碰到問題，但用計算機求解時，對M只能在計算機中輸入一個機器最大字長的數(shù)字；顯然，如果其他參數(shù)值大于或與這個數(shù)字相近，便會導(dǎo)致計算結(jié)果發(fā)生錯誤！運籌學(xué) 第4講：單純形法的進一步討論9max z = -4x1 x2 s.t. 3x1 + x2 = 3 4x1 + 3x2 - x3 = 6 x1 + 2x2 + x4 = 4 x1-4 0例3：P

3、20例2.6運籌學(xué) 第4講：單純形法的進一步討論10運籌學(xué) 第4講：單純形法的進一步討論11三、二階段法 針對大M法存在的問題，我們可以對添加人工變量后的LP模型分為兩個階段來計算，稱為二階段法(P22)。 第一階段：先求一個目標(biāo)函數(shù)中只包含人工變量的LP模型，也就是說，令目標(biāo)函數(shù)中其他變量的系數(shù)為0，人工變量的系數(shù)為某個正常數(shù)(一般為1)，在原問題約束條件不變的情況下求解。 第二階段：當(dāng)?shù)谝浑A段求解結(jié)果表明模型有可行解時，在原問題中去除人工變量，從第一階段的最優(yōu)解出發(fā)，繼續(xù)求解。例4：采用二階段法求解P22中LP模型運籌學(xué) 第4講：單純形法的進一步討論12運籌學(xué) 第4講：單純形法的進一步討論

4、首先應(yīng)確定當(dāng)x5, x6=0時，可行域是否存在！則第一階段先求解如下的LP模型：顯然，若z=0，即x5, x6=0，則問題的可行域存在。13運籌學(xué) 第4講：單純形法的進一步討論x5, x6=0，則 z=0，問題的可行域存在。14運籌學(xué) 第4講：單純形法的進一步討論去除x5和x6，進一步求解第二階段的LP模型：得到最優(yōu)解和最優(yōu)值。15四、采用單純形法求解的幾種情況 惟一最優(yōu)解 無可行解(P23-例2.7) 所有檢驗數(shù)j 0，但基變量中仍含有非零人工變量 無界解(例5) 當(dāng)存在最大的j 0，但值無解 多重最優(yōu)解(例6:習(xí)題2-1) 當(dāng)所有檢驗數(shù)0，但存在非基變量j = 0，該非基變量可以作為換入變量，模型存在多重最優(yōu)解運籌學(xué) 第4講：單純形法的進一步討論16max z = 3x1 + 2x2 s.t. -2x1 + x2 2 x1 - 3x2 3 x1, x2 0例5：求解如下LP模型運籌學(xué) 第4講：單純形法的進一步討論17max z = 3x1 + 2x2 + 0 x3 + 0 x4 s.t. -2x1 + x2 + x3 = 2 x1 - 3x2 + x4 = 3 x1, x2 0解：將模型化為標(biāo)準(zhǔn)型，運籌學(xué) 第4講：單純形法的進一步討論18 由于maxj |j 0所對應(yīng)的值無解，則該LP問題解無界。運籌學(xué)