問題描述

有$N$個任務，需要$N$個人去完成，每個人完成不同工作的效率不同（或者資源、收益等等），需要怎么分配使得整體的效率最高（成本最低等等）呢？這就是經典的指派問題啦！

數學建模

我們首先做以下定義：
$I$: 人的集合；
$J$: 任務的集合；
$c_{ij}$: 把任務$j$分配給$i$的成本；

$x_{ij}$: 是否把任務$j$分配給$i$，0-1變量；

$$\begin{gathered} min\sum _{i\in I}\sum _{j\in J}{x}_{ij}{c}_{ij} \\ s.t\sum _{i\in I}{x}_{ij}=1,?j\in J \\ \sum _{j\in J}{x}_{ij}=1,?i\in I \end{gathered}$$

目標函數表示最小化成本，第一行約束表示每個任務只能分配給一個人，第二行約束表示每個人只能被分配一個任務。

模型求解

方式一：將模型直接扔給求解器（Gurobi、Cplex）等求解就可以啦！如果對求解運籌模型時如何選擇求解器有疑問的小伙伴，可以參考我的文章如何選擇合適的求解器；
后面再補充python實現的代碼(todo)

方式二：對算法求解速度有更高要求的，可以通過匈牙利算法、Ford-Fulkerson算法（FFA）等求解。