0-1规划的介绍

Question

如题所述

Answer 1

0-1规划是决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时，若决策变量采用 0-1变量即逻辑变量，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。

求解 0-1 规划的方法主要是隐枚举法（如分枝定界法）。对一些特殊问题还有一些更加有效的方法，例如对指派问题，用D.柯尼希发明的匈牙利法求解更显方便有效。

0-1 规划问题一般有三种解法，即变换法、穷举法和隐枚举法。变换法用于解特殊的 0-1 规划问题。穷举法就是检查变量取值为 0 或 1 的每一种组合，比较目标函数值来求最优解，这就需要检查变量取值的 2n个组合。对于 n>10 的情况，这几乎是办不到的。

因此常设计一些方法，只检查变量取值组合的一部分，就能得到问题的最优解。这样的方法称为隐枚举法。

采用隐枚举法解 0-1 规划问题时要根据目标函数的性质增加一个相应的不等式作为附加约束条件，称为过滤条件，以减少运算次数。一般还要按目标函数中 xi的系数递增的顺序，重新排列目标函数和约束条件中 xi的次序，以简化计算。

Answer 2

0-1规划是决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时，若决策变量采用 0-1变量即逻辑变量，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。