内容发布更新时间 : 2024/12/24 9:09:56星期一 下面是文章的全部内容请认真阅读。
有些问题隐枚举法并不适用，所以有时穷举法还是必要的。
下面举例说明一种解 0 ?1型整数规划的隐枚举法。 例 6 Max z ? 3x1 ? 2x2 ? 5x3
求解思路及改进措施：
（i） 先试探性求一个可行解，易看出 ( x1 , x2 , x3 ) ? (1,0,0) 满足约束条件，故为一 个可行解，且 z ? 3 。
（ii） 因为是求极大值问题，故求最优解时，凡是目标值 z ? 3 的解不必检验是否 满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：
（iii） 改进过滤条件。 （iv） 由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值 z 大 的组合，这样可提前抬高过滤门槛，以减少计算量。
§4 蒙特卡洛法（随机取样法）
前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线 性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解 法尚未找到，更何况是非线性整数规划。
然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限 个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图 用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一 定的计算量的情况下，完全可以得出一个满意解。
例 7 已知非线性整数规划为：
?x1 ? 2x2 ? x3 ? 2
?x 1 ? 4x 2 ? x 3 ? 4 ????x1 ? x2 ? 3 ?4x ? x ? 6 ??2 3 ??x1 , x2 , x3 ? 0或
Max z ? x 8x1 ? 2x2 ? 3x3 ? x4 ? 2x5 1 ? x 2 ? 3x 3 ? 4x 4 ? 2x 5 ? ?0 ? xi ? 99 (i ? 1,L,5) ?x 1 ? x 2 ? x 3 ? x 4 ? x 5 ? 400 ???x? 2x? 2x? x? 6x? 800 ?1 2 3 4 5 ?2x ? x ? 6x ? 200
3
??1 2 ??x3 ? x4 ? 5x5 ? 200
如果用显枚举法试探，共需计算 (100)5 ? 1010 个点，其计算量非常之大。然而应
用蒙特卡洛去随机计算10个点，便可找到满意解，那么这种方法的可信度究竟怎样 呢？
下面就分析随机取样采集10个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。
假设目标函数落在高值区的概率分别为 0.01，0.00001，则当计算10个点后，有 任一个点能落在高值区的概率分别为
-21-
6
6
6
2 2 2 2 2
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; 1 2 2 1 6 a=1 1 1 1 1 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 求解下列指派问题，已知指派矩阵为 ?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?? 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) 可表示 为如下的分段线性函数（以下价格以千元/吨为单位）： ?10x, 0 ? x ? 500 ?? c(x) ? ?1000 ? 8x, 500 ? x ? 1000 ?3000 ?? 6x, 1000 ? x ? 1500 ?（5） 设原油 A 用于生产甲、乙两种汽油的数量分别为 x11 和 x12 ，原油 B 用于生产甲、 乙两种汽油的数量分别为 x21 和 x22 ，则总的收入为 4.8(x11 ? x21 ) ? 5.6(x12 ? x22 )（千 元）。于是本例的目标函数（利润）为 （6） max z ? 4.8(x11 ? x21 ) ? 5.6(x12 ? x22 ) ? c(x) 约束条件包括加工两种汽油用的原油 A 、原油 B 库存量的限制，原油 A 购买量的 限制，以及两种汽油含原油 A 的比例限制，它们表示为 x11 ? x12 ? 500 ? x （7） （8） x21 ? x22 ? 1000 （9） x ? 1500 x11 ? 0.5 x11 ? x21 （10） （11） x12 ? 0.6 x12 ? x22 （12） x11 , x12 , x21 , x22 , x ? 0 由于（5）式中的 c(x) 不是线性函数，（5）~（12）给出的是一个非线性规划，而 且，对于这样用分段函数定义的 c(x) ，一般的非线性规划软件也难以输入和求解。能 不能想办法将该模型化简，从而用现成的软件求解呢？ 6.3 求解模型 下面介绍 3 种解法 （1）解法一 -24- 一个自然的想法是将原油 A 的采购量 x 分解为三个量，即用 x1 , x2 , x3 分别表示以 价格 10 千元 / 吨、 8 千元 / 吨、 6 千元 / 吨采购的原 油 A 的 吨 数 ， 总支出为 c(x) ? 10x1 ? 8x2 ? 6x3 ，且 x ? x1 ? x2 ? x3 这时目标函数（6）变为线性函数： （13） （14） max z ? 4.8(x11 ? x21 ) ? 5.6(x12 ? x22 ) ? (10x1 ? 8x2 ? 6x3 ) 应该注意到，只有当以 10 千元/吨的价格购买 x1 ? 500 （吨）时，才能以 8 千元/ 吨的价格购买 x2 (? 0) ，这个条件可以表示为 (x1 ? 500)x2 ? 0 （15） 同理，只有当以 8 千元/吨的价格购买 x2 ? 500 （吨）时，才能以 6 千元/吨的价格购买 x3 (? 0) ，于是 (x2 ? 500)x3 ? 0 此外， x1 , x2 , x3 的取值范围是 0 ? x1 , x2 , x3 ? 500 （16） （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 ， 500z3 ? x2 ? 500z2 ， （18） （19） -25-