0-1整数规划实例
1、投资场所的选定——相互排斥的计划
解：解题时先引入0 −1变量xi，并进行问题转换
2、引入0 −1变量y，来解决相互排斥的约束条件
3、扩展：利用0-1变量来解决m 个互相排斥的约束条件
如果有m 个互相排斥的约束条件
4、关于固定费用的问题（Fixed Cost Problem）
某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令
5、举例说明一种解0 −1型整数规划的隐枚举法
6、蒙特卡洛法求解非线性整数规划
(1)、首先编写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];
(2)、编写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
7、Matlab求解指派问题等0 −1整数规划问题
解：编写 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
