Bài tập
Sử dụng bộ sưu tập để sắp xếp ngăn nắp các trang
Lưu và phân loại nội dung dựa trên lựa chọn ưu tiên của bạn.
Một trong những vấn đề phổ biến nhất về tối ưu hoá tổ hợp là bài toán chỉ định. Dưới đây là ví dụ: giả sử một nhóm trình thực thi cần thực hiện một nhóm tác vụ và đối với mỗi
trình thực thi và tác vụ, sẽ có chi phí để chỉ định trình thực thi vào tác vụ.
Vấn đề là chỉ định mỗi trình thực thi cho tối đa một tác vụ, trong đó không có hai trình thực thi nào thực hiện cùng một tác vụ, đồng thời giảm thiểu tổng chi phí.
Bạn có thể hình dung vấn đề này bằng biểu đồ bên dưới, trong đó có 4 worker và 4 tác vụ. Các cạnh thể hiện tất cả các cách có thể dùng để chỉ định trình thực thi cho các tác vụ. Nhãn ở các cạnh là chi phí giao nhân viên cho các nhiệm vụ.
Một bài tập tương ứng với một tập hợp con các cạnh, trong đó mỗi trình thực thi có ít nhất một cạnh hướng ra trước và không có hai trình thực thi nào có các cạnh dẫn đến cùng một tác vụ. Dưới đây là một bài tập khả thi.
Tổng chi phí của việc chỉ định này là 70 + 55 + 95 + 45 = 265.
Mục tiếp theo trình bày cách giải một bài tập về bài tập bằng cách sử dụng cả trình giải MIP lẫn trình giải CP-SAT.
OR-Tools cũng cung cấp một số công cụ khác giúp giải bài tập về bài tập, có thể nhanh hơn trình giải quyết MIP hoặc CP:
Tuy nhiên, các công cụ này chỉ có thể giải quyết các loại bài tập đơn giản.
Vì vậy, đối với những trình giải toán nói chung có thể xử lý nhiều vấn đề (và đủ nhanh cho hầu hết các ứng dụng), bạn nên sử dụng trình giải MIP và CP-SAT.
Trừ phi có lưu ý khác, nội dung của trang này được cấp phép theo Giấy phép ghi nhận tác giả 4.0 của Creative Commons và các mẫu mã lập trình được cấp phép theo Giấy phép Apache 2.0. Để biết thông tin chi tiết, vui lòng tham khảo Chính sách trang web của Google Developers. Java là nhãn hiệu đã đăng ký của Oracle và/hoặc các đơn vị liên kết với Oracle.
Cập nhật lần gần đây nhất: 2024-08-09 UTC.
[null,null,["Cập nhật lần gần đây nhất: 2024-08-09 UTC."],[[["\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."]]
