C.N.A.M.

GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

PROGRAMMES DE TRANSPORT
Présentation

Plusieurs fournisseurs disposent de stocks connus d’une même marchandise . Plusieurs

clients ont passé commande de quantités (connues) de cette marchandise

A chaque déplacement fournisseur-client correspond un coût de transport unitaire

( par ex : en Euros par tonne), qui peut être proportionnel à la distance entre ce client et
ce fournisseur . Mais ce coût dépend souvent d'autres facteurs, tels que les moyens de
transport, les difficultés de circulation routière à proximité des grandes villes ou dans les
régions difficiles d'accès. Dans la suite, on suppose que ces coûts unitaires de transport
ont été déjà évalués.

Les données du problème sont le stock de chaque fournisseur (noté ai : pour

le fournisseur i, i=1 à m) , la demande de chacun des clients (noté bj pour le client j, j =
1 à n ) et les coûts unitaires de transport (cij pour le transport d’une tonne du fournisseur
i vers le client j).

Les hypothèses sont les suivantes :

- les clients peuvent être approvisionnés par plusieurs fournisseurs,
- l'ensemble des stocks des fournisseurs représentant le stock total disponible
doit être égal à la demande globale de tous les clients :
-
Σ ai = Σ bj.
.i=1 à n j= 1 à n

Remarque : en cas de déséquilibre entre le stock total A et la demande globale B, on

peut créer , soit un client fictif ( si A > B), ou un fournisseur fictif (si A< B) et se ramener
au cas précédent où l’offre globale égale la demande globale.

Exemple de réseau de distribution :

Des commandes d’une marchandise X ont été passées n=6 clients avec m=3
fournisseurs . Rappelons qu’on a noté ai les stocks respectifs des trois fournisseurs et
bj les demandes respectives du la marchandise X pour chacun des clients j.
On a ici : i = 1, 2, 3 ; j = 1, 2, 3, 4, 5, 6

Page 1 sur 1 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Un plan de transport décrivant les quantités x ij , livrées du fournisseur ‘i‘ au

client ‘j’ qui minimise le coût total est à déterminer. Chaque coût de transport unitaire
d'un fournisseur ‘i’ vers un client ’j ‘e st , nous l’avons dit, fixé et connu. Le stock
global (offre globale) des trois fournisseurs correspond à la demande totale des clients .

Réseau de distribution:

Le réseau de distribution peut être représenté graphiquement :

Les coûts de transport unitaires entre fournisseurs F et clients C sont
indiqués sous forme de tableau ( à double entrée ).
C2
C1
F2

C4
F1
C3

C6
C5 F3

Matrice des coûts :

Clients’ j ‘ stock
1 2 3 4 5 6

I C11 C12 C13 C14 C15 C16 .a1

Fournisseurs II .a2
C21 C22 C23 C24 C25 C26
‘i’
III C31 C32 C33 C34 C35 C36 .a3

Demandes b1 b2 b3 b4 b5 b6

Page 2 sur 2 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

On a noté x ij le quantité à livrer au client ’i’ depuis le fournisseur ’j’. Les quantités
sont est à déterminer sous les conditions suivantes :

- La somme des quantités livrées à chaque client par chacun des fournisseurs
doit être égale au stock disponible de ce fournisseur. Le système de trois
équations peut s'écrire :
.x11+ x12+ x13+ x14+ x15+ x16 = a 1
x21+ x22+ x23+ x24+ x25+x26 = a 2
x31 + x32 + x33+ x34 +x35+x36 = a 3
6
soit en bref : ∑ xij = ai pour i = 1 à 3
j=1

La somme des quantités livrées par le client doit être égale à la demande
de chacun des clients. D'où les six équations suivantes :

3
en bref : ∑ xij= bj pour j = 1 à 6
i=1

- La fonction objectif (ou économique) de coût est à minimiser. Elle s’écrit :

Z=(c 11x11+c12 x12 + ...+c16 x16) +( c21x21 +c22 x22+ ...+c26 x26) + (c 31 x31 + c32 x32
+...+c36 x36 )

Qui traduit bien que l'objectif de ce programme de transport consiste à déterminer

les quantités à livrer à chaque client depuis chaque fournisseur, de façon à obtenir un
coût global de transport minimal..

La résolution se déroule en deux phases ; d’abord la construction

d’une bonne ‘solution ‘ de base , puis l’optimiser l’optimisation de cette solution de
base .

Page 3 sur 3 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

PROGRAMME DE TRANSPORT

RECHERCHE D'UNE SOLUTION DE BASE

Cette méthode consiste à déterminer une solution initiale du problème , en calculant une
première répartition des quantités à livrer aux clients depuis les fournisseurs.
Cette solution de base sera optimisée par la suite (en seconde phase) par la
méthode d'optimisation dite du "Stepping Stone".

Exemple :

Soit un exemple avec m=2 dépôts et n=5 clients à livrer.

La matrice des coûts unitaires de transport est la suivante :

Clients
j 1 2 3 4 5 ai

i
Dépôts 1 10 6 3 5 25 49 Stocks des
2 5 2 6 12 5 30 fournisseurs

Demandes bj 15 20 5 25 14
des clients

Les stocks des deux dépôts (fournisseurs) sont 49 et de 30 tonnes. Les

demandes respectives de chaque client sont de 15, 20, 5, 25, et 14 tonnes
La demande totale et le stock total disponible sont égaux à 79 unités .Donc le
problème est équilibré ( il n’y a besoin de créer un client fictif ou un dépôt fictif).

Page 4 sur 4 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Nous présentons ci-dessous plusieurs méthodes pour obtenir des solutions de base.

1. METHODE DU COIN NORD-OUEST :

Il s’agit d’une méthode rapide, mais qui ne tient pas compte du tableau des coûts ; c’est
pourquoi la solution initiale qu’elle fournit peut être éloignée de l’optimum.

- En se plaçant au coin nord-ouest du tableau des coûts c’est- à -dire à la

case (1,1) ,on voit que toute la demande du client 1 peut être livrée depuis
dépôt 1 car :
a1> b1 soit x11= b1 = 15 tonnes .
On ″sature″ alors la colonne ‘1’, puis la demande résiduelle du client ‘1’ est nulle.
Et note que l’offre résiduelle du dépôt ‘1’ est de : 49 – 15 = 34 tonnes.

Clients
j 1 2 3 4 5
i
Dépôts 1 15 (49) 34 Stocks
2 0 30

Demandes (15) 20 5 25 14
0
N.B : Si la commande ‘b1 ‘du client 1 avait été supérieure au stock ‘a1’ , on aurait posé
x11 = a1 et la demande résiduelle du client ‘1’ aurait été serait égale à b1-a1 ; dans ce
cas, c’est la ligne 1 qui aurait été saturée.

- Puis, pour la case de droite suivante (associée au couple dépôt1,client2 ), la

demande totale (20) est affectée au dépôt 1 car le stock résiduel du dépôt 1 (34) est
supérieur à la demande du client 2 (20) . La colonne 2 est saturée. Et on poursuit
avec la case suivante à droite et ainsi de suite, de gauche à droite du tableau , dans la
ligne 1, jusqu’à épuisement du stock du dépôt 1.
Clients
1 2 3 4 5
Dépôts 1 15 20 (49) (34) 14 Stocks
Page 5 sur 5 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

2 0 0 30 résiduels

Demandes (15) (20) 5 25 14

résiduelles 0 0

Clients
1 2 3 4 5
Dépôts 1 15 20 5 (49) (34) (14) 9 Stocks
2 0 0 0 30

Demandes (15) (20) (5) 25 14

0 0 0

- à ce stade le stock résiduel du dépôt 1 (9) est inférieur à la commande du client 4 (25) :
on va livrer 9 tonnes du dépôt 1 vers le client 4 , le reste (16 tonnes) sera livré
ultérieurement à partir d’un autre dépôt .
Clients
1 2 3 4 5
Dépôts 1 15 20 5 9 0 (49) (34) (14) (9) 0 Stocks
2 0 0 0 30

Demandes (15) (20) (5) (25) 14

0 0 0 16
- Au bout de la quatrième itération, on voit que la ligne 1 est saturée (le stock du
dépôt 1 désormais épuisé (0) ) . Aussi il n’y aura pas de livraison du dépôt 1 vers le
client 5, et x 15 = 0.
Ensuite, on passe au dépôt suivant, donc à la ligne immédiatement au dessous,
en commençant toujours par l'élément (le client)situé le plus à ″ l'ouest″ ( c’est -à –dire.
à gauche)et dont la demande ( ou demande résiduelle) n’est pas nulle. Puis on itère
comme plus haut jusqu'à à arriver à obtenir 0 comme stock résiduel pour le dépôt
associé à cette ligne..

Clients
1 2 3 4 5
Dépôts 1 15 20 5 9 (49) (34) (14) (9) 0 Stocks
2 0 0 0 16 (30) 14 0 résiduels

Page 6 sur 6 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Demandes (15) (20) (5) (25) 14

résiduelles 0 0 0 (16 )
0 0 0 0

Lors de la dernière étape, il reste un seul client à livrer(ici le client 5) et un seul dépôt ( le
dépôt 2) a encore un stock résiduel, égale à 14 tonnes ; on pose donc x25= 14.

Clients
1 2 3 4 5
Dépôts 1 15 20 5 9 0 49 34 14 9 0 Stocks
2 0 0 0 16 14 30 14 0 0

Demandes (15) (20) (5) (25) (14)

0 0 0 16 0
0 0 0 0 0

- Après ces différentes affectations, une première matrice de quantités xij est
obtenue. Ce sont les quantités à acheminer vers les cinq clients à partir des deux dépôts.

Matrice des quantités xij

Clients
1 2 3 4 5

Dépôts 1 15 20 5 9 0 49 Stocks
2 0 0 0 16 14 30

Demandes 15 20 5 25 14
initiales

Cette solution initiale est dite ‘de base ‘si elle comporte m+n-1 quantités xij non
nulles . Ici m=2 et n=5 , on vérifie que la solution comporte 2+5-1 = 6 xij non nuls. A
cette solution de base correspond un coût de transport total de :

2 5

Page 7 sur 7 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

∑ ∑ cij xij =(15*10) + (20*6) + (5*3) + (9*5) + (16*12) + (14*5) = 592 u.m
i = 1 j=1

Rappelons que dans cette méthode, on n’a pas comparé les coûts unitaires entre eux,
on a seulement voulu obtenir rapidement une solution initiale. Au plan économique la
méthode du coin Nord – ouest peut fournir des solutions de piètre qualité. D’ailleurs
nous verrons plus loin que le coût minimal est de 401 u.m : cette solution initiale est, en
fait, éloigné de l’optimum d’environ 20% ... Ceci n’est guère étonnant : nous n’avons
pas regardé les valeurs des coûts unitaires de transport pour construire cette solution .

D’une manière générale la méthode du coin Nord- ouest se révèle ‘ mauvaise ‘ ( c-à-d.
donner une solution initiale onéreuse), si la structure du tableau des coûts est telle qu’on
trouve dans les cases le long de la diagonale principale (du coin Nord-ouest), les c ij les
plus élevés.

2. METHODE DU COUT MINIMAL ( MINTAB) :

On tente ici de corriger le point faible de la méthode précédente, en prêtant attention
désormais au tableau des coûts.
Dans la méthode MINTAB l'élément des coûts unitaires sélectionné sera, à toute étape ,le
plus faible parmi les liaisons fournisseurs – clients (i,j) encore ″utilisables ″ (c.-à-d. que
ni la ligne ‘i’ , ni la colonne ‘j’ ne doivent être saturées) .

Dans le cas où le minimum du tableau est obtenu plusieurs fois , c'est le premier
coût unitaire rencontré dans l'ordre ligne puis colonne qui est habituellement choisi. On
pourrait ainsi , calculer toutes les possibilités , lorsque le minimum est obtenu plusieurs
fois...
Ici c’est dans la case (2,2) qu’on trouve le coût minimal, qui vaut c22= 2, on débute
donc avec le client 2 : en effet, la demande du client 2 est affectée en entier au dépôt 2
soit 20 tonnes(et 0 au dépôt 1). La colonne 2 est saturée : on la supprime.

Etape k=1 :

Clients
1 2 3 4 5
Dépôts 1 49 Stock s
2 20 30 10

Page 8 sur 8 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Demandes 15 20 5 25 14

On poursuit : à chaque pas on cherche le coût minimal pour les cases des lignes et
des colonnes non saturées, en veillant à saturer au fur et à mesure la ligne ou la colonne
correspondant au coût minimal. Lors de l’étape k=2, c’est le coût c13 = 3 qui est
concerné.
Clients
1 2 3 4 5
Dépôts 1 5 49 44 Stocks
2 20 30 10

Demandes 15 20 5 25 14

Etape k=3 ; c’est le coût c14= 5

Clients
1 2 3 4 5
Dépôts 1 5 25 49 44 19 Stocks
2 20 30 10 0

Demandes 15 20 5 25 14

Etape k= 4 et 5 ; ce sont les coûts c21= 5 puis c12 = 10 qui sont concernés.

Clients
1 2 3 4 5
Dépôts 1 5 0 5 25 49 44 19 14 Stocks
2 10 20 0 0 30 10 0

Demandes 15 20 5 25 14

Dernière étape : k=6. Le seul coût utilisable est c15 = 25 (c’est le plus cher, mais on n’a
pas le choix).
Page 9 sur 9 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Clients
1 2 3 4 5
Dépôts 1 5 0 5 25 14 49 44 19 14 0 Stocks
2 10 20 0 0 0 30 10 0

Demandes 15 20 5 25 14

La matrice des quantités est donc la suivante :

Matrice des quantités finale

Clients
1 2 3 4 5

Dépôts 1 5 0 5 25 14 0 Stocks
2 10 20 0 0 0 0

Demandes 15 20 5 25 14

Cette deuxième solution de base représente un coût de transport total :

2 5
∑ ∑ cij xij =(5*10) ) + (5*3) + (25*5) + (14*25) + (10*25) + (20*2) = 830 um
i=1 j=1

Remarquons que cette solution est plus cher que celle obtenue par la méthode du coin
Nord-Ouest...(cela provient de la dernière itération, où l’on avait plus de choix. On a dû
transporter une quantité importante de marchandise soit 14 tonnes, au coût le plus élevé
du tableau soit 25 u.m .
Mais, si le choix à la troisième itération avait été l'élément de la deuxième ligne et
de la cinquième colonne, une affectation différente aurait été obtenue avec un coût de
transport de :

2 5
∑ ∑ cij xij = (15*10) + (5*3) + (25*5) + (16*2) + (14*5) + (4*6) = 416
i =1 j=1

Page 10 sur 10 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Le coût total est de 416 u. m par cette méthode. Ce coût est alors sensiblement
inférieur à celui de la solution obtenue par la méthode du ‘ coin Nord-Ouest’ .

NB : la méthode MINTAB n’est pas aussi bonne qu’on aurait pu l’attendre . Ceci
s’explique par le fait que si l’on ajoute, dans le tableau des coûts, un même coût
‘ui’ à tous les coûts de la ligne ‘i’ (et /ou un même coût vj à tous les coûts de la
colonne ‘j’), on peut montrer qu’on obtient un programme de transport
équivalent, c’est-à –dire qui a pour optimum le même tableau [x* ij] que le
programme initial ; ainsi cij passe de la valeur c′ ij = ui + vj + c ij : le classement
des cij par valeurs croissantes est différent du classement des c′ ij par valeurs
croissantes.

Page 11 sur 11 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

3. METHODE DES DIFFERENCES MAXIMALES : HEURISTIQUE DE BALAS-HAMMAR

Cette méthode donne le plus souvent des solutions meilleures que les méthodes
précédentes ; il arrive même fréquemment que pour des problèmes de petites
dimensions, elle conduise directement à la solution optimale.
Cette méthode est exposée en 7 étapes.

Le déroulement de la méthode s'effectue toujours en balayant d'abord par les

colonnes, puis les lignes, et ainsi de suite.

Etape n°1 : Pour chaque ligne et chaque colonne, on calcule la différence entre
l'élément de la ligne (ou de la colonne )ayant le coût le plus faible et celui ayant le coût
immédiatement supérieur. Si le coût le plus faible est atteint dans plusieurs cases d’une
même rangée(ligne ou colonne) la différence est nulle pour cette rangée.

Par exemple, pour la série de chiffres suivants 12, 5, 6, 5, 7 , la différence

cherchée est : 5- 5 = 0

1ère itération : tableau initial des coûts de notre exemple :

Différences
en ligne :

Page 12 sur 12 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

C L I E NT S
1 2 3 4 5

Dépôts 1 10 6 3 5 25 2 ( = c14 - c13)

2 5 2 6 12 5 3 ( = c21 - c22)
Demandes 15 20 5 25 14
initiales

Différences 5 4 3 7 20
en colonne :

Etape n°2 :On choisit la colonne (ou la ligne )correspondant à la différence maximale
parmi les m+n ( ici 2+5) différences calculées. Dans cette colonne, la case donnant le
coût le plus faible est retenue. En effet on choisit d’effectuer d’abord le transport , qui
aurait le plus fort surcoût , si on ne pouvait pas l’effectuer ultérieurement
.
Notons cette case (h,k) : la quantité transportée sur cette liaison, soit xh,k ,est égale au
minimum entre le stock courant du dépôt ‘h’ et la demande résiduelle du client k .

Si la différence maximale est atteinte dans plusieurs rangées, on retient la case la case
associée à la première rencontrée( dans un balayage par ligne d’abord).
(NB : m = nombre de dépôts ; n = nombre de clients)

Dans notre exemple, la différence maximale (25-5) est obtenue pour la

colonne 5 et l'élément de cette colonne ayant le coût le plus faible correspond au
transport du dépôt 2 au client 5. La totalité de la demande, de ce client, soit 14 au dépôt
2 (et 0 au dépôt 1) lui est livrée depuis le dépôt 2 ; ainsi h= 2, k=5 et
x h,k = min(14,30)=14.
1ère itération : tableau des quantités xij de notre exemple
Clients
1 2 3 4 5 Stocks reste
Dépôts 1 0 49 49
2 14 30 16
Demandes 15 20 5 25 14
initiales
Page 13 sur 13 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Reste 15 20 5 25 0
NB : on évite ainsi d’utiliser le couple ( dépôt ‘1’, client ‘5’), qui a un coût unitaire
élevé.

Etape n°3 : La quantité livrée au client 5 est déduite du stock du dépôt 2. Il reste
maintenant 16 unités disponibles au dépôt ‘2’.

Etape n°4 : La colonne 5 qui est saturée est alors masquée. Il reste
un tableau de coûts à quatre colonnes (tout se passe dans la suite comme si
la colonne ‘5’ avait disparu du problème)et deux lignes.
Etape n°5 : Les différences maximales en lignes et en colonnes du nouveau tableau
sont recalculées(en ignorant la rangée qu’on vient de supprimer).

2ème itération : tableau modifié des coûts de notre exemple

Clients stocks restant différences

1 2 3 4 5 en ligne

Dépôts 1 10 6 3 5 25 49 2
2 5 2 6 12 5 10 3
Demandes 15 20 5 25 14
Différences 5 4 3 7 20
en colonne

Etape n° 6 : La différence maximale est calculée ; soit chk le plus petit coût dans la
rangée où se trouve la différence maximale .

Dans notre exemple, c'est la ligne 2 qui a la différence maximale et c'est le transport entre
le dépôt 2 et le client 2 qui est le moins coûteux : h= 2 et k = 2.
La demande du client ‘2’ est de 20, alors que le stock restant disponible est de 16, seule
16 unités sont affectées au dépôt 2 (et 4 unités au dépôt 1, implication du choix
précédent, due au fait que notre programme de transport ne comporte que m = 2
lignes).

2ème itération : tableau des quantités de notre exemple

Page 14 sur 14 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Clients
1 2 3 4 5 Stocks
Dépôts 1 4 0 49 45
2 16 14 30 16 0
Demandes 15 20 5 25 14

Reste 0 0
Etape n° 7 : Ce sont maintenant les colonnes qui sont à traiter à partir d'un
nouveau tableau où ont été masqués la colonne 2 et la ligne 2 puisqu'elles sont saturées.
Les opérations se poursuivent de façon identique jusqu'à saturation
complète.
Les tableaux suivants sont obtenus :

3ème itération : tableau modifié des coûts de notre exemple

Clients
1 2 3 4 5

Dépôts 1 10 6 3 5 25 2
2 5 2 6 12 5 3
Demandes 15 20 5 25 14

Différence 5 4 3 7 20
10 3 5

C'est la colonne 1 qui a la différence maximale. On affecte toute la demande

au dépôt 1.
3ème itération : tableau des quantités de notre exemple

Clients
1 2 3 4 5 Stoc
k
Dépôts 1 15 4 0 49 45 30
Page 15 sur 15 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

2 16 14 30 16 0
Demandes 15 20 5 25 14

Reste 0 0 0
On calcule la différence de la ligne 1. 3 étant le coût le plus faible, on lui affecte la totalité
de la demande du client 2. La colonne 2 est saturée (et masquée).
Comme il ne reste que la colonne 3, on affecte la totalité de la demande
du client 3 au dépôt 1.
4ème itération : Tableau modifié des coûts de notre exemple

Clients
1 2 3 4 5
Dépôts 1 10 6 3 5 25 2 2
2 5 2 6 12 5 3
Demandes 15 20 5 25 14

Différence 5 4 3 7 20
10 3 5

4ème itération : tableau des quantités de notre exemple

Clients
1 2 3 4 5 Stocks
Dépôts 1 15 4 5 25 0 49 45 30 25 0
2 16 14 30 16 0
Demandes 15 20 5 25 14

Reste 0 0 0 0 0

La solution finale est atteinte une fois le tableau entièrement rempli.

La matrice des quantités est la suivante :

Matrice des quantités finale

Clients
1 2 3 4 5
Page 16 sur 16 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Dépôts 1 15 4 5 25 0 0 Stock s
2 0 16 0 0 14 0

Demandes 15 20 5 25 14

Cette troisième solution de base représente un coût de transport total de :

2 5
∑ ∑ cij xij = (15*10) + (4*6) + (5*3) + (25*5) + (16*2) + (14*5) = 416 um
i = 1 j=1

Le coût total est de 416 unités monétaires ..

Cette solution de base sera choisie par la suite pour optimiser le problème posé.

L'avantage d'une solution initiale à faible coût est de pouvoir converger plus
e
rapidement vers la solution optimale lors de la 2 , grâce à une diminution du nombre
d'itérations.

PROGRAMME DE TRANSPORT (suite)

DEUXIEME PHASE DE LA RESOLUTION

OPTIMISATION D4UNE SOLUTION DE BASE PAR LA METHODE

DU ″STEPPING -STON″
Nous précisons ci-dessous la définition d’une solution de base :
Associons un graphe à une solution d’un programme de transport comme suite :
Les sommets figurent les m dépôts et les n clients ; le graphe a donc deux niveaux de
sommets.
On figure un arc du sommet associé au dépôt Di vers le sommet associé au client Cj,
si xij est positif, c-à-d si la liaison ( Di, Cj) est effectivement utilisée dans le transport.
Ainsi pour la solution ci-dessus, ce graphe est le suivant :

•C1 1 2 3 4 5

1 15 4 5 25 0
D1• •C2
2 0 16 0 0 14
Page 17 sur 17 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

•C3

•C4 On remarque le graphe obtenu est connexe et sans

cycle : c’est un ‘arbre’, au sens où nous l’avons
défini dans le cours sur le graphe.
D2 •
• C5

Plus généralement on appelle ″solution de base″ toute solution du programme de

transport dont le graphe est un arbre..
On rappelle qu’un arbre est connexe, sans cycle et que le nombre de ses arêtes est :
M=N-1, où N est le nombre total de sommets ( ici N=m+n) ?
Ainsi le graphe d’une solution de base d’un programme de transport comporte
M=m+n –1 arêtes et il est sans cycle.

Les méthodes approchées ( ou heuristiques) qui ont été présentées, produisent des
solutions dont le graphe est sans cycle : en effet, à chaque pas on sature une ligne
(dépôt) ou une colonne (un client) qui disparaît alors pour la suite du problème.

Il reste à vérifier qu’en fin d’application de ces heuristiques on a bien m+n-1 liaisons
utilisées, c-à-d (m+n-1) variables xij positives , les autres étant nulles ( il y en a (m-
1)*(n-1)).
En effet il aurait pu se produire dans l’application des heuristiques ci-dessus que ,lors
d’une certaine itération ,on sature à la fois une ligne et une colonne ; dans ce cas(et ce
cas seulement) la solution obtenue par l’heuristique comportera moins de (m+n-1)
variables xij positives ; ceci se traduira dans le graphe associé à la solution qui ,alors ,ne
sera pas connexe( mais sans cycle).

COUTS REDUITS : δ ij

Où Vj = Ui+cij : pour tout arc (Di, Cj) ; et

δ ij = Ui+cij – Vj : pour toute liaison non employée ( c-à-d., telle que xij = 0 et donc l’arc
(Di, Cj) ne figure pas dans l’arbre ) ;
Le sommet Di : désigne le dépôt ‘i’ ;
De même le sommet Cj désigne le client ‘j’ .

Page 18 sur 18 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Ui Vj
C1 : 10 = V1
10= c11

U1= 0 D1 • 3 = c13 C3 : 3 = V3

5= c14
C4 : 5 = V4
6 = c12

U2= 4 D2 • 2 = c22 C2 : 6 =V2

5 = c25

C5 : 9 = V5

Les quantités Vj et Ui sont nommées ″ potentiels″ (car, pour tout arc (Di, Cj) de l’arbre ,
la différence : Vj – Ui est égale à cij ).

On pose, arbitrairement, U1 = 0, ce qui implique alors que :

V1 = 0 + c11 = 10, V3 = 0+ c13 = 3 ; V4= 0 + c14 = 5 et V2 = 6.
On pose alors à l’arc (D2, C2) qui doit vérifier : V2 – U2 = c22, soit 6-U2 = 2 ,
d’où U2 = 4. En fin V5 = U2 + c25 = 4+ 5 = 9.

NB : On peut montrer qu’une fois qu’on a fixé arbitrairement le potentiel d’un sommet
( ici U1 = 0), les valeurs des potentiels des autres sommets sont uniques.

OPTIMISATION D’UNE SOLUTION DE BASE

METHODE DE ‘STEPPING STONE’

Soit la solution de Base ci-dessous :

(MATRICE DES QUANTITES)
CLIENTS

Page 19 sur 19 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

1 2 3 4 5 stocks
.j
.i
1 15 4 5 25 0 49
Dépôts 2 0 16 0 0 14 30
Demande 15 20 5 25 14

On a calculé les potentiels Ui et Vj des sommets de l’arbre, qui sont définis par
Vj = cij +Ui ; ceci afin de pouvoir ultérieurement calculer les coûts marginaux des liaisons
(i,j) non utilisées ( c’est à dire telles que xij = 0), par la formule :
δ ij = Ui+ cij – Vj (( = cij – (Vj- Ci)) .
Ici On a posé U1= 0, parce que, c’est la première ligne (i=1) qui contient le coût unitaire le
plus élevé (10) . Le détail du calcul des potentiels a été donné plus haut.
Voici le détail du calcul des coûts marginaux ;

δ 15= U1+c15 – V5= 0+25-9 = 16 >0

δ 21 = U2+c21 – V1= 4+5- 10 = - 1
δ 23 = U2 +c23 - V3= 4+6 -3 = 7
δ 24 = U2 + c2 - V4= 4+12-5 = 11
Si les δij pour toutes les cases telles que xij = 0 sont supérieurs à 0, on peut montrer
qu’alors la solution de base est la solution optimale, sinon , la solution de base sera
optimisée par la méthode ‘STEPPING-STONE ‘

Ui Vj

C1 V1= 10
10
U1= 0 D1
3 C3 V3 = 3

5
C4 V4 = 5
6
U2= 4 D2 2
C2 V2 = 6
Page 20 sur 20 Leçon n° : 8

Pr LEMAIRE –EL GOHARY .H

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

5
C5 V5 = 9

Pour les cases vides ( i.e telle que xij= 0)dans la solution de base, on trouve qu’un seul δ
ij négatif : δ 21 = - 1

C1
-1

+1
D1 C3

C4
+1

D2 -1 C2

C5

Si on ajoute à l’arbre l’arc associé : (D2, C1), on crée un cycle et c’est le

″cycle de substitution″ associé à δ 21 = -1. On peut en effet modifier la solution courante
en posant :

x21 := x21 + 1 , x11 := x11 –1

x12 := x12 +1 , x22 := x22 – 1
Ainsi sur les liaisons (D1, C1) et (D2, C2) est –on amené à démineur la quantité
transportée.
Si l’on substitue 1 seule tonne, on fait une économie de :|δ 21| • 1 = 1 u.m.

Pour économiser davantage on va chercher la quantité maximale qu’on peut substituer le

long de ce cycle.
Le long du cycle on marque + l’arc qu’on vient d’ajouter à l’arbre soit (D2, c1), on
marque – l’arc suivant sur le cycle : (D1, C1), puis on marque + l’arc suivant, soit (D1,
C2) et enfin on marque – l’arc (D2, C2) , le dernier du cycle de substitution .

Page 19 sur 26 Leçon n° :8

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Pour déterminer la quantité maximale qu’on peut substituer ( en tonnes) . On inspecte les
liaisons sur lesquelles on va diminuer la quantité transportée
(D1, C1) : x11 = 15 ;
(D2 ,C2) : x22 = 16 .

Quantités transportée en tonnes(avant substitution)

-
D1 C1 x 11 = 15 x 12 = 4
+
.x 21 =0 x22 = 16
+
C2

D2
-
Entre x11 et x 22 , on choisit la plus petite quantité : c’est x11= 15 tonnes( afin de ne rendre
aucun xij négatif ; si on prenait 16 , on aurait x11 := x11 – 16 et donc x11= -1, ce qui n’est
pas admissible..
X 11 = 15-15 = 0 x12 = 4+15 =19
X 21 = 0 +15 = 15 x22 = 16-15 =1

On a donc augmenté de 15 sur l’arc du cycle marqué +, et diminué de 15 sur l’arc du

cycle marqué - .

Donc la nouvelle matrice des quantités à transporter [xij] est :

MATRICE DES QUANTITES

CLIENTS

j 1 2 3 4 5 stocks
.i
Dépôts D1 0 19 5 25 0 49
D2 15 1 0 0 14 30
Demandes 15 20 5 25 14 79

On refait les calcules des δ ij pour les cases vides (c.-à-d telles que xij = 0):

Page 20 sur 26 Leçon n° :8

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

δ 11= U1+ c11- V1 = 0+10-9 = 1;

δ 15= U1+ c15- V5 = 0 +25- 9 = 16 ;
δ 23 = U2+ c23- V3 = 4 + 6 –3 = 7 ;
δ 24 = U2+ c24- V4 = 4+12- 5 = 11.

Les coûts marginaux sont tous positifs.

C4 5 = V4

5
C3 3 = V3
3
U1= 0 D1 6
C2 6= V2
2

U2= 4 D2 5 C1 9 = V1

5
C5 9 = V5

NB : ici nous n’avons qu’une seule itération puisque la solution ci-dessus est optimale.
En effet en traçant l’arbre associé à la solution améliorée , puis en calculant les potentiels
des sommets, puis les δ ij (coût de substitution des liaisons non employées, i.e telles que
xij = 0), on a constaté que tous les coûts marginaux sont positifs.
Si au moins l’un d’entre eux avait été négatif, il aurait fallu pratiquer une nouvelle itération.
On itère tant que dans la solution ( de base) courante il existe encore des δ ij négatifs.

Donc on a obtenu la solution ‘OPTIMALE’ qui coût :

= (19*6)+(5*3)+(25*5)+(15*5)+(1*2)+(14*5) = 401 u.m

Page 21 sur 26 Leçon n° :8

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

AUTRE SOLUTION DU PROBLEME DE TRANSPORT PAR LA METHODE

BALAS- HAMMER

Dans cette méthode , on calcule les différences maximales par ligne et par colonne
, c-à-d ∆ l et ∆ c . on choisit le maximum de (∆l , ∆c ) qui va nous indiquer,
quelle ligne ou colonne qui sera traitée.
Clients stocks des dépôts

1 2 3 4 5

1 10 6 3 5 25 49
dépôts
2 5 2 6 12 5 30

Demandes 15 20 5 25 14
Page 22 sur 26 Leçon n° :8
C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

MATRICE DES QUANTITES

1 2 3 4 5 ∆l 1 2 3 4 5

1 10 6 3 5 25 2 1 0 49

2 5 2 6 12 5 * 3 2 14 30 16

15 20 5 25 0
∆c :5 4 3 7 20

∆ max = 20 colonne 5 . Minimum de coûts unitaires dans la colonne 5 = min(5,

25) =5.
Donc x15 = 14 , et la colonne 5 est saturée ,et disparaît du problème.

MATRICE DES QUANTITES

CLIENTS
1 2 3 4 ∆l 1 2 3 4 5 stocks

1 10 6 3 5* 2 1 25 0 49 24

2 5 2 6 12 3 2 0 14 16

∆c : 5 4 3 7 15 20 5 0 0

∆max = 7 colonne 4.Minimum de coûts unitairesdans la colonne 4= min ( 5, 12)= 5.

Page 23 sur 26 Leçon n° :8
C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Donc x14 = 25 ; la colonne 4 est saturée et disparaît du problème.

1 2 3 ∆l 1 2 3 4 5

1 10 6 3 3 1 0 25 0 24

2 5* 2 6 3 2 15 0 14 16 1

20 5
∆ j :5 4 3

∆ max = 5 colonne 1.Minimum de coûts unitaires dans la colonne 1= min (10, 5)= 5

Donc x 21 = 15. La colonne 1 est saturée et disparaît du problème.

2 3 ∆l 1 2 3 4 5

1 6 3 3 1 0 25 0 24

2* 6 4 2 15 1 0 14 0
0 19 5 0 0
∆c: 4 3

∆ max = 4 colonne 2 .Minimum de coûts unitaires dans la colonne 2= min(2, 6)=

2.

Donc x22 = 1 . La ligne 2 est saturée et disparaît du problème.

Il reste un problème d’une seule rangée(ici une seule ligne)
2 3
1 6 3

Page 24 sur 26 Leçon n° :8

C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

Dans ce cas pour compléter le tableau de la demande resrante [xij] des quantités livrées,
on n’a pas le choix : il reste 24 tonnes au dépôt 1 à repartir entre 19 tonnes pour le client 2
et 5 pour le client 3 :

.x12 = 19 et x13 =5.

Finalement la solution donnée par la méthode de la différence maximale est donc :

MATRICE DES QUANTITES

[X IJ]

CLIENTS STOCKS
1 2 3 4 5

DEPOTS 1 0 19 5 25 0 49

2 15 1 0 0 14 30

DEMANDES : 15 20 5 25 14

Le coût du transport = 15*5 + 1*2 +14*5 + 19*6 +5*3 +25 *5 = 401 u. m

C’est une solution de base : elle comporte m+n-1 = 6 xij non nuls (ici m=2 et n= 5).
En effet on tombe ici directement sur l’optimum. nous l’avons dit, cette méthode quand
elle appliquée à des problèmes de petite taille, fournit fréquement la solution optimale..

En générale pour déterminer si cette solution est optimale ou non , il faut calculer :

δ ij= Ui+cij –Vj , pour les cases vides. Si toutes les δ i j sont positives, c’est la solution
optimale, si non il faut l’optimiser par la méthode ‘STEPPING-STONE’:
Notons que : Vj = Ui + c ij .On pose Ui = 0, où i corresponde à la ligne de la matrice des
coûts unitaire qui porte le coût unitaire le plus fort : c11 = 10 U1= 0 .

Ui Vj
C5 (9) : V5

D2 5 C1 (9) : V1
Page 25 sur 26 Leçon n° :8
C.N.A.M. GRAPHES ET A5
ALGORITHMES
EAD Leçon n° : 8

U2=4 5
2
C2 (6) : V2
6
D1 3 C3 (3) : V3
U1=0
5
C4 (5) : V4

δ 11 = 0 +10-9 = 1 ; δ 15 = 0+25-9 =16

Donc c’est la solution est optimale.
δ 23 = 4+6-3 = 7 ; δ 24 = 4+12-5= 11

Le coût = 19*6+ 5*3+ 25*5+ 15*5+ 1*2+ 14*5 = 401 u .m

Page 26 sur 26 Leçon n° :8