算例

计算结果：

matlab代码

%整数规划:分枝界定法

function [x,z]=BranchBound(N,b,Cn,Aeq,beq,lb,ub,fcheck)
%N:系数矩阵  b:右端常数   Cn:目标函数的系数   Aeq,beq:等式约束左右两端
%lb:决策变量下界  ub:决策变量上界
%fcheck:目标函数最大值问题,填1;目标函数最小值问题,填-1;

[m,n]=size(Cn);
Cn=Cn*(-1*fcheck);

%第一步：求解初始松弛问题
[x1,fval,exitflag]=linprog(Cn,N,b,Aeq,beq,lb,ub);  %linprog求解的是最小化问题

for i=1:n
   if rem(x1(i),1)~=0  %判断最优解是否为整数，取出非整数部分
      get=i;
      break;
   end
end


%第二步：第一次分枝
LP1_bound=zeros(n,2);%定义LP1中x1，x2的上界和下界
LP2_bound=zeros(n,2);%定义LP2中x1，x2的上界和下界
LP1_bound(:,2)=inf;  %上界初始化为inf
LP2_bound(:,2)=inf;
x_bound_low=floor(x1(get));%x1向下取整，作为LP1中x1的上界
x_bound_up=x_bound_low+1;  %LP2中x1的下界

%与原来的上下界进行比较，更新上下界
if x_bound_low<LP1_bound(get,2)   
    LP1_bound(get,2)=x_bound_low;
end
if x_bound_up> LP2_bound(get,1)
    LP2_bound(get,1)=x_bound_up;
end

%求解第一次分枝出来的两个问题
[x_LP1,f1,exitflag1]=linprog(Cn,N,b,Aeq,beq,LP1_bound(:,1),LP1_bound(:,2));
[x_LP2,f2,exitflag2]=linprog(Cn,N,b,Aeq,beq,LP2_bound(:,1),LP2_bound(:,2));

exitf=[exitflag1,exitflag2];  %标志是否有可行解，负数则无可行解

table=zeros(2,n+1);   %用来存储每次分枝问题运算得到的两个结果

f_bound=zeros(1,2);   %存储目标函数取值的上下界
f_bound(1)=-inf;

%后面的分枝进行迭代计算
while 1
    %若出现无可行解
    j=find(exitf<0);
    if j==1         %若LP1无可行解，舍去LP1，后面直接对LP2进行分枝
        LP1_bound=LP2_bound;      %把两个分枝的取值范围统一为LP2的取值范围
        x_LP1=[0;0];           %删去原来LP1的解
        f1=inf;
    elseif j==2      %若LP2无可行解，舍去LP2，后面直接对LP1进行分枝
        LP2_bound=LP1_bound;      %把两个分枝的取值范围统一为LP1的取值范围
        x_LP2=[0;0];          %删去原来LP2的解
        f2=inf;
    end
    
    %对两个分枝的计算结果进行存储
    for i=1:n
        table(1,i)=x_LP1(i);
        table(2,i)=x_LP2(i);
    end
    table(1,n+1)=-fcheck*f1;
    table(2,n+1)=-fcheck*f2;
    
    
    %第三步：定界
    f_bound(2)=-inf;
    for i=1:2
        if table(i,3)>f_bound(2)
            f_bound(2)=table(i,3);
        end
        if max(abs(round(table(i,1:n))-table(i,1:n)))<=1e-10   %这里有可能会出现误差，直接用0会导致结果错误
            if table(i,3)>f_bound(1)
                f_bound(1)=table(i,3);
            end
        end
    end
    
    %判断是否得出最终结果
    if f_bound(1)==f_bound(2)    %若目标函数最优取值的上下界相等，则计算完成，跳出循环
        disp("最优解为:")
        if table(1,3)==f_bound(1)
            x=x_LP1
        end
        if table(2,3)==f_bound(1)
            x=x_LP2
        end
        disp("目标函数最优取值为:")
        z=f_bound(1)
        break;
    end
    
    %第四步：再次分枝
    [max_f,ind]=max(table(:,3));   %找到分枝问题目标函数取值最大处
    for i=1:n
        if rem(table(ind,i),1)~=0   %找到该位置的非整数解部分
            get=i;
            break;
        end
    end
    x_bound_low=floor(table(ind,get));%x1向下取整，作为LP1中x1的下界
    x_bound_up=x_bound_low+1;       %LP2中x1的上界
    
    %判断对哪一枝进行分枝
     if ind==1        %若对LP1进行分枝            %table(ind,3)==-fcheck*f1   
        LP2_bound=LP1_bound;     %统一取值范围
    end
    if  ind==2        %若对LP2进行分枝           %table(ind,3)==-fcheck*f2
        LP1_bound=LP2_bound;     %统一取值范围
    end
    
    %更新两个分枝的x取值范围
    if x_bound_low<LP1_bound(get,2)
        LP1_bound(get,2)=x_bound_low;
    end
    if x_bound_up> LP2_bound(get,1)
        LP2_bound(get,1)=x_bound_up;
    end
    
    %再次对分枝问题求解
    [x_LP1,f1,exitflag1]=linprog(Cn,N,b,Aeq,beq,LP1_bound(:,1),LP1_bound(:,2));
    [x_LP2,f2,exitflag2]=linprog(Cn,N,b,Aeq,beq,LP2_bound(:,1),LP2_bound(:,2));
    exitf=[exitflag1,exitflag2];
end