Chapitre 4 : Problème d'affectation
: Introduction .1
Le problème d'affectation est un cas particulier de la programmation linéaire. Il s'agit
d'un cas classique dont le schéma peut être fourni par l'exemple suivant :
Soient n ouvriers et n postes Pour toute
affectation est attachée une valeur i, j=1, 2, …, n (coût).
Il s'agit d'affecter les ouvriers aux n postes de manière que touts les ouvriers aient
chacun un poste et un seul de telle sorte que la valeur (coût) total des affectations soit
minimale.
La formulation mathématique est la suivante :
: Exemple
Avant d'exposer la principale méthode pour résoudre de tels problèmes, donnons un 76
exemple réel d'un problème d'affectation.
Il s'agit d'un réseau de transport aérien d'une compagnie aérienne internationale.
On se propose de rechercher les frais de déplacement des équipages.
Mohammed Berrajaa | Recherche Opérationnelle
Définissons d'abord le problème des équipages entre deux villes. Soient deux villes A
et B reliées par une ligne aérienne directe (A vers B et B vers A). Supposons qu'on
dispose de trois équipes et que chaque jours, trois avions partent de A vers B et soient
1, 2, 3 les numéros respectifs des vols de A vers B ; soient a, b, c les numéros
respectifs des vols de B vers A.
On connaît évidemment les heures de départs et d’arrivées ; la durée des vols entre
deux villes est connue, uniforme et constante.
Le problème élémentaire qui se propose ici est le suivant :
Comment minimiser le temps passé par les équipages hors de leur domicile (il
intervient sur les plans tant financiers que psychologique), sachant que tout équipage
qui loge en A et part de A vers B doit revenir en A pour terminer sa mission ; de
même pour tout équipage de B.
Ainsi, on peut imaginer diverses dispositions ; par exemple :
La solution 1b, 2a, 3c pour ceux qui partiraient de A et a3, b1, c2 pour ceux qui
partiraient de B.
Il faut choisir la meilleure disposition
Donnons un exemple numérique pour fixer les idées.
)Durée uniforme des vols est 6 heures(
Pour résoudre le problème, on forme deux tableaux, l'un avec tous les équipages
supposés logés dans A, l'autre avec tous les équipages supposés logés dans B ; le
nombre représentant les temps d'absence du domicile. (On suppose que chaque
équipage arrivant à une destination repartira par le premier vol disponible).
76
Mohammed Berrajaa | Recherche Opérationnelle
a b c a b c a b c
1 29 34 16 1 31 26 20 1 29 26 16
2 22 27 33 2 14 33 27 2 14 27 27
3 14 19 25 3 22 17 35 3 14 17 25
Équipages logés en A Équipages logés en B Intervalles de temps les plus couts
courts
On formera ensuite un nouveau tableau issu des deux précédents, en choisissant dans
chaque case le plus petit nombre des deux tableaux.
Enfin, appliquons le programme (P) et choisissons un nombre dans chaque colonne
pour une ligne différente de telle sorte que la somme des nombres soit minimale. On
peut former 3! =6 combinaisons distincts.
Ainsi, le plus favorable est celui qui aboutit à 47 h.
Soient a2, b3 et 1c .Donc deux équipages logeront en B et un équipage en A.
Nous venons de résoudre un problème d'affectation facile comme on l'a vu pour deux
villes, six vols et trois équipages, il devient très compliqué et difficile dés que ces
nombres sont plus élevés. On note qu’avec n équipage on peut former n!
Permutations.
Ainsi, avec 20 équipages, il faudrait calculer permutations ;
c'est à dire quelques siècles pour de bons calculateurs, alors que l'algorithme hongrois 76
exploité sur ordinateur peut fournir le résultat cherché en quelques minutes.
Le problème réel qui a été étudié comprenait 13 villes, 60 liaisons et 400 vols (par la
méthode hongroise). La solution optimale a permis de réaliser une économie de 18%
Mohammed Berrajaa | Recherche Opérationnelle
sur la solution intuitive. Cette économie représentait prés de 150 millions de dirhams
par an, d’où l'intérêt économique de telles méthodes.
: Méthode hongroise .3
Algorithme hongrois
Réduire M;
TANT QU’on peut affecter n zéros, un par ligne et un par
colonne
Affecter le plus possible de zéros
(Au plus un par ligne et par colonne);
Marquer toutes les lignes sans zéro affecté ;
TANT QU'on peut marquer quelques choses
Marquer les colonnes ayant un zéro non affecte dans une ligne
marquée
Marquer les lignes ayant un zéro affecte fans une colonne
marquée ;
FIN TANT QUE
Soit r le plus petit nombre à colonne non marquée et ligne
marquée
Soustraire r de chaque ligne marquée
Ajouter r à chaque colonne marquée
Réduire M
FIN TANT QUE
Tout problème d'affectation peut, en général se résumer sous la forme d'un tableau de
coût, dans lequel il s'agit de choisir un élément et un seul par ligne et par colonne, de 76
manière à obtenir la somme initiale.
La méthode hongroise se divise en cinq phases.
Mohammed Berrajaa | Recherche Opérationnelle
Phase 1 : Obtention des zéros
A tous les éléments d'une même colonne on enlève le plus petit élément de la colonne ; on
fait de même pour les lignes.
Notons qu'on ne change pas le problème en appliquant la phase 1, en effet
17.5 15 9 5.5 12
16 16.5 10.5 5 10.5
]Cij[ 12 15.5 14.5 11 5.5
4.5 8 14 17.5 13
13 9.5 8.5 12 17.5
12.5 6.5 0 0 6 13 7 0.5 0.5 6.5
11.5 8.5 2 0 5 11.5 8.5 2 0 5
~ 7.5
0
7.5
0
6
5.5
6
12.5
0
7.5
7.5
0
7.5
0
6
5.5
6
12.5
0
7.5
8.5 1.5 0 7 12 8.5 1.5 0 7 12
Phase 2 : recherche d'une solution optimale
Avec le tableau obtenu, on cherche à former une bijection pour laquelle le coût total
aient une valeur nulle : elle ne doit contenir que des zéros.
Si cela est possible, on a trouvé une solution optimale sinon on passe à la phase 3.
On cherche d'abord la ligne ou une des lignes comptant le moins de zéros ; on encadre
un des zéros de cette ligne, puis on barre les zéros qui se trouvent sur la même ligne ou
dans la même colonne que le zéro encadré.
Parmi les lignes restantes, on cherche alors celle ou l'une de celles qui contient le moins
de zéros et on répète le même processus. On procède ainsi jusqu’à ce qu'on ne puisse
plus encadré de zéros. 76
Mohammed Berrajaa | Recherche Opérationnelle
12,5
6.5 0 6
11,5 8.5 2 0 5
7.5 7.5 6 6
0 5.5 12,5 7.5
8,5 1,5 0 7 12
Phase 3 : Recherche des lignes et colonnes en nombre minimal contenant tous les
zéros.
On opère pas à pas comme suit :
a) marquer d'une croix (x) toutes les lignes qui ne contiennent aucun zéro encadré
b) marquer d'une croix (x) toute colonne qui a un zéro barré sur une ou plusieurs
lignes marquée.
c) marquer d'une croix (x) toute ligne qui a un zéro encadré dans une colonne
marquée
d) répéter b) et c) jusqu'il n'y ait plus de colonne ou ligne à marquer.
On trace alors un trait sur toute ligne non marquée et d'un trait sur toute colonne
marquée.
On obtient ainsi les lignes et colonnes en nombre minimal qui contiennent tous les
zéros encadrés ou barrés.
X X
12.5 6.5 X 0 6
11.5 8.5 2 X 5
7.5 7.5 6 6
0 5.5 12.5 7.5
X
8.5 1.5 0 7 12
Phase 4 : Déplacement de certain zéros.
Les cases non traversées par un trait constituent un tableau partiel 76
On retranche à toutes les cases de ce tableau partiel le plus petit élément de celui-ci
On ajoute ce même élément à toutes les cases du tableau initial barrées deux fois
Mohammed Berrajaa | Recherche Opérationnelle
On obtient alors un nouveau tableau sur lequel on pourra répéter la succession des
étapes 1 à 3
On prend le plus petit nombre du tableau partiel dont les éléments ne sont traversés
par aucun trait. On enlève ces nombres aux éléments des colonnes non traversées par
un trait et on l'ajoute à ceux des lignes traversées par un double trait
11 5 0 0 4.5
10 7 2 0 3.5
7.5 7.5 7.5 7.5 0
0 0 7 14 7.5
7 0 0 7 10.5
Phase 5 : Obtention da la solution optimale
Sur le nouveau tableau obtenu en phase 4, on cherche une solution optimale selon la
méthode de la phase 2. Si on n'obtient pas une solution optimale, on continue les
opérations 3 et 4 et ainsi de suite …
1 2 3 4 5
1 11 5 0 4.5
2 10 7 2 3.5
3 7.5 7.5 7.5 7.5
0
4 0 5.5 14 7.5 76
5 7 0 7 10.5
Mohammed Berrajaa | Recherche Opérationnelle
: Ici la solution est
: Recherche d'un maximum )4
Dans certains problèmes d'affectation, on se propose de rechercher l'affectation
: donnant le maximum de la fonction économique. On opère de la façon suivante
: Posons )1
: Il est évident que (xij) est solution du programme )2
: Si et seulement si est la solution du programme
76
Mohammed Berrajaa | Recherche Opérationnelle
76
Mohammed Berrajaa | Recherche Opérationnelle