Noms: Matricule :

Sidi Mohamed Lemine Ahmed Henoun C23803

Mariem Brahim Mohamdi Vall C25144

Oum Lkeiri Ahmed Cherif Ahmed Cherif C23945

Introduction au problème de transport :

Le problème de transport est un problème d'optimisation en recherche opérationnelle et

en gestion logistique. Il consiste à déterminer la manière la plus économique de
transporter des marchandises depuis plusieurs sources vers plusieurs destinations, tout
en respectant les contraintes d'offre et de demande. L'objectif est de minimiser le coût
total de transport ou, dans certains cas, de maximiser un profit.

1. Problème :

Un fournisseur de menthe possède 3 fermes situées dans différentes régions de

Mauritanie. Il doit livrer sa récolte à 3 magasins spécialisés dans la vente de thé et
d’accessoires. Chaque ferme a une capacité de production limitée, et chaque
magasin a une demande spécifique en menthe. Le coût de transport dépend de la
distance et des infrastructures

Données du problème :

1. Fermes et leurs capacités de production (en kg)

Fermes Capacité disponible (kg)

Ferme A 150kg
Ferme B 175 kg
Ferme C 275 kg

2. Magasins et leurs demandes (en kg)

Magasins Demande requise

Magasin 1 200 kg
Magasin 2 100 kg
Magasin 3 300 kg
 [Link] de transport (UM/kg) :
Le tableau ci-dessous présente les capacités de production des fermes, la
demande des magasins ainsi que le coût unitaire du transport (en UM/kg) entre
chaque ferme et chaque magasin.

Magasin 1 Magasin 2 Magasin 3 Offre(kg)

Ferme A 6 8 10 150
Ferme B 7 11 11 175
Ferme C 4 5 14 275
Demande (kg) 200 100 300 600⁄
600

2. Modélisation :
a. Variables de décision :
Soit la quantité de menthe transportée de la ferme au magasin :
• 𝑥𝐴,1 est la quantité envoyée de FA à M1
• 𝑥𝐴,2 est la quantité envoyée de FA à M2
• ...
• 𝑥𝐶,3 est la quantité envoyée de FC à M3
b. Fonction Objectif :

𝑀𝑖𝑛 𝑍 = 6𝑥𝐴,1 + 8𝑥𝐴,2 + 10𝑥𝐴,3 + 7𝑥𝐵,1 + 11𝑥𝐵,2 + 11𝑥𝐵,3 + 4𝑥𝐶,1 + 5𝑥𝐶,2 + 14𝑥𝐶,3

c. Contrainte d’intégrité :
• Contraintes d’offre :
Chaque Ferme ne peut pas envoyer plus que sa capacité :
𝑥𝐴,1 + 𝑥𝐴,2 + 𝑥𝐴,3 ≤ 150
𝑥𝐵,1 + 𝑥𝐵,2 + 𝑥𝐵,3 ≤ 175
𝑥𝐶,1 + 𝑥𝐶,2 + 𝑥𝐶,3 ≤ 275
• Contrainte de demande :
Chaque magasin doit recevoir au moins la quantité demandée :
𝑥𝐴,1 + 𝑥𝐵,1 + 𝑥𝐶,1 ≥ 200
𝑥𝐴,2 + 𝑥𝐵,2 + 𝑥𝐶,2 ≥ 100
 𝑥𝐴,3 + 𝑥𝐵,3 + 𝑥𝐶,3 ≥ 300

• Contrainte de positivé :

Toutes les quantités transportées doivent être positives ou nulles

𝑥𝑖𝑗 ≥ 0, ∀𝑖, 𝑗

3. Solution:
A. Méthodes de solution initiale :
a. Méthode du Coin Nord-Ouest :

Dans cette méthode, on commence par la cellule en haut à gauche de la

matrice des coûts, puis on attribue la quantité maximale possible en
fonction de l’offre et de la demande. Ensuite, on se déplace vers la droite ou
vers le bas et on répète le processus jusqu'à ce que toutes les demandes
soient satisfaites.

Magasin 1 Magasin 2 Magasin 3 Offre (kg)

150
Ferme A 8 10 150
6
50 100 25
Ferme B 175
7 11 11
275
Ferme C 4 5 275
14
Demande 600⁄
200 100 300 600
(kg)

Le coût total correspondant à cette solution est de 6125 UM

(150 × 6 + 50 × 7 + 100 × 11 + 25 × 11 + 250 × 14)
La méthode du coin Nord-Ouest est facile à appliquer et ne nécessite aucun
calcul complexe. Cependant, elle ne prend pas en compte les coûts de
transport, ce qui peut entraîner une solution initiale avec un coût total élevé.
C’est une approche rapide pour obtenir une solution de départ, mais elle
doit souvent être améliorée avec d’autres techniques d’optimisation.

b. Méthode de l'Indice de Coût Minimum :

 Dans cette méthode, on commence par identifier la cellule ayant le coût le
plus bas dans la matrice des coûts. Ensuite, on attribue à cette cellule la
quantité maximale possible en fonction de l'offre et de la demande. Après
cela, on ajuste l'offre et la demande en éliminant la ligne ou la colonne
concernée si l'une des deux est totalement satisfaite. On répète ensuite le
processus en recherchant la cellule avec le coût le plus bas parmi les
Cellules restantes, jusqu'à ce que toutes les demandes soient remplies.

Magasin 1 Magasin 2 Magasin 3 Offre (kg)

25 125
Ferme A 150
6 8 10
175
Ferme B 175
7 11 11
200 75
Ferme C 275
4 5 14
Demande 600⁄
200 100 300 600
(kg)

Le coût total correspondant à cette solution est de 4550 UM

(200 × 4 + 25 × 8 + 75 × 5 + 125 × 10 + 175 × 11)

La méthode du coût minimum est simple et permet de minimiser les coûts

de transport dès le début en affectant les quantités aux cellules à coût le
plus bas. Bien qu'elle offre une solution rapide, elle ne garantit pas une
solution optimale et nécessite souvent des techniques d'optimisation
supplémentaires pour améliorer les résultats.

B. Methode d’optimisation :
a. Methode du Stepping-Stone:

Après avoir trouvé une solution initiale (par exemple, avec la méthode du
coût minimum), la méthode du Stepping-Stone est utilisée pour l'optimiser

Dans cette méthode, on commence par identifier les cellules de base (celles
qui ont reçu une allocation) et les cellules non de base (celles sans
allocation). Ensuite, pour chaque cellule non de base, on crée une boucle
fermée qui commence et se termine à cette cellule, en passant uniquement
par des cellules de base avec des mouvements horizontaux et verticaux. On
attribue des signes “+” et “-” aux cellules de la boucle en commençant par
un “+” pour la cellule non de base et en alternant les signes pour les cellules
de base. Enfin, on calcule le coût d'opportunité en utilisant la formule :𝐶𝐷 =
Σ(𝑐𝑜𝑢𝑡 𝑑𝑒𝑠 𝑐𝑒𝑙𝑙𝑢𝑙𝑒𝑠 𝑎𝑣𝑒𝑐 𝑠𝑖𝑔𝑛𝑒 +) − Σ(𝐶𝑜𝑢𝑡 𝑑𝑒𝑠 𝑐𝑒𝑙𝑙𝑒𝑙𝑒𝑠 𝑎𝑣𝑒𝑐 𝑠𝑖𝑔𝑛𝑒 −).
Si le coût d'opportunité est négatif, l'allocation à cette cellule réduit le coût
total

Magasin 1 Magasin 2 Magasin 3 Offre (kg)

25
8 125
Ferme A 6 - 150
10
+

175
Ferme B 175
7 11 11

- +
Ferme C 275
200 75 14
4 5
Demande 600⁄
200 100 300 600
(kg)

(Après avoir identifié la première cellule non de base, je trace son chemin
fermé dans le tableau.)
Calcul des coûts d'opportunité pour les cellules :
𝐶𝑒𝑙𝑙 𝑋11 = 6 − 8 + 5 − 4 = −1 (!)
𝐶𝑒𝑙𝑙 𝑋21 = 7 − 11 + 10 − 8 + 5 − 4 = −1 (!)
𝐶𝑒𝑙𝑙 𝑋22 = 11 − 11 + 10 − 8 = 2
𝐶𝑒𝑙𝑙 𝑋33 = 14 − 10 + 8 − 5 = 7

Tant qu'on trouve qu'un des coûts des cellules est négatif(𝑋11 𝑜𝑢 𝑋21), le
processus continue afin d'ajuster les affectations et optimiser le coût total.
En cherchant à réduire davantage les coûts tout en respectant les
contraintes

Magasin 1 Magasin 2 Magasin 3 Offre (kg)

25 125
Ferme A 150
6 8 10
175
Ferme B 175
7 11 11
Ferme C 175 100 275
 4 5 14
Demande 600⁄
200 100 300 600
(kg)

Calcul des coûts d'opportunité pour les cellules :

𝐶𝑒𝑙𝑙 𝑋12 = 8 − 5 + 4 − 6 = 1
𝐶𝑒𝑙𝑙 𝑋21 = 7 − 6 + 10 − 11 = 0
𝐶𝑒𝑙𝑙 𝑋22 = 11 − 11 + 10 − 6 + 4 − 5 = 3
𝐶𝑒𝑙𝑙 𝑋33 = 14 − 10 + 6 − 4 + 5 = 11

Le tableau est maintenant minimal car tous les coûts des cellules sont
positifs ou nuls. Cela signifie qu'il n'y a plus d'opportunités d'optimisation, et
le coût total ne peut plus être réduit. La solution est donc optimale

Le coût total correspondant à cette solution est de 4525 UM

C. Résolution avec Cplex studio IDE:

• Préparation du modèle dans CPLEX:
Pour résoudre le problème de transport avec CPLEX, nous avons traduit le
modèle mathématique (2. Modelisation) en syntaxe CPLEX. Voici le code
complet que nous avons sauvegardé dans un fichier appelé [Link]
• Exécution du modèle et résultats :
Après avoir sauvegardé le code dans le fichier [Link], nous l'avons
exécuté dans CPLEX Studio IDE. Voici les résultats obtenus après
l'exécution :
Le coût total minimal calculé par CPLEX est 4525 UM

(Cette valeur est identique à celle que nous avons trouvée en utilisant la
méthode de Stepping-Stone, ce qui confirme l’exactitude de notre solution)