您现在的位置：毕业论文 >> 论文 >> 正文

分支定界法求解整数规划问题的设计与实现第5页

更新时间：2012-2-23: 来源：毕业论文

0-1变量可以数量化地描述诸如取与舍，有与无等等现象，也可反映一些互斥问题。对于0-1规划问题，由于每个变量只能取0或1两个整数值，因此它可用于求解固定费用问题和指派问题等等。此类规划一般可以用穷举法来解，即将所有的0，1组合找出，使目标函数达到极值要求的解即为最优解。但此法太繁琐，工作量相对比较大。而隐枚举法[8]就是在穷举法的基础上，通过加入一定的目标值约束条件，就能较快的求得最优解。只检查变量取值的组合的一部分，就能求到问题的最优解。
用隐枚举法求解0—1规划例子[10]：(2-1)
首先通过试探法找到一个可行解，如就全符合条件，算出相应的目标函数值。
求最优解时，对于极大化问题，当然希望能找到一个组合使得，于是
增加一个约束条件：(2-2)
后加的条件(2-2)称为过滤的条件。这样，原问题的线性约束条件就变成5个。若用全部枚举的方法，3个变量共有个求解过程，原来四个约束条件，共需32次运算。现在增加了过滤条件(2-2)，如按下述方法进行，就可减少运算次数，将5个约束条件按顺序排好(表 2-1[10])，对于每个解，依次代入约束条件左侧，然后求出数值，看是否符合模型中不等式条件，如某一条件不符合，同行以下各条件就不必再检查，因而减少了运算次数。本例计算过程如表 2-1，实际只作24次运算。
表 2-1 求解过程本文来自辣.文~论^文·网原文请找腾讯32-49114
点条件满足条件？
是（√）否（×）值

（0）（1）（2）（3）（4）
（0，0，0）
（0，0，1）
（0，1，0）
（0，1，1）
（1，0，0）
（1，0，1）
（1，1，0）
（1，1，1）
于是求得最优解，。论文网http://www.751com.cn/
在计算过程中，若遇到值已超过条件(2-2)右边的值，应动态改变条件(2-2)，使右边为迄今为止最大者，然后继续。例如，当检查点(0，0，1)时因，所以应将条件(2-2)换成下面的式子：
(2-3)
这种对过滤条件的改进，更可以减少计算量⑤。
2.2.2. 优缺点
优点：用隐枚举法求解0-1整数规划时，替代问题是在保持变量0-1约束的条件下，放松问题的资源约束；与穷举法相比，加入过滤条件，减少计算量；简单方便；
缺点：只对求解小规模问题比较简单方便；计算机所存储的数据结构比较零散，枚举时，效率低，比较不适合应用计算机求解。
2.3. 基本分支定界法求解整数规划
2.3.1. 基本思想
基本分支定界法求解整数规划的基本思路[11][12][13]：先求解对应松驰问题，如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件对有约束条件的最优化问题(其可行解为有限数)的可行解空间恰当地进行系统搜索，然后进行分支与定界。通常，把全部可行解空间反复地分割为越来越小的子集，并且对每个子集内的解集计算一个目标下界(对于最小值问题)。在每次分支后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分支，这样，许多子集可不予考虑。这就是分支定界法的主要思路。