matlab 解整数规划 （分支定界).m

来自「matlab解用分支定界法解整数规划的程序。请大家参考」· M 代码 · 共 111 行

function [x,fval]=bech(c,a,b,vlb,uvb,x0)
max=1000;
m=length(x0);
f=ones(max,1)*inf;
u=ones(max,m)*inf;
v=zeros(max,m);
xx=zeros(max,m);
x_0=zeros(1,m);
myu=zeros(1,m);
myv=zeros(1,m);
rx=0;count=0;k=0;j=0;
temp=0;eps=1e-6;n=0;
myv=vlb;
myu=uvb;
[x,fval]=linprog(c,a,b,[],[],myv,myu,x0)
flag=0;
if fval<=min(f)
    for t=1:m
        if rx~=x
            flag=1;
            break;
        end
    end
else
    flag=1;
end

while flag==1
   
    for j=m:-1:1
        rx=round(x(j));
        if rx-x(j)>eps
            temp=rx-1;
       if temp>=myv(j)
           count=count+1;
           u(count,:)=myu;
           v(count,:)=myv;
           u(count,j)=temp;
           f(count)=fval;
           xx(count,:)=x';
           xx(count,j)=temp;
       end
         if temp+1<=myu(j)
           count=count+1;
           u(count,:)=myu;
           v(count,:)=myv;
           v(count,j)=temp+1;
           f(count)=fval;
           xx(count,:)=x';
           xx(count,j)=temp+1;
       end
           break
       end
    if x(j)-rx>eps
            temp=rx;
       if temp>=myv(j)
           count=count+1;
           u(count,:)=myu;
           v(count,:)=myv;
           u(count,j)=temp;
           f(count)=fval;
           xx(count,:)=x';
           xx(count,j)=temp;
       end
         if temp+1<=myu(j)
           count=count+1;
           u(count,:)=myu;
           v(count,:)=myv;
           v(count,j)=temp;
           f(count)=fval;
           xx(count,:)=x';
           xx(count,j)=temp+1;
       end
       break
 end
end
[value,n]=min(f);
myu=u(n,:);
myv=v(n,:);
x_0=xx(n,:);

for k=n:count
    v(k,:)=v(k+1,:);
    u(k,:)=u(k+1,:);
    xx(k,:)=xx(k+1,:);
    f(k)=f(k+1);
end
f(count)=inf;
count=count-1;

[x,fval]=linprog(c,a,b,[],[],myv,myu,x0)
flag=0;
if fval<=min(f)
    for t=1:m
        rx=round(x(t));
        if (rx-x(t))>eps
            flag=1;
            break;
        end
    end
else
    flag=1;
end

end