(数学建模教材)2第二章整数规划 下载本文

有些问题隐枚举法并不适用,所以有时穷举法还是必要的。

下面举例说明一种解 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-