PROBLEMES DE TRANSPORT ALGORITHME DU STEPPING-STONE

Considrons le problme suivant : 4 origines notes O1, O2, O3, O4 et 5 destinations notes D1, D2, D3, D4 , D5 Chaque origine a une offre ( respecter) et chaque destination une demande ( satisfaire) On possde, en outre, les cots de transport unitaires des origines vers les destinations. Tout linformation est rsume dans le tableau suivant (les cots sont dans le corps du tableau) : D1 7 15 8 18 10 D2 12 3 16 8 11 D3 1 12 10 17 15 D4 5 6 12 11 5 D5 9 14 7 16 4 Offre 12 11 14 8

O1 O2 O3 O4 Demande

La question quon se pose est la suivante : quelles quantits de marchandise envoyer des origines vers les destinations en respectant loffre et en satisfaisant la demande au moindre cot ? Cest, lvidence, un problme de programmation linaire avec 20 variables quon pourra prsenter dans un tableau analogue ; on aura donc deux tableaux similaires, un pour les cots et un pour les quantits. On pourrait rsoudre ce problme laide de lalgorithme du simplexe, mais on va prfrer un algorithme spcifique (le Stepping-Stone) qui tiendra compte des particularits du problme pos pour en simplifier la rsolution. Lalgorithme du Stepping-Stone sera un algorithme itratif (donc par tapes successives) visant amliorer (donc faire baisser le cot global) une solution de base. Il nous faut donc une solution de dpart pour dmarrer lalgorithme. Nous allons fournir 2 mthodes permettant den obtenir une : la mthode du coin Nord-Ouest et la mthode de Balas-Hammer

1) Obtention dune solution de base par la mthode du coin Nord-Ouest Lide de la mthode est le suivant : remplir au maximum la case du tableau en haut , gauche (le coin NordOuest ), puis complter sur la ligne ou la colonne (de faon atteindre loffre ou la demande) et continuer ainsi complter les cases immdiatement droite et en dessous alternativement. Exemple : 10, puis droite, en bas, droite, en bas 10 2 9 12 11 14 8

2 13 15

10

11

1 4 5

4 4

Cette mthode a pour elle lavantage de fournir rapidement et aisment une solution de base mais linconvnient (puisquelle ne fait jamais intervenir les cots) dtre en gnral assez loin de loptimum, donc de ncessiter ensuite de nombreuses tapes avant de latteindre.

2) Obtention dune solution de base par la mthode de Balas-Hammer Cette mthode, appele aussi mthode de la diffrence maximale, fera intervenir les cots unitaires de transport et sera donc, en gnral, assez proche de loptimum. Pour chaque range (ligne ou colonne) du tableau des cots, on dterminera llment le plus petit et celui qui lui est immdiatement suprieur et on calculera leur diffrence (note ) O1 O2 O3 O4 D1 7 15 8 18 1 D2 12 3 16 8 5 D3 1 12 10 17 9 D4 5 6 12 11 1 D5 9 14 7 16 2 4 3 1 3

Dans la range correspondant la diffrence maximale (ici la colonne D3) on remplira la case contenant le plus petit lment (ici la case O1D3) avec le minimum de loffre de la ligne et de la demande de la colonne. Puis on recommencera le processus autant de fois que ncessaire en supprimant chaque fois lorigine dont loffre est entirement utilise et/ou la destination dont la demande est compltement satisfaite. Exemple : D1 O1 O2 O3 O4 Demande X O2 O3 O4 X O2 O3 O4 X O2 X O4 X O2 X O4 D1 X 15 8 18 7 X X X X X X X X X X X X X X X D2 X 3 16 8 5 D2 X 3 16 8 5 D2 X 3 X 8 5 X X X X X D3 X 12 10 17 2 D3 X 12 10 17 2 D3 X 12 X 17 5 D3 X X X 17 0 D4 X 6 12 11 5 D4 X 6 12 11 5 D4 X 6 X 11 5 D4 X X X 11 0 D5 X 14 7 16 7 D5 X 14 7 16 7 X X X X X X X X X X D2 D3 12 D4 D5 Offre 12 11 14 8 4 3 1 3

10 1 3 1 3 3 3 3 3 3

11 5

15 9

5 1

4 2 D1 D2 D3 12 D4 D5 Offre 12 11 14 8 4 D5 Offre 12 11 4 14 8 4 D5 Offre 12 11 4 14 8 4 D5 Offre 12 11 4 14 8 4

O1 O2 O3 O4 Demande O1 O2 O3 O4 Demande O1 O2 O3 O4 Demande O1 O2 O3 O4 Demande

10 10 D1 11 D2 3 D3 12 5 D4

10 10 D1 11 D2 11 10 10 D1 11 D2 11 10 10 11 3 3 5 5 3 D3 12 5 D4 3 D3 12 5 D4

3) Droulement de lalgorithme On peut appliquer lalgorithme nimporte laquelle des solutions de base. On va lappliquer, par exemple, la solution fournie par la mthode du Coin Nord-Ouest. Lalgorithme consiste modifier la solution pour une qui soit meilleure, donc rendre non vide une case vide du tableau des quantits

On choisira la case qui permet la plus grande baisse du cot global de transport Pour la dterminer, on calculera : a) les potentiels associs aux origines et aux destinations b) les variations de cot unitaire pour chaque case vide () c) les quantits maximales quon peut ajouter chaque case vide (q)

a) Comment dterminer les potentiels ? On utilisera le tableau des cots limit aux cases o la quantit transite est non nulle : D1 7 15 8 18 D2 12 3 16 8 D3 1 12 10 17 D4 5 6 12 11 D5 9 14 7 16 D1 10 D2 2 9 D3 2 13 D4 D5 O1 O2 O3 O4 D1 7 D2 12 3 D3 12 10 D4 D5

O1 O2 O3 O4

O1 O2 O3 O4

1 4

12 11

16

On dterminera les potentiels de proche en proche : on commencera par une destination, puis une origine, puis une destination..en soustrayant de D O et en ajoutant de O D.

On fixera le premier potentiel arbitrairement etsuivre les flches (on soustrait des destinations aux origines et on ajoute des origines aux destinations)

1 D1 D2 D3 D4 D5 Pot. O1 7 12 0 O2 3 12 O3 10 12 O4 11 16 Pot. 7 2 D1 D2 D3 D4 D5 Pot. O1 7 12 0 O2 3 12 O3 10 12 O4 11 16 Pot. 7 12

3 D1 D2 D3 D4 D5 Pot. O1 7 12 0 O2 3 12 9 O3 10 12 O4 11 16 Pot. 7 12 4 D1 D2 O1 7 12 O2 3 O3 O4 Pot. 7 12 D3 D4 D5 Pot. 0 12 9 10 12 11 16 21

5 D1 D2 O1 7 12 O2 3 O3 O4 Pot. 7 12 6 D1 D2 O1 7 12 O2 3 O3 O4 Pot. 7 12

D3 D4 D5 Pot. 0 12 9 10 12 11 11 16 21 23 D3 D4 D5 Pot. 0 12 9 10 12 11 11 16 12 21 23 28

b) Comment dterminer les ? Pour chaque case nulle, on calculera en ajoutant au cot unitaire de la case le potentiel de lorigine associe et en retranchant le potentiel de la destination correspondante :

Cots D1 O1 O2 15 O3 8 O4 18 Pot. 7

D2

D3 1

D4 5 6

16 8 12

17 21

23

D5 Pot. 9 0 14 9 7 11 12 28

O1 O2 O3 O4 Pot.

D1 17 12 23 7

D2

15 8 12

D3 D4 D5 Pot. -20 -18 -19 0 -8 -5 9 -10 11 8 12 21 23 28

c) Comment dterminer les q ? On dterminera les quantits quon peut ajouter aux cases vides uniquement pour celles dont le est ngatif ; il ne sert rien, en effet, de remplir une case qui fait augmenter le cot ! Pour remplir une case vide, il faut diminuer une case [Link] constituer un circuit de cases pleines quon vide et remplit alternativement : D1 10 D2 2 9 D3 2 13 15 D4 D5 Offre 12 11 14 8

O1 O2 O3 O4 Demande

10

11

1 4 5

4 4

La quantit maximale quon peut dplacer pour remplir la case O1D3 est donc 2 (la valeur minimale des cases o on enlve quelque chose. On obtient tous les q de la mme faon : q O1 O2 O3 O4

D1

D2

D3 2

D4 1 1

D5 1 1 1

En multipliant par q, on obtient la variation de cot conscutive au remplissage dune case vide, cette baisse de cot est maximale pour la case O1D3, cest elle quon va donc remplir en y mettant 2 units, ce qui donne la solution suivante : D1 D2 D3 D4 D5 Offre D1 D2 D3 D4 D5 Offre O1 10 2 12 O1 10 2 12 O2 9 2 11 O2 11 11 O3 13 1 14 O3 13 1 14 O4 4 4 8 O4 4 4 8 Demande 10 11 15 5 4 Demande 10 11 15 5 4

On rpte les tapes a)b)c) tant quil y a des ngatifs. Quand tous les seront positifs, nous aurons une des solutions optimales. Dans lexemple ci-dessus, il faudra 5 tapes pour atteindre cet optimum : D1 D2 D3 D4 D5 D1 D2 D3 D4 D5 O1 12 O1 12 O2 11 O2 11 O3 10 3 1 O3 10 3 1 O4 4 4 O4 5 3

D1 O1 O2 O3 O4

D2 11

D3 12

D4

D5

10 3 5