指派问题是整数规划中一类重要的问题：有$n$项不同的任务，需要$n$个人去完成（每人只完成一项工作），各人完成不同任务所需要的时间（或其他资源）不同。问应指派何人完成何项工作，可以使完成$n$项工作所消耗的总资源最少？
指派问题的数学模型
引入0-1变量$x_{ij}$
$x_{ij}=\begin{cases}1, \quad表示指派第i个人完成第j项工作 \\ 0, \quad表示不指派第i个人完成第j项工作\end{cases}$
用$c_{ij}$表示第$i$个人完成第$j$项工作所需要的资源数，称之为价值系数。因此指派问题的数学模型是：
$$\min z=\sum\limits_{i=1}^n\sum\limits_{j=1}^n c_{ij}x_{ij}$$
$$\mathrm{s.t}\begin{cases}\sum\limits_{i=1}^n x_{ij}=1,\quad i=1,2,\cdots,n \\
\sum\limits_{j=1}^n x_{ij}=1,\quad j=1,2,\cdots,n \\ x_{ij}=0 或 1, \quad i,j=1,2,\cdots,n \end{cases}$$
第一个式子表示完成全部$n$项工作所消耗的总资源数要最少；第二个表示第$i$个人只能完成一项工作；第三个表示第$j$项工作只能由一个人来完成；最后一个式子表示决策变量只能取0或1。
指派问题可以看作0-1整数规划问题来求解，也可以用更简单的匈牙利方法来求解。
匈牙利法的基本原理
匈牙利法的得名是因为匈牙利数学家 D. Konig 证明了这个方法中的主要定理。下面先介绍这几个定理（证明略），再介绍匈牙利法的计算过程。
定理1 设指派问题的价值系数矩阵为 $\mathbf{C}=(c_{ij})_{n\times n}$，若将该矩阵的某一行（或某一列）的各个元素减去同一常数 $t$（$t$可正可负），得到新的价值系数矩阵 $\mathbf{C’}=(c’_{ij})_{n\times n}$，则以 $\mathbf{C’}$ 为价值系数矩阵的新指派问题与原指派问题的最优解相同。
定理2 若将指派问题的价值系数矩阵每一行及每一列分别减去各行各列的最小元素，则得到的新指派问题与原指派问题有相同的最优解。
定义1 在价值系数矩阵$\mathbf{C}$中，有一组在不同行不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。
比如在矩阵$$\mathbf{C}=\begin{bmatrix}5&0&2&0 \\ 2&3&0&0\\ 0&5&6&7\\ 4&8&0&0\end{bmatrix}$$中，{$c_{12}$,$c_{24}$,$c_{31}$,$c_{43}$}就是一个独立零元素组，而{$c_{12}$,$c_{23}$,$c_{31}$,$c_{43}$}就不是。
对于一个大小等于矩阵阶数的独立零元素组，给对应位置上的决策变量取1，其余位置取0，就得到了指派问题的一个最优解，因为这时候消耗的总资源为0。
定理3 价值系数矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
匈牙利解法的过程
对于一个 $n\times n$ 大小的价值系数矩阵
Step 1
对每一行的所有元素减去该行最小的元素。
Step 2
对每一列的所有元素减去该列最小的元素。
Step 3
在适当的行或列上画直线使得这些直线覆盖所有的零元素，同时使用的直线条数最少。
Step 4
最优检测：
(1)如果直线的最小条数为$n$，则说明存在大小为$n$的独立零元素组，即可以进行最优指派，结束。
(2)如果直线条数少于$n$，则说明还不可以进行最优指派，在这种情况下，进入 Step 5。
Step 5
在所有未被直线覆盖的元素中确定出最小的一个，从每一未被直线覆盖的行减去这个最小值，再给每一被直线覆盖的列加上这个元素，回到 Step 3。
一个例子
先从一个例子直观地理解匈牙利算法，后面再介绍各部分如何实现（比如如何画最少的直线）
给定矩阵如下：$$\begin{bmatrix}90&75&75&80 \\ 35&85&55&65 \\ 125&95&90&105 \\ 45&110&95&115\end{bmatrix}$$
Step 1
$$\begin{bmatrix}90&75&75&80 \\ 35&85&55&65 \\ 125&95&90&105 \\ 45&110&95&115\end{bmatrix} \sim \begin{bmatrix}15&0&0&5 \\ 0&50&20&30 \\ 35&5&0&15 \\ 0&65&50&70\end{bmatrix}$$
Step 2
$$\begin{bmatrix}15&0&0&5 \\ 0&50&20&30 \\ 35&5&0&15 \\ 0&65&50&70\end{bmatrix} \sim \begin{bmatrix}15&0&0&0 \\ 0&50&20&25 \\ 35&5&0&10 \\ 0&65&50&65\end{bmatrix}$$
Step 3
Step 4
最小直线数小于4，故转向 Step 5。
Step 5
$$\begin{bmatrix}15&0&0&0 \\ 0&50&20&25 \\ 35&5&0&10 \\ 0&65&50&65\end{bmatrix} \sim \begin{bmatrix}15&0&0&0 \\ -5&45&15&20 \\ 30&0&-5&5 \\ -5&60&45&60\end{bmatrix}$$
$$\begin{bmatrix}15&0&0&0 \\ -5&45&15&20 \\ 30&0&-5&5 \\ -5&60&45&60\end{bmatrix} \sim \begin{bmatrix}20&0&5&0 \\ 0&45&20&20 \\ 35&0&0&5 \\ 0&60&50&60\end{bmatrix}$$
转回 Step 3。
Step 3
Step 4
最小直线数仍小于4，故转向 Step 5。
Step 5
$$\begin{bmatrix}20&0&5&0 \\ 0&45&20&20 \\ 35&0&0&5 \\ 0&60&50&60\end{bmatrix} \sim \begin{bmatrix}20&0&5&0 \\ -20&25&0&0 \\ 35&0&0&5 \\ -20&40&30&40\end{bmatrix}$$
$$\begin{bmatrix}20&0&5&0 \\ -20&25&0&0 \\ 35&0&0&5 \\ -20&40&30&40\end{bmatrix} \sim \begin{bmatrix}40&0&5&0 \\ 0&25&0&0 \\ 55&0&0&5 \\ 0&40&30&40\end{bmatrix}$$
转回 Step 3。
Step 3
Step 4
这时最小直线条数为4，说明可以进行最优指派
Final Step
选出一个大小为4的独立零元素组进行指派
细节实现
至此，我们已经使用匈牙利法解决了一个问题，但在上面的步骤中，有两处仍然比较模糊。一是画最少直线的步骤，即Step 3，对于$n=4$这样的小的情形，我们或许可以试着找出答案。但对于更大的情形，必须有一个有效的方法去找出最少直线。二是找出独立零元素组的步骤，即Final Step，我们也需要一个有效的方法。
画最少直线
尽可能多地分配任务：
对于下面这个矩阵$$\begin{vmatrix}0&c_{12}&c_{13}&c_{14} \\ c_{21}&c_{22}&c_{23}&0 \\ 0&c_{32}&c_{33}&c_{34} \\ c_{41}&0&0&c_{44} \end{vmatrix}$$
(1) 第一行有一个零，所以给这个位置分配任务。同时划掉第三行的零，因为它和这个零在同一列。
(2) 第二行有一个零，所以给这个位置分配任务。
(3) 第三行唯一的一个零已经被划掉，所以什么也不做。
(4) 第4行有两个没有被划掉的零，所以给任意一个位置分配任务，划掉另外一个。
经过上述步骤后的矩阵为（划掉的零加撇表示）$$\begin{vmatrix}0&c_{12}&c_{13}&c_{14} \\ c_{21}&c_{22}&c_{23}&0 \\ 0’&c_{32}&c_{33}&c_{34} \\ c_{41}&0&0’&c_{44} \end{vmatrix}$$画线：
(1) 标记所有不含已分配任务位置的行(行3)
(2) 在刚才新标记行的所有元素中，标记出所有0所在的列(列1)
(3) 在刚才新标记列的所以元素中，标记出所有分配位置所在的行(行1)
(4) 重复上面的步骤(2),(3)直到不会标记新的行或列
经过上述步骤后如下：$$\begin{vmatrix}\times&&&&& \\ 0&c_{12}&c_{13}&c_{14}&\times \\ c_{21}&c_{22}&c_{23}&0& \\ 0’&c_{32}&c_{33}&c_{34}&\times \\ c_{41}&0&0’&c_{44}& \end{vmatrix}$$
(5) 在所有标记的列和未标记的行上画线，这样的直线经过了所有的零
找出独立零元素组
当我们画出的直线条数等于$n$，说明可以进行最优指派，那么具体该怎么指派呢？我们使用圈零法来求出独立零元素。
- 进行行检验
对矩阵逐行检查，当该行只有一个未标记的零元素时，用〇记号将该零元素圈起。然后将被圈起的零元素所在列的其他未被标记的零元素用×划去。重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。
如下$$\begin{vmatrix}0&13&7&0 \\ 6&0&6&9 \\ 0&5&3&2 \\ 0&1&0&0\end{vmatrix} \sim \begin{vmatrix}\times&13&7&0 \\ 6&\mathrm{O}&6&9 \\ \mathrm{O}&5&3&2 \\ \times&1&0&0\end{vmatrix}$$ - 进行列检验
对矩阵逐列检查，当该列只有一个未标记的零元素时，用〇记号将该零元素圈起。然后将被圈起的零元素所在行的其他未被标记的零元素用×划去。重复列检验，直到每一列都没有未被标记的零元素或至少有两个未被标记的零元素时为止。
如下$$\begin{vmatrix}\times&13&7&0 \\ 6&\mathrm{O}&6&9 \\ \mathrm{O}&5&3&2 \\ \times&1&0&0\end{vmatrix} \sim \begin{vmatrix}\times&13&7&\mathrm{O} \\ 6&\mathrm{O}&6&9 \\ \mathrm{O}&5&3&2 \\ \times&1&\mathrm{O}&\times\end{vmatrix}$$ - 这时可能出现两种情形：
(1) 圈零的个数等于$n$，给圈零的位置进行指派即可
(2) 存在未被标记的零元素，但它们所在的行和列中，未被标记过的零元素均至少有两个
对于第二种情况，给每行、每列中未被标记的零元素中任选一个画圈，其余的打叉，再进行行列检验，则最终会达到情形(1)。
Python SciPy 相关函数
Python的SciPy库中有对应的函数可以解指派问题，详见scipy.optimize.linear_sum_assignment