Problème d'affectation
- Problème d'affectation
-
Le problème d'affectation est un problème classique de recherche opérationnelle. L'objectif est de déterminer 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.
Applications pratiques
L'application la plus classique de ce problème est l'affectation de n employés à n tâches. Chaque employé ne peut être affecté qu'à une seule tâche et chaque couple (tâche, employé) a un coût. Le but est de minimiser le coût total d'exécution des tâches.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Problème d'affectation de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Probleme d'affectation — Problème d affectation Le problème d affectation est un problème classique de recherche opérationnelle. L objectif est de déterminer un couplage maximum dans un graphe biparti valué. Applications pratiques L application la plus classique de ce… … Wikipédia en Français
Probleme SAT — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… … Wikipédia en Français
Probleme des lecteurs et des redacteurs — Problème des lecteurs et des rédacteurs Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra,… … Wikipédia en Français
Problème SAT — On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une évaluation sur un ensemble de variables propositionnelles[1] telle qu une formule… … Wikipédia en Français
Problème des lecteurs et des rédacteurs — Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra, qui est également à l origine du problème… … Wikipédia en Français
SAT (problème) — Problème SAT On nomme problème SAT un problème de décision visant à savoir s il existe une solution à une série d équations logiques données. En termes plus précis : une valuation sur un ensemble de variables propositionnelles[1] telle qu… … Wikipédia en Français
Algorithme hongrois — L algorithme hongrois ou méthode hongroise (parfois appelé aussi algorithme de Kuhn) est un algorithme d optimisation combinatoire, qui résout le problème d affectation en temps polynomial. Il a été proposé en 1955 par le mathématicien américain… … Wikipédia en Français
Méthode de l'entropie croisée — Traduction à relire Cross entropy method → … Wikipédia en Français
Optimisation multi-objectif — L optimisation multiobjectif est branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire classique).… … Wikipédia en Français
Optimisation multiobjectif — L optimisation multiobjectif est une branche de l optimisation combinatoire dont la particularité est de chercher à optimiser simultanément plusieurs objectifs d un même problème (contre un seul objectif pour l optimisation combinatoire… … Wikipédia en Français
