大M法

大M法

大M法(big M method)是線性規劃問題的約束條件(=)等式或(≥)大於型時,使用人工變數法後,尋找其初始基可行解的一種方法。

定律定義

線上性規劃問題的約束條件中加人工變數後,要求在目標函式中相應地添加認為的M或一M為係數的項。在極大化問題中,對人工變數賦於一M作為其係數;在極小化問題中,對人工變數賦於一個M作為其係數,M為一任意大(而非無窮大)的正數。把M看作一個代數符號參與運算,用單純形法求解,故稱此方法為大M法。

求解步驟

套用單純形法在改進目標函式的過程中,如果原問題存在最優解,必然使人工變數逐步變為非基變數,或使其值為零。否則,目標函式值將不可能達到最小或最大。在疊代過程中,若全部人工變數變成非基變數,則可把人工變數所在的列從單純形表中刪去,此時便找到原問題的一個初始基可行解。若此基可行解不是原問題的最優解,則繼續疊代,直至所有的檢驗數都小於等於0,求得最優解為止。

方法套用

大M法 大M法

用單純形法求解線性規劃問題:

大M法 大M法

先將其化為標準形式,有

大M法 大M法

這種情況可以添加兩列單位列向量P,P,連同約束條件中的向量P構成單位矩陣:

P,P是人為添加上去的,它相當於在上述問題的約束條件中添加變數x,x,變數x,x相應地稱為人工變數。由於約束條件在添加人工變數前已經是等式,為使這些等式得到滿足,因此在最優解中人工變數取值必須為零。添加人工變數後,數學模型形式就變為:

大M法 大M法

該模型中P,P,P對應的變數x,x,x為基變數,令非基變數x,x,x,x等於0,即得到初始基可行解X =(0,0,0,4,0,1,9) ,並列出初始單純形表。在單純形法疊代運算中,M可當作一個數學符號一起參加運算。檢驗數中含M符號的,當M的係數為正時,該檢驗數為正;當該M的係數為負,該項檢驗數為負。用單純形法求解的過程見下表:

C→(目標函式係數)
-30100-M-M
C
bxxxxxx x
0x41111000
-Mx1-2[1]-10-110
-Mx90310000
c-z-2M-34M10-M00
0x330211-10
0x1-21-10-110
-Mx6[6]0403-31
c-z6M-304M+103M-4M0
0x00001-1/2-1/2-1/2
0x3011/30001/3
-3x1102/301/2-1/21/6
c-z00303/2-M-3/2-M+1/2
0x00001-1/21/2-1/2
0x5/2-1/2100-1/41/41/4
1x3/23/20103/4-3/41/4
c-z-9/2000-3/4-M+3/4-M-1/4

關於大M法的單純形表可以和兩階段法進行對比參照,可以發現二者很大程度上是相同的。

合併圖冊 合併圖冊

註:括弧內表示主元素。

相關詞條

相關搜尋

熱門詞條

聯絡我們