大M法
数学术语
大M法(big M 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的系数为负,该项检验数为负。用单纯形法求解的过程见下表:
关于大M法的单纯形表可以和两阶段法进行对比参照,可以发现二者很大程度上是相同的。
注:括号内表示主元素
参考资料
最新修订时间:2024-04-23 15:43
目录
概述
定律定义
求解步骤
参考资料