分支定界(branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是： 1 ．产生当前扩展结点的所有孩子结点；
2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点；
3 ．将其余的孩子结点加入活结点表；
4 ．从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解（最优解）或活结点表为空。从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式： 1 ．FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。
2 ．最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。又称分支定界搜索法。过程系统综合的一类方法。该法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。所以，对程序进行优化，就成为搜索算法编程中最关键的一环。本文所要讨论的便是搜索算法中优化程序的一种基本方法枣“剪枝”。什么是剪枝相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的：
1、这个方向有路可走，我没走过
2、往这个方向前进
3、是死胡同，往回走，回到上一个路口
4、重复第一步，直到找着出口这样的思路很好理解，编程起来也比较容易。但是当迷宫的规模很大时，回溯法的缺点便暴露无遗：搜索耗时极巨，无法忍受。我们可不可以在向某个方向前进时，先一步判断出这样走会不会走到死胡同里呢？这样一来，搜索的时间不就可以减少了吗？答案是：可以的。剪枝的概念，其实就跟走迷宫避开死胡同差不多。若我们把搜索的过程看成是对一棵树的遍历，那么剪枝顾名思义，就是将树中的一些“死胡同”，不能到达我们需要的解的枝条“剪”掉，以减少搜索的时间。
搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。在设计判断方法的时候，需要遵循一定的原则。剪枝的原则1、正确性正如上文所述，枝条不是爱剪就能剪的。如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。所以，剪枝的前提是一定要保证不丢失正确的结果。2、准确性在保证了正确性的基础上，我们应该根据具体问题具体分析，采用合适的判断手段，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。可以说，剪枝的准确性，是衡量一个优化算法好坏的标准。3、高效性设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。综上所述，我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。剪枝算法按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。对于分支定界算法,上界是已求得的可行解的目标函数值中的最小者,分为初始上界和在探测过程中产生的动态上界.
分支定界法在求最优解的迭代过程中, 若某结点估计的下界不小于已知的上界, 则不必从
该节点往下继续搜索. 因此若能产生一个较好的上界, 可以消除许多不必要的列举计算.
分支定界算法的实现在描述分支定界算法步骤之前, 先对算法涉及到的有关术语进行定义如下: p ——分支层数; C*——当前最优目标函数值; P*——相应于
C*的工件顺序; P1——当前节点(现在需要进行分支的节点)所对应的部分序列.
分支定界算法的实施步骤如下: 步骤1初始化: 设置p = 0, P 1 = Á (空集) , C* = ∞.设当前节点总是与P 1 相对应. 此时, 当前节点即根节点. 步骤2计算从当前节点分支得到的各个子节点的下界, 并按下界值由小到大对各子节点排序. 令p ←p + 1.
步骤3如果当前节点被探测尽, 令p ←p - 1, 转步骤6. 否则, 设当前层(第p 层) 各活动子节点中具有最小下界值的节点为Q , 则在P 1末尾加入Q 对应第p 位置上的工件, 此时的当前节点转为Q , 转步骤4. 步骤4因为当前节点是同层同父节点具有最小下界值的节点, 如果当前节点下界值大于或等于C* , 则不必再搜索当前节点及其同层同父的活动节点, 这样, 当前节点的上一层节点(父节点)被探测尽, p ←p - 1, 去掉P 1 中的最后一个工件,转步骤6. 否则, 转步骤5. 步骤5如果p = n, 则得到一个较优顺序.令P* = P 1, C* 是当前节点的下界值, p ←p - 1,去掉P 1 中最后一个工件, 转步骤6; 否则转步骤2. 步骤6若p ≠ 0, 去掉P 1 中最后一个工件,转步骤3; 否则, 算法停止. C* 是最优的目标函数值, P* 是最优顺序.
// 分支限界法之旅行商问题.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include"stdlib.h"#include
{ city[j].PastCity[boolnum2][i]=city[k].PastCity[boolnum1][i]; i++; } city[j].PastCity[boolnum2][i]=k; }void main(){ int i,j,k; int boolnum=0; int TempMinVal; int TempCity; int TempVal; for(i=0;i<2;i++) for(j=0;j<4;j++) for(k=0;k<4;k++) city[k].PastCity[i][j]=0; for(i=1;i<4;i++) city[i].MinVal[boolnum]=CityVal[i][0]; for(i=0;i<2;i++) { for(j=1;j<4;j++) { TempMinVal=32767; for(k=1;k<4;k++) { if(j!=k&&!find(j,k,boolnum)) { TempVal=CityVal[j][k]+city[k].MinVal[boolnum]; if(TempMinVal>TempVal) { TempMinVal=TempVal; TempCity=k; } } } city[j].MinVal[(boolnum+1)%2]=TempMinVal;
copy(TempCity,boolnum,j,(boolnum+1)%2); } boolnum=(boolnum+1)%2; } TempMinVal=32767; for(i=1;i<4;i++) { TempVal=CityVal[0][i]+city[i].MinVal[boolnum]; if(TempMinVal>TempVal) { TempMinVal=TempVal; TempCity=i; } } cout<<"最小费用为:"< 整数规划分支定界算法matlab通用源程序 %整数规划分支定界算法matlab通用源程序 %各参数的意义同matlab优化工具箱的线性规划函数linprog %调用前，输入参数要化成matlab的标准形式 [x,val]=kfz-f-3(n,f,a,b,aeq,beq,lb,ub) x=zeros(n,1); x1=zeros(n,1); m1=2; m2=1; [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); if (x1==0) x=x1; val=val1; elseif (round(x1)==x1) x=x1; val=val1; else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1; while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1; 期末考试《运筹学》B 卷 一、单项选择题（在下列每题的四个选项中，只有一个选项是符合试题要求的。请把答案填入答题框中相应的题号下。每小题2分，共20分） 1．单纯形迭代中，出基变量在紧接着的下一次迭代中（ ）立即进基。 A ．会 B ．不会 C ．有可能 D ．不一定 2．线性规划的约束条件为 X 1 + X 2 + X 3 = 3 ，2X 1+ 2X 2+ X 4= 4，X i ≥0（i=1-4）,则基本可行解是（ ） A ．（0，0，4， 3） B ．（0，0，3，4） C ．（2，1，0，-2） D ．（3，0，0，-2） 3．普通单纯形法的最小比值定理的应用是为了保证（ ） A ．使原问题保持可行 B ．使对偶问题保持可行 C ．逐步消除原问题不可行性 D ．逐步消除对偶问题的不可行性 4. 原问题与对偶问题都有可行解，则有（ ） A ．原问题有最优解，对偶问题可能没有最优解 B ．原问题与对偶问题可能都没有最优解 C ．可能一个问题有最优解，另一个问题具有无界解 D ．原问题与对偶问题都具有最优解 5. 求解整数规划问题的分支定界法中，有（ ） A ．最大值问题的目标值是各分支的上界 B ．最大值问题的目标值是各分支的下界 C ．最小值问题的目标值是各分支的上界 D ．以上结论都不对 6．在运输方案中出现退化现象，是指数字格的数目 （ ） A ．等于 m+n B ．等于m+n-1 C ．小于m+n-1 D ．大于m+n-1 7．若运输问题的单位运价表的某一行元素分别加上一个常数k ，最优调运方案将（ ）。 A ．发生变化 B ．不发生变化 C ．A 、B 都有可能 D. 都不对 8．在产销平衡运输问题中，设产地为m 个，销地为n 个，那么解中非零 变量的个数（ ）。 A ．不能大于(m+n-1) B ．不能小于(m+n-1) C ．等于(m+n-1) D ．不确定 9．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ ）。 A ．无最优解 B ．有无穷最优解 C ．有唯一最优解 D ．出现退化解 10．动态规划问题中最优策略具有性质：（ ）。 A ．每个阶段的决策都是最优的 B ．当前阶段以前的各阶段决策是最优的 C ．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略 D ．它与初始状态无关 二、判断题（每题1分,共10分） function [x,y]=lpint(f,G,h,lb,ub,x,n,id) % 整数线性规划分枝定界法，可求解线性全整数或线性混合整数规划% 此程序基于Matlab优化工具箱的lp函数写成 % 此程序为GreenSim团队原创作品，转载请注明 % 欢迎访问GreenSim团队的主页https://www.doczj.com/doc/be9375969.html,/greensim % y = min f'x subject to: Gx <= h x为整 % x % 用法 % [x,y]=lpint(f,G,h) % [x,y]=lpint(f,G,h,lb,ub) % [x,y]=lpint(f,G,h,lb,ub,x) % [x,y]=lpint(f,G,h,lb,ub,x,n) % [x,y]=lpint(f,G,h,lb,ub,x,n,id) % 参数说明 % x: 最优解列向量 % y: 目标函数最小值 % f: 目标函数系数列向量 % G: 约束条件系数矩阵 % h: 约束条件右端列向量 % lb: 解的的下界列向量(Default: -inf) % ub: 解的的上界列向量(Default: inf) % x: 迭代初值列向量 % n: 等式约束数(Default: 0) % id: 整数变量指标列向量。1-整数，0-实数(Default: 1) % 举例 % min Z=x1+4x2 % s.t. 2x1+x2<=8 % x1+2x2>=6 % x1, x2>=0且为整数 %先将x1+2x2>=6化为 - x1 - 2x2<= -6 %》[x,y]=lpint([1;4],[2 1;-1 -2],[8;-6],[0;0]) % Y. MA & L.J. HU 1999 global upper opt c N x0 A b ID; if nargin<8, id=ones(size(f));end if nargin<7|isempty(n), n=0;end if nargin<6, x=[];end if nargin<5|isempty(ub), ub=inf*ones(size(f));end if nargin<4|isempty(lb), lb=zeros(size(f));end 1、概念： 分支定界算法(Branch and bound，简称为BB、B&B, or BnB)始终围绕着一颗搜索树进行的，我们将原问题看作搜索树的根节点，从这里出发，分支的含义就是将大的问题分割成小的问题。大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界，如果子问题不能产生一比当前最优解还要优的解，那么砍掉这一支。直到所有子问题都不能产生一个更优的解时，算法结束。 2、例子： 用BB算法求解下面的整数规划模型 因为求解的是最大化问题，我们不妨设当前的最优解BestV为-INF，表示负无穷。 1. 首先从主问题分出两支子问题： 通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75，Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF，说明这两支有搞头，继续往下。 2. 3. 从节点1和节点2两个子问题再次分支，得到如下结果： 子问题3已经不可行，无需再理。子问题4通过线性松弛得到最优解为10，刚好也符合原问题0的所有约束，在该支找到一个可行解，更新BestV = 10。 子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10，因此子问题5还有戏，待下一次分支。而子问题6得到upper bound为9<当前的BestV = 10，那么从该支下去找到的解也不会变得更好，所以剪掉！ 4. 对节点5进行分支，得到： 子问题7不可行，无需再理。子问题8得到一个满足原问题0所有约束的解，但是目标值为4<当前的BestV=10，所以不更新BestV，同时该支下去也不能得到更好的解了。 6. 整数规划分支定界法MATLAB程序 1.这种方法绝对能都解出答案，而且答案正确 function [x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub) x=zeros(n,1); x1=zeros(n,1); m1=2; m2=1; [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); if (x1==0) x=x1; val=val1; elseif (round(x1)==x1) x=x1; val=val1; else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1; while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1; lb1(d)=fix(x1(d))+1; 分支定界法 function [x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options) %整数线性规划分支定界法，可求解纯整数规划和混合整数规划。 %y=minf’*x s.t. G*x<=h Geq*x=heq x为全整数或混合整数列向量 %用法 %[x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options) %参数说明 %lb:解的下界列向量（Default:-int） %ub:解的上界列向量（Default:int） %x:迭代初值列向量 %id：整数变量指标列向量，1-整数，0-实数（Default:1） global upper opt c x0 A b Aeq beq ID options; if nargin<10,options=optimset({});options.Display='off'; https://www.doczj.com/doc/be9375969.html,rgeScale='off';end if nargin<9,id=ones(size(f));end if nargin<8,x=[];end if nargin<7 |isempty(ub),ub=inf*ones(size(f));end if nargin<6 |isempty(lb),lb=zeros(size(f));end if nargin<5,heq=[];end if nargin<4,Geq=[];end upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id; ftemp=ILP(lb(:),ub(:)); x=opt;y=upper; %下面是子函数 function ftemp=ILP(vlb,vub) global upper opt c x0 A b Aeq beq ID options; [x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options); if how <=0 return; end; if ftemp-upper>0.00005 %in order to avoid error return; end; if max(abs(x.*ID-round(x.*ID)))<0.00005 if upper-ftemp>0.00005 %in order to Linprogdis子程序: function [x,fval,exitflag,output,lambda]=... linprogdis(ifint,f,A,b,Aeq,beq,lb,ub,x0,options) %Title: % 分支定届法求解混合整数线性规划模型 % %初步完成：2002年12月 %最新修订: 2004-03-06 %最新注释：2004-11-20 %数据处理 [t1,t2] = size(b); if t2~=1, b=b';%将b转置为列向量 end %调用线性规划求解 [x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb,ub,x0,options); if exitflag<=0,%如果线性规划失败，则本求解也失败 return end %得到有整数约束的决策变量的序号 v1=find(ifint==1);%整数变量的index tmp=x(v1);%【整数约束之决策变量】的当前值 if isempty(tmp), %无整数约束，则是一般的线性规划，直接返回即可 return end v2=find(checkint(tmp)==0);%寻找不是整数的index if isempty(v2), %如果整数约束决策变量确实均为整数，则调用结束 return end %第k个决策变量还不是整数解 %注意先处理第1个不满足整数约束的决策变量 k=v1(v2(1)); %分支1：左分支 tmp1=zeros(1,length(f));%线性约束之系数向量 tmp1(k)=1; low=floor(x(k)); %thisA 分支后实际调用线性规划的不等式约束的系数矩阵A %thisb 分支后实际调用线性规划的不等式约束向量b if ifrowinmat([tmp1,low],[A,b])==1 %如果分支的约束已经存在旧的A，b中，则不改变约束 thisA= A; thisb= b; 整数规划分支定界法MATLAB 程序 1.这种方法绝对能都解出答案，而且答案正确function [x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub) x=zeros(n,1); x1=zeros(n,1); m1=2; m2=1; [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); if (x1==0) x=x1; val=val1; elseif (round(x1)==x1) x=x1; val=val1; else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1; while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1; lb1(d)=fix(x1(d))+1; if (a*lb1<=b) s1=0; end; ub2(d)=fix(x1(d)); if (a*lb2<=b) s2=0; end; end; end; e1={s1,a,b,aeq,beq,lb1,ub1,[],0}; e2={s2,a,b,aeq,beq,lb2,ub2,[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e2}; end; m1=m1+1; 分支定界(branch and bound) 算法是一种在问题的解空间树上搜索问题的解 的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。 利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是： 1 ．产生当前扩展结点的所有子结点； 2 ．在产生的子结点中，抛弃那些不可能产生可行解（或最优解）的结点； 3 ．将其余的子结点加入活结点表； 4 ．从活结点表中选择下一个活结点作为新的扩展结点。 如此循环，直到找到问题的可行解（最优解）或活结点表为空。 分支定界法本质还是一种枚举法，但是是隐枚举法。它是整数规划领域中非常重要的一类算法思想。是很多重要算法的源头。它能解决的实际问题很多，最著名的一个应该就是求解背包问题。 定义 分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。 算法步骤 第1步：放宽或取消原问题的某些约束条件，如求整数解的条件。如果这时求出的最优解是原问题的可行解，那么这个解就是原问题的最优解，计算结束。否则这个解的目标函数值是原问题的最优解的上界。 第2步：将放宽了某些约束条件的替代问题分成若干子问题，要求各子问题的解集合的并集要包含原问题的所有可行解，然后对每个子问题求最优解。这些子问题的最优解中的最优者若是原问题的可行解，则它就是原问题的最优解，计算结束。否则它的目标函数值就是原问题的一个新的上界。另外，各子问题的最优解中，若有原问题的可行解的，选这些可行解的最大目标函数值，它就是原问题的最优解的一个下界。 第3步：对最优解的目标函数值已小于这个下界的问题，其可行解中必无原问题的最优解，可以放弃。对最优解的目标函数值大于这个下界的子问题，都先保留下来，进入第4步。 第4步：在保留下的所有子问题中，选出最优解的目标函数值最大的一个，重复第1步和第2步。如果已经找到该子问题的最优可行解，那么其目标函数值与前面保留的其他问题在内的所有子问题的可行解中目标函数值最大者，将它作为新的下界，重复第3步，直到求出最优解。 整数线性规划之分支定界法 摘要 最优化理论和方法是在上世纪 40 年代末发展成为一门独立的学科。1947年，Dantaig 首先提出求解一般线性规划问题的方法，即单纯形算法，随后随着工业革命、计算机技术的巨大发展，以及信息革命的不断深化，到现在的几十年时间里，它有了很快的发展。目前，求解各种最优化问题的理论研究发展迅速，例如线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等，各种新的方法也不断涌现，并且在军事、经济、科学技术等方 面应用广泛，成为一门十分活跃的学科。 整数规划（integer programming）是一类要求要求部分或全部决策变量取整数值的数学规划，实际问题中有很多决策变量是必须取整数的。本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。 关键词：整数线性规划；分支定界法；matlb程序； 1．引言 1.1优化问题发展现状 最优化理论与算法是一个重要的数学分支，它所讨论的问题是怎样在众多的方案中找到一个最优的方案.例如，在工程设计中，选择怎样的设计参数，才能使设计方案既满足要求又能降低成本；在资源分配中，资源有限时怎样分配，才能使分配方案既可以满足各方面的要求，又可以获得最多的收益；在生产计划安排中，怎样设计生产方案才能提高产值和利润；在军事指挥中，确定怎样的最佳作战方案，才能使自己的损失最小，伤敌最多，取得战争的胜利；在我们的生活中，诸如此类问题，到处可见.最优化作为数学的一个分支，为这些问题的解决提供了一些理论基础和求解方法. 最优化是个古老的课题.长期以来，人们一直对最优化问题进行着探讨和研究.在二十世纪四十年代末，Dantzig 提出了单纯形法，有效地解决了线性规划问题，从而最优化成为了一门独立的学科。目前，有关线性规划方面的理论和算法发展得相当完善,但是关于非线性规划问题的理论和算法还有待进一步的研究，实际应用中还有待进一步的完善。传统的非线性全局最优化方法只能求出问题的局部最优解，但由于许多问题的局部最优解不一定是全局最优解，使得传统的非线性最优化方法不能直接成功地应用于求解非线性全局最优化问题。另外，没有一个固定的评判标准来判断得到的局部最优解是否为全局最优解。随着科学技术的发展和计算机计算能力的提高，最优化理论在最近这几年来得到了迅速的发展，涌现出了许多新的算法, 如打洞函数法,填充函数法，lagrangian 乘子函数方法，信赖域方法，虑子方法等。 本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。 1.2整数线性规划及其数学模型 整数规划主要有以下三大类： （1）全整数规划（all integer programming）：所有的决策变量都取整数值，也称为纯整数规划（pure integer programming）； （2）混合整数规划（mixed integer programming）：仅要求一部分决策变量取整数值； （3）0-1规划（zero-one integer programming）：该类问题的决策变量只能取0或1. 本文主要讨论的整数线性规划问题模型为： 一．线性规划 1.问题背景：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人 们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源. 线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题 2.求解方法： a.单纯形法： 适用的问题：约束条件全部为≤，右边常数全部为非负，对目标函数的系数没有要求。 min z=3x1-2x2 s.t. x1+2x2≤12 2x1+ x2≤18 x1,x2≥0 求解步骤： STEP 0 将线性规划问题标准化 STEP 1 是否有明显的初始基础可行解，如果有，转STEP 3，否则，转STEP 2。 STEP 2 构造辅助问题，用两阶段法求解辅助问题。如果辅助问题最优解的目标函数值大于0，原问题无可行解，算法终止。否则转STEP 3。 STEP 3 写出单纯形表，将基变量在约束条件中的系数消为单位矩阵，将基变量在目标函数中的系数消为0。转STEP 4。 STEP 4 如果所有非基变量的检验数全为负数或0，则已获得最优解，算法终止。否则，选择检验数为正数并且绝对值最大的非基变量为进基变量。转STEP 5。 STEP 5 如果进基变量在约束条件中的系数全为负数或0，目标函数无界，算法终止。否则根据右边常数和正的系数的最小比值，确定离基变量。转STEP 6。 STEP 6 进基变量列和离基变量行交叉的元素称为主元。对单纯形表进行行变换，将主元变为1，将主元所在列的其他元素变为0。转STEP 4。 b.对偶单纯形法： 适用的问题:约束条件中至少有一个是≥，相应的右边常数为非负，目标函数系数全部为非负。 min z=3x1+2x2 s.t. x1+2x2≥12 2x1+ x2≤18 x1,x2≥0 求解步骤： 步骤1 确定原问题（L）的初始基B，使所有检验数，即是对偶可行解，建立初始单纯形表。 步骤2 检查基变量的取值，若≥0，则已得最优解，计算停；否则求确定单纯形表第L行对应的基变量为旋出变量。 步骤3 若所有,则原问题无可行解，计算停；否则，计算确定对应的为旋入变量。 步骤4 以为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。可以证明，按上述方法进行迭代，所得解始终是对偶可行解。 二．运输问题 1.问题背景：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产 地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 分支定界法Matlab 程序实现与验证 为了更深入理解分支定界法计算流程，从而决定花费几天时间仔细学习该算法，并编写出该算法的Matlab 计算程序。同时为了后面个人的借鉴学习，编写本文档。在进行分支定界法计算程序编写过程中，通过网络搜索，发现了Matlab2014版之后嵌入了混合整数线性规划求解函数intlinprog，从而也将该函数的使用方法撰写下来。 1 整数规划问题简介 在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如：所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。人们称这样的问题为整数规划(Integer Programming，IP)，整数规划是最近几十年发展起来的规划论中的一个分支。 整数规划中如果所有的变数都限制为(非负)整数，就称为纯整数规划(Pure Integer Programming，PIP)或称为全整数规划(All Integer Programming，AIP)；如果仅一部分变数限制为整数，则称为混合整数计划(Mixed Integer Programming，MIP)。整数规划的一种特殊情形是0-1规划，该规划中变量的取值仅限于0或1，指派问题就是一类典型的0-1规划问题。 现举例说明用前述单纯形法求得的解不能保证是整数最优解。 例1：某厂拟用集装箱托运甲乙两种货物, 每箱的体积、重量、可获利润以及托运所受限制如表1所示。问两种货物各托运多少箱, 可使获得利润为最大? 表1 货物托运示例数据 货物 体积（m3/箱） 重量（百公斤/箱）利润（百元/箱） 甲 5 2 20 乙 4 5 10 托运限制 24（m3） 13百公斤 设1x 、2x 分别为甲、乙两种货物的托运箱数（为非负整数），列该问题的纯 整数规划模型如下： 12max 2010z x x =+ 分支定界法 分支定界法，顾名思义，就是按照定好的界进行分支。这里说的分支意思是“剪枝”。剪的枝是问题解空间树的枝。所谓解空间树，即此问题所有解和中间解形成的树型结构，是有序的。常有排列树和子集树之分，举个例子，n个物品的0-1背包问题的解空间树就是子集树(每个物品都可能为0或1)，而最短路径问题的解空间树是一颗排列树。 分支定界法一般有两种实现形式：1.优先队列法2.FIFO队列法。这与分支定界的思想无太多本质联系，只是前者在一般情况下能更快的求得问题解。分支定界法要对问题的解空间树进行“剪枝”操作以减少对解空间树的搜索。那么问题是，如何“剪枝”？这就要回答如何定界的问题。在分支定界法中，“界”的作用就是用来阻止对不可行分支的搜索的。当解空间树很深时（叶子节点为解），如果能在前面几层就预先的知道了“此路不通”或者“此路不是最优”而停止此路的继续，这样能大幅度的提高算法效率。如何定界要放入具体问题中考虑，一般可以以“理论最大最小”这个概念来求界。以0-1背包问题为例，设所有物品预先已经按照单位价值量递减排列。在解空间树的第i层（此时正在考虑第i个物品是否应该被放入的时刻），设左子树为放入i物品，右子树为不放i物品。那么在确定左子树的上界的时候有：界=当前价值+i 的价值+MaxValue(背包剩余重量-i物品重量);其中的MaxValue为放i后剩余背包容量能获得的最大价值，应该注意的是此最大价值为理论意义上的最大价值，比如在继续放入p个后(按单位价值量递减),放不下第p+1个，此时应该按(Value[p+1]/Weight[p+1])*(WeightLeft)来计p+1物品的价值,(实际中不可能放入零点几个某物品。。。)；右子树的情形类似。 知道了如何定界，那么在实际流程中就要根据当前目标节点的界来剪枝了（是用上界还是下界，具体问题具体分析）。今天准备举个稍微有点挑战的例子---NPC问题中的TSP问题。 在TSP问题中，由于是环路，每个节点都要进出各一次，我们可以将每个节点最小的入度和最小的出度的和累加作为一个下界，这个下界几乎不可能达到！（全部最小出度的和即为下面提到的rcost的初值） 初始时我们创建一个最小堆，表示活节点队列。堆中按照每个节点的下界来划分优先级，下界越小的优先级越高。由于有是要求回路最小值，所以可以先判断此图是否有回路，没有直接返回，有再继续往下做。然后开始解空间树的搜索，广度优先遍历当前点的连通点，用curcost 来存当前的耗费总和，rcost表示当前点到叶子节点最小出度之和，那么一个节点的下界计算为：curcost+rcost-MinOut(当前点);如果此下界小于当前最优值，则将这个连 分支定界法 分支定界法(branch and bound)是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。 基本信息 中文名称：分支定界法 外文名称：branch and bound 用途：整数规划问题 性质：算法 定义 分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。 算法步骤 第1步：放宽或取消原问题的某些约束条件，如求整数解的条件。如果这时求出的最优解是原问题的可行解，那么这个解就是原问题的最优解，计算结束。否则这个解的目标函数值是原问题的最优解的上界。 第2步：将放宽了某些约束条件的替代问题分成若干子问题，要求各子问题的解集合的并集要包含原问题的所有可行解，然后对每个子问题求最优解。这些子问题的最优解中的最优者若是原问题的可行解，则它就是原问题的最优解，计算结束。否则它的目标函数值就是原问题的一个新的上界。另外，各子问题的最优解中，若有原问题的可行解的，选这些可行解的最大目标函数值，它就是原问题的最优解的一个下界。 第3步：对最优解的目标函数值已小于这个下界的问题，其可行解中必无原问题的最优解，可以放弃。对最优解的目标函数值大于这个下界的子问题，都先保留下来，进入第4步。 第4步：在保留下的所有子问题中，选出最优解的目标函数值最大的一个，重复第1步和第2步。如果已经找到该子问题的最优可行解，那么其目标函数值与前面保留的其他问题在内的所有子问题的可行解中目标函数值最大者，将它作为新的下界，重复第3步，直到求出最优解。 分支定界(branch and bound) s搜索法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同，分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树，并且，在分支定界算法中，每一个活结点只有一次机会成为扩展结点。利用分支定界算法对问题的解空间树进行搜索，它的搜索策略是： 1 ．产生当前扩展结点的所有孩子结点； 2 ．在产生的孩子结点中，抛弃那些不可能产生可行解（或最优解）的结点； 3 ．将其余的孩子结点加入活结点表； 4 ．从活结点表中选择下一个活结点作为新的扩展结点。如此循环，直到找到问题的可行解（最优解）或活结点表为空。从活结点表中选择下一个活结点作为新的扩展结点，根据选择方式的不同，分支定界算法通常可以分为两种形式： 1 ．FIFO(First In First Out) 分支定界算法：按照先进先出原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。 2 ．最小耗费或最大收益分支定界算法：在这种情况下，每个结点都有一个耗费或收益。如果要查找一个具有最小耗费的解，那么要选择的下一个扩展结点就是活结点表中具有最小耗费的活结点；如果要查找一个具有最大收益的解，那么要选择的下一个扩展结点就是活结点表中具有最大收益的活结点。又称分支定界搜索法。过程系统综合的一类方法。该法是将原始问题分解，产生一组子问题。分支是将一组解分为几组子解，定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外，就将这一子组舍弃（剪枝）。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。分支定界法的思想是：首先确定目标值的上下界，边搜索边减掉搜索树的某些支，提高搜索效率。在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。我们知道，深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；而广度优先搜索虽然时间复杂度比前者低一些，但其庞大的空间需求量又往往让人望而却步。所以，对程序进行优化，就成为搜索算法编程中最关键的一环。本文所要讨论的便是搜索算法中优化程序的一种基本方法枣“剪枝”。什么是剪枝相信刚开始接触搜索算法的人，都做过类似迷宫这样的题目吧。我们在“走迷宫”的时候，一般回溯法思路是这样的： 一、编程 利用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 1、分支限界法 (1)描述：采用广度优先产生状态空间树的结点，并使用剪枝函数的方法称为分枝限界法。 所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。 所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。 (2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（E-结点）R后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。然后，从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程，直至找到问题的解或判定无解为止。 (3)分支限界法与回溯法 1)求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2)搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 (4)常见的分支限界法 1)FIFO分支限界法(队列式分支限界法) 基本思想：按照队列先进先出(FIFO)原则选取下一个活结点为扩展结点。 搜索策略：一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 2)LC(least cost)分支限界法(优先队列式分支限界法) 基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。 搜索策略：对每一活结点计算一个优先级（某些信息的函数值），并根据这些优先级；从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点，……，直到找到一个解或活结点队列为空为止。 (5)分支限界法搜索应用举例 1)0-1背包问题，当n=3时，w={16,15,15},p={45,25,25},c=30 以下内容基本为转载内容: 1. 模型 整数规划的模型与线性规划基本相同，只是额外的添加了部分变量为整数的约束。 2. 求解步骤 整数规划求解的基本框架是分支定界法（Branch and bound，BnB）。首先去除整数约束得到“松弛模型”，使用线性规划的方法求解。若有某个变量不是整数，在松弛模型上分别添加约束： x<=floor(A) 和 x>=ceil(A) 然后再分别求解，这个过程叫做分支。当节点求解结果中所有变量都是整数时，停止分支。这样不断迭代，形成了一棵树。 定界，指的是叶子节点产生后，相当于给问题定了一个下界。 之后在求解过程中一旦某个节点的目标函数值小于这个下界，那就直接pass，不用再进行分支了；每次新产生叶子节点，则更新下界。 3. python算法实现 import mathfrom scipy.optimize import linprogimport sys def integerPro(c,A,b,Aeq,beq,t=1.0E-12): res=linprog(c,A_ub=A,b_ub=b,A_eq=Aeq,b_eq=beq) if(type(res.x)is float):#produces error code bestX=[sys.maxsize]*len(c) else: bestX=res.x bestVal=sum([x*y for x,y in zip(c,bestX)]) if all(((x-math.floor(x)) 分枝定界-简介 分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。 分枝定界-方法 有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）： 1) 先进先出（F I F O）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。 2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。 分枝定界-例子 例5-1 【迷宫老鼠】考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（1 , 1）被置为1，以免再次返回到这个位置。（1，1）被扩充，它的相邻节点（1，2）和（2，1）加入到队列中（即活节点表）。为避免再次回到这两个位置，将位置（1，2）和（2，1）置为1。此时迷宫如图1 7 - 1 a所示，E-节点（1，1）被删除。 节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间），只有（1，3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）被置为1，节点（2，1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1） 分支定界法原理简介 分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。分支定界法是计算机最擅长的广义搜索穷举算法。 基本思想： 1. 松弛模型的最优解要优于其相应的整数规划的解 由于松弛模型可行解的区域（多边形）包含了对应的整数规划的可行解的集合（多边形内的整数点），因而松弛模型的解要优于整数规划的解。这就是说，如果问题是求最大值的，则松弛模型最优解对应的目标函数值必大于或等于整数规划最优解对应的目标函数值；如果问题是求最小值的，则松弛模型的最优解对应的目标函数值必小于或等于整数规划最优解对应的目标函数值。由此可以推出： 2. 松弛模型的最优解如果是整数解，则必然也是整数规划的最优解。 3. 松弛模型的最优解如果不是整数解，则如果问题是求最大值的，松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个上界；如果问题是求最小值的，则松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个下界。 我们用例子来说明用分支定界法求解整数规划的步骤。 例 求下面整数规划的最优解 12 12121212max 4090s.t. 9756 72070 ,0 x ,Z x x x x x x x x x =++≤+≤≥为整数 解 从上述各约束条件可见，是一个可行解，对应的松弛模型目标函数值。本问题是一个求最大值的问题，因而整数规划最优解的目标函数的下界可以取为0，即取整数规划模型最优值的下界(0,0)0Z =0Z =。 先考虑此整数规划问题的线性松弛模型0： 其解为 松弛模型0 012356 4.811.82 Z x x === 由于松弛模型解的目标函数值是整数规划模型最优值的一个上界，可以取此处的0Z 为整数规划模型最优值的一个上界356Z =。由于该松弛模型解不是整数 解，分原问题为和两个子模型：子模型1和子模型2。 14x ≤15x ≥整数规划分支定界算法matlab通用源程序
运筹学 (1)
整数规划_分支定界法_MATLAB程序
分支定界法详解
整数规划_分支定界法_MATLAB程序
分支定界法
分支定界算法的MATLAB程序
整数规划_分支定界法_MATLAB程序
分支定界法知识
分支定界法
运筹学方法总结
分支定界法Matlab程序实现与验证
分支定界法
分支定界法
分支定界问题1
整数规划分支定界法
分支定界
分支定界法
分支定界法概述
分支定界法原理简介
相关主题
文本预览