運(yùn)籌學(xué)單純形法的進(jìn)一步討論

關(guān)于運(yùn)籌學(xué)單純形法的進(jìn)一步討論一、LP問題的標(biāo)準(zhǔn)化LP模型的標(biāo)準(zhǔn)形式運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論maxZ=CXs.t.AX=b

X≥0

目標(biāo)函數(shù)為max型

X≥0b≥0!

單純形法僅適于LP標(biāo)準(zhǔn)模型的求解第2頁(yè),共21頁(yè)，星期六，2024年，5月非標(biāo)準(zhǔn)型LP模型的標(biāo)準(zhǔn)化（P10）一、若目標(biāo)函數(shù)為：minZ=CX

令Z’=-Z，則原目標(biāo)函數(shù)轉(zhuǎn)化為maxZ’=-CX二、若存在bi<0

將bi所在的約束條件式兩邊同乘（－1）三、若約束條件不等式為“≤”左式加入松弛變量xj，xj≥0運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第3頁(yè),共21頁(yè)，星期六，2024年，5月五、若存在xj無約束可令xj=xj’-xj’’,xj’,xj’’≥0六、若存在xj<0

令xj’=-xj，xj≥0四、若約束條件不等式為“≥”左式減去剩余變量xj，xj≥0運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第4頁(yè),共21頁(yè)，星期六，2024年，5月minz=x1+2x2+3x3

s.t. -2x1+x2+x3≤9-3x1+x2+2x3≥4 4x1-2x2-3x3=-6

x1≤0

,x2≥0，x3無約束例1：將下述LP模型轉(zhuǎn)化為標(biāo)準(zhǔn)型運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第5頁(yè),共21頁(yè)，星期六，2024年，5月maxz=-3x1+x3

s.t. x1+x2+x3≤4-2x1+x2-x3≥1 3x2+x3=9

x1,

x2,x3≥0例2：求解如下LP模型：運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第6頁(yè),共21頁(yè)，星期六，2024年，5月二、人工變量法(大M法)

為使LP標(biāo)準(zhǔn)模型的初始可行基為單位矩陣，填入人工變量！

在目標(biāo)函數(shù)中，令人工變量的系數(shù)為任意大的負(fù)值，采用“－M”表示。

當(dāng)所有檢驗(yàn)數(shù)σj≤0，但基變量中仍含有非零的人工變量，說明該LP模型無可行解。運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第7頁(yè),共21頁(yè)，星期六，2024年，5月

退化問題：當(dāng)存在多個(gè)相同的θ最小比值，或存在多個(gè)相同的最大σj>0時(shí)，說明模型中存在多余的約束，使多個(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頁(yè),共21頁(yè)，星期六，2024年，5月

大M法的問題在于：采用手工計(jì)算求解不會(huì)碰到問題，但用計(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)一步討論第9頁(yè),共21頁(yè)，星期六，2024年，5月maxz=-4x1–x2

s.t. 3x1+x2=34x1+3x2-x3=

6

x1+

2x2+x4=4

x1-4≥0例3：P20例2.6運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第10頁(yè),共21頁(yè)，星期六，2024年，5月運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第11頁(yè),共21頁(yè)，星期六，2024年，5月三、二階段法

針對(duì)大M法存在的問題，我們可以對(duì)添加人工變量后的LP模型分為兩個(gè)階段來計(jì)算，稱為二階段法(P22)。

第一階段：先求一個(gè)目標(biāo)函數(shù)中只包含人工變量的LP模型，也就是說，令目標(biāo)函數(shù)中其他變量的系數(shù)為0，人工變量的系數(shù)為某個(gè)正常數(shù)(一般為1)，在原問題約束條件不變的情況下求解。第二階段：當(dāng)?shù)谝浑A段求解結(jié)果表明模型有可行解時(shí)，在原問題中去除人工變量，從第一階段的最優(yōu)解出發(fā)，繼續(xù)求解。例4：采用二階段法求解P22中LP模型運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第12頁(yè),共21頁(yè)，星期六，2024年，5月運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論首先應(yīng)確定當(dāng)x5,x6=0時(shí)，可行域是否存在！則第一階段先求解如下的LP模型：顯然，若z=0，即x5,x6=0，則問題的可行域存在。第13頁(yè),共21頁(yè)，星期六，2024年，5月運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論x5,x6=0，則z=0，問題的可行域存在。第14頁(yè),共21頁(yè)，星期六，2024年，5月運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論去除x5和x6，進(jìn)一步求解第二階段的LP模型：得到最優(yōu)解和最優(yōu)值。第15頁(yè),共21頁(yè)，星期六，2024年，5月四、采用單純形法求解的幾種情況

惟一最優(yōu)解無可行解(P23-例2.7)

所有檢驗(yàn)數(shù)σj≤0，但基變量中仍含有非零人工變量無界解(例5)

當(dāng)存在最大的σj>0，但θ值無解多重最優(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)一步討論第16頁(yè),共21頁(yè)，星期六，2024年，5月maxz=3x1+2x2

s.t. -2x1+x2≤2

x1-3x2≤

3

x1,

x2≥0例5：求解如下LP模型運(yùn)籌學(xué)第4講：?jiǎn)渭冃畏ǖ倪M(jìn)一步討論第17頁(yè),共21頁(yè)，星期六，2024年，5月cj→3200bbi/aikcBXBx1x2x3x50x3-21102/0x4[1]-30133δj(1)3200maxz=3x1+2x2

+0x3+0x4

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頁(yè),共21頁(yè)，星期六，2024年，5月cj→3200bbi/aikcBXBx1x2x3x50x3-21102/0x4[1]-30133δj(1)32000x30-5128/3x11-3013/δj(2)0110-3

由于max{σj|σj>0}所對(duì)應(yīng)的θ值無解，則該LP問題解無界。運(yùn)籌學(xué)第4講：