作业

最常见的组合优化问题之一是分配问题。举个例子：假设一组工作器需要执行一组任务，并且对于每个工作器和任务，将工作器分配给任务会产生费用。问题在于，每个工作器最多可分配给一个任务，不能有两个工作器执行相同的任务，同时最大限度地降低总费用。

您可以通过下图直观地了解此问题，在该图中有四个工作器和四个任务。这些边缘代表将 worker 分配给任务的所有可能方式。边缘上的标签是将 worker 分配给任务的成本。

一个分配对应于边缘的子集，其中每个工作器最多有一条向外的边缘，并且没有两个工作器具有通向同一任务的边缘。下面显示了一种可能的分配方式。

总分配费用为 70 + 55 + 95 + 45 = 265。

下一部分将介绍如何使用 MIP 求解器和 CP-SAT 求解器解决赋值问题。

其他用于解决作业问题的工具

OR-Tools 还提供了几种用于解决分配问题的其他工具，这些工具比 MIP 或 CP 求解器更快：

• 线性和赋值求解器
• 最低费用流求解器

不过，这些工具只能解决简单类型的分配问题。因此，对于能够处理各种问题的一般求解器（并且对大多数应用来说速度足够快），我们建议使用 MIP 和 CP-SAT 求解器。