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