北京网站建设公司 网络服务,知名网站建设设计,wordpress cdn加速,上虞网络推广在数学建模当中#xff0c;常常会见到大M法#xff0c;它之所以叫大M法#xff0c;是因为它涉及到一个#xff08;绝对值#xff09;较大的系数M#xff0c;这个大M的值应大于约束中的连续变量或者约束表达式可能取到的任何合理值#xff0c;M值取过大往往会造成优化问题…在数学建模当中常常会见到大M法它之所以叫大M法是因为它涉及到一个绝对值较大的系数M这个大M的值应大于约束中的连续变量或者约束表达式可能取到的任何合理值M值取过大往往会造成优化问题求解的不稳定性。举以下例子 x ≤ 1 0 6 y x ≥ 0 y ∈ { 0 , 1 } x\leq 10^6y\\x\geq 0\\ y\in \{0,1\} x≤106yx≥0y∈{0,1}
大M约束通常用在将二元变量的信息传播给连续变量如上述例子只有当 y 1 y1 y1 时 x x x 才能取到非0的整数值假如求解器的整数容忍误差为 1 0 − 5 10^{-5} 10−5详见相关文章则 y 0.000009999 y0.000009999 y0.000009999 满足整数条件被视为等于0但此时代入上述约束后得到 x ≤ 9.999 x\leq 9.999 x≤9.999 x x x 最大可以取到 9 的正整数值并不符合一开始说的只有 y 1 y1 y1 时 x x x 才能取到非 0 整数值的关系。尽管我们能够调整求解器的整数容忍误差但当大M的取值更大时就不能避免这种情况。
因此另一个常用的方式是通过额外的信息来收紧大M的值详见相关文章对于整数容忍误差为 1 0 − 5 10^{-5} 10−5 的求解器而言大M的值比 1 0 − 5 10^{-5} 10−5 小就能实现目标例如上述约束在如下形式 x ≤ 1 0 3 y x ≥ 0 y ∈ { 0 , 1 } x\leq 10^3y\\x\geq 0\\ y\in \{0,1\} x≤103yx≥0y∈{0,1}
即使 y 0.000009999 y0.000009999 y0.000009999约束也仅允许 x ≤ 0.009999 x\leq 0.009999 x≤0.009999满足约束的初始意图。
特别的如果我们自己用大M法实在是难以收紧大M的取值不得不用较大的值进行约束则可以利用一些求解器自带的SOS约束函数当 y 0 ⇒ x 0 y0\Rightarrow x0 y0⇒x0这些SOS约束函数在求解器内部也是通过大M法进行转化且会以一定的额外求解时间为代价。
