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