安卓 网站整站下载,超市建网站,自己做网站都要什么软件,wordpress 免插件引入
线性规划问题(松弛问题) 图解法: 使用图解法求出最优解,再使用四舍五入求出的整数解不满足条件 完全枚举法(穷举法):找出集合内所有满足条件的整数点,再带入不等式中,看是否有最优解
分支限界法
说明: 松弛问题:线性规划问题 ILP:整数规划,在线性规划的基础上对决策…引入
线性规划问题(松弛问题) 图解法: 使用图解法求出最优解,再使用四舍五入求出的整数解不满足条件 完全枚举法(穷举法):找出集合内所有满足条件的整数点,再带入不等式中,看是否有最优解
分支限界法
说明: 松弛问题:线性规划问题 ILP:整数规划,在线性规划的基础上对决策变量进行取整 所以线性规划无可行解则整数规划也无可行解 增加约束条件,一个个来,一次增加一个 对原始结果进行向上取整 [4.6]5 对原始结果进行向下取整 [4.6]4 流程: 如果添加完约束之后仍然没有找到整数解,那么此时分支限界法已经不能解决此问题了
案例
整数规划的最优解只是针对决策变量x的,与目标值Z无关 所以x14;x21;z14.3(是整数规划的最优解) 1)当增加了x13的条件之后,得出的结果中出现了非整数x22.67;所以此时还需要对x2向下取整与向上取整,看结果对比 判断: 得到目标值高的先进行分支
matlab代码
branchbound.m
function [newx,newfval,status,newbound] branchbound(f,A,B,I,x,fval,bound,Aeq,Beq,lb,ub,e)% 分支定界法求解整数规划
% f,A,B,Aeq,Beq,lb,ub与线性规划相同
% I为整数限制变量的向量
% x为初始解fval为初始值options optimset(display,off);
[x0,fval0,status0]linprog(f,A,B,Aeq,Beq,lb,ub,[],options);%递归中的最终退出条件
%无解或者解比现有上界大则返回原解
if status0 0 || fval0 boundnewx x;newfval fval;newbound bound;status status0;return;
end%是否为整数解,如果是整数解则返回
intindex find(abs(x0(I) - round(x0(I))) e);
if isempty(intindex) %判断是否为空值newx(I) round(x0(I));newfval fval0;newbound fval0;status 1;return;
end%当有非整可行解时则进行分支求解
%此时必定会有整数解或空解
%找到第一个不满足整数要求的变量
n I(intindex(1));
addA zeros(1,length(f));
addA(n) 1;
%构造第一个分支 xfloor(x(n))
A [A;addA];
B [B,floor(x(n))];%向下取整
[x1,fval1,status1,bound1] branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);
A(end,:) [];
B(:,end) [];
%解得第一个分支若为更优解则替换若不是则保持原状status status1;
if status1 0 bound1 boundnewx x1;newfval fval1;bound fval1;newbound bound1;
elsenewx x0;newfval fval0;newbound bound;
end%构造第二分支
A [A;-addA];
B [B,-ceil(x(n))];%向上取整
[x2,fval2,status2,bound2] branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);
A(end,:) [];
B(:,end) [];%解得第二分支并与第一分支做比较如果更优则替换
if status2 0 bound2 boundstatus status2;newx x2;newfval fval2;newbound bound2;
end
intprog.m
function [x,fval,status] intprog(f,A,B,I,Aeq,Beq,lb,ub,e)
%整数规划求解函数 intprog()
% 其中 f为目标函数向量
% A和B为不等式约束 Aeq与Beq为等式约束
% I为整数约束
% lb与ub分别为变量下界与上界
% x为最优解fval为最优值
%例子:
% maximize 20 x1 10 x2
% S.T.
% 5 x1 4 x2 24
% 2 x1 5 x2 13
% x1, x2 0
% x1, x2是整数
% f[-20, -10];
% A[ 5 4; 2 5];
% B[24; 13];
% lb[0 0];
% ub[inf inf];
% I[1,2];
% e0.000001;
% [x v s] IP(f,A,B,I,[],[],lb,ub,,e)
% x 4 1 v -90.0000 s 1% 控制输入参数
if nargin 9, e 0.00001;if nargin 8, ub []; if nargin 7, lb []; if nargin 6, Beq []; if nargin 5, Aeq [];if nargin 4, I [1:length(f)];end, end, end, end, end, end%求解整数规划对应的线性规划,判断是否有解
options optimset(display,off);
[x0,fval0,exitflag] linprog(f,A,B,Aeq,Beq,lb,ub,[],options);
if exitflag 0disp(没有合适整数解);x x0;fval fval0;status exitflag;return;
else%采用分支定界法求解bound inf;[x,fval,status] branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);
end
test.m
%例子1
% f [-40 -90];%A [9 7;7 20];%B [56 70];
% lb [0 0];
%例子2f [-20 -10];A [5 4;2 5];B [24 13];lb [0 0];[x,fval,status] intprog(f,A,B,[1 2],[],[],lb)
