Projet de Recherche Opérationnelle
Problème de Transport
Oussama Beyah
Matricule : C23785
1. Présentation générale du problème de transport
Le problème de transport est un problème classique en recherche opérationnelle. Il
s'agit de déterminer comment transporter des marchandises depuis plusieurs entrepôts
vers plusieurs destinations, de manière à satisfaire la demande de chaque destination,
tout en minimisant le coût total de transport et en respectant les capacités de chaque
entrepôt.
Dans notre cas, nous considérons un système composé de trois entrepôts : S1, S2 et S3,
et de trois destinations : D1, D2 et D3. Chaque entrepôt dispose d'une certaine quantité
de produit (ore), et chaque destination a besoin d'une certaine quantité (demande).
Structure du système et exibilité des échanges
Chaque entrepôt a la possibilité de livrer à n'importe quelle destination, et chaque des-
tination peut être approvisionnée par un ou plusieurs entrepôts. Cela permet une grande
exibilité dans l'organisation du transport. On ne cherche pas à attribuer chaque desti-
nation à un seul entrepôt, mais à permettre une répartition optimale des marchandises
selon les coûts de transport et les quantités disponibles.
Par exemple :
S1 dispose de 30 unités à distribuer,
S2 dispose de 40 unités,
S3 dispose de 20 unités,
D1 demande 20 unités,
D2 demande 30 unités,
D3 demande 40 unités.
Imaginons maintenant que le coût de transport entre S1 et D3 soit très faible (par
exemple 1), tandis que le transport entre S2 et D3 soit très coûteux (par exemple 7). Dans
ce cas, il serait préférable, d'un point de vue économique, d'envoyer les marchandises de
D3 depuis S1 et S3, plutôt que depuis S2.
De même, si D2 demande 30 unités, et que S1 ne peut fournir que 10 unités, alors les
20 unités restantes doivent être envoyées depuis S2. Cela montre qu'une destination peut,
pour des raisons de limitation d'ore ou de réduction de coût, être servie par plusieurs
entrepôts à la fois.
1
Vision réseau du problème
Ce problème peut être représenté sous forme d'un réseau, où chaque entrepôt est
connecté à chaque destination par un arc de transport. Cela génère un total de 9 chemins
possibles : de S1 à D1, D2, D3; de S2 à D1, D2, D3; de S3 à D1, D2, D3. Le but du
modèle est de choisir combien transporter sur chaque chemin de manière à :
respecter les quantités disponibles dans chaque entrepôt,
satisfaire la demande de chaque destination,
minimiser le coût global de transport.
Par exemple, dans une solution optimale possible :
S1 envoie 10 unités à D2 et 20 unités à D3,
S2 envoie 20 unités à D1 et 20 unités à D2,
S3 envoie 20 unités à D3.
2. Modélisation mathématique détaillée
Variables de décision
Soit x la quantité transportée de l'entrepôt S vers la destination D , où :
ij i j
x : quantité envoyée de S1 vers D1
x : quantité envoyée de S1 vers D2
11
x : quantité envoyée de S1 vers D3
12
x : quantité envoyée de S2 vers D1
13
x : quantité envoyée de S2 vers D2
21
x : quantité envoyée de S2 vers D3
22
x : quantité envoyée de S3 vers D1
23
x : quantité envoyée de S3 vers D2
31
x : quantité envoyée de S3 vers D3
32
33
Données du problème
Ores :
S1 : 30 unités
S2 : 40 unités
S3 : 20 unités
Demandes :
D1 : 20 unités
D2 : 30 unités
D3 : 40 unités
Coûts unitaires : D1 D2 D3
S1 2 3 1
S2 5 4 7
S3 3 6 2
2
Formulation du programme linéaire
Objectif : Minimiser le coût total :
min Z = 2x11 + 3x12 + 1x13 + 5x21 + 4x22 + 7x23 + 3x31 + 6x32 + 2x33
Contraintes :
Ores des entrepôts :
x11 + x12 + x13 ≤ 30 (S1)
x21 + x22 + x23 ≤ 40 (S2)
x31 + x32 + x33 ≤ 20 (S3)
Demandes des destinations :
x11 + x21 + x31 = 20 (D1)
x12 + x22 + x32 = 30 (D2)
x13 + x23 + x33 = 40 (D3)
Contraintes de positivité :
xij ≥ 0 pour tout i ∈ {1, 2, 3}, j ∈ {1, 2, 3}
3. Résolution avec Python (PuLP)
import pulp
sources = [ 'S1 ' , ' S2 ' , 'S3 ']
destinations = [ ' D1 ', 'D2 ', 'D3 ']
offres = { 'S1 ': 30 , 'S2 ': 40 , 'S3 ': 20}
demandes = { ' D1 ': 20 , ' D2 ': 30 , 'D3 ': 40}
couts = {
( 'S1 ' , ' D1 ') : 2, ( ' S1 ' , 'D2 '): 3, ( 'S1 ', 'D3 '): 1,
( 'S2 ' , ' D1 ') : 5, ( ' S2 ' , 'D2 '): 4, ( 'S2 ', 'D3 '): 7,
( 'S3 ' , ' D1 ') : 3, ( ' S3 ' , 'D2 '): 6, ( 'S3 ', 'D3 '): 2,
}
model = pulp . LpProblem (" Probleme_de_transport " , pulp . LpMinimize )
x = pulp . LpVariable . dicts ("x " , couts , lowBound =0 , cat = ' Continuous ')
model += pulp . lpSum ( couts [i , j] * x [i , j] for (i , j) in couts )
for i in sources :
model += pulp . lpSum (x [i , j] for j in destinations ) <= offres [i]
for j in destinations :
model += pulp . lpSum (x [i , j] for i in sources ) == demandes [j]
model . solve ()
for (i , j ) in x:
print (f " Quantite de { i} vers {j } : { x[i ,j ]. varValue }")
print (f "\ nCout total minimum : { pulp . value ( model . objective ) }")
3
4. Résultats obtenus
Quantité de S1 vers D1 : 0 unité
Quantité de S1 vers D2 : 10 unités
Quantité de S1 vers D3 : 20 unités
Quantité de S2 vers D1 : 20 unités
Quantité de S2 vers D2 : 20 unités
Quantité de S2 vers D3 : 0 unité
Quantité de S3 vers D1 : 0 unité
Quantité de S3 vers D2 : 0 unité
Quantité de S3 vers D3 : 20 unités
Coût total minimum : 310
5. Interprétation et conclusion
La solution optimale montre une répartition e cace entre les entrepôts. Chaque des-
tination est approvisionnée en totalité, et les quantités envoyées respectent les limites
d'ore de chaque entrepôt. Les chemins de transport ont été choisis en fonction des coûts
les plus faibles, ce qui permet d'obtenir un coût total minimum de 310. Ce modèle peut
donc être utilisé dans des situations réelles pour aider à prendre des décisions logistiques
optimales dans un réseau de distribution.
