Concept

Problème d'affectation

Résumé
En informatique, plus précisément en recherche opérationnelle et d'optimisation combinatoire, le problème d'affectation consiste à attribuer au mieux des tâches à des agents. Chaque agent peut réaliser une unique tâche pour un coût donné et chaque tâche doit être réalisée par un unique agent. Les affectations (c'est-à-dire les couples agent-tâche) ont toutes un coût défini. Le but est de minimiser le coût total des affectations afin de réaliser toutes les tâches. thumb|L'affectation optimale entre le groupe d'agent et de tâche est représenté ici par les arcs rouges. Plus formellement, l'objectif est de déterminer un couplage d'une taille égale au nombre de tâches, de poids minimum dans un graphe biparti valué. Si il y a autant d'agents que de tâches, il s'agit de déterminer un couplage parfait de poids minimum dans un graphe biparti valué. Le problème d'affectation peut être résolu en temps polynomial par l'algorithme hongrois, il appartient par conséquent à la classe de complexité P
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement