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.

3
Tâche 1Tâche 2Tâche 3
Agent 1
Agent 2
Agent 3
Optimisation Combinatoire et Couplage Biparti

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)

Étape 1 : Réduction des Lignes

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.

Étape 2 : Réduction des Colonnes

Sur la matrice réduite, déterminer le minimum de chaque colonne et le soustraire de tous les éléments de la colonne correspondante.

Étape 3 : Couverture Minimale par des Lignes

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.

Étape 4 : Ajustement de la Matrice

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.

Étape 5 : Sélection des Zéros Optimaux

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 / MachineTask 1 (T₁)Task 2 (T₂)Task 3 (T₃)Task 4 (T₄)
Ouvrier 1 (W₁)9278
Ouvrier 2 (W₂)6437
Ouvrier 3 (W₃)5818
Ouvrier 4 (W₄)7694

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 WorkerMatched TaskOriginal 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.