（3）式这个规定可表为下述3个线性约束条件：

yj??xj?yjM,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?10），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

下面举例说明一种解0?1型整数规划的隐枚举法。 例6Maxz?3x1?2x2?5x3

?x1?2x2?x3?2?x?4x?x?4123?? ?x1?x2?3?4x?x?63?2??x1,x2,x3?0或1求解思路及改进措施：

（i） 先试探性求一个可行解，易看出(x1,x2,x3)?(1,0,0)满足约束条件，故为一个可行解，且z?3。

（ii）因为是求极大值问题，故求最优解时，凡是目标值z?3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：

（iii）改进过滤条件。

（iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值大的组合，这样可提前抬高过滤门槛，以减少计算量。 §4 蒙特卡洛法（随机取样法）

前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。

然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。

例7 已知非线性整数规划为：

z

2222Max z?x12?x2?3x3?4x4?2x5 ?8x1?2x2?3x3?x4?2x5

?0?xi?99(i?1,?,5)?x?x?x?x?x?40012345???x1?2x2?2x3?x4?6x5?800 ?2x?x?6x?20023?1??x3?x4?5x5?200对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算

(100)5?1010个点，其计算量非常之大。然而应用蒙特卡洛去随机计算106个点，便可

找到满意解，那么这种方法的可信度究竟怎样呢？

下面就分析随机取样采集10个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。

假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算10个点后，有任一个点能落在高值区的概率分别为

661?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+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)... -x(4)-2*x(5); g(1)=sum(x)-400;

g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800; g(3)=2*x(1)+x(2)+6*x(3)-200; g(4)=x(3)+x(4)+5*x(5)-200;

（ii）编写如下程序求问题的解：

rand('state',sum(clock)); p0=0; tic

for i=1:10^5

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

§5 整数规划的计算机解法

整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等0?1整数规划问题，可以直接利用Matlab的函数bintprog进行求解。

例8 求解下列指派问题，已知指派矩阵为

?38?87??64??84??910210292267393?7??5? ?5?10??解：编写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:5*i)=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。

习 题 二

1. 用分枝定界法解：

Max z?x1?x2

951?x?x??114214?1? ??2x1?x2?3??x1,x2?0,x1,x2整数??2. 试将下述非线性的0?1规划问题转换成线性的0?1规划问题 maxz?x1?x1x2?x3

??2x1?3x2?x3?3 ?x?0或1，(j?1,2,3)?j3. 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费

用为最小。若10个井位的代号为s1,s2,?,s10，相应的钻探费用为c1,c2,?,c10，并且井位选择上要满足下列限制条件：

（1） 或选择s1和s7，或选择钻探s9；

（2） 选择了s3或s4就不能选s5，或反过来也一样；

（3） 在s5,s6,s7,s8中最多只能选两个；试建立这个问题的整数规划模型。