- 中文名
- 大M法
- 外文名
- big M method
- 别 名
- 惩罚因子法the penaltyfactor method
- 适用领域
- 线性规划
- 应用学科
- 数学
在线性规划问题的约束条件中加人工变量后，要求在目标函数中相应地添加认为的M或一M为系数的项。在极大化问题中，对人工变量赋于一M作为其系数；在极小化问题中，对人工变量赋于一个M作为其系数，M为一任意大（而非无穷大）的正数。把M看作一个代数符号参与运算，用单纯形法求解，故称此方法为大M法。 [1]
应用单纯形法在改进目标函数的过程中，如果原问题存在最优解，必然使人工变量逐步变为非基变量，或使其值为零。否则，目标函数值将不可能达到最小或最大。在迭代过程中，若全部人工变量变成非基变量，则可把人工变量所在的列从单纯形表中删去，此时便找到原问题的一个初始基可行解。若此基可行解不是原问题的最优解，则继续迭代，直至所有的检验数都小于等于0，求得最优解为止。
用单纯形法求解线性规划问题：
先将其化为标准形式，有
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 | ||
