Qu'est-ce que le problème d'affectation ?

Le problème d'affectation est un problème classique d'optimisation combinatoire : étant donné un ensemble de travailleurs et de tâches, chacun avec un coût associé, trouver l'appariement un-à-un qui minimise le coût total. Il apparaît naturellement dans la planification, la logistique, l'allocation des ressources et la recherche opérationnelle — toute situation où vous devez associer deux groupes de la manière la plus efficace possible.

Le problème est résolu avec l'algorithme hongrois (aussi appelé algorithme de Munkres), une méthode efficace développée dans les années 1950. Contrairement aux approches par force brute qui doivent évaluer chaque permutation, l'algorithme hongrois trouve la solution optimale en temps polynomial, ce qui le rend pratique même pour les matrices de taille modérément grande.

Description de l'outil

Entrez une matrice de coûts représentant le coût d'affectation de chaque travailleur à chaque tâche, puis cliquez sur Résoudre pour trouver instantanément l'affectation optimale. L'outil met en évidence les paires travailleur-tâche qui minimisent le coût total et affiche le résultat dans un tableau clair accompagné du coût total optimal.

Exemples

Matrice d'entrée (3 travailleurs × 3 tâches) :

Tâche 1 Tâche 2 Tâche 3
Travailleur 1 400 150 400
Travailleur 2 400 450 600
Travailleur 3 300 225 300

Affectations optimales :

Travailleur Tâche Coût
Travailleur 1 Tâche 2 150
Travailleur 2 Tâche 1 400
Travailleur 3 Tâche 3 300

Coût total : 850

Fonctionnalités

  • Matrice modifiable — cliquez sur n'importe quelle cellule ou en-tête de colonne pour renommer les travailleurs, les tâches et les coûts directement dans le tableau
  • Taille configurable — supporte les matrices de 2×2 à 8×8
  • Résultats instantanés — l'algorithme hongrois s'exécute dans le navigateur sans aller-retour serveur

Comment ça fonctionne

L'outil utilise l'algorithme de Munkres (hongrois) pour résoudre le problème d'affectation de manière optimale. Il construit une matrice de coûts à partir de vos entrées, applique une série d'étapes de réduction de lignes et de colonnes, et trouve itérativement un appariement maximal de zéros jusqu'à ce qu'une affectation optimale complète soit identifiée. La complexité temporelle est $O(n^3)$, où $n$ est la dimension de la matrice.

Pour les matrices non carrées (plus de travailleurs que de tâches ou vice versa), l'algorithme complète la matrice avec des zéros afin que chaque travailleur et chaque tâche soit appariés.

Options expliquées

  • Nombre de travailleurs / lignes — contrôle le nombre de lignes qui apparaissent dans la matrice de coûts (2–8)
  • Nombre de tâches / colonnes — contrôle le nombre de colonnes qui apparaissent dans la matrice de coûts (2–8)
  • Cellules de la matrice de coûts — entrez le coût d'affectation d'un travailleur spécifique à une tâche spécifique ; toute valeur numérique est acceptée

Limitations

  • La taille de la matrice est limitée à 8×8 (64 cellules)
  • L'algorithme minimise le coût total ; pour maximiser (par exemple, pour les matrices de profit), négativez les valeurs avant de les entrer
  • Les valeurs de cellules non numériques sont traitées comme zéro