【管理运筹学】第 5 章 | 整数规划 （1，问题提出与分支定界法） 【管理运筹学】第 5 章 | 整数规划 （2，割平面法及 0-1 变量的特性） 【管理运筹学】第 5 章 | 整数规划 （3，隐枚举法计算步骤） 【管理运筹学】第 5 章 | 整数规划（4，指派问题）
文章目录系列文章引言四、0-1 整数规划4.2 0-1 整数规划的解法4.2.1 0-1 规划模型标准型4.2.2 隐枚举法计算步骤写在最后引言经过前文，了解以及体会到 0-1 变量的特性后，我们来研究该如何去求解这类特殊的 0-1 整数规划模型。
四、0-1 整数规划 4.2 0-1 整数规划的解法既然是整数规划，那么所有可行解的数量便是有限的，全枚举法便是一种算法。检查每个变量取 0 或 1 的所有组合，满足所有约束条件并使得目标函数最优的组合就是 0-1 整数规划的最优解。
若 0-1 变量有 n 个，需要检查2 n 2^n2n 个变量组合。当nnn 数量较大时，想要靠全部列举出来，几乎是不可能的。
下面介绍一种隐枚举法，只要检查全部变量组合的一部分组合就可以求出最优解，这有点像前面讲过的分支定界法。
4.2.1 0-1 规划模型标准型首先，要应用隐枚举法进行求解，必须将原模型化为如下标准型。
其中，c j ≥0c_j \geq 0cj≥0 ，b i b_ibi 可以是正数、负数或 0 ，所有约束条件必须是”≤””\leq ””≤” 型。
和平常的标准型有一些不同，不用化成等式，右端可以是负数，但是必须是求最小。
如果所给的模型不是标准形式，可以通过如下方法进行变换。
如果目标函数求最大，可将目标函数乘 -1 。如果变量x jx_jxj 对应的目标函数系数c j≤ 0 c_j \leq 0cj≤0 ，可以用 ( 1 −x j) (1-x_j)(1−xj) 替换x jx_jxj ，最后记得还原结果。如果约束条件为 “ ≥ ” “\geq”“≥” 形式，将其乘上 -1 。如果约束条件为 “ = ” “=”“=” 形式，将其变为一个 " ≥ " "\geq""≥" 和一个 " ≤ " "\leq""≤" ，将前者乘以 -1 。 4.2.2 隐枚举法计算步骤隐枚举法首先令全部变量为 0 ，检验解是否可行。若可行，z=0z=0z=0 ，已取得最优解；若不可行，则令一个变量取值为 0 或 1 ，称为固定变量。固定变量每一个值对应一个子问题，可将问题分为两个子域，其余未被指定取值的变量称为自由变量。
根据标准型要求，这些自由变量的系数均为非负，令所有自由变量为 0 ，加上固定变量的取值，组合该子域的解。经过检验，或停止分支，或继续指定固定变量，直至没有自由变量或全部子域停止分支为止。
其流程图如下所示： 
由于第 3,4,5,均有停止分支的情况，对于这些子域自由变量取 0 或 1 值的所有可能组合都被隐含地考虑了，不必再一一列举。所以这种方法称为隐枚举法，可大大减少计算量。
同时，实际解题中，指定固定变量时，可优先指定目标函数系数最小的变量，加快计算速度。
写在最后隐枚举法求解过程还是相对复杂和繁琐些，对待每一步都需要理清思路和逻辑。下篇文章我们来学习指派问题的相关内容。