打算结果：
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(-1fcheck);%第一步：求解初始松弛问题[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; endend%第二步：第一次分枝LP1_bound=zeros(n,2);%定义LP1中x1，x2的上界和下界LP2_bound=zeros(n,2);%定义LP2中x1，x2的上界和下界LP1_bound(:,2)=inf; %上界初始化为infLP2_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;endif 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)=-fcheckf1; table(2,n+1)=-fcheckf2; %第三步：定界 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)==-fcheckf1 LP2_bound=LP1_bound; %统一取值范围 end if ind==2 %若对LP2进行分枝 %table(ind,3)==-fcheckf2 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
