Calculateur de la Méthode Hongroise (Problème d'Affectation)
Résolvez vos problèmes d'affectation pas à pas via l'algorithme Hongrois : réduction des lignes et colonnes, couverture par lignes et appariement optimal.
| Tâche 1 | Tâche 2 | Tâche 3 | |
|---|---|---|---|
| Agent 1 | |||
| Agent 2 | |||
| Agent 3 |
Le Problème d'Affectation et l'Algorithme Hongrois : Guide Académique
Formalisation mathématique de l'algorithme de Kuhn-Munkres (Méthode Hongroise) pour l'affectation optimale et la minimisation des coûts.
1. Quel problème résout le Modèle d'Affectation ?
Le Problème d'Affectation est un modèle classique d'optimisation combinatoire dans lequel n agents (ouvriers, machines) doivent être affectés à n tâches de façon strictement bijective (un pour un). Étant donné une matrice de coûts C où cᵢⱼ représente le coût de confier la tâche j à l'agent i, le but est de minimiser le coût total ∑ cᵢⱼ xᵢⱼ sous contrainte que chaque agent et tâche reçoivent exactement une assignation, avec xᵢⱼ ∈ {0, 1}. La méthode hongroise d'Harold Kuhn résout ce problème en temps polynomial O(n³).
2. Les 5 Étapes de l'Algorithme Hongrois (Kuhn-Munkres)
Déterminer le minimum de chaque ligne et le soustraire de tous les éléments de cette même ligne pour faire apparaître au moins un zéro par ligne.
Sur la matrice réduite, déterminer le minimum de chaque colonne et le soustraire de tous les éléments de la colonne correspondante.
Tracer le nombre minimal de droites horizontales et verticales pour couvrir tous les zéros. Si ce nombre égale n, une affectation optimale est possible (Étape 5). S'il est inférieur à n, passer à l'Étape 4.
Repérer le plus petit élément non couvert k. Le soustraire de toutes les cases non couvertes et l'ajouter aux cases situées à l'intersection de deux droites. Les cases couvertes par une seule droite restent inchangées. Retourner à l'Étape 3.
Choisir n zéros indépendants (aucun ne partageant la même ligne ou colonne). Reporter ces positions sur la matrice de départ pour sommer les coûts minimaux.
3. Exemple Académique Résolu : 4 Ouvriers × 4 Tâches
Suivez les réductions successives d'une matrice 4×4 et vérifiez le résultat de notre calculateur.
| Worker / Machine | Task 1 (T₁) | Task 2 (T₂) | Task 3 (T₃) | Task 4 (T₄) |
|---|---|---|---|---|
| Ouvrier 1 (W₁) | 9 | 2 | 7 | 8 |
| Ouvrier 2 (W₂) | 6 | 4 | 3 | 7 |
| Ouvrier 3 (W₃) | 5 | 8 | 1 | 8 |
| Ouvrier 4 (W₄) | 7 | 6 | 9 | 4 |
A. Réduction des Lignes (Soustraire les Minima de Ligne)
Ligne 1 min = 2 → [7, 0, 5, 6] | Ligne 2 min = 3 → [3, 1, 0, 4] | Ligne 3 min = 1 → [4, 7, 0, 7] | Ligne 4 min = 4 → [3, 2, 5, 0]. Chaque ligne contient au moins un zéro.
B. Réduction des Colonnes (Soustraire les Minima de Colonne)
Colonne 1 minimum 3 → [4, 0, 1, 0]. Les colonnes 2, 3 et 4 contiennent déjà des zéros et restent inchangées : Col 2 = [0, 1, 7, 2], Col 3 = [5, 0, 0, 5], Col 4 = [6, 4, 7, 0].
C. Couverture par Droites et Indépendance
Les zéros obtenus sont en (W₁, T₂), (W₂, T₁), (W₂, T₃), (W₃, T₃), (W₄, T₁) et (W₄, T₄). Le nombre minimal de droites pour tous les couvrir est exactement de 4 (= n). L'optimum est donc immédiatement atteint.
| Assigned Worker | Matched Task | Original Cost |
|---|---|---|
| Ouvrier 1 (W₁) | Tâche 2 (T₂) | 2 € |
| Ouvrier 2 (W₂) | Tâche 1 (T₁) | 6 € |
| Ouvrier 3 (W₃) | Tâche 3 (T₃) | 1 € |
| Ouvrier 4 (W₄) | Tâche 4 (T₄) | 4 € |
Résultat du Coût Minimal Optimal
Coût Total Z* = 2 + 6 + 1 + 4 = 13 €. (Chaque ouvrier est affecté à une tâche exclusive avec un coût global minimal, identique à la résolution du calculateur).
4. Pièges Fréquents lors des Résolutions
Problèmes de Maximisation sans Inversion
Si l'objectif est de maximiser un profit, transformez la matrice en soustrayant chaque valeur du maximum global de la matrice d'origine, ou multipliez par -1.
Matrices Rectangulaires Non Carrées (m ≠ n)
La méthode hongroise requiert une matrice carrée. Ajoutez des lignes ou colonnes fictives de coût nul pour équilibrer les dimensions avant les réductions.
Erreur de Calcul à l'Étape 4
À l'Étape 4, la valeur k est soustraite des cases non couvertes et ajoutée uniquement aux intersections de deux droites. Les cases couvertes par une seule droite ne changent pas.