Problème d'affectation

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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.

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.

Définition formelle[modifier | modifier le code]

Le problème peut être énoncé de la manière suivante^[1]. Étant donné un ensemble d'agents ${\displaystyle S}$ et un ensemble de tâches ${\displaystyle T}$, On modélise le problème par un graphe biparti ${\displaystyle G=((S,T),E)}$, avec une fonction de poids sur les arêtes ${\displaystyle c:E\rightarrow \mathbb {R} }$. Le problème d'affectation consiste donc à trouver un couplage ${\displaystyle F\subseteq E}$, avec ${\displaystyle |F|=|T|}$, et minimisant la somme ${\displaystyle \sum _{e\in F}c(e)}$ des poids des arêtes de ${\displaystyle F}$.

Algorithmes[modifier | modifier le code]

L'algorithme hongrois, parfois appelé algorithme de Kuhn-Munkres, résout le problème en temps polynomial. On peut aussi écrire le problème sous forme d'un problème d'optimisation linéaire. Sa solution sera entière car la matrice ainsi définie est totalement unimodulaire.

Applications[modifier | modifier le code]

L'application la plus classique de ce problème est, en ordonnancement de tâches, l'affectation de ${\displaystyle n}$ machines à ${\displaystyle m}$ tâches. Chaque machine ne peut être affectée qu'à une seule tâche et chaque couple (tâche;machine) a un coût. Le but est de minimiser le coût total d'exécution des tâches.

Lien avec d'autres problèmes[modifier | modifier le code]

L'algorithme d'Edmonds pour les couplages traite le problème du couplage de cardinal maximum dans tous les graphes en temps polynomial.

Le problème d'affectation est aussi lié au problème du flot de coût minimum.

Notes et références[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

• Problème des mariages stables

• Portail de l'informatique théorique