有些问题隐枚举法并不适用，所以有时穷举法还是必要的。 下面举例说明一种解0-1型整数规划的隐枚举法。 例6Max三=3x,-2x2+5x3 [x1+2x2-x3≤2 x1+4x2+x3≤4 +x≤3 4x2+x3≤6 x,2,x3=0或1 求解思路及改进措施： ()先试探性求一个可行解，易看出(x,x,x,)=(1,0.0)满足约束条件，故为 个可行解，且 (目标值下界) (v)由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值：大 的组合，这样可提前拾高过滤门槛，以减少计算量。 §4蒙特卡洛 (随 取样法 法 法尚未找 是非线性救 尽管整数规划由于限制变量为整数而增加了难度：然而又由于整数解是有限 个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图 用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在 定的计算最的情况下，完全可以得出一个满意解。 例7已知非线性整数规划为： Max=x+x3x+4x2+2x2 -8x,-2x,-3x,-xa-2x 0≤x,≤991=1.，5 x+x2+x3+x4+x5≤400 x+2x2+2x3+x4+6x5≤800 2x1+x2+6x3≤200 3+x4+5x≤200 如果用显枚举法试探，共需计算(100)=100个点，其计算量非常之大。然而应 下面就分析随机取样采集1O个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是机立的奇点。 假设目标函数落在高值区的概率分别为0.01,0.00001，则当计算10°个点后，有 21
-21- 有些问题隐枚举法并不适用，所以有时穷举法还是必要的。 下面举例说明一种解0 −1型整数规划的隐枚举法。 例 6 Max 3 1 2 2 5 3 z = x − x + x ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ = + ≤ + ≤ + + ≤ + − ≤ , , 0 1 4 6 3 4 4 2 2 1 2 3 2 3 1 2 1 2 3 1 2 3 x x x 或 x x x x x x x x x x 求解思路及改进措施： （i） 先试探性求一个可行解，易看出( , , ) (1,0,0) x1 x2 x3 = 满足约束条件，故为一 个可行解，且 z = 3。 （ii） 因为是求极大值问题，故求最优解时，凡是目标值 z < 3的解不必检验是否 满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）： （iii） 改进过滤条件。 （iv）由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值 z 大 的组合，这样可提前抬高过滤门槛，以减少计算量。 §4 蒙特卡洛法（随机取样法） 前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线 性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解 法尚未找到，更何况是非线性整数规划。 然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限 个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图 用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一 定的计算量的情况下，完全可以得出一个满意解。 例 7 已知非线性整数规划为： 1 2 3 4 5 2 5 2 4 2 3 2 2 2 1 8 2 3 2 Max 3 4 2 x x x x x z x x x x x − − − − − = + + + + ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ + + ≤ + + ≤ + + + + ≤ + + + + ≤ ≤ ≤ = 5 200 2 6 200 2 2 6 800 400 0 99 ( 1, ,5) 3 4 5 1 2 3 1 2 3 4 5 1 2 3 4 5 x x x x x x x x x x x x x x x x x i i L 如果用显枚举法试探，共需计算 5 10 (100) = 10 个点，其计算量非常之大。然而应 用蒙特卡洛去随机计算 6 10 个点，便可找到满意解，那么这种方法的可信度究竟怎样 呢？ 下面就分析随机取样采集 6 10 个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。 假设目标函数落在高值区的概率分别为 0.01，0.00001，则当计算 6 10 个点后，有
任一个点能落在高值区的概率分别为 1-0.991000≈0.99.99100多位)， funetion mente.m定义目标函数f和约束向量函数g,程序如下 f,g) x(2)^2+3*x(3)^2+4*x(4)2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-. 5egow9Q。 400 (1 ot如下求题的解 0=0: tic fori=1:106 x=99*rand(5,1): xl=floor(x):x2=ceil(x) [f,g]-mengte(x1): 1fsum(80)=4 if po= 0=x1:p0=f end en 「f.gl=mengte(x2) if sum(8<=0)==4 if po<=f 0=x2:p0=f: end en x0,0 toc 本题可以使用LINGO软件求得精确的全局最有解，程序如下： mode 8i.4/:b endsets CI-1 1,3,4,2: 131,2 -22
-22- 任一个点能落在高值区的概率分别为 1− 0.991000000 ≈ 0.99L99(100多位）， 1 0.99999 0.999954602 1000000 − ≈ 。 解 （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=[sum(x)-400 x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800 2*x(1)+x(2)+6*x(3)-200 x(3)+x(4)+5*x(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