运筹系列86:MIP问题的建模tips

1. Either-or constraint

添加辅助变量y。
比如
Either

3

x

1

+

2

x

2

18

3x_1+2x_2 le 18

3x1+2x218
or

x

1

+

4

x

2

16

x_1+4x_2 le 16

x1+4x216

可以用

3

x

1

+

2

x

2

18

+

M

y

3x_1+2x_2 le 18+My

3x1+2x218+My

x

1

+

4

x

2

16

+

M

(

1

y

)

x_1+4x_2 le 16+M(1-y)

x1+4x216+M(1y)
来代替。

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=Nk,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

xle My

xMy

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_3le 2

y1+y2+y32的约束。
然后是约束2,要求两座工厂二选一,因此添加Either-or变量

y

4

y_4

y4,最终模型为:
在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>