本文主要是介绍运筹系列86:MIP问题的建模tips,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1. Either-or constraint
添加辅助变量y。
比如
Either 3 x 1 + 2 x 2 ≤ 18 3x_1+2x_2 \le 18 3x1+2x2≤18
or x 1 + 4 x 2 ≤ 16 x_1+4x_2 \le 16 x1+4x2≤16
可以用
3 x 1 + 2 x 2 ≤ 18 + M y 3x_1+2x_2 \le 18+My 3x1+2x2≤18+My
x 1 + 4 x 2 ≤ 16 + M ( 1 − y ) x_1+4x_2 \le 16+M(1-y) x1+4x2≤16+M(1−y)
来代替。
2. k out of N constraints must hold
类似上面,添加辅助变量 y 1 y_1 y1~ y N y_N yN
从
f 1 ( . . . ) ≤ d 1 f_1(...)\le d_1 f1(...)≤d1
…
f N ( . . . ) ≤ d N f_N(...)\le d_N fN(...)≤dN
变为
f 1 ( . . . ) ≤ d 1 + M y 1 f_1(...)\le d_1+My_1 f1(...)≤d1+My1
…
f N ( . . . ) ≤ d N + M y N f_N(...)\le d_N+My_N fN(...)≤dN+MyN
Σ 1 N y i = N − k , y i \Sigma_1^N y_i=N-k, y_i Σ1Nyi=N−k,yi binary.
3. functions with N possible values
f ( x ) ∈ ( d 1 , . . . , d N ) f(x)\in (d_1,...,d_N) f(x)∈(d1,...,dN)
添加辅助变量 y 1 y_1 y1~ y N y_N yN
f ( x ) = Σ d i y i f(x)=\Sigma d_iy_i f(x)=Σdiyi
Σ y i = 1 \Sigma y_i=1 Σyi=1 (mutally exclusive alternatives)
4. fixed-charge problem
f ( x ) = { k + c x , x > 0 0 , x = 0 f(x)=\begin {equation} \begin{cases} k+cx, x>0\\ 0,x=0\\ \end{cases} \end {equation} f(x)={k+cx,x>00,x=0
可以变为
f ( x ) = c x + k y f(x)=cx+ky f(x)=cx+ky
x ≤ M y x\le My x≤My
y y y binary.
5. 综合例子
如果没有题目中的两个restriction,那么模型为:
接下来我们看约束1,要求 x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3最多只能有2个,因此添加 y 1 + y 2 + y 3 ≤ 2 y_1+y_2+y_3\le 2 y1+y2+y3≤2的约束。
然后是约束2,要求两座工厂二选一,因此添加Either-or变量 y 4 y_4 y4,最终模型为:
这篇关于运筹系列86:MIP问题的建模tips的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!