Optimisation des affectations en Python : du graphe biparti au choix optimal

Optimiser une affectation consiste à associer chaque agent à une tâche distincte afin d’optimiser la somme des coûts. Le modèle classique est un couplage parfait dans un graphe biparti pondéré. L’algorithme hongrois résout ce problème en temps polynomial ; un petit exemple permet de comprendre pourquoi choisir successivement les associations les moins coûteuses ne suffit pas. [3]

1. Définir précisément ce que l’on optimise

1. Un agent, une tâche : dans l’affectation complète classique, chaque agent reçoit exactement une tâche et chaque tâche est attribuée exactement une fois. L’objectif porte sur l’ensemble des associations, pas sur chaque décision prise isolément. [3]
2. Le coût total est une somme. Si les valeurs représentent des durées, le modèle présenté minimise la somme des temps de travail, et non nécessairement la date de fin de tous les travaux. [3]
3. L’algorithme hongrois, également appelé Kuhn–Munkres, recherche un couplage parfait de poids optimal en temps polynomial. Il peut correspondre à une minimisation ou à une maximisation, selon l’objectif du problème. [3]

Cette distinction sur l’objectif est essentielle avant de programmer. Pour des équipes et des tâches, une matrice de durées répond à la question « quelle répartition minimise le travail cumulé ? ». Elle ne répond pas, à elle seule, à une question d’ordonnancement. Choisir les bons coûts fait partie de la résolution : un programme peut optimiser correctement une somme tout en répondant à une autre question que celle que vous souhaitiez poser. [3]

2. Passer du graphe à la matrice de coûts

Le graphe comporte deux ensembles de sommets : les agents d’un côté, les tâches de l’autre. Une arête entre un agent et une tâche porte le coût de cette association. Dans le cadre classique décrit ici, les deux ensembles ont le même nombre d’éléments. Chercher une solution revient à sélectionner des arêtes de façon que chaque sommet appartienne exactement à une association, tout en minimisant leur poids total. [3]

La matrice représente les mêmes informations autrement : une ligne par agent, une colonne par tâche, et un coût à leur intersection. Pour préparer des données en Python, cette représentation donne une correspondance simple entre indices et décisions. L’important est de conserver les étiquettes des lignes et des colonnes : le résultat numérique n’a de sens opérationnel que si l’on sait à quelle équipe et à quelle tâche chaque indice correspond. [3]

3. Un exemple où le choix le moins cher devient coûteux

Prenons un exemple hypothétique avec deux équipes A et B et deux tâches 1 et 2. La ligne de A contient les coûts (1, 2), celle de B les coûts (2, 100). Ces valeurs illustratives suivent le modèle d’une matrice de coûts équipe–tâche. L’association individuellement la moins chère est A → 1, de coût 1. Mais, une fois cette décision fixée, il ne reste que la tâche 2 pour B, ce qui impose un coût de 100. [3]

Il existe seulement deux affectations complètes : A → 1 et B → 2 coûtent 1 + 100 = 101 ; A → 2 et B → 1 coûtent 2 + 2 = 4. La seconde est donc optimale. Le raisonnement montre précisément l’erreur du choix glouton : économiser une unité sur A oblige ici à en dépenser 98 de plus sur B. Une association doit être évaluée avec les possibilités qu’elle laisse aux autres agents. [3]

Voici une traduction pédagogique en Python. Elle compare explicitement les deux possibilités de cet exemple ; ce n’est pas une implémentation de l’algorithme hongrois. Elle sert à rendre visibles les contraintes et le calcul du coût total, sans dépendre d’une bibliothèque d’optimisation. [3]

couts = [[1, 2], [2, 100]]

# Chaque tuple donne les tâches des équipes A puis B.
# Les indices Python 0 et 1 désignent les tâches 1 et 2.
affectations = [(0, 1), (1, 0)]

resultats = []
for affectation in affectations:
    total = 0
    for equipe, tache in enumerate(affectation):
        total += couts[equipe][tache]
    resultats.append((total, affectation))

cout_minimal, solution = min(resultats)
print(cout_minimal)  # 4
print(solution)      # (1, 0) : A → 2, B → 1

4. Ce qu’apporte réellement l’algorithme hongrois

Comparer les deux solutions à la main suffit pour cet exemple. L’intérêt de l’algorithme hongrois est de résoudre le problème général en temps polynomial, plutôt que de se limiter à un choix local. Sa propriété utile est la recherche d’un optimum global sous les contraintes d’affectation : chaque agent et chaque tâche interviennent exactement une fois dans la solution complète. [3]

La formulation par optimisation linéaire permet aussi de clarifier le modèle. Une variable de décision indique si une association est retenue ; son coût contribue alors à la somme à minimiser. Les exigences d’unicité viennent du couplage parfait. Cette lecture sépare trois éléments qu’un programme doit respecter : les données de coût, les décisions autorisées et la fonction objectif. Le graphe, la matrice et la formulation d’optimisation décrivent ainsi le même problème sous des angles complémentaires. [3]

5. Préparer une résolution Python sans confondre les outils

Pour passer à une application, commencez par vérifier que votre besoin correspond bien à ce modèle : deux groupes de même taille, une association unique par élément et un objectif additif. Si un agent doit recevoir plusieurs tâches ou si certaines tâches peuvent rester libres, vous avez modifié les contraintes du problème présenté. Il faut alors vérifier explicitement que la formulation et le solveur choisis prennent en charge ces différences, plutôt que de supposer que toute méthode d’affectation les traite automatiquement. [3]

Enfin, distinguez le calcul de son interface. La documentation officielle définit tkinter comme une interface Python vers la boîte à outils graphique Tcl/Tk : elle ne documente pas un solveur d’affectation. Une interface peut servir à présenter les coûts ou les résultats, mais elle ne remplace pas l’algorithme d’optimisation. Pour vérifier votre logique, le petit exemple précédent constitue déjà un repère utile : le coût attendu est 4, avec deux tâches distinctes attribuées aux deux équipes. [2], [3]

Explore next

1. Comment distinguer un problème d’affectation d’un problème d’ordonnancement ?
2. Comment vérifier automatiquement qu’une affectation respecte toutes ses contraintes ?
3. Comment adapter le modèle lorsque le nombre d’agents diffère du nombre de tâches ?
4. Comment interpréter les variables de décision d’une formulation d’affectation ?

Sources

Open a source or expand its cited passages.

Relevance scores are model estimates of how well each source addresses this question, not probabilities or fact-check ratings. Reasoned guidance is identified on hover.

1. 91Algorithme hongrois — Wikipédiafr.wikipedia.orgRéférence directement pertinente pour le graphe biparti, la matrice de coûts et le rôle de l’algorithme hongrois ; les détails d’implémentation Python restent absents.›
2. 20tkinter — Python interface to Tcl/Tk — Python 3.15.2 documentationdocs.python.orgPermet de distinguer précisément tkinter d’un solveur d’optimisation, mais ne documente aucun algorithme d’affectation.›