Problème d'affectation
Affecter n agents à n tâches au moindre coût : matrice des coûts, modèle biparti, méthode hongroise (réduction des lignes puis des colonnes, couverture des zéros, ajustement) et lecture de l'affectation optimale.
- 26 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Affectation : de quoi s'agit-il ?
Voir la réponse
Choix d'une tâche pour chaque agent, de sorte que chaque agent ait une tâche et que chaque tâche soit prise par un seul agent.
Pour n agents et n tâches, il y a n! affectations possibles. On cherche celle de coût total minimal.
Qu'affiche ce programme ?
```python
from itertools import permutations
cost = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]
print(min(sum(cost[i][p[i]] for i in range(3)) for p in permutations(range(3))))`9101411
Voir la réponse
9Le programme essaie les 3! = 6 affectations. La meilleure : agent 0 sur la tâche 1 (2), agent 1 sur la tâche 0 (6), agent 2 sur la tâche 2 (1), soit 9. Prendre ligne après ligne la case la moins chère dont la tâche est encore libre donnerait 2 + 3 + 5 = 10, et la diagonale 14.
La méthode hongroise commence par soustraire de chaque ligne son …, puis de chaque … son minimum.
Voir la réponse
La méthode hongroise commence par soustraire de chaque ligne son minimum, puis de chaque colonne son minimum.
Chaque ligne et chaque colonne contient alors au moins un zéro, et aucun coût n'est négatif. L'affectation optimale n'a pas changé.
Matrice des coûts : de quoi s'agit-il ?
Voir la réponse
Tableau carré dont la case (i, j) donne le prix d'avoir l'agent i sur la tâche j : une ligne par agent, une colonne par tâche.
Une affectation se lit comme un choix d'une case par ligne et par colonne ; son coût est la somme des cases choisies.