作业
使用集合让一切井井有条
根据您的偏好保存内容并对其进行分类。
最常见的组合优化问题之一是分配问题。举个例子：假设一组工作器需要执行一组任务，并且对于每个工作器和任务，将工作器分配给任务会产生费用。问题在于，每个工作器最多可分配给一个任务，不能有两个工作器执行相同的任务，同时最大限度地降低总费用。
您可以通过下图直观地了解此问题，在该图中有四个工作器和四个任务。这些边缘代表将 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。"],[[["\u003cp\u003eThe 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.\u003c/p\u003e\n"],["\u003cp\u003eThis problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment.\u003c/p\u003e\n"],["\u003cp\u003eOR-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.\u003c/p\u003e\n"]]],["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"],null,["# Assignment\n\nOne of the most well-known combinatorial optimization problems is the\n[*assignment problem*](https://en.wikipedia.org/wiki/Assignment_problem). Here's an example: suppose a group of workers needs to perform a set of tasks, and for\neach worker and task, there is a cost for assigning the worker to the task.\nThe problem is to assign each worker to at most one task, with no two workers\nperforming the same task, while minimizing the total cost.\n\nYou can visualize this problem by the graph below, in which there are four\nworkers and four tasks. The edges represent all possible ways to assign workers\nto tasks. The labels on the edges are the costs of assigning workers to tasks.\n\nAn assignment corresponds to a subset of the edges, in which each worker has at\nmost one edge leading out, and no two workers have edges leading to the same\ntask. One possible assignment is shown below.\n\nThe total cost of the assignment is `70 + 55 + 95 + 45 = 265`.\n\nThe [next section](/optimization/assignment/assignment_example) shows how solve\nan assignment problem, using both the MIP solver and the CP-SAT solver.\n\n### Other tools for solving assignment problems\n\nOR-Tools also provides a couple of other tools for solving assignment problems,\nwhich can be faster than the MIP or CP solvers:\n\n- [Linear sum assignment solver](/optimization/assignment/linear_assignment)\n- [Minimum cost flow solver](/optimization/flow/assignment_min_cost_flow)\n\nHowever, these tools can only solve simple types of assignment problems.\nSo for general solvers that can handle a wide variety of problems (and are fast\nenough for most applications), we recommend the MIP and CP-SAT solvers."]]
