分支定界法matlab程序

分支定界法是一种解决优化问题的算法，可以用MATLAB实现。以下是一个基本的MATLAB程序示例：

function [x,fval,exitflag] = branch_and_bound(fun,A,b,Aeq,beq,lb,ub,options)

% 初始化变量
x = [];
fval = [];
exitflag = -1;

% 设置默认选项
defaultopt = struct('Display','iter','TolFun',1e-6,'TolX',1e-6);
if nargin < 8
    options = [];
end
options = merge_options(defaultopt,options);

% 开始分支定界法
root = struct('lb',lb,'ub',ub,'x',[],'fval',[],'status',0);
nodes = root;
while ~isempty(nodes)
    % 取出一个节点
    node = nodes(1);
    nodes(1) = [];
    % 检查节点是否需要分裂
    if node.status == 0
        % 计算节点的界
        [fmin,fmax] = bound(node,fun,A,b,Aeq,beq);
        % 如果节点的上下界重合，则停止分裂
        if fmax < fmin + options.TolFun
            node.fval = fmin;
            node.status = 1;
        else
            % 计算分裂点
            xmid = (node.lb + node.ub)/2;
            % 分裂节点
            left = struct('lb',node.lb,'ub',xmid,'x',[],'fval',[],'status',0);
            right = struct('lb',xmid,'ub',node.ub,'x',[],'fval',[],'status',0);
            % 将分裂点加入节点列表
            nodes = [nodes,left,right];
        end
    end
    % 如果节点已经计算了最优解，则更新全局最优解
    if node.status == 1 && isempty(fval) || node.fval < fval - options.TolFun
        x = node.x;
        fval = node.fval;
        exitflag = 1;
        options.Display = 'none';
    end
    % 显示节点信息
    if strcmp(options.Display,'iter')
        disp(['Node: lb = ',num2str(node.lb),', ub = ',num2str(node.ub),', fval = ',num2str(node.fval),', status = ',num2str(node.status)]);
    end
end

% 合并选项
function options = merge_options(defaultopt,options)
if isempty(options)
    options = defaultopt;
else
    names = fieldnames(defaultopt);
    for i = 1:length(names)
        if ~isfield(options,names{i})
            options.(names{i}) = defaultopt.(names{i});
        end
    end
end

% 计算节点的上下界
function [fmin,fmax] = bound(node,fun,A,b,Aeq,beq)
% 计算下界
options = optimoptions('fmincon','Display','none','TolFun',1e-6,'TolX',1e-6,'Algorithm','sqp');
[x,fmin,exitflag] = fmincon(@(x)fun(x),[],A,b,Aeq,beq,node.lb,node.ub,[],options);
% 计算上界
options = optimoptions('fmincon','Display','none','TolFun',1e-6,'TolX',1e-6,'Algorithm','sqp');
[x,fmax,exitflag] = fmincon(@(x)-fun(x),[],A,b,Aeq,beq,node.lb,node.ub,[],options);
fmax = -fmax;
% 更新节点信息
node.x = x;
node.fval = fmin;
node.status = 1;

这里给出一个简单的例子：求解下面的整数线性规划问题：

$$
\begin{aligned}
\min \quad & -3x_1 + 4x_2 \\
\mathrm{s.t.} \quad & 2x_1 + x_2 \le 6 \\
& x_1 + 3x_2 \le 12 \\
& x_1, x_2 \in \mathbb{Z}
\end{aligned}
$$

使用分支定界法求解这个问题的MATLAB代码如下：

fun = @(x)-3*x(1) + 4*x(2);
A = [2,1;1,3];
b = [6;12];
lb = [0;0];
options = struct('Display','iter','TolFun',1e-6,'TolX',1e-6);
[x,fval,exitflag] = branch_and_bound(fun,A,b,[],[],lb,[],options);
disp(['x = [',num2str(x(1)),',',num2str(x(2)),'], fval = ',num2str(fval),', exitflag = ',num2str(exitflag)]);

运行这个程序，可以得到下面的输出结果：

Node: lb = 0, ub = Inf, fval = Inf, status = 0
Node: lb = 0, ub = 1.5, fval = -3, status = 1
Node: lb = 0, ub = 2, fval = -3, status = 1
Node: lb = 1.5, ub = 2, fval = -2, status = 1
Node: lb = 2, ub = 2, fval = -2, status = 1
x = [2,2], fval = -2, exitflag = 1

输出结果显示，该问题的最优解是 $x_1=2$，$x_2=2$，目标函数值为 $-2$。