Restez organisé à l'aide des collections
Enregistrez et classez les contenus selon vos préférences.
L'un des problèmes d'optimisation combinatoire les plus connus est le problème d'attribution. Voici un exemple: supposons qu'un groupe de nœuds de calcul doive effectuer un ensemble de tâches, et que pour chaque nœud de calcul et chaque tâche, l'attribution d'un nœud de calcul à la tâche entraîne un coût.
Le problème consiste à attribuer chaque nœud de calcul au maximum à une tâche, sans que deux nœuds de calcul effectuent la même tâche, tout en minimisant le coût total.
Vous pouvez visualiser ce problème dans le graphique ci-dessous, qui comporte quatre nœuds de calcul et quatre tâches. Les arêtes représentent toutes les façons possibles d'affecter des nœuds de calcul à des tâches. Les étiquettes sur les arêtes correspondent aux coûts liés à l'affectation de nœuds de calcul aux tâches.
Une attribution correspond à un sous-ensemble d'arêtes, dans lequel chaque nœud de calcul a au maximum un bord sortant, et deux nœuds de calcul n'ont pas d'arêtes menant à la même tâche. Une attribution possible est illustrée ci-dessous.
Le coût total de l'attribution est de 70 + 55 + 95 + 45 = 265.
La section suivante explique comment résoudre un problème d'attribution à l'aide du résolveur MIP et du résolveur CP-SAT.
D’autres outils pour résoudre les problèmes des devoirs
OR-Tools fournit également d'autres outils pour résoudre les problèmes d'attribution, qui peuvent être plus rapides que les résolveurs MIP ou CP:
Toutefois, ces outils ne peuvent résoudre que des types de problèmes d'attribution simples.
Ainsi, pour les solutions générales capables de gérer une grande variété de problèmes (et assez rapides pour la plupart des applications), nous recommandons les résolveurs MIP et CP-SAT.
Sauf indication contraire, le contenu de cette page est régi par une licence Creative Commons Attribution 4.0, et les échantillons de code sont régis par une licence Apache 2.0. Pour en savoir plus, consultez les Règles du site Google Developers. Java est une marque déposée d'Oracle et/ou de ses sociétés affiliées.
Dernière mise à jour le 2024/08/09 (UTC).
[[["Facile à comprendre","easyToUnderstand","thumb-up"],["J'ai pu résoudre mon problème","solvedMyProblem","thumb-up"],["Autre","otherUp","thumb-up"]],[["Il n'y a pas l'information dont j'ai besoin","missingTheInformationINeed","thumb-down"],["Trop compliqué/Trop d'étapes","tooComplicatedTooManySteps","thumb-down"],["Obsolète","outOfDate","thumb-down"],["Problème de traduction","translationIssue","thumb-down"],["Mauvais exemple/Erreur de code","samplesCodeIssue","thumb-down"],["Autre","otherDown","thumb-down"]],["Dernière mise à jour le 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"]]
