基于线性规划的“任务指派问题”的整数规划建模与隐枚举法求解示例 1. 问题描述 任务指派问题是将 \( n \) 个任务分配给 \( n \) 个执行者（例如工人、机器等），每个执行者仅能承担一个任务，且每个任务只能分配给一个执行者。已知执行者 \( i \) 完成任务 \( j \) 的成本为 \( c_ {ij} \)，目标是找到总成本最小的指派方案。该问题可视为二分图最小权完美匹配问题，但此处我们重点展示如何通过整数规划建模，并利用隐枚举法（一种系统化的搜索剪枝方法）进行求解。 2. 整数规划建模 定义决策变量： \[ x_ {ij} = \begin{cases} 1, & \text{如果任务 } j \text{ 分配给执行者 } i \\ 0, & \text{否则} \end{cases} \] 则数学模型为： \[ \text{最小化} \quad \sum_ {i=1}^{n} \sum_ {j=1}^{n} c_ {ij} x_ {ij} \] 约束条件： \[ \sum_ {j=1}^{n} x_ {ij} = 1, \quad \forall i = 1,\dots,n \quad \text{(每个执行者恰好做一个任务)} \] \[ \sum_ {i=1}^{n} x_ {ij} = 1, \quad \forall j = 1,\dots,n \quad \text{(每个任务恰好分配给一个执行者)} \] \[ x_ {ij} \in \{0, 1\}, \quad \forall i,j \] 这是一个0-1整数规划问题，其系数矩阵是全幺模矩阵，因此线性规划松弛的最优解自动为整数解（但我们将演示隐枚举法以理解通用整数规划的求解思路）。 3. 隐枚举法求解步骤 隐枚举法通过系统枚举部分变量组合，并利用界限剪枝避免搜索整个解空间。以 \( n=3 \) 为例，成本矩阵为： \[ C = \begin{pmatrix} 9 & 2 & 7 \\ 6 & 4 & 3 \\ 5 & 8 & 1 \end{pmatrix} \] 步骤1：变量排序与下界计算 为加速剪枝，先对成本矩阵进行归约： 行归约：每行减去该行最小值，新矩阵为 \[ \begin{pmatrix} 7 & 0 & 5 \\ 3 & 1 & 0 \\ 4 & 7 & 0 \end{pmatrix} \] 列归约：每列减去该列最小值，得到归约矩阵 \[ R = \begin{pmatrix} 4 & 0 & 5 \\ 0 & 1 & 0 \\ 1 & 7 & 0 \end{pmatrix} \] 归约常数 \( \text{RedCost} = (2+3+1) + (0+0+0) = 6 \)。任何可行解的实际成本 = 归约成本 + 6。 此时归约矩阵中每行每列至少有一个零，下界 \( LB = 6 \)。 步骤2：构造搜索树 变量按字典序 \( x_ {11}, x_ {12}, \dots, x_ {33} \) 分支。每个节点表示部分变量赋值，计算该部分赋值下的成本下界。 根节点A ：无赋值，下界 \( LB_ A = 6 \)。 分支 \( x_ {11}=1 \) ： 若 \( x_ {11}=1 \)，则第1行、第1列其他变量必须为0。去掉第1行第1列，剩余子矩阵为 \[ \begin{pmatrix} 1 & 0 \\ 7 & 0 \end{pmatrix} \] 对该子矩阵归约：第1行减1，得 \[ \begin{pmatrix} 0 & 0 \\ 7 & 0 \end{pmatrix} \] 归约常数增加1，因此节点B的下界 \( LB_ B = 6 + 1 = 7 \)。 分支 \( x_ {11}=0 \) ： 节点C的下界仍为 \( LB_ C = 6 \)（因 \( x_ {11}=0 \) 不增加成本）。 步骤3：递归搜索与剪枝 从下界最小的节点继续分支（即节点C）。 在节点C下分支 \( x_ {12}=1 \)： 若 \( x_ {12}=1 \)，则第1行、第2列其他变量为0。去掉第1行第2列，剩余子矩阵为 \[ \begin{pmatrix} 0 & 0 \\ 7 & 0 \end{pmatrix} \] 无需归约，节点D的下界 \( LB_ D = 6 \)。 在节点C下分支 \( x_ {12}=0 \)： 节点E的下界 \( LB_ E = 6 \)。 继续对节点D搜索： 在节点D下分支 \( x_ {23}=1 \)： 剩余变量 \( x_ {31} \) 必为1（因第3行只剩第1列可选）。得到完整解 \( x_ {12}=1, x_ {23}=1, x_ {31}=1 \)，其余为0。 计算原始成本：\( c_ {12}=2, c_ {23}=3, c_ {31}=5 \)，总成本 \( 2+3+5=10 \)。 记录为当前最优解 \( Z^* = 10 \)。 回溯到其他节点，若其下界 \( LB \geq 10 \) 则剪枝。例如节点B的下界7 < 10，需继续搜索，但后续可能发现更优解。 步骤4：回溯与最优解确认 通过系统搜索，最终得到最优解： \[ x_ {12}=1, x_ {23}=1, x_ {31}=1, \text{其他为0} \] 总成本 = 10。 （注：此例中归约下界6，实际最优解10，差距源于归约矩阵的零元素分布。） 4. 算法扩展与注意事项 隐枚举法通常结合启发式变量选择（如选择成本最小的可行分配优先分支）。 剪枝效率依赖于下界质量：利用归约矩阵计算的下界比简单累加部分成本更紧。 对于大规模问题，隐枚举法可能仍计算昂贵，此时可用匈牙利算法（专门用于指派问题）在 \( O(n^3) \) 时间内求解。 5. 核心思想总结 本问题展示了如何将现实中的分配任务建模为0-1整数规划，并通过隐枚举法——一种基于分支定界思想的系统搜索方法，利用下界剪枝有效求解。尽管指派问题有更高效的特殊算法，但隐枚举法是通用整数规划求解器的基本原理之一，适用于各类组合优化问题。