运筹学经典问题（一）：指派问题

问题描述

有$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,\forall j\in J \\ \sum _{j\in J}{x}_{ij}=1,\forall i\in I \end{gathered}$$

目标函数表示最小化成本，第一行约束表示每个任务只能分配给一个人，第二行约束表示每个人只能被分配一个任务。

整数最优解特性

即使把变量$x_e$松弛成$0\le x_e\le 1$，原问题变成线性规划，该问题仍然存在整数最优解。

模型求解

方式一：将模型直接扔给求解器（Gurobi、Cplex）等求解就可以啦！如果对求解运筹模型时如何选择求解器有疑问的小伙伴，可以参考我的文章如何选择合适的求解器；
后面再补充python实现的代码(todo)

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