Affectation de tâches en Python : partir d’un CSV avec contraintes

Vous avez un fichier de coûts, plusieurs tâches à distribuer et des associations interdites. Une affectation de tâches en Python doit respecter ces contraintes, mais aussi expliquer ce qui se passe lorsqu’une tâche reste sans agent. Dans ce cas pratique, trois agents se partagent quatre tâches : le script lit un CSV, calcule une solution avec SciPy et exporte un résultat dont le coût est vérifiable.

Résultat de la démonstration : avec une pénalité de 10 points par tâche non attribuée, T1 revient à Bilal, T2 à Alice et T3 à Chloe. T4 reste sans agent. Les affectations coûtent 9 points, auxquels s’ajoutent 10 points de pénalité : l’objectif vaut 19. Une pénalité de 1 change complètement la décision : les quatre tâches restent non attribuées.

Télécharger le script, les CSV et les tests — ZIP gratuit. Sans inscription : deux fichiers de données fictives, le programme complet, les dépendances et les résultats de référence.

Définir ce qu’une affectation doit respecter

Notre problème est volontairement précis : une tâche reçoit au plus un agent, un agent réalise au plus une tâche et le coût total doit être minimal. Les valeurs sont des points fictifs, choisis pour rendre le calcul lisible. Elles ne représentent ni des prix ni des durées mesurées.

Le programme propose deux politiques. Avec --toutes, chaque tâche doit avoir un agent distinct autorisé ; si c’est impossible, il s’arrête avec une erreur. Avec --penalite P, il autorise des tâches non attribuées et ajoute P points pour chacune d’elles. La valeur par défaut, 10, sert uniquement à reproduire l’exemple.

Pour comprendre d’abord le problème d’affectation et ses matrices de coûts, consultez le guide de l’affectation en Python. Nous nous concentrons ici sur le passage du fichier au résultat et sur les échecs que ce passage peut masquer.

Préparer le CSV : une cellule vide interdit le couple

Le fichier couts_demo.csv contient les données suivantes. Les lignes représentent les tâches et les colonnes, après tache, les agents.

tache,Alice,Bilal,Chloe
T1,7,2,
T2,3,,8
T3,,6,4
T4,,,11

Une cellule vide signifie que l’association est interdite : Chloe ne peut pas recevoir T1. Un 0, en revanche, autoriserait une affectation de coût nul. Ne remplacez donc pas les cellules vides par zéro. Et si une cellule est vide parce que le coût est inconnu, corrigez la donnée ou définissez une autre politique avant de lancer ce programme.

Le lecteur accepte les CSV séparés par des virgules, encodés en UTF-8 avec ou sans BOM. Il retire les espaces autour des cellules, puis contrôle le nombre de colonnes, les identifiants uniques et les coûts. Les identifiants commencent par une lettre ASCII ; ils comportent au plus 40 caractères parmi les lettres ASCII, chiffres, tirets et soulignements. Les coûts sont des entiers de 0 à 1 000 000. Les nombres négatifs, décimaux et NaN sont refusés.

Le module csv renvoie normalement les cellules sous forme de chaînes : la conversion et ces règles de validation appartiennent à notre script. L’ouverture du fichier utilise newline="", comme indiqué dans la documentation Python du module csv.

Modéliser la non-affectation avec des colonnes fictives

La fonction linear_sum_assignment résout un problème de coût minimal. Elle accepte aussi des matrices rectangulaires ; le côté le plus grand peut alors conserver des éléments sans correspondance. Pour éviter qu’une tâche disparaisse silencieusement de notre résultat, le mode complet refuse d’abord un nombre de tâches supérieur au nombre d’agents.

En mode avec pénalité, nous ajoutons une colonne fictive par tâche. La tâche T1 peut utiliser sa propre colonne fictive pour P points ; les autres tâches ne peuvent pas utiliser cette colonne. Toutes les tâches disposent ainsi d’une décision explicite : recevoir un agent réel ou rester non attribuées. Une seule colonne fictive ne permettrait de laisser qu’une seule tâche sans agent.

Le calcul minimise :

Somme des coûts des affectations + P × nombre de tâches non attribuées.

Dans la matrice de minimisation de cet exemple, les couples interdits valent np.inf. Le programme vérifie ensuite que chaque ligne est couverte, qu’aucun couple interdit n’a été choisi et qu’aucun agent n’a été réutilisé. Remplacer une interdiction par un très grand coût fini changerait sa signification : ce couple pourrait encore être choisi si le reste du problème l’y pousse.

Vous rencontrerez souvent l’expression « algorithme hongrois » pour ce problème. La documentation actuelle précise que SciPy utilise ici une variante de Jonker–Volgenant. Ce script appelle cette fonction ; il ne réimplémente pas lui-même l’algorithme hongrois. Voir la référence officielle de linear_sum_assignment et notre guide consacré à l’algorithme hongrois.

Lire le résultat et choisir la pénalité

Voici les lignes réellement obtenues sur couts_demo.csv avec une pénalité de 10. Le CSV exporté conserve séparément le coût d’affectation, la pénalité et le statut.

Le calcul se vérifie à la main : 2 + 3 + 4 + 10 = 19. Pour T4, le coût d’affectation affiché vaut zéro parce qu’aucun agent ne lui est attribué ; la pénalité de 10 figure dans une autre colonne. Ce zéro ne décrit pas une prestation gratuite.

Avec P = 1, attribuer la moindre tâche coûte plus cher que la laisser sans agent. Le solveur reporte donc les quatre tâches. C’est cohérent avec l’objectif fourni, même si cette décision peut être inutilisable dans votre activité.

La pénalité exprime le coût que vous donnez à la non-affectation. Ce n’est pas un réglage à augmenter jusqu’à obtenir un tableau qui vous plaît. Elle doit utiliser la même échelle que les autres coûts. Si votre règle est « attribuer le plus de tâches possible, puis minimiser leur coût », il s’agit d’un autre objectif, à modéliser explicitement. Si chaque tâche doit absolument être attribuée, utilisez le mode complet et traitez les impossibilités.

Détecter un conflit même avec autant d’agents que de tâches

Le second fichier, couts_conflit.csv, contient trois tâches et trois agents. Chacune des tâches a au moins un candidat :

tache,Alice,Bilal,Chloe
T1,2,,
T2,3,,
T3,,4,5

Pourtant, une affectation complète est impossible : T1 et T2 nécessitent toutes les deux Alice, qui ne peut réaliser qu’une tâche. Compter les agents ou vérifier séparément chaque ligne ne suffit donc pas. En mode complet, le script signale le conflit et ne produit pas de nouveau fichier de résultat.

Avec une pénalité de 10, ce second cas attribue T1 à Alice pour 2 points et T3 à Bilal pour 4 points, puis laisse T2 sans agent pour 10 points. L’objectif vaut 16. Cette solution partielle ne résout pas un manque de capacité : elle le rend visible.

Exécuter le programme et récupérer les fichiers

Après extraction du ZIP, ouvrez un terminal dans son dossier. Utilisez un environnement Python dédié ; le fichier README explique son activation sous PowerShell, macOS et Linux. Installez les dépendances, puis lancez la démonstration et les tests :

python -m pip install -r requirements.txt
python affectation_csv.py
python test_exemple.py

La démonstration lit le CSV fourni, affiche un résumé JSON et écrit sortie/affectations.csv ainsi que sortie/resultat.json. Les deux fichiers sont remplacés s’ils existent déjà. Pour conserver les résultats de plusieurs essais, choisissez un dossier différent avec --sortie.

python affectation_csv.py couts_demo.csv --penalite 1 --sortie sortie-p1
python affectation_csv.py couts_demo.csv --penalite 10 --sortie sortie-p10
python affectation_csv.py couts_conflit.csv --toutes --sortie sortie-complete

La dernière commande doit échouer avec un code de sortie 2 : c’est le cas impossible décrit plus haut. Les options --toutes et --penalite sont mutuellement exclusives. Après l’installation des bibliothèques, le programme travaille localement sans appel réseau.

"""Affectation unitaire depuis un CSV. Données fictives, coûts en points."""
import argparse
import csv
import json
import re
from dataclasses import dataclass
from pathlib import Path

import numpy as np
from scipy.optimize import linear_sum_assignment

MAX_COUT = 1_000_000
MAX_DIMENSION = 200
IDENTIFIANT = re.compile(r"[A-Za-z][A-Za-z0-9_-]{0,39}\Z")


class AffectationImpossible(ValueError):
    """Toutes les tâches ne peuvent pas recevoir un agent distinct autorisé."""


@dataclass(frozen=True)
class Probleme:
    taches: tuple[str, ...]
    agents: tuple[str, ...]
    couts: tuple[tuple[int | None, ...], ...]


def lire_couts(chemin):
    """Une cellule vide interdit le couple. Un zéro reste un coût autorisé."""
    with Path(chemin).open(encoding="utf-8-sig", newline="") as fichier:
        lignes = list(csv.reader(fichier, strict=True))
    if len(lignes) < 2 or len(lignes[0]) < 2:
        raise ValueError("Le CSV doit contenir un en-tête et au moins une tâche.")
    entete = [cellule.strip() for cellule in lignes[0]]
    agents = entete[1:]
    if entete[0] != "tache":
        raise ValueError("La première colonne doit se nommer tache.")
    if len(agents) != len(set(agents)):
        raise ValueError("Les identifiants des agents doivent être uniques.")
    if not all(IDENTIFIANT.fullmatch(agent) for agent in agents):
        raise ValueError("Identifiant agent invalide : lettres ASCII, chiffres, _ ou -.")
    if max(len(agents), len(lignes) - 1) > MAX_DIMENSION:
        raise ValueError("Exemple limité à 200 tâches et 200 agents.")

    taches, couts = [], []
    for numero, ligne in enumerate(lignes[1:], start=2):
        if len(ligne) != len(entete):
            raise ValueError(f"Ligne {numero} : nombre de colonnes incorrect.")
        tache = ligne[0].strip()
        if not IDENTIFIANT.fullmatch(tache) or tache in taches:
            raise ValueError(f"Ligne {numero} : tâche invalide ou répétée.")
        valeurs = []
        for cellule in ligne[1:]:
            cellule = cellule.strip()
            if cellule == "":
                valeurs.append(None)
            elif re.fullmatch(r"[0-9]{1,7}", cellule) and int(cellule) <= MAX_COUT:
                valeurs.append(int(cellule))
            else:
                raise ValueError(f"Ligne {numero} : coût entier de 0 à {MAX_COUT} attendu.")
        taches.append(tache)
        couts.append(tuple(valeurs))
    return Probleme(tuple(taches), tuple(agents), tuple(couts))


def resoudre(probleme, penalite=None):
    """None exige toutes les tâches. Un entier autorise la non-affectation."""
    if penalite is not None and (type(penalite) is not int or not 0 <= penalite <= MAX_COUT):
        raise ValueError("La pénalité doit être un entier entre 0 et 1 000 000.")
    n, m = len(probleme.taches), len(probleme.agents)
    if penalite is None and n > m:
        raise AffectationImpossible("Plus de tâches que d'agents en mode complet.")

    # Les lignes représentent les tâches. Un agent ne remplit qu'une colonne.
    largeur = m if penalite is None else m + n
    matrice = np.full((n, largeur), np.inf, dtype=np.float64)
    for i, ligne in enumerate(probleme.couts):
        for j, cout in enumerate(ligne):
            if cout is not None:
                matrice[i, j] = cout
        if penalite is not None:
            # Une colonne fictive propre à chaque tâche permet plusieurs reports.
            matrice[i, m + i] = penalite

    try:
        lignes, colonnes = linear_sum_assignment(matrice)
    except ValueError as erreur:
        raise AffectationImpossible(
            "Aucune affectation complète autorisée : vérifier les conflits entre tâches."
        ) from erreur
    if len(lignes) != n or not np.isfinite(matrice[lignes, colonnes]).all():
        raise AffectationImpossible("La solution ne couvre pas toutes les lignes.")

    affectations, utilises = [], set()
    cout_affectations = total_penalites = 0
    for i, j in zip(lignes.tolist(), colonnes.tolist()):
        if j < m:
            cout = probleme.couts[i][j]
            if cout is None or j in utilises:
                raise RuntimeError("Solution invalide : couple interdit ou agent réutilisé.")
            utilises.add(j)
            cout_affectations += cout
            affectations.append({"tache": probleme.taches[i], "agent": probleme.agents[j],
                                 "cout": cout, "penalite": 0, "statut": "attribuee"})
        else:
            total_penalites += penalite
            affectations.append({"tache": probleme.taches[i], "agent": None,
                                 "cout": 0, "penalite": penalite, "statut": "non_attribuee"})

    objectif = cout_affectations + total_penalites
    if objectif != int(matrice[lignes, colonnes].sum()):
        raise RuntimeError("Le coût recalculé diffère de celui du solveur.")
    return {"affectations": affectations, "cout_affectations": cout_affectations,
            "penalites": total_penalites, "objectif": objectif,
            "non_attribuees": [a["tache"] for a in affectations if a["agent"] is None],
            "agents_inutilises": [a for j, a in enumerate(probleme.agents) if j not in utilises]}


def enregistrer(resultat, dossier):
    dossier = Path(dossier)
    dossier.mkdir(parents=True, exist_ok=True)
    (dossier / "resultat.json").write_text(
        json.dumps(resultat, ensure_ascii=False, indent=2) + "\n", encoding="utf-8")
    with (dossier / "affectations.csv").open("w", encoding="utf-8", newline="") as fichier:
        ecrivain = csv.DictWriter(fichier, fieldnames=["tache", "agent", "cout", "penalite", "statut"])
        ecrivain.writeheader()
        ecrivain.writerows(resultat["affectations"])


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("csv", nargs="?", default=str(Path(__file__).with_name("couts_demo.csv")))
    groupe = parser.add_mutually_exclusive_group()
    groupe.add_argument("--penalite", type=int, default=10, help="Points par tâche non attribuée, défaut : 10.")
    groupe.add_argument("--toutes", action="store_true", help="Exiger un agent pour chaque tâche.")
    parser.add_argument("--sortie", default="sortie", help="Dossier des deux fichiers de résultat.")
    args = parser.parse_args()
    try:
        probleme = lire_couts(args.csv)
        resultat = resoudre(probleme, None if args.toutes else args.penalite)
    except (ValueError, OSError, csv.Error) as erreur:
        parser.exit(2, f"Erreur : {erreur}\n")
    enregistrer(resultat, args.sortie)
    print(json.dumps(resultat, ensure_ascii=False, indent=2))


if __name__ == "__main__":
    main()

Vérifier l’optimum et connaître les limites du cas

Le téléchargement comprend 13 tests. Ils couvrent notamment les cellules vides, les coûts nuls, les CSV invalides, les conflits d’affectation, les agents inutilisés et les exports. L’un d’eux compare le solveur à une énumération indépendante de toutes les décisions possibles sur 72 petites matrices, chacune examinée avec cinq politiques : mode complet et pénalités 0, 1, 5 et 10. Cela représente 360 comparaisons, y compris des problèmes impossibles.

L’énumération sert de témoin sur ces petits cas ; elle n’est pas destinée aux fichiers volumineux. La suite réussit également après extraction de l’archive publiée. Ces vérifications contrôlent les résultats annoncés et plusieurs cas limites, sans constituer une preuve formelle pour toutes les entrées.

Le lecteur limite volontairement les fichiers à 200 tâches et 200 agents. Cette borne est celle de l’exemple, pas une limite de SciPy ni une mesure de sa performance. Les coûts entiers bornés permettent aussi de recalculer exactement les totaux utilisés ici. Pour adapter le code, construisez les données avec lire_couts afin de conserver ces validations.

Ce modèle ne gère pas les horaires, les durées, les compétences changeant dans le temps ou un agent réalisant plusieurs tâches. Il ne choisit pas non plus une priorité métier entre deux solutions de même coût optimal. Si plusieurs affectations ont le même objectif, ne déduisez pas une préférence du seul ordre des lignes renvoyées.

Continuer avec vos propres données

Commencez par un petit CSV dont vous pouvez vérifier le résultat à la main. Contrôlez surtout le sens des cellules vides, l’unité des coûts et la règle de non-affectation avant d’ajouter des lignes. Conservez le fichier d’entrée et le JSON de résultat pour pouvoir expliquer chaque décision.

Pour travailler la lecture et la validation des fichiers, retrouvez nos cinq exercices CSV gratuits avec indices et corrigés. La page de ressources Python rassemble aussi les autres cas pratiques et leurs téléchargements.

Exemple original exécuté le 23 octobre 2026 avec Python 3.12.14, numpy 2.5.3, scipy 1.18.1. Les versions testées figurent dans le téléchargement. Données fictives ; résultats calculés par le script fourni. Miniature illustrative générée avec image_gen. Notre méthode éditoriale.