««««««««« «««««
ANNEE UNIVERSITAIRE: 2021/2022
SOLVEUR DE PROBLEME DE
TRANSPORT
Projet en Supply Chain Management
Encadré par :
M. AKIL Said
Réalisé par :
- KARAM Souhail
- FARJIA Taha
- BOUHMIDI Razan
Zainab
Introduction :
Le problème du transport est un programme linéaire qui a une structure particulière. Cette classe
de PLs englobe les problèmes qui s'énoncent dans une forme approximative à celle-ci : Il y a m origines et
n destinations, dans chaque origine on dispose d'une certaine quantité de matières premières (ou produit
donné), et dans chaque destination on demande une certaine quantité de ce produit. Le coût de transport
est différent pour chaque couple origine-destination. On cherche un plan de transport optimal dans le
sens qu'il minimise le coût total de transport.
L'usage des tableaux de simplexe dans le cas des problèmes de transport est bien entendu possible.
Toutefois, cette alternative ne présente pas un réel intérêt pratique car les problèmes de transport
aboutissent généralement à un grand nombre de variables et de contraintes. Heureusement, une
représentation intuitive et permettant un traitement facile des problèmes de transport existe : il s'agit du
tableau de transport.
Résolution du Problème de transport
Pendant tout le déroulement de ce rapport nous traiterons comme exemple le premier exercice du td :
PARTIE 1 : calcul classique
La méthode du Nord-Ouest :
Partir du coin supérieur gauche du tableau.
1. allouer le plus possible à la cellule courante et ajuster l’offre et la demande.
2. se déplacer d’une cellule vers la droite (demande nulle) ou le bas (offre nulle).
3. répéter jusqu’au moment où toute l’offre est allouée.
D1 D2 D3 D4 D5 S
S1 10 6 3 5 25 49
S2 5 2 6 12 5 30
D 15 20 5 25 14
On satisfait la demande de la première destination.
On affecte 15 unités à D1 depuis S1.
D2 D3 D4 D5 S
S1 6 3 5 25 34
S2 2 6 12 5 30
D 20 5 25 14
On affecte 20 unités à D2 depuis S1.
D3 D4 D5 S
S1 3 5 25 14
S2 6 12 5 30
D 5 25 14
On affecte 5 unités à D3 depuis S1.
D4 D5 S
S1 5 25 9
S2 12 5 30
D 25 14
On affecte 9 unités à D4 depuis S1.
D4 D5 S
S2 12 5 30
D 16 14
On affecte 12 unités à D4 depuis S2.
D4 D5 S
S2 12 5 30
D 16 14
On affecte 14 unités à D5 depuis S2.
Le cout totale = 592
Moindres coûts :
Sélectionner la cellule de coût minimum :
1. allouer le plus possible à la cellule courante et ajuster l’offre et la demande.
2. sélectionner la cellule de coût minimum ayant une demande et une offre non nulles.
3. répéter jusqu’au moment où toute l’offre est allouée.
Exemple :
D1 D2 D3 D4 D5 S
S1 10 6 3 5 25 49
S2 5 2 6 12 5 30
D 15 20 5 25 14
Cm=2. Cout minimal de j(k,l)=(2,2).
a2=30, b2=20, a2 > b2.
Donc : a1=a2-b2=10.
On affecte 20 unité à la destination D2 depuis la source S2.
D1 D3 D4 D5 S
S1 10 3 5 25 49
S2 5 6 12 5 10
D 15 5 25 14
Cm=3. Cout minimal de j(k,l)=(1,3).
a1=49, D3=5, a2 > b2.
Donc : a1=49-5=44.
On affecte 5 unité à la destination D3 depuis la source S1.
D1 D4 D5 S
S1 10 5 25 44
S2 5 12 5 10
D 15 25 14
Cm=5. Cout minimal de j(k,l)=(2,1).
a1=49, a2 < b1.
Donc : b1=b1-a2=5.
On affecte 15 unité à la destination D1 depuis la source S2.
D1 D4 D5 S
S1 10 5 25 44
D 15 25 14
Cm=5. Cout minimal de j(k,l)=(1,4).
a1=44-25=19.
On affecte 5 unité à la destination D1 depuis la source S1.
D1 D5 S
S1 10 25 19
D 15 14
On affecte 14 unité à la destination D5 depuis la source S1.
Le cout totale = 630
Méthode de BALAS – HAMMER ou bien regret maximal :
L’algorithme de Balas-Hammer :
∆l représente la différence entre le coût minimum et celui immédiatement supérieur sur une ligne.
∆c représente la différence entre le coût minimum et celui immédiatement supérieur sur une colonne.
1- Calculer les différences ∆l et ∆c pour chaque ligne et colonne.
2- Sélectionner la ligne ou la colonne ayant le ∆l ou ∆c maximum.
3- Choisir dans cette ligne ou colonne le coût le plus faible.
4- Attribuer à la relation (i, j) correspondante le maximum possible de matière transportable de
façon à saturer soit la destination soit la disponibilité.
5- Calculer la quantité résiduelle soit demande soit en disponibilité.
6- Eliminer la ligne ou la colonne ayant sa disponibilité ou demande satisfaite.
7- SI nombre de lignes ou colonnes> 2 retour en 2. SINON affecter les quantités restantes aux
liaisons.
Exemple :
D1 D2 D3 D4 D5 R S
S1 10 6 3 5 25 2 49
S2 5 2 6 12 5 3 30
D 15 20 5 25 14
Rmax=20.
Cmin=5.
A2=b2-b5=30-14=16.
D1 D2 D3 D4 R S
S1 10 6 3 5 2 49
S2 5 2 6 12 3 16
D 15 20 5 25
Rmax=7
Cmin=5.
a1=a1-b4=49-25=24.
D1 D2 D3 R S
S1 10 6 3 2 24
S2 5 2 6 3 16
D 15 20 5
Rmax=5.
Cmin=5.
a2=a2-b1=16-15=1.
D2 D3 R S
S1 6 3 2 24
S2 2 6 3 1
D 20 5
Rmax=4.
Cmin=2.
b2=4-1=3.
D2 D3 R S
S1 6 3 2 24
D 19 5
Le cout totale = 401
(la solution optimale)
PARTIE 2 : calcul réalisé par le solveur
Nous avons développé une application nous permettant de résoudre n’importe quel problème
de transport.
Présentation de l’application :
Interface de l’application :
L’interface contient une première section qui nous permet de choisir une des trois méthodes
(cout minimal, nord-ouest ou regret maximal)
Une deuxième qui nous permet de choisir le nombre de sources et de destinations
Une troisième contenant un bouton « entrer les données » nous permettant d’insérer le cout de
chaque couple (source, destination). Ainsi qu’un bouton « Go » qui permet de débuter le
process
Une dernière qui affiche le cout total de transport
Code :
La méthode du Nord-Ouest :
Moindres coûts :
Méthode de BALAS – HAMMER ou bien regret maximal :
Démonstration par l’exemple traité au paravent :
On insère le nombre de sources et le nombre de colonnes
On appuie en suite sur le bouton « Enter les données » pour remplir le tableau
La méthode du Nord-Ouest :
Le cout totale = 592
Une table EXCEL est créé automatique après avoir cliquer sur le bouton « Go », nous permettant de
visualiser toute les itérations
(Pour ne pas encombrer le rapport on n’affichera que les itérations des méthodes nord-ouest et regret
maximal)
Itérations :
Méthode de BALAS – HAMMER ou bien regret maximal :
Le cout totale = 401
(la solution optimale)
Itérations :
Moindres coûts :
Le cout totale =630
