Problème d'affectation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème d'affectation est un problème classique de recherche opérationnelle et d'optimisation combinatoire. Informellement ce problème consiste à attribuer au mieux des tâches à des machines. Plus formellement, l'objectif est de déterminer un couplage parfait de poids minimum (ou un couplage maximum) 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 graphe biparti G =((S,T),E), avec une fonction de poids sur les arêtes : c:E \rightarrow \mathbb{N}, trouver un couplage, c'est-à-dire sous-ensemble d'arêtes F\subset E tel que les arêtes ne partagent pas de sommet, en minimisant la somme des poids des arêtes de F, c'est-à-dire: \sum_{e\in F} c(e).

Algorithmes[modifier | modifier le code]

L'algorithme hongrois, parfois appelé algorithme de Kuhn-Munkres, résout le problème en temps polynomial.

Applications[modifier | modifier le code]

L'application la plus classique de ce problème est, en ordonnancement de tâches, l'affectation de n machines à n 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.

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

  1. Bernard Fortz, « Recherche opérationnelle et applications », sur Université libre de Bruxelles,‎ .

Articles connexes[modifier | modifier le code]

Problème des mariages stables