(1,01) √、、、√3x-2x2+53≥8 (1,1,1) 6 从而得最优解(x1,x2,x3)=(10,1),最优值z=8 §4蒙特卡洛法(随机取样法) 前面介绍的常用的整数规划求解方法,主要是针对线性整数规划而言,而对于非线 性整数规划目前尚未有一种成熟而有效的求解方法,因为非线性规划本身的通用有效解 法尚未找到,更何况是非线性整数规划。 然而,尽管整数规划由于限制变量为整数而增加了难度:然而又由于整数解是有限 个,于是为枚举法提供了方便。当然,当自变量维数很大和取值范围很宽情况下,企图 用显枚举法(即穷举法)计算出最优值是不现实的,但是应用概率理论可以证明,在 定的计算量的情况下,完全可以得出一个满意解。 例7已知非线性整数规划为 Max ==x1+x2+3x3+44+2x5 x2 0≤x1≤99(i=1,…,5) x1+x2+x3+x4+x5≤400 t.{x1+2x2+2x3+x4+6x5≤800 2x1+x2+6x3≤200 x3+x4+5x5≤200 对该题,目前尚无有效方法求出准确解。如果用显枚举法试探,共需计算 (100)5=100个点,其计算量非常之大。然而应用蒙特卡洛去随机计算10°个点,便可 找到满意解,那么这种方法的可信度究竟怎样呢? 下面就分析随机取样采集10°个点计算时,应用概率理论来估计一下可信度。 不失一般性,假定一个整数规划的最优点不是孤立的奇点。 假设目标函数落在高值区的概率分别为001,00000,则当计算10°个点后,有 任一个点能落在高值区的概率分别为 1-099000999100多位), 1-0.9999900999954602 解(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(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800; (3)=2*x(1)+x(2)+6*x(3)-200; (4)=x(3)+x(4)+5*x(5)-200-17- (1,1,0) 1  (1,0,1) 8 √ √ √ √ √ 3x1 − 2x2 + 53  8 (1,1,1) 6  (0,1,1) 3  从而得最优解 ( , , ) (1,0,1) * 3 * 2 * x1 x x = ，最优值 8 * 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 − − − − − = + + + + s.t.          + +  + +  + + + +  + + + +    = 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  对该题，目前尚无有效方法求出准确解。如果用显枚举法试探，共需计算 5 10 (100) = 10 个点，其计算量非常之大。然而应用蒙特卡洛去随机计算 6 10 个点，便可 找到满意解，那么这种方法的可信度究竟怎样呢？ 下面就分析随机取样采集 6 10 个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。 假设目标函数落在高值区的概率分别为 0.01，0.00001，则当计算 6 10 个点后，有 任一个点能落在高值区的概率分别为 1− 0.991000000  0.9999(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(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;