關于運籌學單純形法的進一步討論一、LP問題的標準化LP模型的標準形式運籌學第4講：單純形法的進一步討論maxZ=CXs.t.AX=b

X≥0

目標函數為max型

X≥0b≥0!

單純形法僅適于LP標準模型的求解第2頁,共21頁，星期六，2024年，5月非標準型LP模型的標準化（P10）一、若目標函數為：minZ=CX

令Z’=-Z，則原目標函數轉化為maxZ’=-CX二、若存在bi<0

將bi所在的約束條件式兩邊同乘（－1）三、若約束條件不等式為“≤”左式加入松弛變量xj，xj≥0運籌學第4講：單純形法的進一步討論第3頁,共21頁，星期六，2024年，5月五、若存在xj無約束可令xj=xj’-xj’’,xj’,xj’’≥0六、若存在xj<0

令xj’=-xj，xj≥0四、若約束條件不等式為“≥”左式減去剩余變量xj，xj≥0運籌學第4講：單純形法的進一步討論第4頁,共21頁，星期六，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模型轉化為標準型運籌學第4講：單純形法的進一步討論第5頁,共21頁，星期六，2024年，5月maxz=-3x1+x3

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

x1,

x2,x3≥0例2：求解如下LP模型：運籌學第4講：單純形法的進一步討論第6頁,共21頁，星期六，2024年，5月二、人工變量法(大M法)

為使LP標準模型的初始可行基為單位矩陣，填入人工變量！

在目標函數中，令人工變量的系數為任意大的負值，采用“－M”表示。

當所有檢驗數σj≤0，但基變量中仍含有非零的人工變量，說明該LP模型無可行解。運籌學第4講：單純形法的進一步討論第7頁,共21頁，星期六，2024年，5月

退化問題：當存在多個相同的θ最小比值，或存在多個相同的最大σj>0時，說明模型中存在多余的約束，使多個基可行解對應同一頂點。當模型存在退化解時，處理方法如下：

θ最小比值相同時，取下標值最大的變量為換出變量

σj最大值相同時，取下標值最小的變量為換入變量運籌學第4講：單純形法的進一步討論第8頁,共21頁，星期六，2024年，5月

大M法的問題在于：采用手工計算求解不會碰到問題，但用計算機求解時，對M只能在計算機中輸入一個機器最大字長的數字；顯然，如果其他參數值大于或與這個數字相近，便會導致計算結果發生錯誤！運籌學第4講：單純形法的進一步討論第9頁,共21頁，星期六，2024年，5月maxz=-4x1–x2

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

6

x1+

2x2+x4=4

x1-4≥0例3：P20例2.6運籌學第4講：單純形法的進一步討論第10頁,共21頁，星期六，2024年，5月運籌學第4講：單純形法的進一步討論第11頁,共21頁，星期六，2024年，5月三、二階段法

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

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

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

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

當存在最大的σj>0，但θ值無解多重最優解(例6:習題2-1)

當所有檢驗數≤0，但存在非基變量σj

=0，該非基變量可以作為換入變量，模型存在多重最優解運籌學第4講：單純形法的進一步討論第16頁,共21頁，星期六，2024年，5月maxz=3x1+2x2

s.t. -2x1+x2≤2

x1-3x2≤

3

x1,

x2≥0例5：求解如下LP模型運籌學第4講：單純形法的進一步討論第17頁,共21頁，星期六，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解：將模型化為標準型，運籌學第4講：單純形法的進一步討論第18頁,共21頁，星期六，2024年，5月cj→3200bbi/aikcBXBx1x2x3x50x3-21102/0x4[1]-30133δj(1)32000x30-5128/3x11-3013/δj(2)0110-3

由于max{σj|σj>0}所對應的θ值無解，則該LP問題解無界。運籌學第4講：