Question

求matlab高手帮我解决一个整数线性规划问题，急急急!!!!

Answer 1

由于是整数规划，可以用穷举的方法但是穷举本体穷举有2.7089e+013种可能
所以先求出每天符合的可能减少穷举的量
A=[
6
0
6
0
7;
0
6
0
6
0;
4
8
3
0
5;
5
5
6
0
4;
3
0
4
8
0;
0
6
0
6
3];
p=[10,10,9.9,9.8,10.8,11.3];
maxm=zeros(1,size(A,2));
TT=cell(size(A,1),1);
for
jj=1:size(A,2)%先排每一天的班，找出每天符合条件的排班
ind=find(A(:,jj)>0);
maxn=length(ind);
Tjj=zeros(size(A,1),1);
stack=zeros(size(A,1),1);
TT{jj}=[];
maxm(jj)=0;
n=1;
while(n~=0)
stack(ind(n))=stack(ind(n))+1;
if
stack(ind(n))==1,Tjj(ind(n))=0;else
Tjj(ind(n))=stack(ind(n));end
if
stack(ind(n))>A(ind(n),jj)
stack(ind(n))=0;
n=n-1;
else
if
n==maxn
if
sum(Tjj)==14&&sum(Tjj(5:6)>0)>=1&&sum(Tjj>0)<=3
TT{jj}=[TT{jj}
Tjj];maxm(jj)=maxm(jj)+1;
end
else
n=n+1;
end
end
end
end
stack=zeros(1,size(A,2));
T=zeros(size(A));
mincost=inf;
Tmin=zeros(size(A));
n=1;
while(n~=0)%从每天符合的排班中找到符合条件的一周组合
stack(n)=stack(n)+1;
if
stack(n)>maxm(n)
stack((n))=0;
n=n-1;
else
T(:,n)=TT{n}(:,stack(n));
if
n==size(A,2)
if
all(sum(T>0,2)<=3)&&all(sum(T(1:4,:),2)>=8)&&all(sum(T(5:6,:),2)>=7)
cost=sum(p*T);
if
cost<mincost,mincost=cost;Tmin=T;end
end
else
n=n+1;
end
end
end
Tmin
mincost
Tmin
=
6
0
6
0
7
0
4
0
6
0
0
8
0
0
5
5
0
6
0
0
3
0
2
5
0
0
2
0
3
2
mincost
=
713.6000