Projekt
Zadbaj o dobrą organizację dzięki kolekcji
Zapisuj i kategoryzuj treści zgodnie ze swoimi preferencjami.
Jednym z najbardziej znanych problemów z optymalizacją kombinacyjną jest problem z przypisywaniem. Oto przykład: załóżmy, że grupa instancji roboczych musi wykonać zestaw zadań, a w przypadku każdej instancji roboczej i zadania jej przypisanie wiąże się z kosztem.
Problem polega na tym, że każdy z nich należy przypisać maksymalnie do 1 zadania, a 2 innych nie może wykonywać tego samego zadania przy jednoczesnym zminimalizowaniu całkowitego kosztu.
Możesz zwizualizować ten problem na wykresie poniżej, na którym znajdują się 4 instancje robocze i 4 zadania. Krawędzie przedstawiają wszystkie możliwe sposoby przypisywania instancji roboczych do zadań. Etykiety na krawędziach to koszty przypisywania instancji roboczych do zadań.
Przypisanie odpowiada podzbiorze krawędzi, w którym każda instancja robocza ma co najmniej 1 krawędź wystającą i żadne 2 instancje robocze nie mają krawędzi prowadzących do tego samego zadania. Poniżej znajdziesz jedno z możliwych przypisań.
Łączny koszt przypisania wynosi 70 + 55 + 95 + 45 = 265.
W następnej sekcji pokazujemy, jak rozwiązywać problemy z projektami przy użyciu zarówno rozwiązań MIP, jak i CP-SAT.
LUB oferuje też kilka innych narzędzi do rozwiązywania problemów z projektami, które mogą być szybsze niż rozwiązania MIP lub CP:
Te narzędzia rozwiązują jednak tylko proste problemy z projektami.
Jeśli więc masz ogólne rozwiązania, które mogą obsłużyć szeroką gamę problemów (i które są szybkie w większości zastosowań), zalecamy rozwiązania MIP i CP-SAT.
O ile nie stwierdzono inaczej, treść tej strony jest objęta licencją Creative Commons – uznanie autorstwa 4.0, a fragmenty kodu są dostępne na licencji Apache 2.0. Szczegółowe informacje na ten temat zawierają zasady dotyczące witryny Google Developers. Java jest zastrzeżonym znakiem towarowym firmy Oracle i jej podmiotów stowarzyszonych.
Ostatnia aktualizacja: 2024-08-09 UTC.
[null,null,["Ostatnia aktualizacja: 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."]]
