定律定義
線上性規劃問題的約束條件中加人工變數後,要求在目標函式中相應地添加認為的M或一M為係數的項。在極大化問題中,對人工變數賦於一M作為其係數;在極小化問題中,對人工變數賦於一個M作為其係數,M為一任意大(而非無窮大)的正數。把M看作一個代數符號參與運算,用單純形法求解,故稱此方法為大M法。
求解步驟
套用單純形法在改進目標函式的過程中,如果原問題存在最優解,必然使人工變數逐步變為非基變數,或使其值為零。否則,目標函式值將不可能達到最小或最大。在疊代過程中,若全部人工變數變成非基變數,則可把人工變數所在的列從單純形表中刪去,此時便找到原問題的一個初始基可行解。若此基可行解不是原問題的最優解,則繼續疊代,直至所有的檢驗數都小於等於0,求得最優解為止。
方法套用
用單純形法求解線性規劃問題:
先將其化為標準形式,有
這種情況可以添加兩列單位列向量P,P,連同約束條件中的向量P構成單位矩陣:
P,P是人為添加上去的,它相當於在上述問題的約束條件中添加變數x,x,變數x,x相應地稱為人工變數。由於約束條件在添加人工變數前已經是等式,為使這些等式得到滿足,因此在最優解中人工變數取值必須為零。添加人工變數後,數學模型形式就變為:
該模型中P,P,P對應的變數x,x,x為基變數,令非基變數x,x,x,x等於0,即得到初始基可行解X =(0,0,0,4,0,1,9) ,並列出初始單純形表。在單純形法疊代運算中,M可當作一個數學符號一起參加運算。檢驗數中含M符號的,當M的係數為正時,該檢驗數為正;當該M的係數為負,該項檢驗數為負。用單純形法求解的過程見下表:
C→(目標函式係數) | -3 | 0 | 1 | 0 | 0 | -M | -M | ||
C | 基 | b | x | x | x | x | x | x | x |
0 | x | 4 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
-M | x | 1 | -2 | [1] | -1 | 0 | -1 | 1 | 0 |
-M | x | 9 | 0 | 3 | 1 | 0 | 0 | 0 | 0 |
c-z | -2M-3 | 4M | 1 | 0 | -M | 0 | 0 | ||
0 | x | 3 | 3 | 0 | 2 | 1 | 1 | -1 | 0 |
0 | x | 1 | -2 | 1 | -1 | 0 | -1 | 1 | 0 |
-M | x | 6 | [6] | 0 | 4 | 0 | 3 | -3 | 1 |
c-z | 6M-3 | 0 | 4M+1 | 0 | 3M | -4M | 0 | ||
0 | x | 0 | 0 | 0 | 0 | 1 | -1/2 | -1/2 | -1/2 |
0 | x | 3 | 0 | 1 | 1/3 | 0 | 0 | 0 | 1/3 |
-3 | x | 1 | 1 | 0 | 2/3 | 0 | 1/2 | -1/2 | 1/6 |
c-z | 0 | 0 | 3 | 0 | 3/2 | -M-3/2 | -M+1/2 | ||
0 | x | 0 | 0 | 0 | 0 | 1 | -1/2 | 1/2 | -1/2 |
0 | x | 5/2 | -1/2 | 1 | 0 | 0 | -1/4 | 1/4 | 1/4 |
1 | x | 3/2 | 3/2 | 0 | 1 | 0 | 3/4 | -3/4 | 1/4 |
c-z | -9/2 | 0 | 0 | 0 | -3/4 | -M+3/4 | -M-1/4 |
關於大M法的單純形表可以和兩階段法進行對比參照,可以發現二者很大程度上是相同的。
註:括弧內表示主元素。