Les problèmes de transport et d'affectation

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

• formuler un problème de transport et vérifier son équilibre ;
• construire une solution de base par les méthodes du coin nord-ouest, du moindre coût et de Vogel ;
• tester l'optimalité d'une solution par la méthode des potentiels (MODI) ;
• formuler un problème d'affectation ;
• le résoudre par la méthode hongroise.

5.1 Le problème de transport

Une entreprise dispose de $m$ origines (usines, entrepôts) qui offrent des quantités $a_i$, et de $n$ destinations (clients, magasins) qui demandent des quantités $b_j$. Transporter une unité de l'origine $i$ vers la destination $j$ coûte $c_{ij}$. On cherche les quantités $x_{ij}$ qui minimisent le coût total :

$$\min Z = \sum_{i}\sum_{j} c_{ij}\,x_{ij} \quad \text{s.c.} \quad \sum_j x_{ij} = a_i \;\; \text{(offres)}, \qquad \sum_i x_{ij} = b_j \;\; \text{(demandes)}, \qquad x_{ij} \ge 0$$

C'est un programme linéaire, mais sa structure particulière permet des méthodes beaucoup plus rapides que le simplexe général. Il est au cœur de la logistique : approvisionnement des points de vente d'une chaîne de distribution, acheminement des phosphates, des céréales importées ou des carburants vers les régions.

Définition — Problème équilibré : l'offre totale est égale à la demande totale, $\sum a_i = \sum b_j$. Si l'offre dépasse la demande, on ajoute une destination fictive (stock non expédié) à coût nul ; si la demande dépasse l'offre, une origine fictive (demande non satisfaite).

Une solution de base d'un problème à $m$ origines et $n$ destinations comporte $m + n - 1$ cases occupées (l'une des contraintes est redondante, puisque l'offre totale égale la demande totale).

5.2 Trouver une première solution

On présente les données dans un tableau de transport : une ligne par origine, une colonne par destination, le coût dans chaque case, les offres en marge droite et les demandes en bas.

• Coin nord-ouest : on part de la case en haut à gauche, on y affecte le maximum possible ($\min(a_i, b_j)$), on barre la ligne ou la colonne épuisée et on continue vers la droite ou vers le bas. Méthode rapide mais aveugle aux coûts.
• Moindre coût : on affecte le maximum possible à la case de plus petit coût encore disponible, et ainsi de suite. Elle tient compte des coûts mais peut « piéger » des quantités dans des cases très chères à la fin.
• Vogel (méthode des pénalités) : pour chaque ligne et chaque colonne, on calcule la pénalité, différence entre les deux plus petits coûts disponibles. On choisit la ligne ou la colonne de plus forte pénalité et on affecte le maximum possible à sa case la moins chère. On recalcule les pénalités après chaque affectation. Elle donne souvent la solution optimale ou une solution très proche.

La pénalité mesure le surcoût qu'on subirait si l'on ne servait pas la ligne (ou la colonne) par sa case la moins chère : on traite d'abord les situations où une erreur coûterait le plus cher.

5.3 Tester l'optimalité : la méthode des potentiels (MODI)

On associe un potentiel $u_i$ à chaque origine et $v_j$ à chaque destination, tels que, pour chaque case occupée :

$$u_i + v_j = c_{ij}$$

On fixe arbitrairement $u_1 = 0$ et l'on déduit les autres potentiels de proche en proche. Pour chaque case vide, on calcule le coût réduit :

$$\delta_{ij} = c_{ij} - u_i - v_j$$

Critère d'optimalité : la solution est optimale si tous les coûts réduits des cases vides sont positifs ou nuls.

Si une case a un coût réduit négatif, y faire passer une unité réduit le coût total de $|\delta_{ij}|$. On construit alors un cycle (chemin fermé alternant lignes et colonnes, passant uniquement par des cases occupées) : on ajoute $\theta$ à la case entrante, on retranche et on ajoute alternativement $\theta$ le long du cycle, avec $\theta$ égal à la plus petite quantité des cases « à retrancher ». Puis on recommence le test. C'est exactement le simplexe, appliqué à la structure du tableau de transport.

Un coût réduit nul sur une case vide signale une solution optimale multiple.

5.4 Le problème d'affectation

Il s'agit d'affecter $n$ personnes (ou machines, véhicules) à $n$ tâches, une personne par tâche et une tâche par personne, au moindre coût (ou temps). Avec $x_{ij} = 1$ si la personne $i$ fait la tâche $j$ et 0 sinon :

$$\min Z = \sum_{i}\sum_{j} c_{ij}\,x_{ij} \quad \text{s.c.} \quad \sum_j x_{ij} = 1, \qquad \sum_i x_{ij} = 1, \qquad x_{ij} \in \{0, 1\}$$

C'est un problème de transport particulier où toutes les offres et demandes valent 1. Le nombre d'affectations possibles est $n!$ : déjà 3 628 800 pour $n = 10$. On ne peut pas les énumérer, d'où l'intérêt d'une méthode efficace.

5.5 La méthode hongroise (Kuhn, 1955)

Elle repose sur une propriété simple : retrancher une même constante à tous les coûts d'une ligne (ou d'une colonne) ne change pas l'affectation optimale, puisque chaque ligne contient exactement une affectation.

1. Réduire les lignes : retrancher à chaque ligne son plus petit élément.
2. Réduire les colonnes : retrancher à chaque colonne son plus petit élément.
3. Chercher une affectation sur les zéros : un zéro par ligne et par colonne (zéros indépendants). S'il en existe $n$, c'est l'optimum.
4. Sinon, couvrir tous les zéros avec le nombre minimal de lignes et de colonnes. Soit $k$ le plus petit élément non couvert : le retrancher à tous les éléments non couverts, l'ajouter aux éléments couverts deux fois (intersections). Revenir à l'étape 3.

Exemple. Trois techniciens d'une usine de Kénitra doivent régler trois machines ; les durées (en heures) sont :

Réduction des lignes (minimums 5, 2 et 3) : T1 → (9 ; 0 ; 3), T2 → (0 ; 10 ; 4), T3 → (4 ; 5 ; 0). Chaque colonne contient déjà un zéro. Les zéros (T1, M2), (T2, M1) et (T3, M3) sont indépendants : affectation optimale T1 → M2, T2 → M1, T3 → M3, pour $5 + 2 + 3 = 10$ heures.

Un problème de maximisation (rendement, chiffre d'affaires) se ramène à une minimisation en remplaçant chaque valeur par (plus grande valeur du tableau − valeur). Un problème non carré se complète par des lignes ou colonnes fictives à coût nul.

5.6 Méthode : résoudre un problème de transport

1. Vérifier l'équilibre ; ajouter une origine ou destination fictive si nécessaire.
2. Construire une solution de base (Vogel de préférence) ; vérifier qu'elle compte $m + n - 1$ cases occupées.
3. Calculer les potentiels $u_i$, $v_j$ sur les cases occupées.
4. Calculer les coûts réduits des cases vides ; s'ils sont tous positifs ou nuls, c'est optimal.
5. Sinon, faire entrer la case la plus négative par un cycle et recommencer.
6. Calculer le coût total et interpréter (quelles liaisons utiliser, quelles liaisons abandonner).

Les pièges à éviter

• Oublier d'équilibrer le problème avant d'appliquer les méthodes.
• Calculer une pénalité de Vogel avec des cases déjà barrées.
• Calculer les potentiels avec des cases vides (uniquement les cases occupées).
• Avoir moins de $m + n - 1$ cases occupées (dégénérescence) : ajouter alors une case occupée avec une quantité nulle.
• Dans la méthode hongroise, couvrir les zéros avec plus de lignes que nécessaire.