practice53｜第21章 指派问题自测

ONEPSOFT | 软考学习知识库

---

practice53｜第21章 指派问题自测

三题覆盖情境判断 / 概念辨析 / 综合连接。做完对照 " 教材依据 " 与 " 参考答案解读 "，再用底部自评表打分。

题目一（情境判断）

用匈牙利算法求下面 3 人 3 任务（耗时矩阵，min 型）的最优指派与最小总耗时：

＼	T1	T2	T3
P1	3	2	5
P2	4	1	3
P3	2	4	6

教材依据

匈牙利算法：行减最小→列减最小→最少直线覆盖 0，线数=n 即最优；否则未覆盖−最小、交叉 + 最小，重复。最终每行每列取一个 0 配对。

参考答案解读

• 行减（行最小 2,1,2）：\[1,0,3; 3,0,2; 0,2,4]。
• 列减（仅第 3 列最小 2）：\[1,0,1; 3,0,0; 0,2,2]。
• 0 位置：(P1,T2)、(P2,T2)、(P2,T3)、(P3,T1)；最少覆盖线 = 列 1+ 列 2+ 列 3 = 3 = n → 最优。
• 独立 0：P1→T2、P2→T3、P3→T1。
• 原成本 = 2 + 3 + 2 = 7（最小）。

土木画像提示

3 台设备分 3 个作业面：P1 干 T2、P2 干 T3、P3 干 T1 最省时，总耗时 7。像排班 " 谁擅长哪面就固定哪面 "。

---

题目二（概念辨析）

关于匈牙利算法，下列说法正确的是（ ）

A. 行减、列减会改变最优配对方案

B. 最少直线覆盖所有 0，若直线数 = n 则已得最优指派

C. 调整时，被线盖住的所有格子都要加回最小值

D. 指派问题允许一人同时做多项任务

教材依据

行/列减仅整体平移，不改变相对优劣；覆盖线数=n 即存在独立 0 配对；仅 " 两条线交叉 " 的格子加回；指派是一一配对。

参考答案解读

选 B。A 错：行/列减只平移，不影响谁配谁最优；B 对：线数=n 说明能选出每行每列各一个 0（无冲突配对）；C 错：仅被两条线交叉盖住的格子加回，单线盖住的不动；D 错：指派是一一对应（n 人 n 任务各用一次）。

土木画像提示

" 减最小 " 只是把基准线拉平，不改变谁最合适；线数够 n 就能排出互不打架的班；加回只针对 " 交叉点 "；一个人同一时刻只能守一个面。

---

题目三（综合连接）

若上题改为求 " 总效率最高 "，原效率矩阵为 \[3,2,5; 4,1,3; 2,4,6]（数值越大越好）。应如何改用匈牙利算法？并求最大总效率。

教材依据

max 型指派：用矩阵最大值减全体元素，转为 min 型成本矩阵，再按匈牙利算法求最小，等价于原效率最大。

参考答案解读

• 矩阵最大值 = 6；机会成本矩阵 = 6 − 原阵：\[3,4,1; 2,5,3; 4,2,0]。
• 对该 min 型矩阵跑匈牙利（行减最小 1,2,0 → \[2,3,0;0,3,1;4,2,0]；列减最小 0,2,0 → \[2,1,0;0,1,1;4,0,0]；覆盖需 3 线=n）→ 独立 0：P1→T3、P2→T1、P3→T2。
• 回原效率：P1T3=5、P2T1=4、P3T2=4，总效率 = 5+4+4 = 13（最大）。
• （校验：与上题 min 型解 P1T2,P2T3,P3T1=2+3+2=7 互补, 留待自行验证其他组合均 ≤13。）

土木画像提示

要 " 总产出最大 " 而非 " 总耗时最小 "，就先把效率翻成 " 机会成本 "（最大−各值），再求最小，得到的配对就是原效率最大的排班。

---

自评表（做完打 √ / 打分）

维度	自评分（1-5）	备注
我会做行减/列减
我理解 " 最少线覆盖 0，线数=n 即最优 "
我会调整（未覆盖−最小、交叉 + 最小）
我会从独立 0 读出指派方案
我会处理 max 型（转 min 型）

低于 3 分的项目，回看 deepread53 的 ③ 段和 calculate53 分步解题再巩固一遍。