deepread22｜第21章 指派问题详解

ONEPSOFT | 软考学习知识库

---

deepread22｜第21章 指派问题详解

一、定位

• 章节位置：第 21 章 项目管理科学基础 → 21.2.3 指派问题。
• 知识链条：n 项任务、n 个人（一一对应），每人做每件事的效率/成本不同，求总成本最小（或总效率最高）的配对方案。典型 " 一对一最优匹配 "。
• 考试分量：综合知识考 " 研究什么问题 "（人岗最优配对）；计算考匈牙利算法（行减、列减、划线、调整）。

二、教材原文精摘

以下依据第 4 版教材第 21 章 21.2.3 节。fetch 不全标注：本次 fetch 对 " 指派问题 " 仅于其他章节例题处提及 " 匈牙利算法 "，未录完整正文与例题矩阵。下方用自行构造的 4×4 完整例题演示匈牙利算法全流程，数字均经手算核对。

• 定义：有 n 项任务，恰好有 n 个人可分别完成任一项；各人完成不同任务效率不同。应指派哪个人完成哪项任务，使总效率最高（或总成本最低）？
• 方法（匈牙利算法）：①每行减该行最小；②每列减该列最小；③用最少直线覆盖所有 0，若直线数=n 则得最优；④否则对未覆盖元素减最小、交叉点加最小，重复③。

三、系统解读（平实分点）

1. 一句话理解：4 台设备、4 个作业面，每台干每个面耗时不同，怎么 " 一对一 " 分配让总耗时最少，这就是指派问题。
2. 为什么叫 " 匈牙利算法 "：用 " 每行/列减最小 " 把矩阵变出一堆 0，最优配对就藏在 " 独立的 0" 里（每行每列恰好一个 0）。
3. 行减 + 列减：每行减该行最小 → 保证每行至少 1 个 0；每列减该列最小 → 保证每列至少 1 个 0。这步不改变最优配对（只是整体平移）。
4. 最少直线覆盖 0：用尽量少的横线/竖线盖住所有 0。如果刚好 n 条线（=任务数）就能盖住，说明存在 n 个 " 互相不冲突 " 的 0，直接指派；否则线数 < n，还要调整。
5. 调整（未覆盖−最小，交叉 + 最小）：没被线盖住的元素都减掉 " 未覆盖区最小值 "，让新 0 冒出来；被两条线交叉盖住的格子加回该值（保持已配对不变），直到能盖住 n 条线为止。

四、工程举例（土木类比 + 数值）

例题（构造，min 型）：4 名员工 P1~P4 完成 4 项任务 T1~T4 的耗时（小时）矩阵：

＼	T1	T2	T3	T4
P1	9	4	6	7
P2	5	8	3	4
P3	7	2	5	6
P4	3	6	8	5

匈牙利法：

• 行减最小（行最小 4,3,2,3）：得 [5,0,2,3; 2,5,0,1; 5,0,3,4; 0,3,5,2]。
• 列减最小（仅第 4 列最小=1）：得 [5,0,2,2; 2,5,0,0; 5,0,3,3; 0,3,5,1]。
• 划线覆盖 0：需 3 条线 < 4 → 调整。未覆盖区最小=1，未覆盖−1、交叉 +1 → [5,0,1,1; 3,6,0,0; 5,0,2,2; 0,3,4,0]。
• 再划线仍 3 条 < 4 → 再调整（未覆盖最小=1）→ [4,0,0,0; 3,7,0,0; 4,0,1,1; 0,4,4,0]。
• 划线覆盖 0：需 4 条线 = n=4 → 最优。独立 0：P1→T3、P2→T4、P3→T2、P4→T1。
• 原矩阵成本 = 6 + 4 + 2 + 3 = 15（小时）最小。

高项概念	土木 / 施工类比
人 / 任务	设备 / 作业面
成本矩阵	每台设备干每个面的耗时
独立 0 指派	一对一配对，互不冲突
行/列减最小	先扣掉 " 每人最擅长项 "，再看相对差

五、追问引导

• 指派问题和运输问题有什么不同？（指派=一对一配对 n×n；运输=多对多调运）
• 行减、列减为什么 " 不改变最优配对 "？（只是给每行/列整体平移常数，相对优劣不变）
• 最少直线覆盖 0 的条数 = n 为什么就 " 能指派 " 了？（意味着能选出每行每列各一个 0，即无冲突配对）
• 调整时 " 未覆盖元素减最小、交叉点加最小 " 分别解决什么问题？（制造新 0；保持已存在的可行 0 结构）
• 若求 " 总效率最高 " 而非 " 成本最小 "，匈牙利算法要怎么做？（把效率矩阵转为机会成本：用最大元素减全体，变 min 型）