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