什么是分支定界法

出处:游戏玩家inone    更新日期:2019-01-20
先不考虑整数限制,求出相应的线性规划的最优解,若此解不符合整数要求,则去掉不包含整数解的部分可行域,将可行域D分成D1、D2两部分(分枝) ,然后分别求解这两部分可行域对应的线性规划,如果它们的解仍不是整数解,则继续去掉不包含整数解的部分可行域,将可行域或分成与两部分,再求解与对应的线性规划,……,在计算中若已得到一个整数可行解,则以该解的目标函数值作为分枝的界限,如果某一线性规划的目标值Z≤Z0,就没有必要继续分枝,因为分枝(增加约束)的结果所得的最优解只能更差。反之若Z>Z0,则该线性规划分枝后,有可能产生更好的整数解,一旦真的产生了一个更好的整数解,则以这个更好的整数解目标值作为新的界限,继续进行分枝,直至产生不出更好的整数解为止。

算法分析中的,比如解决旅行商问题的一种方法。

一个搜索50个城市中任意两个最短路径的程序,分支定界法实现。另有一份程序说明,留下邮箱,给分后发你 /* 用记事本阅读程序源代码时,请将“格式”-〉“自动换行”去掉 */ /* 程序源代码如下,在VC++6.0上编译运行通过 */ /* 本程序用C语言实现,故依据C语言的语法,数字0表示甲城市,数字49表示乙城市 */ #include #include #include #define MAX 500 /* 用栈来实现深度优先遍历,MAX表示栈的最大容量 */ #define N 50 /* 城市的数目 */ #define TRUE 1 #define FALSE 0 void Floyd(int d[N][N]); /* 弗洛伊德算法的实现函数 */ void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]); /* 分枝定界算法的实现函数 */ void input(int a[N][N],int b[N][N]); /* 把矩阵b赋值给矩阵a */ int p[N][N][N]; /* 三维数组p[N][N][N]是用来实现弗洛伊德算法的辅助矩阵 */ int visited[N],distBound=9999,costBound=1500; /* 数组visited[N]用来标识所代表的城市是否被访问,1表示被访问,0表示未被访问 */ int bestPath[N],bestLength=0,shortestDist=0,minimumCost=0; /* bestPath[N]用来记录寻找出的可行路径,bestLength 、shortestDist和minimumCost 分别表示所找到的可行路径的所经历城市的数目、距离和代价 */ void main() { int i,j,mindist[N][N],mincost[N][N],m1[N][N],m2[N][N]; /* m1[N][N]和m2[N][N]分别代表题目所给的距离矩阵和代价矩阵 */ FILE *fp; system("cls"); for(i=0;i<N;i++) { visited[i]=0; bestPath[i]=0; } fp=fopen("m1.txt","r"); /* 把文件中的距离矩阵m1读入数组mindist[N][N] */ if(fp==NULL) { printf("can not open file\n"); return; } for(i=0;i<N;i++) for(j=0;j<N;j++) fscanf(fp,"%d",&mindist[i][j]); fclose(fp); /* 距离矩阵m1读入完毕 */ fp=fopen("m2.txt","r"); /* 把文件中的代价矩阵m2读入数组mincost[N][N] */ if(fp==NULL) { printf("can not open file\n"); return; } for(i=0;i<N;i++) for(j=0;j<N;j++) fscanf(fp,"%d",&mincost[i][j]); fclose(fp); /* 代价矩阵m2读入完毕 */ input(m1,mindist); /* mindist[N][N]赋值给m1[N][N],m1[N][N]代表题目中的距离矩阵 */ input(m2,mincost); /* mincost[N][N]赋值给m2[N][N],m2[N][N]代表题目中的代价矩阵 */ for(i=0;i<N;i++) /* 把矩阵mindist[i][i]和mincost[i][i]的对角元素分别初始化,表明城市到自身不连通,代价为0 */ { mindist[i][i]=9999; mincost[i][i]=0; } Floyd(mindist); /* 用弗洛伊德算法求任意两城市之间的最短距离,结果存储在数组mindist[N][N]中 */ Floyd(mincost); /* 用弗洛伊德算法求任意两城市之间的最小代价,结果存储在数组mincost[N][N]中 */ fenzhi(m1,m2,mindist,mincost); /* 调用分支定界的实现函数,寻找出所有的可行路径并依次输出 */ printf("请按任意键退出:"); getchar(); } void Floyd(int d[N][N]) /* 弗洛伊德算法的实现函数 */ { int v,w,u,i; for(v=0;v<N;v++) for(w=0;w<N;w++) { for(u=0;u<N;u++) p[v][w][u]=FALSE; if(d[v][w]!=9999) { p[v][w][v]=TRUE; p[v][w][w]=TRUE; } } for(u=0;u<N;u++) for(v=0;v<N;v++) for(w=0;w<N;w++) if(d[v][u]+d[u][w]<d[v][w]) { d[v][w]=d[v][u]+d[u][w]; for(i=0;i<N;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } } void input(int a[N][N],int b[N][N]) /* 把矩阵b赋值给矩阵a */ { int i,j; for(i=0;i<N;i++) for(j=0;j<N;j++) a[i][j]=b[i][j]; } void fenzhi(int m1[N][N],int m2[N][N],int mindist[N][N],int mincost[N][N]) { int stack[MAX],depth=0,next,i,j; /* 定义栈,depth表示栈顶指针;next指向每次遍历时当前所处城市的上一个已经遍历的城市 */ int cur,currentDist=0,currentCost=0; /* cur指向当前所处城市,currentDist和currentCost分别表示从甲城市到当前所处城市的最短距离和最小代价, currentDist和currentCost初值为0表示从甲城市出发开始深度优先搜索 */ stack[depth]=0; /* 对栈进行初始化 */ stack[depth+1]=0; visited[0]=1; /* visited[0]=1用来标识从甲城市开始出发进行遍历,甲城市已被访问 */ while(depth>=0) /* 表示遍历开始和结束条件,开始时从甲城市出发,栈空,depth=0;结束时遍历完毕,所有节点均被出栈,故栈也为空,depth=0 */ /* 整个while()循环体用来实现从当前的城市中寻找一个邻近的城市 */ { cur=stack[depth]; /* 取栈顶节点赋值给cur,表示当前访问到第cur号城市 */ next=stack[depth+1]; /* next指向当前所处城市的上一个已经遍历的城市 */ for(i=next+1;i<N;i++) /* 试探当前所处城市的每一个相邻城市 */ { if(m1[cur][i]==9999) continue; /* 所试探的城市不连通 */ if(visited[i]==1) continue; /* 所试探的城市已被访问 */ if((currentCost+mincost[cur][N-1]>costBound)||(currentDist+mindist[cur][N-1]>=distBound)) /* 所试探的城市满足剪枝条件,进行剪枝 */ continue; if(i<N) break; /* 所试探的城市满足访问条件,找到新的可行城市,终止for循环 */ } if(i==N) /* 判断for循环是否是由于搜索完所有城市而终止的,如果是(i==N),进行回溯 */ { depth--; currentDist-=m1[stack[depth]][stack[depth+1]]; currentCost-=m2[stack[depth]][stack[depth+1]]; visited[stack[depth+1]]=0; } else /* i!=N,表示for循环的终止是由于寻找到了当前城市的一个可行的邻近城市 */ { currentDist+=m1[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的距离加入currentDist */ currentCost+=m2[stack[depth]][i]; /* 把从当前所处城市到所找到的可行城市的代价加入currentCost */ depth++; /* 所找到的可行城市进栈 */ stack[depth]=i; /* 更新栈顶指针,指向所找到的可行城市 */ stack[depth+1]=0; visited[i]=1; /* 修改所找到的城市的访问标志 */ if(i==N-1) /* i==N-1表示访问到了乙城市,完成了所有城市的一次搜索,找到一条通路 */ { for(j=0;j<=depth;j++) /* 保存当前找到的通路所经过的所有节点 */ bestPath[j]=stack[j]; bestLength=depth; /* 保存当前找到的通路所经过的所有节点的节点数 */ shortestDist=currentDist; /* 保存当前找到的通路的距离之和 */ minimumCost=currentCost; /* 保存当前找到的通路的代价之和 */ distBound=currentDist; /* 更新剪枝的路径边界,如果以后所找到的通路路径之和大于目前通路的路径之和,就剪枝 */ if(minimumCost>1500) continue; /* 如果当前找到的通路的代价之和大于1500,则放弃这条通路 */ printf("最短路径:%3d,路径代价:%3d,所经历的节点数目:%3d,所经历的节点如下:\n",shortestDist,minimumCost,bestLength+1); /* 输出找到的通路的结果 */ bestPath[bestLength]=49; for(i=0;i<=bestLength;i++) /* 输出所找到的通路所经过的具体的节点 */ printf("%5d",bestPath[i]); printf("\n"); depth--; /* 连续弹出栈顶的两个值,进行回溯,开始寻找新的可行的通路 */ currentDist-=m1[stack[depth]][stack[depth+1]]; currentCost-=m2[stack[depth]][stack[depth+1]]; visited[stack[depth+1]]=0; depth--; currentDist-=m1[stack[depth]][stack[depth+1]]; currentCost-=m2[stack[depth]][stack[depth+1]]; visited[stack[depth+1]]=0; } } } }

你那目标函数的x1的系数是多少? 看不清

以前数模学过 有点忘了 好象是取出一个数代进去不对就可以知道所有大于(或者小于)这个数的值都不对 希望对你有帮助

 什么是分支定界法?基本思想是什么 : 分支定界 (branch and bound) 算法是一种在问题的解空间树上搜索问题的解的方法.但与...
什么是分支定界法?基本思想是什么 : 分支定界法是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划,还可以求解混合整数规划...
分支定界法的算法步骤 : (1)求整数规划的松弛问题最优解。(2)若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转...
分支定界法的优缺点是什么: 把问题的可行解展开如树的分枝,再经由各个分枝中寻找最佳解.求解医院运输部门运输中心个数最佳化之研究。...
分支定界法中的定界是什么意思:   意思是:通过搜索与迭代,得到整数规划的最优解   分支定界法(branch and bound)...
分支定界法 : 。通常,把全部可行解空间反复地分割为越来越小的子 集,称为分枝;并且对每个子集内的解集计算一个目标下...
运筹学的问题 用分支定界法解整数规划问题时,停止分支的条件是什么?3个空格,: 1 这个分支不大于其它分支的值;2 得到的就是整数解;3 无可行域.
分支定界算法?: 第1步:放宽或取消原问题的某些约束条件 如求整数解的条件.如果这时求出的最优解是原问题的可行解 那么...
如何有分枝定界法解指派问题: 分枝定界法(branch and bound)是一种求解非线性整数规划问题的常用算法.这种...运筹...