第13章 整数规划.docx
《第13章 整数规划.docx》由会员分享，可在线阅读，更多相关《第13章 整数规划.docx（18页珍藏版）》请在冰点文库上搜索。
第13章整数规划
第13章整数规划
本章通过分析应用问题建立数学模型并求解，学习掌握整数规划及其求解的分枝定界算法以及应用MATLAB求解。
加强从“模型的建立到求解”的数学建模重要过程的实验活动。
补充知识，将介绍0—1规划及其求解的隐牧举算法，并介绍如何用MATLAB求解。
13.1引例
现4有一节火车货车车厢，长10m，最大载重量为40t，可以运载7类货物包装箱。
包装箱的长度和重量不同，但宽度高度相同且适合装车，每件包装箱不能拆开装卸。
今有如表13-1所示货物，请给出装货方案，使总的价值最大。
表13-1货物数据表
货物
长度（cm）
重量（t/件）
价值（千元）
件数
1
55
0.5
40
8
2
58
1.7
37
8
3
62.4
3
58
6
4
49
2.2
36
7
5
40.6
3
35
3
6
53.3
1
45
4
7
66
4
50
8
设xi代表该车厢装入第i类货物包装箱的件数。
则易得如下数学模型
此模型与前面所讲的线性规划模型极为相似，所不同的是在此要求变量为正整数，此类优化问题称为整数线性规划。
对于变量限定只取0或1的整数线性规划称为0-1线性规划。
13.2基本理论介绍
整数规划是一类要求变量取值为整数的数学规划。
若整数规划中目标函数和约束条件都是线性的，则称之为整数线性规划（integerlinearprogramming，简记为ILP）。
若只要求部分变量取整数，则称为混合整数规划。
13.2.1问题的表述
在一般的线性规划中增加限定：
决策变量为整数，即为ILP问题：
标准形式为：
其中
13.2.2算法
求解ILP问题时，如果可行域是有界的，理论上可以用穷举法求解，对于变量个数较少时此法可行，但变量个数较多时这种穷举法往往是行不通的。
到目前为止，还缺乏十分有效的算法。
分枝定界法是应用的最为广泛的一种算法。
分枝定界法是1960年初由Doig和Land等人提出来的，可用于求解纯整数规划和混合整数规划问题。
分枝定界法比穷举法优越，它仅在一部分可行解的整数解中寻找最优解，计算量比穷举法小。
当然，若变量个数很大，其计算量也相当大。
分枝定界法的基本思想如下。
首先不考虑ILP中变量的整数约束，求解相应的线性规划问题（LP）:
若最优解中所有的变量都取整数，则已得到整数规划的最优解。
否则，记它此时的目标函数值为f0、最优解为
。
这时若记f为ILP的最优目标函数值，则必有
.如果其中某一个值li不是整数，那么分枝：
即分别求解如下两个子问题：
这样做，实际上是将原约束区域中不含任何整数解的区域去掉，在剩下的约束区域寻找最优解。
分别以LP1和LP2后继子问题为一分枝并标明求解的结果，找出最优目标函数值最小者作为新的下界，替换f0。
应当指出子问题的最优目标值一定不会优于原问题的目标函数值。
如果两个子问题的任何一个的解仍然不是整数，则继续选择一个非整数变量，将这个子问题再次分解为更下一级的子问题。
如果某一个子问题的最优解已满足变量为整数的要求，这就得到一个可行的整数解。
将这个这个子问题的目标函数值记录下来，作为整数规划最优目标值的上界。
从已符合整数条件的各分枝中，找出目标函数值为最小者作为新的上界f*，即有
。
如果其他子问题在分枝过程中，尽管尚未获得整数解，但该子问题的目标函数值已超过这个上界，则这个分枝无须再分枝求解。
这是因为即使继续分枝再得到一个整数解，这个解的目标函数值，一定会超过所得到的上界，从而不可能是最优解。
因此，利用定界，可以终止许多不必要的分枝过程，此为剪枝。
如果在分枝过程中得到新的整数解且该整数解的目标函数值小于已记录的上界，则将较小的整数解的目标值代替原来的上界。
因为上界越小，就可能删除更多不必要的分枝。
当所有最底层子问题出现以下三种情况之一时，分枝定界算法终止。
（1）子问题无可行解；
（2）子问题已获得整数解；
（3）子问题的目标函数值超过上界。
我们用一个例子来说明上述过程。
例1：
求解如下整数规划
解：
先解相应的
得：
按条件
将问题LP分解成如下子问题LP1和LP2并赋它们的下界为14.2。
求解LP1得：
；
求解LP2得：
；
可见
，LP2可分成两个子问题LP3和LP4并赋他们下界为14.33。
求解LP3得：
；求解LP4得：
；
由于x3和小x4是原整数规划问题的可行解且
，所以置f*=15为上界。
以下再将LP1分枝为如下LP5和LP6，并赋予它们下界14.33。
求解LP5得:
；
求解LP6得:
；
由于f5、f6>f*=15，所以LP5和LP6都没有继续分枝求解的必要。
至此求得最优解x*=x3=（0，5，0）或x*=x4=（1，4，0），最优目标函数值为f=f3=f4=15.
上述过程可以用如下框图13-1表示。
图13-1
13.3解整数线性规划的分枝定界法的MATLAB程序
如下的M函数可用来整数线性规划问题
在程序中，x0表示初值，调用时可以[]代替x0；neqcstr表示约束条件中前neqcstr个是等式；pre是精度；调用时，当neqcstr=0时可以省略，此时也可以省略x0，即调用格式：
x=ILp（c,A,b,vlb,vub）；返回的结果x是最优解，f是最优处目标函数的值。
%M函数ILp.m
function[x,f]=ILp（c,A,b,vlb,vub,x0,neqcstr,pre）
ifnargin<8,pre=0;
ifnargin<7,neqcstr=0;
ifnargin<6,x0=[];
ifnargin<5,vub=[];
ifnargin<4,vlb=[];
end,end,end,end,end
x0=x0（:
）;c=c（:
）;b=b（:
）;vlb=vlb（:
）;vub=vub（:
）;
mm=1;j=1;nvars=length（c'）;
fvub=inf;xall=[];fall=[];x_f_b=[];
[xtempztemp,how]=lp（c,A,b,vlb,vub,x0,neqcstr,-1）;
ftemp=c'*xtemp;
ifstrcmp（how,'ok'）
temp0=round（xtemp）;temp1=floor（xtemp）;
temp2=find（abs（xtemp-temp0）>pre）;
mtemp=length（temp2）;
if~isempty（temp2）
x_f_b=[xtemp;ftemp;vlb;vub];
whilej<=mm
i=1;
whilei<=mtemp
ifx_f_b（nvars+1,j）<=fvub
vlb1=x_f_b（nvars+2:
2*nvars+1,j）;
vub1=x_f_b（2*nvars+2:
3*nvars+1,j）;
vub1（temp2（i））=temp1（temp2（i））;
[xtempz,how]=lp（c,[A;c'],[b;fvub],…
vlb1,vub1,x0,neqcstr,-1）;
ftemp=c'*xtemp;
ifstrcmp（how,'ok'）,
temp10=round（xtemp）;temp11=floor（xtemp）;
temp12=find（abs（xtemp-temp10）>pre）;
ifisempty（temp12）,
xall=[xall,xtemp];fall=[fall,ftemp];
fvub=min（[fvub,fall]）;
elseifftemp<=fvub
x_f_b=[x_f_b,[xtemp;ftemp;vlb1;vub1]];
end,end,end
ifx_f_b（nvars+1,j）<=fvub
vlbr=x_f_b（nvars+2:
2*nvars+1,j）;
vlbr（temp2（i））=temp1（temp2（i））+1;
vubr=x_f_b（2*nvars+2:
3*nvars+1,j）;
[xtempz,how]=lp（c,[A;c'],[b;fvub],vlbr,vubr,x0,neqcstr,-1）;
ftemp=c'*xtemp;
ifstrcmp（how,'ok'）,
tempr0=round（xtemp）;tempr1=floor（xtemp）;
tempr2=find（abs（xtemp-tempr0）>pre）;
ifisempty（tempr2）,
xall=[xall,xtemp];fall=[fall,ftemp];
fvub=min（[fvub,fall]）;
elseifftemp<=fvub
x_f_b=[x_f_b,[xtemp;ftemp;vlbr;vubr]];
end,end,end
i=i+1;end
xint=x_f_b（1:
nvars,:
）;[m,mm]=size（xint）;j=j+1;
ifj>mm,break,end
temp0=round（xint（:
j））;temp1=floor（xint（:
j））;
temp2=find（abs（xint（:
j）-temp0）>pre）;
mtemp=length（temp2）;end,
else,x=xtemp;f=ftemp;end,
if~isempty（fall）
fmin=min（fall）;nmin=find（fall==fmin）;
x=xall（:
nmin）;f=fmin;end,
else,x=nan*ones（1,nvars）;end
13.4例题
例2引例“火车货车装箱方案”的计算。
调用ILp.m计算如下
>>clear;c=-[40;37;58;36;35;45;50];
>>A=[55,58,62.4,49,40.6,53.3,66;0.5,1.7,3,2.2,3,1,4];
>>b=[1000;40];vlb=zeros（7,1）;
>>vub=[7;5;6;7;3;4;3];
>>tic;[x,f]=linprog（c,A,b,vlb,vub,[],0,0.001）,toc
输出结果：
x=
3
1
6
0
3
4
1
f=
-840
elapsed_time=
544.1500
注意：
分枝定界法本质上还是一种牧举法，并不是一种完全有效的算法，当变量较多或条件较复杂时，计算耗时可能很多。
本例用时544.15秒。
当然，这与使用的计算机有关。
例3:
某厂拟用集装箱托远甲乙两种货物，每箱的体积、重量、可获利润以及托远所受的限制如表13-2。
问两种货物各托运多少箱，可使获得的利润为最大？
表13-2
货物
体积
每箱（m3）
重量
每箱（t）
利润
每箱（千元）
甲
5
2
20
乙
4
5
10
托远限制
24
13
解：
显然，该问题可用整数规划求解。
设x1和x2分别为甲和乙两种货物的托运箱数（皆为非负整数），则有
解法一：
直接利用分枝定界算法的思想。
首先放弃整数性条件，求线性规划问题
>>c=[-20,-10];A=[5,4;2,5];b=[24,13];
>>[x,f]=linprog（c,A,b,[],[],[0;0],[]）
x=
4.8000
0.0000
f=
-96.0000
增加条件
，求线性规划问题
>>c=[-20,-10];A=[5,4;2,5];b=[24,13];
>>[x,f]=linprog（c,A,b,[],[],[0;0],[4;inf]）
x=
4.0000
1.0000
f=
-90.0000
增加条件
，求线性规划问题
>>c=[-20,-10];A=[5,4;2,5];b=[24,13];
>>[x,f]=linprog（c,A,b,[],[],[5;0],[]）
x=
5.0000
0.0000
f=
-100.0000
不是可行解（因为不满足限制条件）。
可见x1=4,x2=1,f=90为最优解。
解法二：
调用ILp.m求解。
>>c=[-20,-10];A=[5,4;2,5];b=[24,13];
>>[x,f]=ILp（c,A,b,[0;0],[inf;inf],[],0,0.0001）
x=
4.0000
1.0000
f=
-90
13.5习题
1、求如下整数规划问题
2、（生产计划制定）某工厂用甲、乙两种原料A,B,C,D四种产品，每种产品消耗原料定额如表13-3所示。
现有甲原料18t，乙原料3t，请制定一个使总利润最大的生产计划。
表13-3
A（万件）
B（万件）
C（万件）
D（万件）
甲：
2
3
10
4
乙：
—
—
2
0.5
单位利润（万元/万件）
9
8
50
19
13.6补充:
0-1型整数线性规划
13.6.10-1型整数线性规划
0-1型整数线性规划是一类变量仅取0或1的特殊的整数规划；一般描述如下
其中
。
此时的决策变量称为0-1变量或二进制变量。
在实际问题中，如果引进0-1变量，就可以把各种需要分别讨论的线性（或非线性）规划问题统一在一个问题中讨论。
13.6.2求解0-1线性规划的隐牧举法
分枝定界法就是一种解整数规划的隐牧举法，0-1规划可以通过增加限定
的整数规划来求解。
对于n个变量的0-1规划，如果使用穷举法，则需要检查2n个取值组合，这显然不是聪明的办法。
这里所说的隐牧举法，是根据0-1规划的特点，设计的一些方法，只检查变量组合的一部分，而不是全部。
值得说明的是，对于有些问题（例如一部分变量是0-1变量的混合线性规划）隐牧举法有时是不适用的，还得使用穷举法。
隐牧举法原理与算法步骤：
（ⅰ）记
，将n个决策变量构成的x的2n个取值组合按二进制（或某种顺序）排列；
（ⅱ）按上述顺序对x的取值首先检验
是否成立，若不成立则放弃该取值的x，按次序换（ⅰ）中下一x的取值重复上述过程；若成立，则转下一步；
（ⅲ）对x逐一检验
中的m个条件是否满足，一旦某一条件不满足便停止检验后面的条件，而放弃这一x的取值，按次序换（ⅰ）中下一x的取值执行（ⅱ），若m个条件全满足，则转下一步；
（ⅳ）记
按次序换（ⅰ）中下一x的取值，执行（ⅱ）；
（ⅴ）最后一组满足
的x即为最优解。
13.6.3求解0-1型整数线性规划的MATLAB程序
Ⅰ、转换十进制数为二进制数的程序
如下是枚举和隐枚举程序中要调用的把十进制数转换为二进制数的程序。
b=de2bi（d）转换整数向量d成二进制矩阵b，二进制矩阵b中的每一行表示十进制向量d中相应的数；b=de2bi（d,n）转换整数向量d成二进制矩阵b，但指定b的列数n；而b=debi（d,n,p）转换整数向量d成p进制矩阵b，p进制矩阵b中的每一行表示十进制向量d中相应的数。
%M函数de2bi.m
functionb=de2bi（d,n,p）
d==d（:
）;len_d=length（d）;
ifmin（d）<0,error（'Cannotconvertanegativenumber'）;
elseif~isempty（find（d==inf））,
error（'InputmustnotbeInf.'）;
elseiffind（d~=floor（d））,
error（'Inputmustbeaninteger.'）;
end;
ifnargin<2,
tmp=max（d）;b1=[];
whiletmp>0
b1=[b1rem（tmp,2）];tmp=floor（tmp/2）;
end;
n=length（b1）;
end;
ifnargin<3,p=2;end
b=zeros（len_d,n）;
fori=1:
len_d
j=1;tmp=d（i）;
while（j<=n）&（tmp>0）
b（i,j）=rem（tmp,p）;tmp=floor（tmp/2）;
j=j+1;
end,end;
Ⅱ、牧举法程序
如下程序用牧举法求解0-1线性规划
minf=c*x,s.t.A*x<=b,x的分量全为0或1。
程序中的N表示约束条件A*x<=B中的前N个是等式,N=0时可以省略。
返回结果x是最优解，f是最优解处的函数值。
%M函数L01p_e.m
function[x,f]=L01p_e（c,A,b,N）
ifnargin<4,N=0;end
c=c（:
）;b=b（:
）;
[m,n]=size（A）;x=[];f=abs（c'）*ones（n,1）;i=1;
whilei<=2^n
B=de2bi（i-1,n）';
t=A*B-b;t11=find（t（1:
N,:
）~=0）;
t12=find（t（N+1:
m,:
）>0）;t1=[t11;t12];
ifisempty（t1）
f=min（[f,c'*B]）;
ifc'*B==f,x=B;end
end
i=i+1;
end
Ⅲ、隐牧举法程序
%M函数L01p_ie
function[x,f]=L01p_ie（c,A,b,N）
ifnargin<4,N=0;end
c=c（:
）;b=b（:
）;
a=[-A（1:
N,:
）;A];b=[-b（1:
N）;b];
[m,n]=size（A）;x=[];f=abs（c'）*ones（n,1）;
A=[c';A];b=[f;b];i=1;
whilei<=2^n
B=de2bi（i-1,n）';
j=1;t1=A（j,:
）*B-b（j）;
while（t1<=0&jj=j+1;t1=A（j,:
）*B-b（j）;
ift1>0,j=1;end;
end
ifj==m+1
x=B;f=c'*B;
b
（1）=min（[b
（1）,f]）;
end
i=i+1;
end
13.6.4补充例题
例4：
求解如下0-1型整数规划
解：
牧举法
>>c=[3,-2,5];b=[2;4;3;6]；
>>a=[1,2,-1,;1,4,1;1,1,0;0,4,1];
>>[x,f]=L01p_e（c,a,b）
x=
0
1
0
f=
-2
隐牧举法
>>c=[3,-2,5];b=[2;4;3;6]；
>>a=[1,2,-1,;1,4,1;1,1,0;0,4,1];
>>[x,f]=L01p_ie（c,a,b）
x=
0
1
0
f=
-2
例5：
一架货运飞机，有效载重量24t（吨），可运物品的重量及运费收入如表13-4所示，其中各物品只有一件可供选择。
问如何选运物品运费总收入最多？
物品
1
2
3
4
5
6
重量（t）
8
13
6
9
5
7
收入（万元）
3
5
2
4
2
3
表13-4
解：
记
则有
牧举法求解
>>c=-[3,5,2,4,2,3];A=[8,13,6,9,5,7];b=24;
>>[x,f]=L01p_e（c,A,b）
x=
1
0
0
1
0
1
f=
-10
隐牧举法求解
>>c=-[3,5,2,4,2,3];A=[8,13,6,9,5,7];b=24;
>>[x,f]=L01p_ie（c,A,b）
x=
1
0
0
1
0
1
f=
-10
13.7补充习题
1、求解如下0-1规划
（1）
（2）
2、某公司拟在市东、西、南三区建立门市部。
拟议中有7个位置Ai（i=1,…,7）可供选择。
规定：
在东区，由三个点A1、A2、A3中至少选两个；在西区，由两个点A4、A5中至少选一个；在南区，由两个点A6、A7中至少选一个。
投资总额不能超过700万元。
设备投资费与每年可获利润见表13-5。
问应选择哪几个点可使年利润为最大？
表13-5
A1
A2
A3
A4
A5
A6
A7
设备投资费（万元）
13
18
21
29
11
28
19
年终或利润（万元）
21
25
27
37
19
33
25
升级会员 