作业
最常见的组合优化问题之一是分配问题。举个例子：假设一组工作器需要执行一组任务，并且对于每个工作器和任务，将工作器分配给任务会产生费用。问题在于，每个工作器最多可分配给一个任务，不能有两个工作器执行相同的任务，同时最大限度地降低总费用。
您可以通过下图直观地了解此问题，在该图中有四个工作器和四个任务。这些边缘代表将 worker 分配给任务的所有可能方式。边缘上的标签是将 worker 分配给任务的成本。
一个分配对应于边缘的子集，其中每个工作器最多有一条向外的边缘，并且没有两个工作器具有通向同一任务的边缘。下面显示了一种可能的分配方式。
总分配费用为 70 + 55 + 95 + 45 = 265。
下一部分将介绍如何使用 MIP 求解器和 CP-SAT 求解器解决赋值问题。
OR-Tools 还提供了几种用于解决分配问题的其他工具，这些工具比 MIP 或 CP 求解器更快：
不过，这些工具只能解决简单类型的分配问题。因此，对于能够处理各种问题的一般求解器（并且对大多数应用来说速度足够快），我们建议使用 MIP 和 CP-SAT 求解器。
如未另行说明，那么本页面中的内容已根据知识共享署名 4.0 许可获得了许可，并且代码示例已根据 Apache 2.0 许可获得了许可。有关详情，请参阅 Google 开发者网站政策。Java 是 Oracle 和/或其关联公司的注册商标。
最后更新时间 (UTC)：2024-08-09。
[null,null,["最后更新时间 (UTC)：2024-08-09。"],[[["The assignment problem focuses on optimally assigning workers to tasks to minimize the total cost, where each worker is assigned at most one task and no task is assigned to multiple workers."],["This problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment."],["OR-Tools offers various solvers like MIP, CP-SAT, Linear Sum Assignment, and Minimum Cost Flow, but MIP and CP-SAT are recommended for their versatility and efficiency in handling a broader range of assignment problems."]]],["The content describes the assignment problem, a combinatorial optimization challenge where workers are assigned to tasks to minimize total cost. Each worker is assigned to at most one task, and each task is done by at most one worker. The example shows how the problem can be represented graphically, with edges representing possible assignments and their costs. The total cost is calculated by adding up the costs of the assigned edges. OR-Tools offer multiple tools to solve such problems, among which the MIP and CP-SAT are the most general.\n"]]
