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:nif 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 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:ntable(1,i)=x_LP1(i);table(2,i)=x_LP2(i);endtable(1,n+1)=-fcheck*f1;table(2,n+1)=-fcheck*f2;%第三步：定界f_bound(2)=-inf;for i=1:2if table(i,3)>f_bound(2)f_bound(2)=table(i,3);endif 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);endendend%判断是否得出最终结果if f_bound(1)==f_bound(2)    %若目标函数最优取值的上下界相等，则计算完成，跳出循环disp("最优解为:")if table(1,3)==f_bound(1)x=x_LP1endif table(2,3)==f_bound(1)x=x_LP2enddisp("目标函数最优取值为:")z=f_bound(1)break;end%第四步：再次分枝[max_f,ind]=max(table(:,3));   %找到分枝问题目标函数取值最大处for i=1:nif rem(table(ind,i),1)~=0   %找到该位置的非整数解部分get=i;break;endendx_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;     %统一取值范围endif  ind==2        %若对LP2进行分枝           %table(ind,3)==-fcheck*f2LP1_bound=LP2_bound;     %统一取值范围end%更新两个分枝的x取值范围if x_bound_low 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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！