# Solveur du problème d'affectation (algorithme hongrois) Résout les problèmes d'affectation 2–8 × 2–8 par l'algorithme hongrois des manuels (matrices rectangulaires acceptées, complétées par des lignes/colonnes fictives de coût nul) : réductions par lignes et colonnes, couplage maximal des zéros par chemins augmentants, sinon couverture minimale des zéros par des droites selon König en retranchant le plus petit élément non couvert et en l'ajoutant aux intersections ; les maximisations sont résolues sur la matrice inversée en interne. Chaque tour de réduction/couverture est affiché ; l'affectation optimale et le coût total sont vérifiés par substitution. Classique : [[9,2,7],[6,4,3],[5,8,1]] en min → coût total 9. > Page canonique: https://elysiatools.com/fr/tools/assignment-problem-solver - **Catégorie:** Math & Numbers - **Mots-clés:** problème d'affectation, algorithme hongrois, kuhn-munkres, affectation optimale, matrice des coûts, couplage, recherche opérationnelle, affectation des tâches, ouvrier tâche, optimisation combinatoire ## Présentation Le solveur du problème d'affectation applique l'algorithme hongrois (Kuhn-Munkres) pour associer de manière optimale des agents à des tâches sur des matrices de 2×2 à 8×8. Il prend en charge la minimisation des coûts ou la maximisation des profits, équilibre automatiquement les matrices rectangulaires avec des variables fictives de coût nul, et détaille chaque étape de réduction de ligne/colonne et de couverture par droites selon le théorème de König. ## Entrées - **Matrice des coûts (une ligne par ligne)** (textarea): Cost (or benefit) matrix, one row per worker, one column per task. 2–8 rows × 2–8 columns; rectangular matrices are padded with zero-cost dummies. - **Objectif** (select) - **Décimales** (number) ## Quand l'utiliser - Pour attribuer des opérateurs à des postes de travail en minimisant le coût global ou le temps cumulé d'exécution. - Pour répartir des projets ou des territoires commerciaux afin de maximiser le rendement et les bénéfices totaux. - Pour valider pas à pas des exercices universitaires de recherche opérationnelle et de couplage biparti de poids optimal. ## Fonctionnement - Saisissez la matrice des coûts ou des gains (de 2 à 8 lignes et colonnes), en plaçant un agent par ligne et une tâche par colonne. - Sélectionnez votre objectif d'optimisation : minimiser le coût total ou maximiser le bénéfice total, puis ajustez la précision décimale. - Le solveur applique les réductions par lignes et colonnes, recherche les chemins augmentants de zéros et trace la couverture minimale de droites. - Consultez les étapes détaillées d'itération, la matrice d'affectation optimale et la valeur totale vérifiée par substitution. ## Cas d'usage - Optimisation du planning d'un atelier d'usinage en assignant chaque machine à la pièce la plus adaptée. - Attribution de tournées de livraison à des chauffeurs pour minimiser la distance totale parcourue. - Vérification didactique des calculs d'algorithmique combinatoire pour étudiants et enseignants en informatique ou gestion. ## Questions fréquentes ### Comment l'outil gère-t-il une matrice rectangulaire non carrée ? Il ajoute automatiquement des lignes ou des colonnes fictives avec un coût de zéro pour équilibrer la matrice avant d'exécuter l'algorithme. ### Comment fonctionne la résolution pour un objectif de maximisation ? La matrice est inversée (valeurs multipliées par -1) en interne, ce qui permet de réutiliser le processus de minimisation standard tout en affichant le bénéfice réel. ### Quelles sont les dimensions de matrice acceptées ? L'outil accepte des dimensions allant de 2 lignes sur 2 colonnes jusqu'à 8 lignes sur 8 colonnes. ### Quels séparateurs puis-je utiliser pour entrer les valeurs ? Vous pouvez séparer les éléments d'une même ligne par des virgules ou des espaces, et utiliser un saut de ligne pour chaque nouvel agent. ### Le solveur montre-t-il les étapes intermédiaires de calcul ? Oui, il affiche les minima soustraits à chaque étape, les rondes de couplage des zéros et les ajustements de couverture par droites. ## Outils associés - [Calculateur de plus court chemin (Dijkstra pas à pas)](https://elysiatools.com/fr/tools/graph-shortest-path): Aide au calcul manuel de Dijkstra : saisissez 1–30 arêtes (une par ligne : départ, arrivée, poids) et les nœuds source/cible ; non orienté par défaut, avec option orientée. Chaque itération journalise quel nœud est fixé, à quelle distance, et comment chaque relâchement met à jour la table des distances provisoires ; les égalités se tranchent par le plus petit nom lexicographique, si bien que le journal correspond à une trace de manuel ; les poids négatifs sont rejetés et une cible inatteignable est une réponse valide. Classique : A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, D-E 4, D-F 11, E-F 8, de A vers F → distance 13 via A→C→E→F. - [Texte à l'Envers](https://elysiatools.com/fr/tools/upside-down-text): Retourne le texte à l'envers (ɥǝllo) par rotations lettre par lettre, avec des bascules optionnelles pour conserver l'ordre de lecture et protéger URLs/emails. Texte Unicode brut, sans police. - [Générateur de marqueurs de chapitres podcast (ID3 / Podcasting 2.0)](https://elysiatools.com/fr/tools/podcast-chapter-marker-builder): Collez une liste de chapitres horodatés et générez d'un coup tous les formats de livraison : JSON de chapitres Podcasting 2.0 (v1.2.0) et balise RSS podcast:chapters, gravure optionnelle des trames ID3v2.4 CHAP+CTOC dans un MP3 téléversé (millisecondes en uint32 big-endian simple, offsets 0xFFFFFFFF, sous-trame TIT2 par chapitre, trames existantes préservées), paires de commentaires Vorbis CHAPTER001 (OGG/Opus), texte mp4chaps, bloc d'horodatages pour la description YouTube et sidecar SRT, plus la matrice réelle de support des lecteurs (Apple accepte le JSON via RSS depuis 2025 ; Pocket Casts/Overcast ne lisent que l'ID3 embarqué ; Spotify ignore les deux). - [Physique STEM : tuteur du graphe vitesse-temps](https://elysiatools.com/fr/tools/education-stem-physics-kinematics-velocity-time-graph): Tuteur visuel de cinématique : graphe v-t (avec solveur SUVAT à accélération constante, aire = déplacement), simulateur de projectile (g réglable + résistance de l’air) et chute libre - [Liste indentée vers arbre ASCII](https://elysiatools.com/fr/tools/ascii-tree-from-indented-list): Transforme une liste hiérarchique indentée (2/4 espaces ou tabulation ; préfixes -, *, 1. facultatifs) en arbre ASCII copiable. Deux styles : cadre Unicode et ASCII classique. Options : lignes guides complètes, espaces de fin, feuilles entre crochets. - [Calculateur de Jour de la Semaine](https://elysiatools.com/fr/tools/day-of-week-calculator): Calcule quel jour de la semaine correspond à une date donnée - [Transcripteur audio vers texte (IA)](https://elysiatools.com/fr/tools/audio-to-text-transcriber): Transcrit la voix d'un audio (wav/mp3/m4a/flac/ogg/webm/aac) en texte, SRT, VTT ou JSON avec grok-stt. Jusqu'à 10 min. - [Réduction de Bruit Audio FFmpeg](https://elysiatools.com/fr/tools/ffmpeg-audio-noise-reduction): Réduction de bruit audio professionnelle utilisant les filtres avancés FFmpeg (highpass, afftdn, loudnorm) pour un nettoyage audio optimal ## Exemples - [Exemples d'Analyse de Logs ELK Stack](https://elysiatools.com/fr/samples/elk-stack-samples): Exemples complets ELK Stack pour agrégation, traitement et visualisation de logs dans les systèmes distribués - [Échantillons Audio MP3 Libres de Droits](https://elysiatools.com/fr/samples/mp3-samples): Collection d'échantillons audio libres de droits pour les tests et le développement, incluant les sons de la nature, la musique de méditation et l'audio ambiant - [Groupes de Capture Nommés Regex](https://elysiatools.com/fr/samples/regex-named-groups): Collection de modèles regex utilisant des groupes de capture nommés pour extraire des données structurées du texte. Les groupes nommés rendent les modèles plus lisibles et maintenables en assignant des noms significatifs aux parties capturées. - [Exemples de Variables d'Environnement (.env)](https://elysiatools.com/fr/samples/env-samples): Exemples de configuration de variables d'environnement pour différents types d'applications et environnements