Recherche opérationnelle
Le problème d’affectation
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 9 : Le problème d’affectation
Un transport dégénéré
L’énoncé
Le problème
n agents, n tâches, un coût c_{ij} si l’agent i exécute la tâche j.
Affecter un agent à une tâche et une seule, de façon à minimiser le coût total.
C’est un problème de transport
Chaque agent a une « offre » de 1, chaque tâche une « demande » de 1.
On pourrait donc le résoudre par MODI — mais la dégénérescence y est massive : une base compte 2n-1 cases pour seulement n affectations non nulles.
Pourquoi l’énumération ne marche pas
Le nombre d’affectations possibles
| n | n! |
|---|---|
| 4 | 24 |
| 8 | 40\,320 |
| 12 | 479\,001\,600 |
| 20 | 2{,}4 \times 10^{18} |
L’ordre de grandeur
À un million d’essais par seconde, n = 20 demanderait soixante-dix mille ans.
L’algorithme hongrois résout le même problème en quelques millisecondes. C’est ce que la recherche opérationnelle apporte : passer de l’impossible au trivial.
L’algorithme hongrois
Le principe
L’idée fondatrice
Retrancher une constante à toute une ligne — ou à toute une colonne — ne change pas la solution optimale, seulement la valeur totale.
Car toute affectation prend exactement un élément par ligne et un par colonne.
Ce qu’on cherche à obtenir
Faire apparaître assez de zéros pour qu’on puisse en choisir n, un par ligne et un par colonne.
Une telle sélection a un coût nul dans la matrice réduite : elle est donc optimale dans l’originale.
Les quatre étapes
La marche à suivre
- Retrancher à chaque ligne son minimum.
- Retrancher à chaque colonne son minimum.
- Couvrir tous les zéros avec le minimum de traits horizontaux et verticaux.
- Si le nombre de traits vaut n, c’est fini. Sinon, ajuster et retourner en 3.
L’ajustement de l’étape 4
Soit \delta le plus petit élément non couvert.
Le retrancher à toutes les cases non couvertes, l’ajouter aux cases doublement couvertes, laisser les autres.
L’exemple
Les données
Quatre techniciens, quatre machines - en heures
| M_1 | M_2 | M_3 | M_4 | |
|---|---|---|---|---|
| T_1 | 13 | 4 | 7 | 6 |
| T_2 | 1 | 11 | 5 | 4 |
| T_3 | 6 | 7 | 2 | 8 |
| T_4 | 1 | 3 | 5 | 9 |
Les deux réductions
Après retrait des minima de ligne - 4, 1, 2, 1
| M_1 | M_2 | M_3 | M_4 | |
|---|---|---|---|---|
| T_1 | 9 | 0 | 3 | 2 |
| T_2 | 0 | 10 | 4 | 3 |
| T_3 | 4 | 5 | 0 | 6 |
| T_4 | 0 | 2 | 4 | 8 |
Puis les colonnes
Seule la colonne M_4 n’a pas de zéro : son minimum vaut 2. On le retranche.
La colonne M_4 devient 0, 1, 4, 6.
Le test de couverture
Les zéros, et les traits
Zéros en (1,2), (1,4), (2,1), (3,3), (4,1).
Ils se couvrent avec trois traits : la ligne T_1, la ligne T_3, la colonne M_1.
Trois traits, pas quatre
3 < 4 : il n’existe pas encore d’affectation complète sur les zéros. Il faut ajuster.
L’ajustement
Le plus petit non couvert vaut 1
Cases non couvertes : lignes T_2 et T_4, colonnes M_2, M_3, M_4 — soit 10, 4, 1 et 2, 4, 6.
On retranche 1 à ces six cases, et on ajoute 1 aux cases doublement couvertes : (1,1) et (3,1).
La matrice obtenue
| M_1 | M_2 | M_3 | M_4 | |
|---|---|---|---|---|
| T_1 | 10 | \mathbf{0} | 3 | 0 |
| T_2 | 0 | 9 | 3 | \mathbf{0} |
| T_3 | 5 | 5 | \mathbf{0} | 4 |
| T_4 | \mathbf{0} | 1 | 3 | 5 |
La solution
Quatre zéros indépendants
T_3 n’a qu’un zéro, en M_3. T_4 n’en a qu’un, en M_1. Restent T_1 et T_2 pour M_2 et M_4 : T_1 \to M_2, T_2 \to M_4.
Le coût, dans la matrice d’origine
T_1 \to M_2 : 4 \qquad T_2 \to M_4 : 4 \qquad T_3 \to M_3 : 2 \qquad T_4 \to M_1 : 1
\text{Total} = 4 + 4 + 2 + 1 = \mathbf{11 \text{ heures}}
Ce que l’affectation naïve aurait donné
Confier à chaque technicien la machine où il est le plus rapide donnerait T_2 et T_4 sur M_1 : impossible.
L’optimum global n’est pas la somme des optima individuels — c’est toute la leçon du chapitre.
Les variantes
Maximiser au lieu de minimiser
La transformation
Remplacer chaque c_{ij} par \max(c) - c_{ij}, puis minimiser.
Le problème devient une affectation classique, et la solution est la même.
Matrice non carrée ou affectation interdite
Deux ajustements
Plus de tâches que d’agents : ajouter des agents fictifs à coût nul. Les tâches qu’ils reçoivent ne seront pas exécutées.
Affectation interdite : mettre un coût très grand — M — dans la case, qui ne sera jamais choisie.
Un conseil de prudence
Choisir M assez grand pour dominer, mais pas au point de perturber les soustractions.
Une valeur dix fois le coût maximal suffit toujours.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- L’affectation est un transport où toutes les offres et demandes valent 1.
- L’énumération est impossible : 20! \approx 2{,}4 \times 10^{18}.
- Retrancher une constante à une ligne ou une colonne ne change pas l’optimum.
- L’algorithme réduit, couvre les zéros, ajuste tant que les traits sont moins de n.
- Sur l’exemple : T_1 \to M_2, T_2 \to M_4, T_3 \to M_3, T_4 \to M_1, pour 11 heures.
- L’optimum global n’est pas la somme des optima individuels.
La suite
Les chapitres 8 et 9 ont manipulé des réseaux sans jamais les nommer. Le chapitre 10 leur donne un vocabulaire — celui de la théorie des graphes — dont les quatre chapitres suivants vivront.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)