運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論

1、第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論1一、LP問(wèn)題的標(biāo)準(zhǔn)化LP模型的標(biāo)準(zhǔn)形式運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論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運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論3五、若存在xj無(wú)約束 可令xj = xj - xj, xj, xj0六、若存在xj 0時(shí)，

2、說(shuō)明模型中存在多余的約束，使多個(gè)基可行解對(duì)應(yīng)同一頂點(diǎn)。當(dāng)模型存在退化解時(shí)，處理方法如下： 最小比值相同時(shí)，取下標(biāo)值最大的變量為換出變量 j最大值相同時(shí)，取下標(biāo)值最小的變量為換入變量運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論8 大M法的問(wèn)題在于：采用手工計(jì)算求解不會(huì)碰到問(wèn)題，但用計(jì)算機(jī)求解時(shí)，對(duì)M只能在計(jì)算機(jī)中輸入一個(gè)機(jī)器最大字長(zhǎng)的數(shù)字；顯然，如果其他參數(shù)值大于或與這個(gè)數(shù)字相近，便會(huì)導(dǎo)致計(jì)算結(jié)果發(fā)生錯(cuò)誤！運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論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運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論10運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論11三、二階段法 針對(duì)大M法存在的問(wèn)題，我們可以對(duì)添加人工變量后的LP模型分為兩個(gè)階段來(lái)計(jì)算，稱為二階段法(P22)。 第一階段：先求一個(gè)目標(biāo)函數(shù)中只包含人工變量的LP模型，也就是說(shuō)，令目標(biāo)函數(shù)中其他變量的系數(shù)為0，人工變量的系數(shù)為某個(gè)正常數(shù)(一般為1)，在原問(wèn)題約束條件不變的情況下求解。 第二階段：當(dāng)?shù)谝浑A段求解結(jié)果表明模型有可行解時(shí)，在原問(wèn)題中去除人工變量，從第一階段的最優(yōu)解出發(fā)，繼續(xù)求解。例4：采用二階段法求解P22中LP模型運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論12運(yùn)籌學(xué) 第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論

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