由于这方法灵活且便于用计算机求解，所以现在它已是解决整数规划问题的重要方法之一。目前已成功地应用于求解整数规划问题、生产进度问题、背包问题及分配问题等等。本文来自优.文~论^文·网原文请找腾讯3249.114
用分支定界法求解整数规划(以最大值为例)问题的步骤[14]为：
开始，将求解的整数规划问题称为问题IP，将与它相应的线性规划问题(松驰问题)称为问题LP。
(1)求解问题LP可能得到以下情况之一：
①若LP没有可行解，这时IP也没有可行解，则停止。
②若LP有最优解，并符合问题IP的整数条件，LP的最优解即为IP的 最优解，则停止。
③若LP有最优解，但不符合问题IP的整数条件，记目标函数值为 。
(2)用观察法找问题IP的一个整数可行解，一般可取 进行试探，求得其目标函数值，并记作 。以 表示问题IP的最优目标函数值；这时有
进行迭代。
第一步：分支，在LP的最优解中任选一个不符合整数条件的变量 ，其值为 ，以 表示小于 的最大整数。构造两个约束条件
和
将这两个约束条件，分别加入问题LP约束条件中，不考虑整数条件求解这两个后继问题。
定界，以每个后继子问题为一分支并标明求解的结果，与其它问题的解的结果相比较，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界 ，若无作用 。
第二步：比较与剪枝，各分支的最优目标函数中若有小于 者，则剪掉此分支，即以后不再考虑求解。若大于 ，且不符合整数条件，则重复第一步骤。一直到最后得到 为止，得最优整数解
论文网http://www.youerw.com/ 。
应用基本分支定界法求解整数规划例子如下： (3-1)
(1)先不考虑整数限制条件，即解相应的线性规划 ，得最优解为：
可见它不符合整数条件。这时 是原问题 的最优目标函数值 的上界，记作 。而 显然是问题 的一个整数可行解，这时 ，是 的一个下界，记作 ，即 。
(2)因为 当前均为非整数，故不满足整数要求，任选一个进行分支。设选 进行分支，把可行集分成2个子集：
因为3与4之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分支。这两个子集的规划及求解如下：本文来自优.文~论^文·网原文请找腾讯324,9114
问题 ：(3-2)
最优解为： (3-3)
最优解为： 。 符合整数条件，不再进行分支。
再定界： 。
(3)对问题 再进行分支得问题 和 ，它们的最优解为
上一页 [1] [2] [3] [4] [5] [6] [7] [8] 下一页
分支定界法求解整数规划问题的设计与实现 第6页下载如图片无法显示或论文不完整，请联系qq752018766
