数学与软件科学学院 实验报告
学期：__2011_至__2012__ 第___一__ 学期 20##年11月9日
课程名称:__运 筹 学 ________ 专业:_信息与计算科学___ 级__班
实验编号： 4 实验项目_利用Matlab求解整数线性规划 指导教师__黄娟___
姓名：＿ ____ 学号： __ 实验成绩：＿＿＿＿＿
一、实验目的及要求
利用Matlab求解整数线性规划，掌握相关函数的调用格式和参数的具体含义。
二、实验内容
把优化问题转化为Matlab能识别的矩阵运算, 调用Matlab提供的优化函数, 编写相应的M文件，并执行相应的程序。
三、实验步骤(该部分不够填写.请填写附页)
整数线性规划的求解步骤
<1>把整数线性规划化为要求的格式
<2> 将程序BranchBound.m放到当前目录中。
<3>编写M文件(ILP.m)，并保存。
>> f=[-3 -2]';
>> a=[-1 2;5 2;-1 -1];
>> b=[4;16;1];
>> [x,f_opt]=BranchBound(f,a,b,[],[])
<4>运行M文件。在》后输入ILP，按“Enter”键。结果参见附页
0-1规划的求解步骤
<1> 把0-1规划化为要求的格式
<2>编写M文件(ILP01.m)，并保存。
>> f=[0;0;0;0;0;0;-30;-30;-45;-45;-55;-55;-50;-50];
>> a=[400 0 320 0 560 0 250 0 330 0 500 0 450 0;
0 400 0 320 0 560 0 250 0 330 0 500 0 450;
0 0 0 0 0 0 1 1 0 0 0 0 0 0 ;
0 0 0 0 0 0 0 0 1 1 0 0 0 0 ;
0 0 0 0 0 0 0 0 0 0 1 1 0 0 ;
0 0 0 0 0 0 0 0 0 0 0 0 1 1];
>> b=[1000;1500;1;1;1;1];
>> aeq=[1 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 1 1 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 0 0 0 0 0 0 0 0];
>> beq=[1;1;1];
>> [x,f_opt,flag]=bintprog(f,a,b,aeq,beq),answer=180+f_opt
<3>运行M文件。在》后输入ILP01，按“Enter”键。结果参见附页
实 验 报 告 附 页
四、实验结果分析与评价 (该部分不够填写.请填写附页)
整数线性规划的求解结果
x =
2
3
f_opt =
-12
0-1规划的求解结果
x =
1
0
0
1
0
1
0
1
0
1
1
0
0
0
f_opt =
-130
flag =
1
answer =
50
注:实验成绩等级分为(90-100分)优,(80-89分)良,(70-79分)中,(60-69分)及格,(59分)不及格
第二篇：Matlab求解线性规划和整数规划问题
1.线性规划问题：min f*x
s.t. A*x<=b
Aeq*x=beq
lb<=x<=ub
其中：A为不等式约束的系数矩阵，Aeq表示等式约束的系数矩阵，b表示不等式约束的常向量，beq表示等式约束的常向量，lb和ub表示自变量的上下范围。
求解函数：
linprog(f,A,b,Aeq,beq,lb,ub)
其中： f,A,b ,Aeq,beq,lb,ub的定义如上。
2.整数规划问题：利用函数（linprog）
先把BranchBound函数存在matlab的路径下，BranchBound函数的内容如下： function [y,fval]=BranchBound(c,A,b,Aeq,beq)
NL=length(c);
UB=inf;
LB=-inf;
FN=[0];
AA(1)={A};
BB(1)={b};
k=0;
flag=0;
while flag==0;
[x,fval,exitFlag]=linprog(c,A,b,Aeq,beq);
if (exitFlag == -2) | (fval >= UB)
FN(1)=[];
if isempty(FN)==1
flag=1;
else
k=FN(1);
A=AA{k};
b=BB{k};
end
else
for i=1:NL
if abs(x(i)-round(x(i)))>1e-7
kk=FN(end);
FN=[FN,kk+1,kk+2];
temp_A=zeros(1,NL);
temp_A(i)=1;
temp_A1=[A;temp_A];
AA(kk+1)={temp_A1};
b1=[b;fix(x(i))];
BB(kk+1)={b1};
temp_A2=[A;-temp_A];
AA(kk+2)={temp_A2};
b2=[b;-(fix(x(i))+1)];
BB(kk+2)={b2};
FN(1)=[];
k=FN(1);
A=AA{k};
b=BB{k};
break;
end
end
if (i==NL) & (abs(x(i)-round(x(i)))<=1e-7) UB=fval;
y=x;
FN(1)=[];
if isempty(FN)==1
flag=1;
else
k=FN(1);
A=AA{k};
b=BB{k};
end
end
end
end
y=round(y);
fval=c*y;
再利用命令[y,fval]=BranchBound(c,A,b,Aeq,beq)即可。