Article publié le vendredi 20 novembre 2026 dans la catégorie digital.
L’algorithme hongrois résout un problème très précis : attribuer des ressources à des tâches en minimisant un coût total, sans qu’une ressource ou une tâche soit utilisée deux fois. Il transforme une matrice de coûts en une structure de zéros permettant d’identifier une solution optimale. Mise au point à partir des travaux de Harold Kuhn, puis améliorée par James Munkres, cette méthode reste une référence pour les appariements bipartis de taille raisonnable.
Le problème d’affectation : associer chaque ressource à une tâche au moindre coût
Matrice de coûts, affectation unique et objectif d’optimalité
Le problème d’affectation linéaire met en présence autant d’agents que de tâches. Chaque case d’une matrice \(C_{ij}\) représente le coût d’attribuer l’agent i à la tâche j : durée, distance, prix, consommation ou pénalité. L’objectif est de choisir une case par ligne et une par colonne afin de
minimiser la somme des coûts retenus.
On peut aussi le représenter comme un graphe biparti pondéré : les agents forment un premier ensemble de sommets, les tâches le second, et chaque arête porte un coût. La solution recherchée est alors un
appariement parfait de poids minimal.
| Élément | Rôle dans le modèle |
| Ligne | Un agent, une machine ou un véhicule |
| Colonne | Une tâche, une commande ou une destination |
| Case \(C_{ij}\) | Coût de l’association i ? j |
| Solution | Une sélection sans ligne ni colonne répétée |
Exemples d’applications : planification, logistique et allocation de ressources
Cette formulation convient, par exemple, à l’envoi de techniciens vers des interventions, à l’attribution de commandes à des livreurs ou à la distribution de créneaux de production entre machines. Elle sert également à rapprocher des candidats et des postes lorsque chaque compatibilité reçoit un score converti en coût.
Le modèle doit cependant correspondre à la réalité : chaque acteur ne reçoit ici qu’une seule mission. Lorsqu’un véhicule peut effectuer plusieurs livraisons ou qu’une tâche exige plusieurs personnes, il faut un modèle plus riche, tel qu’un
problème de flot à coût minimum.
Le principe de l’algorithme hongrois et ses conditions d’utilisation
Pourquoi les soustractions de lignes et de colonnes préservent la solution optimale
L’idée centrale consiste à créer des zéros sans modifier l’ordre des solutions. Soustraire une constante à tous les coûts d’une même ligne réduit chaque affectation possible du même montant, puisqu’une solution valide sélectionne exactement une case dans cette ligne. Le même raisonnement vaut pour une colonne.
Les écarts entre deux affectations complètes restent donc inchangés. Les zéros de la matrice réduite constituent le graphe d’égalité : ils désignent les associations compatibles avec les potentiels de lignes et de colonnes. Cette lecture fait de l’algorithme une méthode primale-duale, plutôt qu’une simple manipulation arithmétique.
Matrices carrées, problèmes de minimisation et ajout de tâches fictives
La version standard utilise une matrice carrée. Si le nombre d’agents diffère du nombre de tâches, on ajoute des lignes ou colonnes fictives. Un coût nul peut signifier qu’un agent reste inactif ; un coût élevé peut au contraire décourager cette option. Le choix doit traduire le coût métier réel de la non-affectation.
Pour maximiser des gains, on transforme d’abord la matrice en coûts, par exemple en remplaçant chaque gain par la différence entre le gain maximal observé et ce gain. Des coûts négatifs sont également possibles après une normalisation cohérente : l’algorithme repose sur les différences de coûts, non sur leur signe initial.
Les étapes de l’algorithme hongrois sur une matrice de coûts
Réduire chaque ligne puis chaque colonne
Pour chaque ligne, on repère son minimum et on le soustrait à toutes ses cellules. Chaque ligne contient alors au moins un zéro. On répète l’opération pour les colonnes : la matrice contient désormais au moins un zéro par ligne et par colonne.
Couvrir les zéros avec un nombre minimal de lignes
On couvre ensuite tous les zéros avec le plus petit nombre possible de lignes horizontales et verticales. Si une matrice est de dimension n et que n lignes suffisent, elle contient un ensemble de n zéros indépendants : une affectation optimale peut être extraite.
Ce critère s’appuie sur le théorème de König, qui relie, dans un graphe biparti, la taille d’un appariement maximal à celle d’une couverture minimale de sommets. En pratique, la couverture évite de choisir trop tôt des zéros incompatibles entre eux.
Ajuster la matrice lorsque les lignes ne suffisent pas
Si moins de n lignes couvrent tous les zéros, on prend la plus petite valeur non couverte. On la soustrait à toutes les cases non couvertes et on l’ajoute aux cases situées à l’intersection de deux lignes de couverture. Les cases couvertes une seule fois ne changent pas.
- Cases non couvertes : création possible de nouveaux zéros.
- Intersections doublement couvertes : compensation nécessaire pour préserver l’équivalence.
- Cases couvertes une fois : valeurs inchangées.
L’opération est répétée jusqu’à ce que n lignes de couverture soient nécessaires. Elle conserve les conditions de dualité tout en enrichissant le graphe d’égalité.
Sélectionner des zéros indépendants pour construire l’affectation
Il reste à sélectionner un zéro par ligne et par colonne. On commence souvent par les lignes ou colonnes qui ne possèdent qu’un seul zéro disponible, puis on propage les exclusions. Si plusieurs choix existent, différentes affectations optimales peuvent être obtenues, mais leur coût total initial est identique.
Exemple simplifié d’affectation avec une matrice 3 × 3
Réduction de la matrice et identification des zéros
Considérons la matrice de coûts suivante : A vers les tâches 1, 2 et 3 coûte respectivement 9, 2 et 7 ; B coûte 6, 4 et 3 ; C coûte 5, 8 et 1. Après réduction des lignes, on obtient : A : 7, 0, 5 ; B : 3, 1, 0 ; C : 4, 7, 0. La réduction des colonnes donne ensuite : A : 4, 0, 5 ; B : 0, 1, 0 ; C : 1, 7, 0.
Les zéros permettent de choisir A ? 2, B ? 1 et C ? 3. Ils sont indépendants, car aucune ligne ni colonne n’est répétée. L’algorithme s’arrête donc sans ajustement supplémentaire.
Lecture de l’affectation optimale et calcul du coût initial
Le coût doit être relu dans la matrice de départ : 2 pour A ? 2, 6 pour B ? 1 et 1 pour C ? 3, soit
un total de 9. La matrice réduite sert à trouver la structure optimale ; elle ne donne pas le coût métier final.
Atouts, limites et erreurs fréquentes lors de l’application
Une solution exacte en temps polynomial pour l’affectation classique
L’algorithme hongrois fournit une solution exacte pour le problème classique, avec une complexité usuelle de l’ordre de
\(O(n^3)\) pour une matrice n × n. Il est donc bien plus fiable qu’un choix glouton local, qui peut sélectionner un coût faible au départ et bloquer une meilleure combinaison globale. Pour situer cette performance, la
complexité pseudo-polynomiale concerne d’autres familles de problèmes, dépendantes de valeurs numériques.
Cas non couverts : contraintes supplémentaires et affectations multiples
Des capacités, des horaires, des précédences, des incompatibilités complexes ou plusieurs tâches par agent dépassent le cadre un-à-un. La programmation linéaire en nombres entiers, les flots ou la
programmation dynamique en optimisation peuvent alors être plus adaptées. Les problèmes de plus court chemin relèvent encore d’une autre logique, illustrée par
l’algorithme de Dijkstra.
Confondre zéros de la matrice réduite et coûts nuls de la matrice d’origine
C’est l’erreur la plus courante. Un zéro réduit indique une association admissible dans la recherche d’optimalité, pas une prestation gratuite. Il faut aussi vérifier que les coûts fictifs, les unités employées et les contraintes métier ont été correctement définis avant d’interpréter le résultat.
Questions courantes
L’algorithme hongrois donne-t-il toujours une unique solution ?
Non. Plusieurs affectations peuvent avoir
exactement le même coût minimal lorsque plusieurs combinaisons respectent les mêmes arbitrages. L’algorithme en retourne généralement une, selon l’ordre de traitement des lignes, colonnes ou zéros. Pour identifier toutes les solutions optimales, il faut explorer les alternatives compatibles après avoir établi le coût minimal, ce qui peut devenir coûteux lorsque les égalités sont nombreuses.
Comment interdire une association agent-tâche précise ?
Il faut attribuer à cette association un coût très élevé, supérieur à toute solution réaliste acceptable, ou l’exclure dans une implémentation qui gère les arêtes absentes. Une valeur artificiellement élevée doit être choisie avec prudence : elle ne doit pas provoquer de dépassement numérique ni être sélectionnée faute d’autre possibilité. Si l’interdiction rend toute affectation complète impossible, le modèle doit pouvoir le signaler.
Que faire si certains coûts sont inconnus ou difficilement comparables ?
Il faut d’abord définir une métrique commune. Temps, distance, niveau de priorité et dépense financière ne peuvent être additionnés qu’après pondération explicitement décidée. Un coût manquant ne doit pas être remplacé automatiquement par zéro : il peut représenter une donnée à estimer, une incompatibilité ou une association non autorisée.
La qualité du résultat dépend d’abord de la qualité de la matrice.
Peut-on utiliser cette méthode avec des préférences plutôt que des coûts ?
Oui, à condition de convertir les préférences en valeurs numériques cohérentes. Une note élevée peut devenir un faible coût par transformation, tandis qu’un classement ordinal peut être traduit en pénalités. Cette conversion exige toutefois de vérifier que l’écart entre deux notes a bien un sens opérationnel : l’algorithme optimise les nombres fournis, non l’intention implicite derrière les préférences.
Comment contrôler que l’affectation obtenue est exploitable ?
Il faut vérifier que chaque agent et chaque tâche apparaissent une seule fois, puis recalculer le total dans les données initiales. Il est également utile de contrôler les contraintes externes non intégrées dans la matrice : disponibilités, compétences requises, horaires ou règles de sécurité.
Une solution mathématiquement optimale peut rester inutilisable si ces conditions n’ont pas été modélisées avant le calcul.
Chiffres clés de la méthode
| Indicateur | Chiffre clé |
| Taille de la matrice | Pour 100 agents et 100 tâches, les données d’entrée comptent 10 000 coûts, soit une valeur pour chaque paire possible. |
| Passage à grande échelle | Une matrice de 1 000 × 1 000 contient 1 million de coûts : la préparation et le stockage des données deviennent alors déterminants. |
| Croissance théorique | La complexité usuelle en O(n³) signifie que passer de 100 à 1 000 lignes multiplie l’ordre de grandeur du travail par 1 000. |
| Nombre de combinaisons possibles | Pour 10 agents, il existe 3 628 800 affectations complètes possibles ; l’intérêt est d’éviter leur énumération exhaustive. |
Le point essentiel à retenir
L’algorithme hongrois apporte une réponse rigoureuse lorsqu’il faut réaliser des associations exclusives en maîtrisant un critère chiffré. Sa force ne tient pas à un choix intuitif des coûts les plus faibles, mais à la transformation progressive de la matrice jusqu’à faire apparaître une combinaison globalement optimale.
Les zéros servent de repères de calcul, tandis que la valeur finale doit toujours être vérifiée dans les données initiales.
Cette méthode reste particulièrement adaptée aux situations équilibrées et clairement quantifiées. Lorsque les contraintes opérationnelles deviennent plus nombreuses, le modèle doit évoluer plutôt que forcer une matrice inadéquate. Avant de lancer le calcul, la priorité est donc de définir des coûts comparables, d’intégrer les interdictions pertinentes et de contrôler que
l’appariement obtenu est réellement applicable.
Choisir la bonne méthode selon les contraintes
| Configuration | Attribution par ressource | Méthode adaptée | Élément déterminant |
| Agents et tâches équilibrés | Une seule | Algorithme hongrois | Coût d’association direct |
| Capacité de plusieurs missions | Multiple | Flot à coût minimum | Capacités sur les arcs |
| Règles métier complexes | Variable | Programmation linéaire entière | Contraintes logiques ou horaires |
| Itinéraire vers une destination | Non concernée | Dijkstra | Coût cumulé d’un chemin |