整数规划分支定界法.doc

一、编程 利用Matlab的线性规划指令： [x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) 编写计算整数规划函数，输入与输出与上述指令相同 分枝定界法（递归实现） 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]; % e=0.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 0 disp(没有合适整数解); 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 子函数 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 = bound newx = 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; %构造第一个分支 x=floor(x(n)) A = [A;addA]; B = [B,floor