# 指派问题求解器（匈牙利算法）

用教科书版匈牙利算法求解 2–8 × 2–8 的指派问题（支持矩形矩阵，自动补零成本哑行/哑列）：先做行约简与列约简，再用增广路径在零元素中找最大匹配，不够则按 König 定理用最少直线覆盖所有零并调整矩阵，每轮减未覆盖最小元、加双覆盖交点；最大化问题内部取负求解后报告收益。逐步输出约简与覆盖过程，给出最优指派与总成本并代回验证。经典例：[[9,2,7],[6,4,3],[5,8,1]] 最小化 → 总成本 9（工人 1→任务 2、工人 2→任务 1、工人 3→任务 3）。

> 标准页面: https://elysiatools.com/zh/tools/assignment-problem-solver

- **分类:** Math & Numbers

- **关键词:** 指派问题, 匈牙利算法, 库恩-芒克斯, 最优指派, 成本矩阵, 匹配, 运筹学, 任务分配, 人员分工, 组合优化

## 概述

指派问题求解器基于经典匈牙利算法（Kuhn-Munkres 算法），专为 2×2 至 8×8 规模的成本或收益矩阵提供最优任务分配方案。工具支持矩形矩阵自动补零拓展，完整展示行列约简、增广路径最大匹配、König 定理最少直线覆盖与矩阵调整的详细推导步骤，并输出验证后的最优分配对与总成本或总收益。

## 输入项

- **成本矩阵（每行一行）** (textarea): Cost (or benefit) matrix, one row per worker, one column per task. 2–8 rows × 2–8 columns; rectangular matrices are padded with zero-cost dummies.
- **目标** (select)
- **小数位数** (number)

## 适用场景

- 需要为多名员工分配不同任务，以最小化总工时或人工成本时。
- 需要在有限机台与加工订单之间建立一一对应关系，以最大化产出收益时。
- 在运筹学与组合优化课程中验证匈牙利算法的手算约简和划线调整过程时。

## 工作原理

- 输入 2–8 行/列的成本或收益矩阵，若行数与列数不相等，系统自动添加成本为 0 的虚拟行或虚拟列构成方阵。
- 选择目标类型；若为最大化问题，系统内部将矩阵元素取负转化为标准最小化形式，并执行行约简与列约简提取独立零元素。
- 通过增广路径寻找零元素最大匹配；若未达到完全匹配，则按 König 定理用最少直线覆盖所有零点，并利用未覆盖区域最小元调整矩阵直至收敛。
- 根据最终矩阵反向代入原始数据，输出每项指派的对应关系以及总成本或总收益数值。

## 使用案例

- 项目经理为团队成员分配多项开发模块，以耗时最短为目标获得最优人员分工。
- 车间调度员将不同批次的工件分配至各加工中心，以综合加工费用最低为目标生成排产指派。
- 高校师生在运筹学作业与教学演示中，比对匈牙利算法各轮划线与矩阵变换细节。

## 常见问题

### 当工人数量和任务数量不相等时如何处理？

工具会自动补充成本为 0 的哑行（虚拟工人）或哑列（虚拟任务），将其补齐为标准方阵后求解。

### 最大化收益问题是如何计算的？

系统会在内部对收益矩阵取负转换为最小化指派问题，求解完成后还原为实际最大收益。

### 支持的最大矩阵规模是多少？

支持行数和列数在 2 到 8 之间的任意成本或收益矩阵。

### 计算结果中是否包含手算推导步骤？

包含，输出内容会逐步展示行列约简极小值、各轮零元素匹配情况及直线覆盖调整过程。

### 如何设置输出结果的小数精度？

可通过“小数位数”选项设置 0 到 8 位的显示精度，系统将按设定值格式化各步骤与总结果。

## 相关工具

- [图最短路径计算器（Dijkstra 手算辅助）](https://elysiatools.com/zh/tools/graph-shortest-path): Dijkstra 最短路径的手算辅助工具：输入 1–30 条边（每行：起点、终点、权重）与起点/终点，默认无向、可切换有向。逐轮记录“定居哪个节点、距离多少、每次松弛如何更新临时距离表”，平局按字典序取最小节点名，日志与教科书演算完全一致；负权重按业务拒绝，终点不可达作为合法结果报告。经典例：A-B 4、A-C 2、B-C 5、B-D 10、C-E 3、D-E 4、D-F 11、E-F 8，从 A 到 F → 最短距离 13，路径 A→C→E→F。
- [颠倒文字](https://elysiatools.com/zh/tools/upside-down-text): 用逐字母旋转把文字颠倒（ɥǝllo），并提供可选开关保留阅读顺序、保护链接/邮箱不被搅乱。纯 Unicode 文本，无需字体。比聚合器里固定行为的颠倒行更可控。
- [播客章节标记生成器（ID3 / Podcasting 2.0）](https://elysiatools.com/zh/tools/podcast-chapter-marker-builder): 粘贴时间码章节列表，一次生成全部交付格式：Podcasting 2.0 章节 JSON（v1.2.0）与 RSS podcast:chapters 标签、可选把 ID3v2.4 CHAP+CTOC 章节帧直接烧入上传的 MP3（毫秒为普通大端 uint32、偏移 0xFFFFFFFF、每章嵌 TIT2 子帧、保留原有标签帧）、Vorbis CHAPTER001 注释对（OGG/Opus）、mp4chaps 文本、YouTube 说明栏时间戳块与 SRT 副车文件，并附各播放器真实支持情况（Apple 自 2025 起支持 RSS JSON；Pocket Casts/Overcast 仅读内嵌 ID3；Spotify 两者都不读）。
- [STEM 物理运动学：速度-时间图导师](https://elysiatools.com/zh/tools/education-stem-physics-kinematics-velocity-time-graph): 运动学可视化导师：速度-时间曲线绘制（含匀加速 SUVAT 求解器、位移 = 曲线下面积填色）、抛体抛物线模拟器（可调 g + 空气阻力开关）、自由落体计时
- [缩进列表转 ASCII 目录树](https://elysiatools.com/zh/tools/ascii-tree-from-indented-list): 把 2 空格 / 4 空格 / Tab 缩进的层级列表（Markdown bullet、- * 1. 前缀可选）渲染为可复制的 ASCII 目录树。支持 Unicode 方框与经典 ASCII 两种风格，以及整根纵线、行尾空格、叶节点方括号等开关。
- [星期计算器](https://elysiatools.com/zh/tools/day-of-week-calculator): 计算给定日期是星期几
- [音频转文字转录器 (AI)](https://elysiatools.com/zh/tools/audio-to-text-transcriber): 用 grok-stt AI 模型将语音(wav/mp3/m4a/flac/ogg/webm/aac)转录为文本、SRT、VTT 或 JSON。最长 10 分钟。
- [FFmpeg音频降噪工具](https://elysiatools.com/zh/tools/ffmpeg-audio-noise-reduction): 使用FFmpeg高级滤波器（高通、afftdn、loudnorm）进行专业音频降噪，获得最佳音频清洁效果

## 示例

- [ELK Stack 日志分析示例](https://elysiatools.com/zh/samples/elk-stack-samples): 全面的 ELK Stack（Elasticsearch、Logstash、Kibana）示例，用于分布式系统中的日志聚合、处理和可视化
- [无版权MP3音频样本](https://elysiatools.com/zh/samples/mp3-samples): 免费使用和测试的无版权音频样本集合，包括自然声音、冥想音乐和环境音频，适用于测试和开发目的
- [正则表达式命名捕获组](https://elysiatools.com/zh/samples/regex-named-groups): 使用命名捕获组从文本中提取结构化数据的正则表达式模式集合。命名组通过为捕获的部分分配有意义的名称，使模式更易读和更易维护。
- [环境变量(.env)示例](https://elysiatools.com/zh/samples/env-samples): 不同应用程序类型和环境的环境变量配置示例