求解整数线性规划的分支定界法通用程序

admin

function [x,min_fval] = Ch1_FZDJ(f,A,b,Aeq,beq,lb,ub)
%% 程序功能说明
%求解整数线性规划的分支定界法通用程序
%====输入参数====
  %f            目标函数系数向量
  %A            不等式约束矩阵
  %b            不等式约束右端向量
  %Aeq          等式约束矩阵
  %beq          等式约束右端向量
  %lb           自变量下界
  %ub           自变量上界
%====输出参数====
  %x            目标函数取最小值时的自变量值
  %min_fval     目标函数的最小值
%程序编写时间：2012年05月；完善时间：2015年12月。
%参考文献：龚纯, 王正林. 精通MATLAB最优化计算[M]. 电子工业出版社, 2009年4月
%参考文献：张建林. MATLAB定量预测与决策——运作案例精编[M]. 北京：电子工业出版社, 2012年7月

%% 程序主体部分
x = NaN;
fm = NaN;
NF_lb = zeros(size(lb));
NF_ub = zeros(size(ub));
NF_lb(:,1) = lb;
NF_ub(:,1) = ub;
F = inf;

while 1
    sz = size(NF_lb);
    k = sz(2);
    opt = optimset('TolX',1e-9);
    %求解线性规划
    [xm,fv,exitflag] = linprog(f,A,b,Aeq,beq,NF_lb(:,1),NF_ub(:,1),[],opt);
    if exitflag == -2   %不存在最优解
        xm = NaN;
        fv = NaN;
    end
    if xm == NaN
        fv = inf;
    end
    if fv ~= inf
        if fv < F
            if max(abs(round(xm) - xm))<1.0e-7   %判断最优解的各个分量是否为整数
                F = fv;
                x = xm;
                tmpNF_lb = NF_lb(:,2:k);         %去掉第一列
                tmpNF_ub = NF_ub(:,2:k);         %去掉第一列
                NF_lb = tmpNF_lb;                %新的下界
                NF_ub = tmpNF_ub;                %新的上界
                if isempty(NF_lb) == 0
                    continue;
                else
                    if x ~= NaN
                        min_fval = F;
                        return;
                    else
                        disp('不存在最优解!');
                        x = NaN;
                        min_fval = NaN;
                        return;
                    end
                end
            else
                lb1 = NF_lb(:,1);
                ub1 = NF_ub(:,1);
                tmpNF_lb = NF_lb(:,2:k);
                tmpNF_ub = NF_ub(:,2:k);
                NF_lb = tmpNF_lb;
                NF_ub = tmpNF_ub;
                [bArr,index] = find(abs((xm - round(xm)))>=1.0e-7);
                p = bArr(1);
                new_lb = lb1;
                new_ub = ub1;
                new_lb(p) = max(floor(xm(p)) + 1,lb1(p));
                new_ub(p) = min(floor(xm(p)),ub1(p));
                NF_lb = [NF_lb new_lb lb1];
                NF_ub = [NF_ub ub1 new_ub];
                continue;
            end
        else
            tmpNF_lb = NF_lb(:,2:k);
            tmpNF_ub = NF_ub(:,2:k);
            NF_lb = tmpNF_lb;
            NF_ub = tmpNF_ub;
            if isempty(NF_lb) == 0
                continue;
            else
                if x ~= NaN
                    min_fval = F;
                    return;
                else
                    disp('不存在最优解!');
                    x = NaN;
                    fm = NaN;
                    return;
                end
            end
        end
    else     
        tmpNF_lb = NF_lb(:,2:k);
        tmpNF_ub = NF_ub(:,2:k);
        NF_lb = tmpNF_lb;
        NF_ub = tmpNF_ub;
        if isempty(NF_lb) == 0
            continue;
        else
            if x ~= NaN
                min_fval = F;
                return;
            else
                disp('不存在最优解!');
                x = NaN;
                min_fval = NaN;
                return;
            end
        end
    end
end