基于非线性整数规划离散型优化问题代码(在MATLAB5.3使用)-内含matlab源码和数据集.zip

function [errmsg,Z,X,t,c,fail] = BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,maxSQPit,varargin); %非线性整数规划模型求解分支定界迭代算法。在MATLAB5.3中使用，需Optimization toolbox 2.0支持? % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)可为连续变量，整数，或固定值 % 使用格式 %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun： M文件名，表示最小化目标函数f=fun(x) %x0: 列向量，表示变量初值 %xstat： 列向量，xstat(i)=0表示x(i)为连续变量，1表示整数，2表示固定值 %xl： 列向量，表示变量下界 %xu: 列向量，表示变量上界 %A: 矩阵, 表示线性不等式约束系数 %B: 列向量, 表示线性不等式约束上界 %Aeq: 矩阵, 表示线性等式约束系数 %Beg: 列向量, 表示线性不等式约束右端值 %nonlcon: M文件名，表示非线性约束函数[C,Ceq]=nonlin(x),其中C(x)为不等式约束, % Ceq(x)为等式约束 %setts: 算法设置 %errmsq: 返回错误提示 %Z: 返回目标函数最小值 %X: 返回最优解 % %例题 % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % 先写 M函数discfun.m % function f=discfun(x) % f=-x(1)*x(2)*x(3); %求解 % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z % % BNB18 Finds the constrained minimum of a function of several possibly integer variables. % Usage: [errmsg,Z,X,t,c,fail] = % BNB18(fun,x0,xstatus,xlb,xub,A,B,Aeq,Beq,nonlcon,settings,options1,options2,maxSQPiter,P1,P2,...) % % BNB solves problems of the form: % Minimize F(x) subject to: xlb <= x0 <=xub % A*x <= B Aeq*x=Beq % C(x)<=0 Ceq(x)=0 % x(i) is continuous for xstatus(i)=0 % x(i) integer for xstatus(i)= 1 % x(i) fixed for xstatus(i)=2 % % BNB uses: % Optimization Toolbox Version 2.0 (R11) 09-Oct-1998 % From this toolbox fmincon.m is called. For more info type help fmincon. % % fun is the function to be minimized and should return a scalar. F(x)=feval(fun,x). % x0 is the starting point for x. x0 should be a column vector. % xstatus is a column vector describing the status of every variable x(i). % xlb and xub are column vectors with lower and upper bounds for x. % A and Aeq are matrices for the linear constrains. % B and Beq are column vectors for the linear constrains. % nonlcon is the function for the nonlinear constrains. % [C(x);Ceq(x)]=feval(nonlcon,x). Both C(x) and Ceq(x) should be column vectors. % % errmsg is a string containing an error message if BNB found an error in the input. % Z is the scalar result of the minimization, X the values of the accompanying variables. % t is the time elapsed while the algorithm BNB has run, c is the number of BNB cycles and % fail is the number of unsolved leaf sub-problems. % % settings is a row vector with settings for BNB: % settings(1) (standard 0) if 1: use phase 1 by relaxation. This sometimes makes the algorithm % faster, because phase 1 means the algorithm first checks if there is a feasible solution % for a sub-problem before trying to find a best solution. If there is no feasible solution BNB % will not try to find a best solution. % settings(2) (standard 0) if 1: if the sub-problem did not converge do not branch. If a sub- % problem did not converge this means BNB did not find a solution for it. Normally BNB will % branch the problem so it can try again to find a solution. % A sub-problem that is a leaf of the branch-and-bound-three can not be branched. If such % a problem does not converge it will be considered unfeasible and the parameter fail will be % raised by one. % settings(3) (standard 0) if 1: if 1 a sub-problem that did not converge but did return a feasible % point will be considered convergent. This might be useful if fmincon is having a hard time with % a certain problem but you do want some results. % options1 and options2 are options structures for phase 1 and phase 2. % For details about the options structure type help optimset. % maxSQPiter is a global variable used by fmincon (if modified as described in bnb18.m). % maxSQPiter is 1000 by default. % P1,P2,... are parameters to be passed to fun and nonlcon. % F(x)=feval(fun,x,P1,P2,...). [C(x);Ceq(x)]=feval(nonlcon,x,P1,P2,...). % Type edit BNB18 for more info. % E.C. Kuipers % e-mail E.C.Kuipers@cpedu.rug.nl % FI-Lab % Applied Physics % Rijksuniversiteit Groningen % To get rid of bugs and to stop fmincon from hanging make the following chances: % % In optim/private/nlconst.m ($Revision: 1.20 $ $Date: 1998/08/24 13:46:15 $): % Get EXITFLAG independent of verbosity. % After the lines: disp(' less than 2*options.TolFun but constraints are not satisfied.') % end % EXITFLAG = -1; % end % end % status=1; % add the line: if (strncmp(howqp, 'i',1) & mg > 0), EXITFLAG = -1; end; % % In optim/private/qpsub.m ($Revision: 1.21 $ $Date: 1998/09/01 21:37:56 $): % Stop qpsub from hanging. % After the line: % Andy Grace 7-9-90. Mary Ann Branch 9-30-96. % add the line: global maxSQPiter; % and changed the line: maxSQPiters = Inf; % to the line: if exist('maxSQPiter','var'), maxSQPiters = maxSQPiter; else maxSQPiters=inf; end; % I guess there was a reason to put maxSQPiters at infinity, but this works fine for me. global maxSQPiter; % STEP 0 CHECKING INPUT Z=[]; X=[]; t=0; c=0; fail=0; if nargin<2, errmsg='BNB needs at least 2 input arguments.'; return; end; if isempty(fun), errmsg='No fun found.'; return; end; if isempty(x0), errmsg='No x0 found.'; return; elseif size(x0,2)>1, errmsg='x0 must be a column vector.'; return; end; xstatus=zeros(size(x0)); if nargin>2 & ~isempty(xstat) if all(size(xstat)<=size(x0)) xstatus(1:size(xstat))=xstat; else errmsg='xstatus must be a column vector the same size as x0.'; return; end; if any(xstatus~=round(xstatus) | xstatus<0 | 2<xstatus) errmsg='xstatus must consist of the integers 0,1 en 2.'; return; end; end; xlb=zeros(size(x0)); xlb(find(xstatus==0))=-inf; if nargin>3 & ~isempty(xl) if all(size(xl)<=size(x0)) xlb(1:size(xl,1))=xl; else errmsg='xlb must be a column vector the same size as x0.'; return; end; end; if any(x0<xlb) errmsg='x0 must be in the range xlb <= x0.'; return; elseif any(xstatus==1 & (~isfinite(xlb) | xlb~=round(xlb))) errmsg='xlb(i) must be an integer if x(i) is an integer variabele.'; return; end; xlb(find(xstatus==2))=x0(find(xstatus==2)); xub=ones(size(x0)); xub(find(xstatus==0))=inf; if nargin>4 & ~isempty(xu) if all(size(xu)<=size(x0)) xub(1:size(xu,1))=xu; else errmsg='xub must be a column vector the same size as x0.'; return; end; end; if any(x0>xub) errmsg='x0 must be in the range x0 <=xub.'; return; elseif any(xstatus==1 & (~isfinite(xub) | xub~=round(xub))) errmsg='xub(i) must be an integer if x(i) is an integer variabale.'; return; end; xub(find(xstatus==2))=x0(find(xstatus==2)); if nargin>5 if ~isempty(A) & size(A,2)~=size(x0,1), errmsg='Matrix A not correct.'; return; end; else A=[]; end; if nargin>6 if ~isempty(B) & any(size(B)~=[size(A,1) 1]), errmsg='Column vector B not correct.'; return; end; else B=[]; end; if isempty(A) & ~isempty(B), errmsg='A and B should only be nonempty together.'; return; end; if isempty(B) & ~isempty(A), B=zeros(size(A,1),1); end; if nargin>7 & ~isempty(Aeq) if size(Aeq,2)~=size(x0,1), errmsg='Matrix Aeq not correct.'; return; end; else Aeq=[]; end; if nargin>8 if ~isemp