(数学建模教材)2第二章整数规划

x3 ? 500z3 , z1 , z2 , z3 ? 0 或 1

model: sets:

var1/1..4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22; var2/1..3/:x,z,c; endsets

max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var2:c*x); y(1)+y(3)<@sum(var2:x)+500; y(2)+y(4)<1000; 0.5*(y(1)-y(2))>0; 0.4*y(3)-0.6*y(4)>0;

@for(var1(i)|i #lt# 3:500*z(i+1)

@for(var2:@bin(z));

@for(var2:@bnd(0,x,500)); data:

c=10 8 6; enddata end

(20) (21)

式(7)~(14),式(17)~(21)构成混合整数线性规划模型,将它输入 LINGO 软 件如下:

(3)解法三

直接处理分段线性函数 c(x) 。式(5)表示的函数 c(x) 如图 1 所示。

记 x 轴上的分点为 b1 ? 0 ,b2 ? 500 ,b3 ? 1000 。当 x 属于第 1 个小区间[b1 , b2 ] 时,记 x ? w1b1 ? w2b2 , w1 ? w2 ? 1 , w1 , w2 ? 0 ,因为 c(x) 在[b1 , b2 ] 上是线性的,

图 1 分段线性函数 c(x) 图形

所以 c(x) ? w1c(b1 ) ? w2c(b2 ) 。同样,当 x 属于第 2 个小区间 [b2 , b3 ] 时,

x ? w2b2 ? w3b3 , w2 ? w3 ? 1, w2 , w3 ? 0 , c(x) ? w2c(b2 ) ? w3c(b3 ) 。当 x 属于第 3 个 小 区 间 [b3 , b4 ] 时 , x ? w3b3 ? w4b4 , w3 ? w4 ? 1 , w3 , w4 ? 0 , c(x) ? w3c(b3 ) ? w4c(b4 ) 。为了表示 x 在哪个小区间,引入 0-1 变量 zk (k ? 1,2,3) , 当 x 在第 k 个小区间时, zk ? 1 ,否则, zk ? 0 。这样, w1 , w2 , w3 , w4 , z1 , z2 , z3 应满

w1 ? z1 , w2 ? z1 ? z2 , w3 ? z2 ? z3 , w4 ? z3

-26-

(22)

w1 ? w2 ? w3 ? w4 ? 1, wk ? 0 ( k ? 1,2,3,4 ) z1 ? z2 ? z3 ? 1 , z1 , z2 , z3 ? 0 或1 此时 x 和 c(x) 可以统一地表示为

x ? w1b1 ? w2b2 ? w3b3 ? w4b4 ? 500w2 ?1000w3 ? 1500w4 c(x) ? w1c(b1 ) ? w2c(b2 ) ? w3c(b3 ) ? w4c(b4 )

? 5000w2 ? 9000w3 ? 12000w4

(23) (24) (25) (26)

式(6)~(13),式(22)~(26)也构成一个混合整数线性规划模型,可以用 LINGO 求解。输入的 LINGO 模型如下:

model: sets:

var/1..4/:b,c,y,z,w;

!这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22 端点数为4,即分段数为3; endsets data:

b=0,500,1000,1500; c=0,5000,9000,12000;

z=,,,0; !增加的虚拟变量z(4)=0; enddata

max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var:c*w); y(1)+y(3)<@sum(var:b*w)+500; y(2)+y(4)<1000; 0.5*(y(1)-y(2))>0; 0.4*y(3)-0.6*y(4)>0; w(1)

@for(var(i)|i #ne# 1:w(i)

@for(var:@bin(z)); End

注:这个问题的关键是处理分段线性函数,我们推荐化为整数线性规划模型的第2

和第3种解法,第3种解法更具一般性,其做法如下。

设一个 n 段线性函数 f (x) 的分点为 b1 ? L ? bn ? bn?1 ,引入 wk 将 x 和 f (x) 表示 为

n?1

x ? ? wkbk

k ?1

n?1

f (xk ) ? ? wk f (bk )

k ?1

w和0-1变量 z满足

w1 ? z1 , w2 ? z1 ? z2 ,…, wn ? zn?1 ? zn , wn?1 ? zn z1 ? z2 ?L? zn ? 1 , zk ? 0 或1

w1 ? w2 ?L? wn?1 ? 1 , wk ? 0 ( k ? 1,2,L, n ? 1)

(27) (28) (29)

-27-

习 题 二

1. 用分枝定界法解:

3. 某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油,使总的钻探费 用为最小。若 10 个井位的代号为 s1 , s2 ,L, s10 ,相应的钻探费用为 c1 , c2 ,L, c10 ,并且 井位选择上要满足下列限制条件:

(1) 或选择 s1 和 s7 ,或选择钻探 s9 ;

(2) 选择了 s3 或 s4 就不能选 s5 ,或反过来也一样;

(3) 在 s5 , s6 , s7 , s8 中最多只能选两个;试建立这个问题的整数规划模型。 4.有一条河流由于河床泥沙淤结,每当上游发生洪水时,就会破堤淹没两岸,造 成人员和财产的损失,为减少总的损失,人们采取破堤泄洪的方法,图 2 是该河流一岸 区域的信息示意图,在该区域边界上有很高的山,使该区域成为封闭区域。区域内又分 成十五个小区,每个小区内标有三个数字,分别表示该区域的海拔高度 h(m) 、面积

Max z ? x1 ? x2

?? 9 ??51 x1 ? x2 14 ?14 ??

1 ??

? 2x? x???1 2

3 ??

?x1 , x2 ? 0, x1 , x2整???

2. 试将下述非线性的 0 ? 1规划问题转换成线性的 0 ? 1规划问题 max z ? x1 ? x1 x2 ? x3

?? 2x1 ? 3x2 ? x3 ? 3 ??

( j ? 1,2,3) ?x j ? 0或1,

S (km2 ) 和被完全淹没时土地、房屋和财产等损失总数 k (百万元),我们假设

(a)各小区间有相对高度为 1.2m 的小堤相互隔离,例如第一区和第二区之间事

实上有海拔 5.2m 小堤。

(b)当洪水淹没一个小区且洪水高于该小区高度 pm 时,该小区的损失 f (k, p) 为 该小区的 k 和 p 的函数:

(c)假设决堤口,可选在大堤或小堤的任何地方,决堤口的数量不受限制,但已 经决口,就不能再补合,从河流经大堤决口流入小区的洪水量按决口数成比例分配,如 在小区之间小堤开一决口,则假设该两小区之间的这段小堤不复存在,若水位高过小堤, 则将自动向邻近最低的小区泄洪,若这样的小区有多块时,则平均泄洪。

(1)整个区域全部受损失的最小洪水量 Q 。 (2)当洪水量为 Q / 6 , Q / 3 时,分别制定泄洪方案,使总损失最小(在一种方 案中,决堤同时进行),并计算出该方案的损失数。

-28-

?kp, 0 ? p ? 1

f (k, p) ? ??

?k, p ? 1

河 流

大堤 高 H3.6 S6.1 K1.4 1 H3.3 S3.6 K9.4 6 1 11 H4.0 S8.4 K7.0 2 H2.5 S8.5 K6.0 H4.7 S7.0 2 K5.8 3 H5.0 S1.8 K7.2 9 H4.4 S9.3 3 K3.3 1 H4.4 S0.1 K1.6 H3.8 S4.8 5 4 K2.0 55 1 H3.2 S0.9 K0.9 7 8 10 H3.8 S1.3 K4.4 15 山 H3.0 S4.6 K3.0 11 H2.5 S1.5 K4.1 12 H2.4 S2.3 K4.1 13 H3.8 S8.8 K5.3 14 高 山 图 2 河流一岸区域示意图 表 1 校址选择数据

备选校址

覆盖的居民小区

B1 A1 , A5

A7

B2 A1 , A2 A5 , A8

B3 A1 , A3 , A5

B4 A2 , A4 A8

B5 A3 , A6

B6 A4 , A6 A8

5.某市为方便小学生上学,拟在新建的 8 个居民小区 A1 , A2 , L , A8 增设若干所 小学,经过论证知备选校址有: B1 , B2 , L , B6 ,它们能够覆盖的居民小区如表 1。 试

建立一个数学模型,确定出最小个数的建校地址,使其能覆盖所有的居民小区。 6.某公司新购置了某种设备 6 台,欲分配给下属的 4 个企业,已知各企业获得这 种设备后年创利润如表 2 所示,单位为千万元。问应如何分配这些设备能使年创总利润

-29-

最大,最大利润是多少?

表 2 各企业获得设备的年创利润数

企业

设备

1

2 3 4 5 6

甲 4 6 7 7 7 7

乙 2 4 6 8 9 10

丙 3 5 7 8 8 8

丁 4 5 6 6 6 6

7.有一场由四个项目(高低杠、平衡木、跳马、自由体操) 组成的女子体操团

体赛,赛程规定:每个队至多允许 10 名运动员参赛,每一个项目可以有 6 名选手参加。 每个选手参赛的成绩评分从高到低依次为:10;9.9;9.8;…;0.1;0。每个代表队的 总分是参赛选手所得总分之和,总分最多的代表队为优胜者。此外,还规定每个运动员 只能参加全能比赛(四项全参加) 与单项比赛这两类中的一类,参加单项比赛的每个运 动员至多只能参加三个单项。每个队应有 4 人参加全能比赛,其余运动员参加单项比赛。

表 3 运动员各项目得分及概率分布表

1

运动员

项目

4

5

2

3

高低杠

平衡木

跳马

自由体操

8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 9.1~0.1 9.3~0.1 9.5~0.6 9.8~0.2 8.7~0.1 8.9~0.2 9.1~0.6 9.9~0.1 9.3~0.1 9.5~0.1 9.6~0.6 9.8~0.2 8.4~0.15 9.0~0.5 9.2~0.25 9.4~0.1 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.9~0.1 9.1~0.1 9.3~0.6 9.6~0.2 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.1~0.1 9.1~0.5 9.3~0.3 9.5~0.1 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 9.5~0.1 9.7~0.1 9.8~0.6 10~0.2 8.1~0.1 9.1~0.5 9.3~0.3 9.5~0.1 8.7~0.1 8.9~0.2 9.1~0.6 9.9~0.1 9.0~0.1 9.4~0.1 9.5~0.5 9.7~0.3 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 9.0~0.1 9.2~0.1 9.4~0.6 9.7~0.2 8.3~0.1 8.7~0.1 8.9~0.6 9.3~0.2 9.4~0.1 9.6~0.1 9.7~0.6 9.9~0.2

运动员 项目

6

续表 3 运动员各项目得分及概率分布表

7

9

10

8

高低杠

平衡木 -30-

9.4~0.1

9.6~0.1 9.7~0.6 9.9~0.2 8.7~0.1 9.5~0.1 9.7~0.1 9.8~0.6 10~0.2 8.4~0.1 8.4~0.1 8.8~0.2 9.0~0.6 10~0.1 8.8~0.05 8.4~0.15 9.5~0.5 9.2~0.25 9.4~0.1 8.4~0.1 9.0~0.1 9.2~0.1 9.4~0.6 9.7~0.2 8.1~0.1

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4