Introduction
Toute entreprise qu’elle que soit sa taille, son domaine d’activité est amenée a
faire face a des problèmes de gestion au quotidien.
Parmi ces problèmes, on cite les problèmes de flot, d’affectation et de transport
qui nécessitent la mise en œuvre d’un procède de prise de décision rationnel,
notamment la recherche operationnelle, a cause de leur niveau de complexite
particulierement eleve et a cause des couts supplementaires qu’ils generent s’ils
sont mal geres.
Ce qui souligne l’importance qu’occupe ce type de probleme dans la gestion
quotidienne de l’entreprise.
C’est pour cette raison que le but de notre travail est de présenter des methodes
faciles de formulation et de résolution de ce genre de problème.
Et pour cela, nous avons divise notre travail en trois parties, ou nous allons
aborder dans un premier temps le probleme de flot et plus precisement le
probleme de flot maximal a cout minimal, et ensuite nous allons presenter le
problème de transport ainsi que des algorithmes de résolution appropries. Et
enfin nous allons traiter les problèmes d’affectation.
Problème de transport
Presentation :
Un problème de transport peut être défini comme l’action de transporter depuis
"m origines" vers "n destinations" des matériaux, au moindre cout.
Donc, la résolution d’un problème de transport consiste à organiser le transport
de façon à minimiser son cout.
Formulation :
= production ou offre
= demande
= quantité transportée
Probleme d’affectation
Presentation :
Il s’agit d’un cas particuliers du problème de transport avec n entrepôts et n
magasins, et ou la demande associée a chaque destination égale a 1.
Le problème consiste a affecter les éléments d’un ensemble a ceux d’un autre
ensemble de sorte que la
somme des couts des
affectations soit minimale.
Formalisation :
Le programme a résoudre est :
xij =1 si i est affecté a j.
xij =0 si i n'est pas affecté a
j.
Cij = cout d’affectation de i a
j.
La methode Hongroise :
Presentation
Cet algorithme repose essentiellement sur la constatation suivante. On ne
change pas la ou les solutions optimales en augmentant ou en diminuant d'une
meme quantite ߣ tous les elements d'une meme ligne (ou d'une meme colonne)
de la matrice des Cij.
Apres une telle operation, la valeur totale est augmentee ou diminuee de ߣ .
Par consequent, si l'on fait apparaitre, par des transformations de ce type,
suffisamment de zeros dans le tableau, mais pas de couts negatifs, et qu'il existe
n zeros "independants" (c'est-a-dire un seul zero dans chaque ligne et dans
chaque colonne), on aura alors trouve l'affectation optimale.
Resolution d’un probleme d’affectation par l’algorithme hongrois :
Afin d'expliquer la demarche suivie, considerons l'exemple suivant :
Soit La societe Beta possedant quatre ateliers : fonte, moulage, laminage et
traitement thermique, qu’on va nommer respectivement F, M, L et T, pour
lesquels elle veut affecter quatre chef de service polyvalents, monsieur A, B, C et
D.
Les couts d’affectation pour chaque liaison sont donnes par le tableau cidessous.
Comment organiser l’affectation de facon a en minimiser le cout?
F M L T
A 60 170 330 360
B 130 200 200 400
C 50 300 170 180
D 120 90 250 200
Première étape :
Réduction des lignes : on crée une nouvelle matrice des coûts en choisissant le
coût minimal sur chaque ligne et en le soustrayant de chaque coût sur la ligne.
Reduit
F M L T
de
A 0 110 270 300 60
B 0 70 70 270 130
C 0 250 120 130 50
D 30 0 160 110 90
Exemple : pour la première ligne (A) :
Relation (A, F) : 60 -60 = 0
Relation (A, M) : 170-60=110
Relation (A, L) : 330-60=270
Relation (A, T) : 360-60=300
Deuxième étape :
Réduction des colonnes : on crée une nouvelle matrice des coûts en choisissant
le coût minimal dans chaque colonne et en le soustrayant de chaque coût dans la
colonne.
F M L T
A 0 110 200 190
B 0 70 0 160
C 0 250 50 20
D 30 0 90 0
Reduit
0 0 70 110
de :
Troisième étape :
Maintenant, il faut déterminer le nombre minimal de lignes
nécessaires sur les lignes et les colonnes pour couvrir tous les zéros.
Si ce nombre est égal au nombre de lignes (ou colonnes), la matrice
est réduite; aller à l’étape 5. Si ce nombre est inférieur au nombre
de lignes (ou colonnes), aller à l’étape 4.
F M L T
A 0 110 200 190
B 0 70 0 160
C 0 250 50 20
D 30 0 90 0
Dans ce cas, le nombre minimal de lignes est de 3 qui est
inférieur au nombre de ligne ou colonne (4), alors on passe à
l’étape 4.
Quatrième étape :
Premièrement, il faut trouver la cellule de valeur minimum
non couverte par une ligne, puis, soustraire cette valeur de
toutes les cellules non couvertes.
Ensuite, ajouter cette valeur aux cellules situées à
l’intersection de deux lignes. Et enfin, retourner à l’étape 3.
F M L T
A 0 110 200 190
B 0 70 0 160
C 0 250 50 20
20
D 30 0 90 0
La valeur minimum des cellules non couvertes est 20.
On soustrait 20 des cellules non couvertes et on l’ajoute aux
cellules qui se trouvent à l’intersection des lignes, ceci nous
donne le tableau suivant :
0 F M L T
A 0 90 180 170
B 20 70 0 160
+2 -20
C 0 230 30 0
0
D 50 0 90 0
Maintenant, le nombre minimal de ligne est égale à 4.
F M L T
A 0 90 180 170
B 20 70 0 160
C 0 230 30 0
D 50 0 90 0
La solution optimale est donc la suivante:
F M L T
A 0 90 180 170
B 20 70 0 160
C 0 230 30 0
D 50 0 90 0
Résultat donné par la méthode Hongroise :
F M L T
A 1
B 1
C 1
D 1
La solution à pour coût :
F M L T
A 60 170 330 360
B 130 200 200 400
C 50 300 170 180
D 120 90 250 200
60 + 200 + 180 + 90 = 530 UM
