0-1规划的隐枚举法

发布网友发布时间：2022-04-30 18:03

共1个回答

热心网友时间：2022-06-28 19:29

0-1规划问题一般有三种解法,即变换法、穷举法和隐枚举法。上述方法即为变换法，用于解特殊的0-1规划问题。穷举法就是检查变量取值为0或 1的每一种组合，比较目标函数值来求最优解，这就需要检查变量取值的2^n个组合。对于n>10的情况，这几乎是办不到的。因此常设计一些方法，只检查变量取值组合的一部分，就能得到问题的最优解。这样的方法称为隐枚举法。
采用隐枚举法解 0-1规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件，称为过滤条件，以减少运算次数。一般还要按目标函数中xi的系数递增的顺序，重新排列目标函数和约束条件中xi的次序，以简化计算。