有些问题隐枚举法并不适用,所以有时穷举法还是必要的 下面举例说明一种解0-1型整数规划的隐枚举法。 例6Maxz=3x1-2x,+5 x2-x3≤2 x1+4x2+x3≤4 4x,+x2≤6 或1 求解思路及改进措施 ()先试探性求一个可行解,易看出(x1,x2,x3)=(1,0,0)满足约束条件,故为 个可行解,且z=3。 (ⅱi)因为是求极大值问题,故求最优解时,凡是目标值z<3的解不必检验是否 满足约束条件即可删除,因它肯定不是最优解,于是应增加一个约束条件(目标值下界) (ⅲi)改进过滤条件。 (ⅳv)由于对每个组合首先计算目标值以验证过滤条件,故应优先计算目标值z大 的组合,这样可提前抬高过滤门槛,以减少计算量。 §4蒙特卡洛法(随机取样法) 前面介绍的常用的整数规划求解方法,主要是针对线性整数规划而言,而对于非线 性整数规划目前尚未有一种成熟而准确的求解方法,因为非线性规划本身的通用有效解 法尚未找到,更何况是非线性整数规划。 然而,尽管整数规划由于限制变量为整数而增加了难度;然而又由于整数解是有限 个,于是为枚举法提供了方便。当然,当自变量维数很大和取值范围很宽情况下,企图 用显枚举法(即穷举法)计算出最优值是不现实的,但是应用概率理论可以证明,在 定的计算量的情况下,完全可以得出一个满意解 例7已知非线性整数规划为 Max=x2+x2+3x2+4x2+2x3 0≤xs99(=1;5) x1+x2+x3+x4+x5≤400 x1+2x2+2x3+x4+6x5≤800 2x1+x2+6x3≤200 xs≤20 00 如果用显枚举法试探,共需计算(1005=100个点,其计算量非常之大。然而应 用蒙特卡洛去随机计算10°个点,便可找到满意解,那么这种方法的可信度究竟怎样 ? 下面就分析随机取样采集10°个点计算时,应用概率理论来估计一下可信度。 不失一般性,假定一个整数规划的最优点不是孤立的奇点 假设目标函数落在高值区的概率分别为001,00001,则当计算10个点后,有
-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.9900.99…99(100多位), 1-0.99990009954602。 解(i)首先编写M文件 mente. m定义目标函数f和约束向量函数g,程序如下 function [f, g]=mengte(x)i 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)) tic x=99*rand(5,1) xl=floor(x): x2=ceil(x) If, g]=mengte (x1) if sum(g<=0)==4 if pO< end end If, g]=mengte(x2) if sum (g<=0)==4 x0=x2;p0=f; end 本题可以使用 LINGO软件求得精确的全局最有解,程序如下: row/1..4/:b; co1/1..5/:c1,c2,x link(row, col): ai endsets c1=1,1,3,4,2 a=11111 12216 21600
-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