编辑实验 创建词条
人大经济论坛-经管百科

分枝界限法 发表评论(0) 编辑词条

目录

[显示全部]

分枝界限法(Branch and Bound Method)

什么是分枝界限法 编辑本段回目录

 分枝界限法是由三栖学者查理德·卡普Richard M.Karp)在20世纪60年代发明,成功求解含有65个城市旅行商问题,创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝,再经由各个分枝中寻找最佳解。

  分枝界限法也能够使用在混合整数规划问题上,其为一种系统化的解法,以一般线性规划之单形法解得最佳解后,将非整数值之决策变量分割成为最接近的两个整数,分列条件,加入原问题中,形成两个子问题(或分枝)分别求解,如此便可求得目标函数值的上限(上界)或下限(下界),从其中寻得最佳解[2]

分枝界限法的基本思想[3] 编辑本段回目录

  1、基本思想

  分枝定界法是一个用途十分广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)。在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支。这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。

  将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。

  2、分枝节点的选择

  对搜索树上的某些点必须作出分枝决策,即凡是界限小于迄今为止所有可行解最小下界的任何子集(节点),都有可能作为分枝的选择对象(对求最小值问题而言)。怎样选择搜索树上的节点作为下次分枝的节点呢?有两个原则:

  1)从最小下界分枝(队列式FIFO分枝限界法):每次算完界限后,把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点,此结点即为下次分枝的结点。

  • 优点:检查子问题较少,能较快地求得最佳解;
  • 缺点:要存储很多叶节点的界限及对应的耗费矩阵,花费很多内存空间。

  2)从最新产生的最小下界分枝(优先队列式分枝限界法):从最新产生的各子集中选择具有最小的下界的结点进行分枝。

优点:节省了空间; 缺点:需要较多的分枝运算,耗费的时间较多。

  这两个原则更进一步说明了,在算法设计中的时空转换概念。

  分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题,分枝与界限的步骤和内容可能不同,但基本原理是一样的。

分枝界限法的步骤[4] 编辑本段回目录

  分枝界限法是组合优化问题的有效求解方法,其步骤如下所述:

  步骤一:如果问题的目标为最小化,则设定目前最优解的值Z=∞

  步骤二:根据分枝法则(Branching rule),从尚未被洞悉(Fathomed)节点(局部解)中选择一个节点,并在此节点的下一阶层中分为几个新的节点。

  步骤三:计算每一个新分枝出来的节点的下限值(Lower bound,LB)

  步骤四:对每一节点进行洞悉条件测试,若节点满足以下任意一个条件,则此节点可洞悉而不再被考虑:

  • 此节点的下限值大于等于Z值。
  • 已找到在此节点中,具最小下限值的可行解;若此条件成立,则需比较此可行解与Z值,若前者较小,则需更新Z值,燕以此为可行解的值。
  • 此节点不可能包含可行解。

  步骤五:判断是否仍有尚未被洞悉的节点,如果有,则进行步骤二,如果已无尚未被洞悉的节点,则演算停止,并得到最优解。

  Kolen等曾利用此方法求解含时间窗约束的车辆巡回问题,其实验的节点数范围为6-15。当节点数为6时,计算机演算所花费的时间大约1分钟(计算机型为VAZ11/785),当节点数扩大至12时,计算机有内存不足的现象产生,所以分枝定界法比较适用于求解小型问题。Held和Karp指出分枝定界法的求解效率,与其界限设定的宽紧有极大的关系。

分枝界限法的算法实例[3] 编辑本段回目录

  1、型推销员问题

  设有5个城v1,v2,v3,v4,v5 ,从某一城市出发,遍历各城市一次且仅一次,最后返回原地,求最短路径。其费用矩阵如下:

  D=\begin{bmatrix}\infty&14&1&16&2\\ 14&\infty&25&2&3\\1&25&\infty&9&9\\16&2&9&\infty&6\\2&3&9&6&\infty\end{bmatrix}

  将矩阵D对角线以上的元素从小到大排列为:

  d13,d15,d24,d45,d34,d35KKKK

  取最小的5个求和得:d13 + d15 + d24 + d45 = 14

  用分枝界限法表示,要构成一个回路,所以每个顶点的下标在回路的所有边中各出现两次。(1)中显然5出现了3次,若用d35代替d15d13 + d35 + d24 + d25 + d45 = 21

  分枝界限法

  搜索过程可以表示如下图:

  分枝界限法

  图(2)的下界为21,图(3)的下界为20,都大于19故没有进一步搜索的价值,因此(5)为最佳路径:v_1\to v_3\to v_4\to v_2\to v_5\to v_1

  2、型推销员问题

  D = (dij)n * nd_{ij}\ne d_{ji}。不妨把D看成旅费,即从vivj的旅费与vjvi不一样。

  D=\begin{bmatrix}\infty&24&34&14&15\\ 19&\infty&20&9&6\\7&9&\infty&6&8\\23&10&22&\infty&7\\20&8&11&20&\infty\end{bmatrix}

  对D的每行减去该行的最小元素,或每列减去该列的最小元素,得一新矩阵,使得每行每列至少都有一个0元素。

  分枝界限法

  第一列和第三列没有为0的元素,所以第一列和第三列分别减去其最小元素1和3得:

  D=\begin{bmatrix}\infty&10&17&0&1\\ 12&\infty&11&3&0\\0&3&\infty&0&2\\15&3&12&\infty&0\\11&0&0&12&\infty\end{bmatrix}_{45}

  由于从任一vi出发一次,进入vi也是一次,所以问题等价于求D=\begin{bmatrix}\infty&10&17&0&1\\ 12&\infty&11&3&0\\0&3&\infty&0&2\\15&3&12&\infty&0\\11&0&0&12&\infty\end{bmatrix}_{45} 的最佳路径,下标45是估计的界,即旅费起码为45单位(每个点出发都去最小值)。

  由于矩阵D第一行第四列元素为0,故从v1出发的路径应选择v1 − − v4,为了排除v1出发进入其他点和从其他点进入v4的可能,并封锁v4v1的路径,在矩阵中除去第一行和第四列,并将第四列第一行元素15改为∞。得:

  \begin{bmatrix}12&\infty&11&0\\ 0&3&\infty&2\\\infty&3&12&0\\11&0&0&\infty\end{bmatrix}_{45}

  类似的从v2出的路径应选v2 − − v5,消第v2行和第v5列,并将第v5行第v2列元素改为∞得:

  \begin{bmatrix}0&3&\infty\\\infty&3&12\\11&\infty&0\end{bmatrix}_{45}

  这时第二行没有0元素,减去最小元素3得:   \begin{bmatrix}0&3&\infty\\\infty&0&9\\11&\infty&0\end{bmatrix}_{45}

  搜索过程如下图:

  分枝界限法

  最后得到最佳路径为:v_1\to v_4\to v_2\to v_5\to v_3\to v_1

分枝界限法的算法分析[3] 编辑本段回目录

  1、算法优点:可以求得最优解、平均速度快。

  因为从最小下界分支,每次算完限界后,把搜索树上当前所有的叶子结点的限界进行比较,找出限界最小的结点,此结点即为下次分支的结点。这种决策的优点是检查子问题较少,能较快的求得最佳解。

  2、缺点:要存储很多叶子结点的限界和对应的耗费矩阵。花费很多内存空间。

  存在的问题:分支定界法可应用于大量组合优化问题。其关键技术在于各结点权值如何估计,可以说一个分支定界求解方法的效率基本上由值界方法决定,若界估计不好,在极端情况下将与穷举搜索没多大区别。

参考文献 编辑本段回目录

  1. 邓宇佑(硕士).求解医院运输部门运输中心个数最佳化之研究
  2. 《作业研究》[M].第七章 整数规划
  3. 3.0 3.1 3.2 分枝界限法
  4. 夏新海.物流配送车辆调度优化研究[D].武汉理工大学,2004年
经管百科已经为您找到更多关于“分枝界限法”的相关信息,点击查看>>

附件列表

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
0

标签: 分枝界限法 决策 城市 旅行商问题 武汉理工大学 货郎担问题 查理德·卡普 Richard M.Karp

收藏到: Favorites  

同义词: 暂无同义词

关于本词条的评论 (共0条)发表评论>>