運籌學

（OperationsResearch）上海海事大學20131009任課教師：鄧偉郵箱：dengwei1663@單純形表總結

注：在單純形表中，檢驗數的形式為

其中，對于基變量來說，檢驗數而(此因：基變量的系數矩陣為一個單位陣，當前僅當

)因此線性規劃所有變量的檢驗數可統一為單純形表總結在初始的單純形表中，在常數項b的下方添加上當前解（初始基本可行解）對應的目標函數值的相反數，這樣，經過一系列的迭代，在最優單純形表中，這個相反數經過迭代后為最優解對應的目標函數值的相反數。單純形表總結cj02-210θCBXBbx1x2x3x4x50x15111000x4601-4100x52402601cj-zj-Z1=-601200初始目標函數值的相反數人工變量法在應用單純形法確定初始基本可行解X1時，如果約束矩陣中不含有單位陣，可以采用人工變量進行處理。人工變量的引入在約束矩陣中不含單位陣時，一般要在模型中人為地添加一些非負變量，稱為人工變量，構造一個新的線性規劃問題，使新問題的約束矩陣中含有單位陣，從而可以方便地確定新問題的一個基本可行解然后再根據新問題與原問題的解的關系，給出原問題的解的結果。

人工變量法例5.1對于下面的模型

在加入人工變量之后，就得到新問題的約束條件。

此約束矩陣中含有單位矩陣，可以取變量為基變量，確定新問題的初始基本可行解。人工變量法下面介紹兩種人工變量方法。大M法引入人工變量的目的是為了使約束系數矩陣中含有單位矩陣，由于此模型已有x4的系數列向量為單位向量，只需要再有兩個單位向量就可以得到單位矩陣，所以只在第1個和第2個約束方程中添加兩個人工變量即可。添人工變量的原則是，只要在約束矩陣中出現一個單位矩陣即可。構造上面模型對應的“大M規劃”人工變量法其中x5,x6為人工變量，目標函數中人工變量的負系數M是非常大的正數，大M法即因此得名。下面分析構造大M規劃的原理根據上述大M規劃的形式，可以得到大M規劃的一個初始基本可行解

(x1,x2,……，x6)T=(0,0,0,26,15,20)T由于x5,x6>0，所以(x1,x2,x3,x4)T=(0,0,0,26)T不是原規劃問題的可行解。顯然，為了使大M規劃的基本可行解，對于原規劃從不可行變為可行，需要借助于目標函數使人工變量的值減小到零。人工變量法

由于在大M規劃的目標函數中，M為很大的數，所以在原規劃存在可行解的情況下，只要人工變量不為零，目標函數就不可能實現極大化。可以說，大M對人工變量具有一種懲罰作用，一旦人工變量為零，這種懲罰作用就消失了，是大M使得人工變量趨于零的。由于非基變量是取零值的，所以M的作用反映在單純形法的計算中，就是將人工變量從基本可行解的基變量中替換出去，使它們成為非基變量。人工變量法

關于大M法的幾個結論：(1)大M規劃有最優解，并且在最優解中人工變量皆取零值，則在這個最優解中去掉人工變量的部分后，就是原規劃的最優解。(2)大M規劃有最優解，但在最優解中人工變量不全為零，則原規劃沒有最優解。(3)大M規劃沒有最優解，則原規劃也沒有最優解。人工變量法

用大M法求解線性規劃模型解加入人工變量x5,x6后，得到大M規劃模型。取x4,x5,x6為基變量，將目標函數化為典式形式。建立大M規劃的單純形表，進行計算，計算過程如下面的單純形表。人工變量法人工變量法由于M為很大的數，所以最后表中所有檢驗數均已小于等于零，因此得到新規劃的最優解為(x1,x2,……，x6)T=(25/3,10/3,0,11,0,0)T。由于人工變量已取零值，根據大M法的結論，得到原規劃問題的最優解為(x1,x2,x3,x4)T=(25/3,10/3,0,11)T

，最優目標函數值為112/3。

人工變量法例5.2

用大M法解下面模型先引入松弛變量x3,x4化為標準形式人工變量法

再引入人工變量x5,構造大M規劃模型。取x3,x5為基變量，由約束條件解出代入目標函數中，得到典式形式人工變量法建立單純形表進行求解：在上面的最優單純形表中，檢驗數全部小于等于零，已得到大M規劃的最優解。但是在最優解中人工變量x5=3不為零，所以原規劃沒有可行解。人工變量法解引入人工變量x5,x6構造大M規劃

例5.3用大M法求解下面線性規劃問題：由約束條件解出人工變量法代入目標函數，得到目標的典式形式構造單純形表進行計算，得到人工變量法表中檢驗數，而皆小于等于零，故大M規劃沒有最優解。由大M法的結論可知，原規劃也沒有最優解。人工變量法在機器計算時，大M法有時出現變量字長限制的問題。兩階段法是另一種人工變量法，它是分兩階段進行求解的。兩階段法以下針對大M法中的模型進行討論。1.引入人工變量構造第一階段規劃，也稱輔助規劃，求原規劃的一個基本可行解。輔助規劃的目標函數是求所有人工變量的和的最小值。由于人工變量非負，因此，使人工變量之和趨于零，就是使每個人工變量趨于零。人工變量法關于第一階段規劃(輔助規劃)有以下結論：在第一階段規劃的最優解中，如果人工變量不為零，則原規劃沒有可行解，計算停止；如果人工變量全為零，并且人工變量均為非基變量，則在第一階段規劃的最優解中，去掉人工變量部分之后，就得到原規劃的一個基本可行解，繼續第二階段的計算。人工變量法經過第一階段的求解，得到原規劃的一個基本可行解之后，要進行第二階段的求解，即求解原規劃。求解原規劃不必另用新表，只需要在第一階段規劃的最優單純形表中，將檢驗數行數字去掉，并將原目標函數用非基變量表示，得到檢驗數后填入表中。另外，由于人工變量已不起作用，所以將人工變量對應的兩列元素去掉，經過這些調整之后，繼續按照單純形法步驟求解，直至得到最優解。人工變量法例5.4用兩階段方法求解下面的線性規劃問題。解求解第一階段規劃：上面模型的第一階段規劃為，人工變量法由約束條件解出建立單純形表進行計算，得到最優單純形表，從表中可以看出，檢驗數已全部小于等于零，得到第一階段規劃的最優解(0,15/7,25/7,52/7,0,0)T。由于最優解中人工變量皆取零值，故得到原規劃的一個基本可行解(0,15/7,25/7,52/7)T。代入目標函數w中，得到化為求極大人工變量法求解第二階段規劃：在最優單純形表中，去掉人工變量部分的所有元素，并將檢驗數行換成原規劃相應于基本可行解

(0,15/7,25/7,52/7)T的檢驗數。由于此時x2,x3,x4為基變量，由最優單純形表可以得到：人工變量法人工變量法代入原規劃的目標函數Z，得到將此檢驗數代入表中進行計算，去掉x5,x6兩列元素，得到檢驗數全部非正，得到原規劃的最優解(25/3,10/3,0,11)T,最優值112/3。人工變量法人工變量法例5.5用單純形法求解下面線性規劃問題解引入松弛變量x3,x4化為標準形，引入人工變量x5,x6求解第一階段規劃人工變量法將目標函數化為求極大，并用非基變量表示建立單純形表進行計算由這個最優單純形表可以看出第一階段的最優解為(0,1/2,0,0,0,3/2)T，其中人工變量x6=3/2不為零，所以原規劃沒有可行解。多個最優解的討論關于多個最優解的討論：在圖解法中已經看到，一個線性規劃問題可能存在多個最優解，這里討論如何在單純形方法中識別一個模型是否有多個最優解，在存在的情況下，如何將這些最優解求出。在單純形表中，存在第二個最優解的判別方法：如果在最優單純形表中，除去基變量對應的檢驗數為零外，還存在非基變量xk對應的檢驗數也為零，并且xk所在列的各個系數aik不全小于等于零，則此模型存在第二個最優解。事實上，這是因為如果將這個檢驗數為零的非基變量作為進基變量進行迭代計算，則原最優解將發生變化，得到一新解。但是，由于這個進基變量的檢驗數已經為零，所以檢驗數行并不需要再做初等變換，因此得到的新解與原最優解取相同的函數值，所以新解也是最優解。多個最優解的討論在得到第二個最優解后，可以通過下面方法得到無窮多個最優解。設X1,X2為兩個最優解，則仍為最優解。當取[0,1]區間上不同值時，對應著不同的X0，因此可以得到無窮多個最優解。注：記Z*為最優值，X1,X2為最優解，則Z*=CX1=CX2，而又可證明X0為可行解，所以X0為最優解。多個最優解的討論例5.6求出下面線性規劃問題的多個最優解：在最優單純形表中，得到第一個最優解X1=(0,2,16,4,0,0)T，最優值為128.從最優單純形表可以看出，非基變量x6的檢驗數為零，并且，因此將x6引入基變量，求解第二個最優解。解

加入松弛變量x4,x5,x6化為標準形，求第一個最優解：多個最優解的討論多個最優解的討論第二個最優解為X2=(0,4,16,0,0,2)T，因此原規劃的全部解可以表示為多個最優解的討論第二個最優解為X2=(0,4,16,0,0,2)T，因此原規劃的全部解可以表示為退化盡管計算過程的循環現象極少出現，但還是有可能的。先后有人提出了“攝動法”、“字典序法”。1974年Bland提出一種簡便的規則（Bland規則）：如何解決這個問題？（1）選擇中下標最小的非基變量xk為換入變量，即（2）當按最小比值規則計算存在兩個以上的最小比值時，選取下標最小的基變量為換入變量。當按Bland規則計