有些问题隐枚举法并不适用，所以有时穷举法还是必要的。
下面举例说明一种解0?1型整数规划的隐枚举法。 例6 Maxz=3x1?2x2+5x3
?x1+2x2?x3≤2?x+4x+x≤4123??
?x1+x2≤3
?4x+x≤6
3
?2??x1,x2,x3=0或1
求解思路及改进措施：
（i） 先试探性求一个可行解，易看出(x1,x2,x3)=(1,0,0)满足约束条件，故为一个可行解，且z=3。
（ii） 因为是求极大值问题，故求最优解时，凡是目标值z<3的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：
（iii） 改进过滤条件。 （iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z大的组合，这样可提前抬高过滤门槛，以减少计算量。
§4 蒙特卡洛法（随机取样法）
前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。
然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。
例7 已知非线性整数规划为：
2222
Max z=x12+x2+3x3+4x4+2x5?8x1?2x2?3x3?x4?2x5
?0≤xi≤99(i=1,L,5)?x+x+x+x+x≤40012345??
?x1+2x2+2x3+x4+6x5≤800 ?2x+x+6x≤200
23
?1??x3+x4+5x5≤200
如果用显枚举法试探，共需计算(100)=10个点，其计算量非常之大。然而应用蒙特卡洛去随机计算10个点，便可找到满意解，那么这种方法的可信度究竟怎样
呢？
下面就分析随机取样采集10个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。
假设目标函数落在高值区的概率分别为0.01，0.00001，则当计算10个点后，有任一个点能落在高值区的概率分别为
-21-
6
6
6
5
10
1?0.991000000≈0.99L99(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=[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 0 0 1 1 5;
b=400,800,200,200;
-22-
enddata
max=@sum(col:c1*x^2+c2*x);
@for(row(i):@sum(col(j):a(i,j)*x(j)) @for(col:@bnd(0,x,99)); end §5 指派问题的计算机求解 整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划问题，无法直接利用Matlab的函数，必须利用Matlab编程实现分枝定界解法和割平面解法。但对于指派问题等0?1整数规划问题，可以直接利用Matlab的函数bintprog进行求解。 例8 求解下列指派问题，已知指派矩阵为 ?382103?? ? 87297? ?? 64 275? ??84235? ??9106910??? 解：编写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。求解的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); @for(link:@bin(x)); end -23- §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)可表示为如下的分段线性函数（以下价格以千元/吨为单位）： 0≤x≤500?10x, ? c(x)=?1000+8x,500≤x≤1000 （5） ?3000+6x,1000≤x≤1500? 设原油A用于生产甲、乙两种汽油的数量分别为x11和x12，原油B用于生产甲、乙两种汽油的数量分别为x21和x22，则总的收入为4.8(x11+x21)+5.6(x12+x22)（千 元）。于是本例的目标函数（利润）为 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） x11 ≥0.5 （10） x11+x21 x12 ≥0.6 （11） x12+x22 x11,x12,x21,x22,x≥0 （12） 由于（5）式中的c(x)不是线性函数，（5）~（12）给出的是一个非线性规划，而且，对于这样用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解。能 不能想办法将该模型化简，从而用现成的软件求解呢？ 6.3 求解模型 下面介绍3种解法 （1）解法一 -24- max 一个自然的想法是将原油A的采购量x分解为三个量，即用x1,x2,x3分别表示以价格10千元/吨、8千元/吨、6千元/吨采购的原油A的吨数，总支出为c(x)=10x1+8x2+6x3，且 x=x1+x2+x3 （13） 这时目标函数（6）变为线性函数： maxz=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:c*x); y(1)+y(3)<@sum(var2:x)+500; y(2)+y(4)<1000; 0.5*(y(1)-y(2))>0; 0.4*y(3)-0.6*y(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）可以替换为 500z2≤x1≤500z1， （18） 500z3≤x2≤500z2， （19） -25-