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.
Các công cụ khác để giải bài tập về bài tập
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.
[[["Dễ hiểu","easyToUnderstand","thumb-up"],["Giúp tôi giải quyết được vấn đề","solvedMyProblem","thumb-up"],["Khác","otherUp","thumb-up"]],[["Thiếu thông tin tôi cần","missingTheInformationINeed","thumb-down"],["Quá phức tạp/quá nhiều bước","tooComplicatedTooManySteps","thumb-down"],["Đã lỗi thời","outOfDate","thumb-down"],["Vấn đề về bản dịch","translationIssue","thumb-down"],["Vấn đề về mẫu/mã","samplesCodeIssue","thumb-down"],["Khác","otherDown","thumb-down"]],["Cập nhật lần gần đây nhất: 2024-08-09 UTC."],[[["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"]]
