第二章 整数规划
§1 概论
1.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。
2o 变量部分限制为整数的，称混合整数规划。
1.2 整数规划特点
（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例 1 原线性规划为
min z = x1 + x2
2x1 + 4x2 = 5, x1 ≥ 0, x2 ≥ 0
其最优实数解为：x1 = 0, xmin z
③有可行解（当然就存在最优解），但最优解值变差。
例 2 原线性规划为
min z = x1 + x2
2x1 + 4x2 = 6, x1 ≥ 0, x2 ≥ 0
其最优实数解为：x1 = 0, xmin z
若限制整数得：x1 = 1, x2 = 1, min z = 2 。
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类：
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
（v）蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝， -16-
这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。
设有最大化的整数规划问题 A，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合 A的整数条件，那么B 的最优目标函数必是 A的最优目标函数z* 的上界，记作 z ；而 A 的任意可行解的目标函数值将是z * 的一个下界 z 。分枝定界法就是将B 的可行域分成子区域的方法。逐步减小 z 和增大z ，最终求到z * 。现用下例来说明：
例 3 求解下述整数规划
Max z = 40x1 + 90x2
整数
解 （i）先不考虑整数限制，即解相应的线性规划B ，得最优解为：
x1 = 4.8092, x2 = 1.8168, z = 355.8779
可见它不符合整数条件。这时 z 是问题 A 的最优目标函数值 z* 的上界，记作 z 。而x1 = 0, x2 = 0 显然是问题 A 的一个整数可行解，这时z = 0 ，是z * 的一个下界，记作z ，即0 ≤ z* ≤ 356 。
（ii）因为x1 , x2 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成 2 个子集：
x1 ≤ [4.8092] = 4 ，x1 ≥ [4.8092] + 1 = 5
因为 4 与5 之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：
问题B1 ： Max z = 40x1 + 90x2
最优解为：x1 = 4.0, x2 = 2.1, z1 = 349 。
问题B2 ： Max z = 40x1 + 90x2
最优解为：x1 = 5.0, x2 = 1.57, z1 = 341.4 。
再定界：0 ≤ z* ≤ 349 。
（iii）对问题 B1 再进行分枝得问题B11 和B12 ，它们的最优解为
-17-
B11 : x1 = 4, x2 = 2, z11 = 340
B12 : x1 = 1.43, x2 = 3.00, z12 = 327.14
再定界：340 ≤ z* ≤ 341，并将 B12 剪枝。
（iv）对问题 B2 再进行分枝得问题B21 和B22 ，它们的最优解为
B21 : x1 = 5.44, x2 = 1.00, z22 = 308
B22 无可行解。
将B21, B22 剪枝。
于是可以断定原问题的最优解为：
*
x1 = 4, x2 = 2, z = 340
从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的整数规划问题称为问题 A，将与它相应的线性规划问题称为问题B 。
（i）解问题 B 可能得到以下情况之一：
（a）B 没有可行解，这时 A 也没有可行解，则停止．
（b） B 有最优解，并符合问题 A 的整数条件， B 的最优解即为 A 的最优解，则停止。
（c）B 有最优解，但不符合问题 A 的整数条件，记它的目标函数值为z 。
（ii）用观察法找问题 A 的一个整数可行解，一般可取xj = 0, j = 1, … , n ，试探，求得其目标函数值，并记作z 。以 z * 表示问题 A 的最优目标函数值；这时有
*
z ≤ z ≤ z进行迭代。
第一步：分枝，在B 的最优解中任选一个不符合整数条件的变量xj ，其值为 bj ，以[bj ] 表示小于bj 的最大整数。构造两个约束条件
xj ≤ [bj ] 和 xj ≥ [bj ] + 1
将这两个约束条件，分别加入问题B ，求两个后继规划问题B1 和B2 。不考虑整数条件求解这两个后继问题。
定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z 。从已符合整数条件的各分支中， 找出目标函数值为最大者作为新的下界z ，若无作用 z 不变。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了。若大于 z ，且不符合整数条件，则重复第一步骤。一直到最后得到
z* = z 为止。得最优整数解x , j = 1, … , n 。
§3 0 −1 型整数规划
0 −1 型整数规划是整数规划中的特殊情形，它的变量xj 仅取值 0 或 1。这时xj 称为0 −1 变量，或称二进制变量。xj 仅取值 0 或 1 这个条件可由下述约束条件：
0 ≤ xj ≤ 1，整数
-18-
所代替，是和一般整数规划的约束条件形式一致的。在实际问题中， 如果引入 0 −1 变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0 −1 变量的实际问题，再研究解法。
3.1 引入0 −1 变量的实际问题
3.1.1 投资场所的选定——相互排斥的计划
例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置（点） Ai (i = 1,2, … ,7) 可供选择。规定
在东区。由 A1, A2, A3 三个点中至多选两个；
在西区。由 A4, A5 两个点中至少选一个；
在南区，由 A6, A7 两个点中至少选一个。
如选用 Ai 点，设备投资估计为bi 元，每年可获利润估计为ci 元，但投资总额不能超过B 元。问应选择哪几个点可使年利润为最大？
解题时先引入0 −1 变量xi (i = 1,2, … ,7)令
i l0， 当Ai点没被选中. , , ,于是问题可列写成：
xi = 0或1
3.1.2 相互排斥的约束条件
有两个相互排斥的约束条件
5x1 + 4x2 ≤ 24 或 7x1 + 3x2 ≤ 45 。
为了统一在一个问题中，引入0 −1 变量y ，则上述约束条件可改写为：
其中M 是充分大的数。
约束条件
x1 = 0 或 500 ≤ x1 ≤ 800可改写为
-19-
如果有m 个互相排斥的约束条件：
ai1x1 + … + ainxn ≤ bi i = 1,2, … , m
为了保证这m 个约束条件只有一个起作用，我们引入m 个 0 −1 变量yi (i = 1,2, … , m)和一个充分大的常数M ，而下面这一组m + 1 个约束条件
ai1x1 + + ainxn ≤ bi + yiM i = 1,2, … , m （ 1）
y1 + + ym = m −1 （2）
就合于上述的要求。这是因为，由于（2），m 个yi 中只有一个能取 0 值，设 yi* = 0 ，代入（1），就只有i = i * 的约束条件起作用，而别的式子都是多余的。
3.1.3 关于固定费用的问题（Fixed Cost Problem）
在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。
例 5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令
xj 表示采用第j 种方式时的产量；
cj 表示采用第j 种方式时每件产品的变动成本；
kj 表示采用第j 种方式时的固定成本。
为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为
cj xj j = 1,2,3 .
在构成目标函数时，为了统一在一个问题中讨论，现引入0 −1变量 yj ，令
yj ，式即，x，时. （3）
于是目标函数
min z = (k1y1 + c1x1 ) + (k2 y2 + c2 x2 ) + (k3y3 + c3x3 )
（3）式这个规定可表为下述 3 个线性约束条件：
yj ε ≤ xj ≤ yj M , j = 1,2,3 （4）
其中 ε 是一个充分小的正常数，M 是个充分大的正常数。（4）式说明，当xj > 0 时yj必须为 1；当 xj = 0 时只有yj 为 0 时才有意义，所以（4）式完全可以代替（3）式。
3.2 0 −1型整数规划解法之一（过滤隐枚举法）
解0 −1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为 0 或 1 的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2n 个组合。对于变量个数n 较大（例如n > 100 ），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对
-20-
有些问题隐枚举法并不适用，所以有时穷举法还是必要的。
下面举例说明一种解0 −1型整数规划的隐枚举法。
例 6 Max z = 3x1 − 2x2 + 5x3
求解思路及改进措施：
（i） 先试探性求一个可行解，易看出(x1, x2, x3 ) = (1,0,0) 满足约束条件，故为一个可行解，且z = 3 。
（ii） 因为是求极大值问题，故求最优解时，凡是目标值z < 3 的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：
（iii） 改进过滤条件。
（iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z 大的组合，这样可提前抬高过滤门槛，以减少计算量。
§4 蒙特卡洛法（随机取样法）
前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。
然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然， 当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。
例 7 已知非线性整数规划为：
− 8x1 − 2x2 − 3x3 − x4 − 2x5
如果用显枚举法试探，共需计算(100)5 = 1010 个点，其计算量非常之大。然而应用蒙特卡洛去随机计算106 个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？
下面就分析随机取样采集106 个点计算时，应用概率理论来估计一下可信度。
不失一般性，假定一个整数规划的最优点不是孤立的奇点。
假设目标函数落在高值区的概率分别为 0.01 ，0.00001，则当计算106 个点后，有
-21-
任一个点能落在高值区的概率分别为
1 - 0.991000000 ≈ 0.99…99(100多位），
1- 0.999991000000 ≈ 0.999954602 。
解 （i）首先编写 M 文件 mente.m 定义目标函数 f 和约束向量函数 g，程序如下：
function [f,g]=mengte(x);
f=x(1)2+x(2)2+3x(3)2+4*x(4)2+2x(5)-8x(1)-2x(2)-3x(3)-… x(4)-2x(5);
g=[sum(x)-400
x(1)+2x(2)+2x(3)+x(4)+6x(5)-800 2x(1)+x(2)+6x(3)-200
x(3)+x(4)+5x(5)-200];
（ii）编写M文件mainint.m如下求问题的解： rand(‘state’,sum(clock));
p0=0;
tic
for i=1:10^6
x=99*rand(5,1);
x1=floor(x);x2=ceil(x);
[f,g]=mengte(x1); if sum(g<=0)==4
if p0<=f
x0=x1;p0=f; end
end
[f,g]=mengte(x2); if sum(g<=0)==4
if p0<=f
x0=x2;p0=f;
end end
end
x0,p0
toc
本题可以使用LINGO软件求得精确的全局最有解，程序如下：
model:
sets:
row/1…4/:b;
col/1…5/:c1,c2,x;
link(row,col):a;
endsets
data:
c1=1,1,3,4,2;
c2=-8,-2,-3,-1,-2;
a=1 1 1 1 1
1 2 2 1 6
2 1 6 0 0
-22-
0 0 1 1 5;
b=400,800,200,200; enddata
max=@sum(col:c1x^2+c2x);
@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));
@for(col:@gin(x));
@for(col:@bnd(0,x,99));
end
§5 指派问题的计算机求解
整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题，无法直接利用 Matlab 的函数，必须利用 Matlab 编程实现分枝定界解法和割平面解法。但对于指派问题等0 -1 整数规划问题，可以直接利用 Matlab 的函数 bintprog 进行求解。
例 8 求解下列指派问题，已知指派矩阵为
解：编写 Matlab 程序如下：
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5
8 4 2 3 5;9 10 6 9 10];
c=c(😃;
a=zeros(10,25);
for i=1:5
a(i,(i-1)5+1:5i)=1;
a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,y]=bintprog(c,[],[],a,b);
x=reshape(x,[5,5]),y
求得最优指派方案为x15 = x23 = x32 = x44 = x51 = 1，最优值为 21。
求解的 LINGO 程序如下：
model:
sets:
var/1…5/;
link(var,var):c,x;
endsets
data:
c=3 8 2 10 3
8 7 2 9 7
6 4 2 7 5
8 4 2 3 5
9 10 6 9 10;
enddata
min=@sum(link:c*x);
@for(var(i):@sum(var(j):x(i,j))=1);
@for(var(j):@sum(var(i):x(i,j))=1);
-23-
@for(link:@bin(x));
end
§6 生产与销售计划问题
6.1 问题实例
例 9 某公司用两种原油（ A 和B ）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油的最低比例分别为 50％和 60％，每吨售价分别为 4800 元和 5600 元。该公司现有原油 A 和B 的库存量分别为 500 吨和 1000 吨，还可以从市场上买到不超过 1500吨的原油 A 。原油 A 的市场价为：购买量不超过 500 吨时的单价为 10000 元/吨；购买量超过 500 吨单不超过 1000 吨时，超过 500 吨的部分 8000 元/吨；购买量超过 1000 吨时，超过 1000 吨的部分 6000 元/吨。该公司应如何安排原油的采购和加工。
6.2 建立模型
（1）问题分析
安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油 A的采购价，利润为销售汽油的收入与购买原油 A 的支出之差。这里的难点在于原油 A 的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。
（2）模型建立
设原油 A 的购买量为x （单位：吨）。根据题目所给数据， 采购的支出c(x) 可表示为如下的分段线性函数（以下价格以千元/吨为单位）：
设原油 A 用于生产甲、乙两种汽油的数量分别为x11 和x12 ，原油 B 用于生产甲、乙两种汽油的数量分别为x21 和x22 ，则总的收入为4.8(x11 + x21 ) + 5.6(x12 + x22 )（千元）。于是本例的目标函数（利润）为
max z = 4.8(x11 + x21 ) + 5.6(x12 + x22 ) - c(x) （6）
约束条件包括加工两种汽油用的原油 A 、原油 B 库存量的限制，原油 A 购买量的限制，以及两种汽油含原油 A 的比例限制，它们表示为
x11 + x12 ≤ 500 + x （7）
x21 + x22 ≤ 1000 （ 8）
x ≤ 1500 （9）
（10）
（11）
x11 , x12 , x21 , x22 , x ≥ 0 （12）
由于（5）式中的c(x) 不是线性函数，（5）~（12）给出的是一个非线性规划，而且，对于这样用分段函数定义的c(x) ，一般的非线性规划软件也难以输入和求解。能不能想办法将该模型化简，从而用现成的软件求解呢？
-24-
6.3 求解模型
下面介绍 3 种解法
（1）解法一
一个自然的想法是将原油 A 的采购量x 分解为三个量，即用 x1, x2, x3 分别表示以价格 10 千元/ 吨、 8 千元/ 吨、 6 千元/ 吨采购的原 油 A 的 吨 数 ， 总支出为c(x) = 10x1 + 8x2 + 6x3 ，且
x = x1 + x2 + x3 （13）
这时目标函数（6）变为线性函数：
max z = 4.8(x11 + x21 ) + 5.6(x12 + x22 ) − (10x1 + 8x2 + 6x3 ) （14）
应该注意到，只有当以 10 千元/吨的价格购买x1 = 500 （吨）时，才能以 8 千元/吨的价格购买x2 (> 0) ，这个条件可以表示为
(x1 − 500)x2 = 0 （15）同理，只有当以 8 千元/吨的价格购买x2 = 500 （吨）时，才能以 6 千元/吨的价格购买x3 (> 0) ，于是
(x2 − 500)x3 = 0 （16）
此外，x1 , x2 , x3 的取值范围是
0 ≤ x1 , x2 , x3 ≤ 500 （17）
由于有非线性约束（15）、（16），因而（7）～（17）构成非线性规划模型。将该模型输入 LINGO 软件如下：
model:
sets:
var1/1…4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22;
var2/1…3/:x,c;
endsets
max=4.8*(y(1)+y(2))+5.6*(y(3)+y(4))-@sum(var2:cx);
y(1)+y(3)<@sum(var2:x)+500;
y(2)+y(4)<1000;
0.5(y(1)-y(2))>0;
0.4y(3)-0.6y(4)>0;
(x(1)-500)*x(2)=0;
(x(2)-500)*x(3)=0;
@for(var2:@bnd(0,x,500));
data:
c=10 8 6;
enddata
end
可以用菜单命令“LINGO|Options”在“Global Solver”选项卡上启动全局优化选型，并运行上述程序求得全局最有解：购买 1000 吨原油 A，与库存的 500 吨原油 A 和1000 吨原油B 一起，共生产 2500 吨汽油乙，利润为 5000（千元）。
（2）解法二
引入 0－1 变量将（15）和（16）转化为线性约束。
令z1 = 1 ，z2 = 1 ，z3 = 1分别表示以 10 千元/吨、8 千元/吨、6 千元/吨的价格采购原油 A ，则约束（15）和（16）可以替换为
-25-
500z2 ≤ x1 ≤ 500z1 ， （ 18）
500z3 ≤ x2 ≤ 500z2 ， （ 19）
x3 ≤ 500z3 ， （20）
z1 , z2 , z3 = 0 或 1 （21）
式（7）～（14），式（17）～（21）构成混合整数线性规划模型，将它输入 LINGO 软件如下：
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:cx);
y(1)+y(3)<@sum(var2:x)+500;
y(2)+y(4)<1000;
0.5(y(1)-y(2))>0;
0.4y(3)-0.6y(4)>0;
@for(var1(i) |i #lt# 3:500z(i+1)<x(i);x(i)<500z(i)); x(3)<500*z(3);
@for(var2:@bin(z));
@for(var2:@bnd(0,x,500));
data:
c=10 8 6;
enddata
end
（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 ) + w2 c(b2 ) 。 同 样 ， 当 x 属 于 第 2 个 小 区 间 [b2, b3 ] 时 ， x = w2b2 + w3b3 ，w2 + w3 = 1 ，w2 , w3 ≥ 0 ，c(x) = w2 c(b2 ) + w3c(b3 ) 。当 x 属于第3 个 小 区 间 [b3, b4 ] 时 ， x = w3b3 + w4b4 ， w3 + w4 = 1 ， w3 , w4 ≥ 0 ， c(x) = w3c(b3 ) + w4 c(b4 ) 。为了表示 x 在哪个小区间，引入 0-1 变量zk (k = 1,2,3) ，当x 在第k 个小区间时， zk = 1 ，否则，zk = 0 。这样， w1, w2, w3, w4, z1, z2, z3 应满
-26-
足
w1 ≤ z1 ， w2 ≤ z1 + z2 ，w3 ≤ z2 + z3 ， w4 ≤ z3 （22）
w1 + w2 + w3 + w4 = 1 ，wk ≥ 0 （ k = 1,2,3,4 ） （23）
z1 + z2 + z3 = 1 ，z1 , z2 , z3 = 0 或1 （24）
此时x 和c(x) 可以统一地表示为
x = w1b1 + w2b2 + w3b3 + w4b4 = 500w2 +1000w3 +1500w4 （25）
式（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:cw);
y(1)+y(3)<@sum(var:bw)+500;
y(2)+y(4)<1000;
0.5*(y(1)-y(2))>0;
0.4y(3)-0.6y(4)>0;
w(1)<z(1);
@for(var(i) |i #ne# 1:w(i)<z(i-1)+z(i));
@sum(var:z)=1;
@sum(var:w)=1;
@for(var:@bin(z));
End
注：这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第2和第3种解法，第3种解法更具一般性，其做法如下。
设一个n 段线性函数f (x) 的分点为b1 ≤ … ≤ bn ≤ bn+1 ，引入 wk 将x 和f (x) 表示为
wk 和0-1变量zk 满足
w1 ≤ z1 ， w2 ≤ z1 + z2 ， … , wn ≤ zn−1 + zn ， wn+1 ≤ zn （27）
-27-
z1 + z2 + … + zn = 1 ， zk = 0 或1 （28）
w1 + w2 + … + wn+1 = 1 ， wk ≥ 0 （ k = 1,2, … , n +1 ） （29）
习 题 二
用分枝定界法解：
Max z = x1 + x2
整数试将下述非线性的0 - 1规划问题转换成线性的0 - 1规划问题max z = x1 + x1x2 - x3
某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油，使总的钻探费用为最小。若 10 个井位的代号为s1 , s2 , … , s10 ，相应的钻探费用为c1 , c2 , … , c10 ，并且井位选择上要满足下列限制条件：
（1） 或选择s1 和s7 ，或选择钻探 s9 ；
（2） 选择了s3 或s4 就不能选s5 ，或反过来也一样；
（3） 在s5, s6, s7, s8 中最多只能选两个；试建立这个问题的整数规划模型。
4．有一条河流由于河床泥沙淤结，每当上游发生洪水时，就会破堤淹没两岸，造成人员和财产的损失，为减少总的损失，人们采取破堤泄洪的方法，图 2 是该河流一岸区域的信息示意图，在该区域边界上有很高的山，使该区域成为封闭区域。区域内又分成十五个小区，每个小区内标有三个数字，分别表示该区域的海拔高度 h(m) 、面积S(km2 ) 和被完全淹没时土地、房屋和财产等损失总数k （百万元），我们假设
（a）各小区间有相对高度为 1.2m 的小堤相互隔离，例如第一区和第二区之间事实上有海拔 5.2m 小堤。
（b）当洪水淹没一个小区且洪水高于该小区高度pm时，该小区的损失f(k, p) 为该小区的k 和p 的函数：
（c）假设决堤口，可选在大堤或小堤的任何地方，决堤口的数量不受限制，但已经决口，就不能再补合，从河流经大堤决口流入小区的洪水量按决口数成比例分配，如在小区之间小堤开一决口，则假设该两小区之间的这段小堤不复存在，若水位高过小堤，则将自动向邻近最低的小区泄洪，若这样的小区有多块时，则平均泄洪。
求
-28-
（1）整个区域全部受损失的最小洪水量Q 。
（2）当洪水量为Q /6 ，Q /3 时，分别制定泄洪方案，使总损失最小（在一种方案中，决堤同时进行），并计算出该方案的损失数。
图 2 河流一岸区域示意图
表 1 校址选择数据
备选校址 B1 B2 B3 B4 B5 B6
覆盖的居民小区 1 , 5
7 1 , 2
5 , 8 1 , 3 ,
5 A A
A8 A3 , A6 A A
A8
5 ．某市为方便小学生上学，拟在新建的 8 个居民小区 A1 , A2 , … , A8 增设若干所-29-
小学，经过论证知备选校址有:B1 , B2 , … , B6 ,它们能够覆盖的居民小区如表 1。
试建立一个数学模型，确定出最小个数的建校地址，使其能覆盖所有的居民小区。
6 ．某公司新购置了某种设备 6 台，欲分配给下属的 4 个企业，已知各企业获得这种设备后年创利润如表 2 所示，单位为千万元。问应如何分配这些设备能使年创总利润最大，最大利润是多少？
表 2 各企业获得设备的年创利润数
企业设备 甲 乙 丙 丁
1 4 2 3 4
2 6 4 5 5
3 7 6 7 6
4 7 8 8 6
5 7 9 8 6
6 7 10 8 6
7 ．有一场由四个项目(高低杠、平衡木、跳马、自由体操) 组成的女子体操团体赛，赛程规定：每个队至多允许 10 名运动员参赛，每一个项目可以有 6 名选手参加。每个选手参赛的成绩评分从高到低依次为：10；9.9；9.8；…；0.1；0。每个代表队的总分是参赛选手所得总分之和，总分最多的代表队为优胜者。此外， 还规定每个运动员只能参加全能比赛(四项全参加) 与单项比赛这两类中的一类，参加单项比赛的每个运动员至多只能参加三个单项。每个队应有 4 人参加全能比赛，其余运动员参加单项比赛。
表 3 运动员各项目得分及概率分布表
运动员项目
1
2
3
4
5
高低杠 8.4~0.15
9.5~0.5
9.2~0.25
9.4~0.1 9.3~0.1
9.5~0.1
9.6~0.6
9.8~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
平衡木 8.4~0.1
8.8~0.2
9.0~0.6
10~0.1 8.4~0.15
9.0~0.5
9.2~0.25
9.4~0.1 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.2~0.1
9.4~0.6
9.7~0.2
跳马 9.1~0.1
9.3~0.1
9.5~0.6
9.8~0.2 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.4~0.1
9.5~0.5
9.7~0.3 8.3~0.1
8.7~0.1
8.9~0.6
9.3~0.2
自由体操 8.7~0.1
8.9~0.2
9.1~0.6
9.9~0.1 8.9~0.1
9.1~0.1
9.3~0.6
9.6~0.2 9.5~0.1
9.7~0.1
9.8~0.6
10~0.2 8.4~0.1
8.8~0.2
9.0~0.6
10~0.1 9.4~0.1
9.6~0.1
9.7~0.6
9.9~0.2
续表 3 运动员各项目得分及概率分布表
运动员项目
6
7
8
9
10
-30-
高低杠 9.4~0.1
9.6~0.1
9.7~0.6
9.9~0.2 9.5~0.1
9.7~0.1
9.8~0.6
10~0.2 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.7~0.1 8.4~0.1 8.8~0.05 8.4~0.1 8.1~0.1
8.9~0.2 8.8~0.2 9.2~`0.05 8.8~0.1 9.1~0.5
9.1~0.6 9.0~0.6 9.8~0.5 9.2~0.6 9.3~0.3
9.9~0.1 10~0.1 10~0.4 9.8~0.2 9.5~0.1
跳马 8.5~0.1 8.3~0.1 8.7~0.1 8.4~0.1 8.2~0.1
8.7~0.1 8.7~0.1 8.9~0.2 8.8~0.2 9.2~0.5
8.9~0.5 8.9~0.6 9.1~0.6 9.0~0.6 9.4~0.3
9.1~0.3 9.3~0.2 9.9~0.1 10~0.1 9.6~0.1
自由体操 8.4~0.15 8.4~0.1 8.2~0.1 9.3~0.1 9.1~0.1
9.5~0.5 8.8~0.1 9.3~0.5 9.5~0.1 9.3~0.1
9.2~0.25 9.2~0.6 9.5~0.3 9.7~0.5 9.5~0.6
9.4~0.1 9.8~0.2 9.8~0.1 9.9~0.3 9.8~0.2
现某代表队的教练已经对其所带领的 10 名运动员参加各个项目的成绩进行了大量测试，教练发现每个运动员在每个单项上的成绩稳定在 4 个得分上(见表 3) ，她们得到这些成绩的相应概率也由统计得出(见表中第二个数据。例如：8.4～0.15 表示取得8.4 分的概率为 0.15)。试解答以下问题：
（1）每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高；每个选手的各单项得分按均值估算，在此前提下，请为该队排出一个出场阵容，使该队团体总分尽可能高。
（2）若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计为不少于 236.2 分，该队为了夺冠应排出怎样的阵容？以该阵容出战，其夺冠的前景如何？得分前景（即期望值）又如何？它有 90％的把握战胜怎样水平的对手？
