GESTION DU PROBLEME DE TRANSPORT Réalisé par : Salma ADNAN & Ghita ACHOUAK 2008-2009

GESTION DU PROBLEME DE TRANSPORT

Réalisé par :Salma ADNAN & Ghita ACHOUAK 2008-2009

Recherche Opérationnelle Management Logistique 2

SOMMAIRE

INTRODUCTION RAPPEL SUR LA THEORIE DES

GRAPHES PRESENTATION DU PROBLEME DE

TRANSPORT PROBLEME D’AFFECTATION PROBLEME DE FLOTS CONCLUSION


INTRODUCTION

La gestion du problème de transport est parmi les préoccupations majeures des entreprises.

La RO permet une modélisation de ces problèmes en utilisant plusieurs méthodes.


La théorie des graphes Un graphe est une représentation

symbolique d’un réseau. Il s’agit d’une abstraction de la réalité de sorte à permettre sa modélisation.

Un réseau de transport, comme tout réseau, peut être représenté sous forme de graphe. Un graphe G consiste en un ensemble de noeuds v et d’arcs e. Par suite, G=(v,e).

Un sommet v (nœud )est un point d’extrémité ou un point d’intersection d’un graphe .

Un arc e est un lien entre deux sommets. Un arc possède une direction souvent symbolisée par une flèche.


On appelle un sous-graphe d'un graphe un graphe dont

on a enlevé des sommets. Dans le graphe G précédant, le sous graphe p=1.

Ce graphe se définit de façon suivante:

G = (v,e)v = (1,2,3,4,5)e = (1,2), (1,3), (2,2),

(2,5), (4,2), (4,3), (4,5)

La théorie des graphes


la théorie des graphes

Une arête est un groupe de deux sommets tels que chaque sommet fait partie de l’ensemble des correspondants de l’autre sommet.

Ce graphe comporte 5 arcs [(1,2), (2,1),(2,3), (4,3), (4,4)]

et 3 arêtes [(1-2), (2-3), (3-4)].


la théorie des graphes

L’établissement de chemins est une étape fondamentale dans la mesure d’accessibilité et de flux de trafic au sein d’un réseau.

Un chemin eulérien est un chemin simple qui passe une fois et une seule par chaque arc.

Un chemin hamiltonien est un chemin qui passe une fois et une seule par chaque sommet.

Une chaîne est une suite d’arcs telle que chaque arc de la suite a une extrémité en commun avec l’arc précedent. La direction n’a pas d’importance.


la théorie des graphes Un circuit est un chemin fini et fermé dont

l’extrémité terminale du dernier arc coïncide avec l’extrémité initiale du premier.

Un cycle est une chaîne dont le sommet initial et terminal coïncide et qui n’emprunte pas le même arc constitue un cycle.

Il convient de distinguer deux grands types de graphes : les graphes orientés et ceux qui ne le sont pas (les graphes non orientées).


LE problème de transport

PRESENTATION

Le P.T est un problème classique de la R.O

La solution du P.T est celle qui permet de transporter les flux du point de départ au point d’arrivée.

La solution doit également être la plus économique.



FOMRMULATION

Données : un ensemble K d'usines, un ensemble L de clients, les offres des usines, les demandes des clients, les coûts de transports unitaires

c(k,l)

ka

lb



FOMRMULATION

q

1

p

1

c11 x11

c12 x12

cpq xpq

a1

a2

ap

b1

b2

bq

cp2 xp2

2 2



FOMRMULATION

On suppose que:

Hypothèse 1:

où ak >0 et bl > 0.

p

1k

q

1llk ba



FOMRMULATION

Le P.T peut être modélisé de la méthode suivante:

(T)

q1,2,...,l et p1,2,...,k0x

(demande)q1,2,...,lbx

lité)(disponibip1,2,...,kax

xczMin

kl

lkl

kkl

klkl

p

1k

q

1l

p

1k

q

1l



FOMRMULATION

Sous l’hypothèse (1), (T) est dit :

« Le problème Standard de Transport » (PST)

p

1k

q

1ll

q

1l

p

1kkl

p

1k

q

1lklk bxxa


p1,2,...,k0,c

bab

1kq

p

1k

q

1llk1q

Si

alors on crée un client fictif :

p

1k

q

1llk ba


FOMRMULATION


p1,2,...,k0,c

aba

1kp

p

1k

q

1lkl1p

Si

alors on crée un entrepôt fictif :

p

1k

q

1llk ba


FOMRMULATION



La solution de base initiale:

(a) La règle du coin Nord-Ouest

(b) La règle des Coûts Minimums

(c) Méthode des Approximations de

Vogel



A- La règle du coin Nord-ouest :Soit le problème suivant:

Une E/se de vente représentant trois dépôts et 5 client. LaMatrice des couts ainsi que la disponibilité et la demande duproduit sont

ClientDépôt

1 2 3 4 5 Dispo

IIIIII

578

693

416

852

1064

805070

DDE 40

20

60

30

50

200



1 2 3 4 5

I 80

II 50

III 70

40 20 60 30 50

ia

Jb

A- La règle du coin Nord-ouest

(The Northwest Corner Rule)



1 2 3 4 5

I 40 20 80 40 20

II 50

III 70

40

0

20

0

60 30 50

ia

Jb

On répète cette étapeJusqu’à ce que la Solution initiale soit obtenue

A- La règle du coin Nord-ouest :



1 2 3 4 5

I 40 20 20 80 40 20 0

II 40 10 50 10 0

III 20 50 70 50 0

40

0

20

0

60

40

0

30

20

0

50

0

ia

Jb

La solution initiale est atteinte

Matrice de S.I



B- la méthode de VogelAppelée également méthode des regrets

ou de la différence maximale, ou deBalas-Hammer

Cette méthode permet d’obtenir la solution

optimale en moins d’itération


1 2 3 4 5 ai

I 5 6 4 8 10 80 1 5-4

II 7 9 10 5 6 50 1 6-5

III 8 3 6 2

30

4 70 40 1 3-2

bj 40 20 60 30

0

50

2

7-5

3

6-3

2

6-4

3

5-2

2

6-4




1 2 3 4 5 ai

I 5 6 4 10 80 1 5-4

II 7 9 10 6 50 1 6-5

III 8 3

20

6

30

4 40 20 1 3-2

bj 40 20

0

60 0 50

2

7-5

3

6-3

2

6-4

__ 2

6-4


1 2 3 4 5 ai

I 5 4

60

10 80 20 1

II 7 10 6 50 1

III 8

20

6

30

4 20 2

bj 40 0 60

0

0 50

2 __ 2 __ 2




1 2 3 4 5 ai

I 5

20 60

10 20 0 5

II 7 6 50 1

III 8

20 30

4 20 4

bj 40

20

0 0 0 50

2 __ __ __ 2


1 2 3 4 5 ai

I

20 60

0

II 7 6 50 1

III 8

20 30

4

20

20 4

bj 20 0 0 0 50

30

2 __ __ __ 2




1 2 3 4 5 ai

I20 60

0

II 7

20

6

30

50 0

III

20 30 20

0

bj 20

0

0 0 0 30

0

2 __ __ __ 2


LE problème de Transport

Exemple du transport de M/SE

La société GALAXY ELECTRONICS est spécialisée dans la vente d’articles électroménager, cette dernière doit livrer ses 4 clients, qui lui achètent respectivement 10, 8, 5 et 7 de produit. Il lui reste exactement 30 articles mais ils sont répartis sur 3 entrepôts : 6, dans le 1er, 9 dans le 2e et 15 dans le 3e.

Les coûts de transport, en DH/A, entre chaque

entrepôts Ri et chaque point de livraison Lj sont

donnés dans le tableau suivant:


2

2

7

7

5

9

3

4

6

4

3

5

R1

R2

R3

L4L3L2L1

Points de

livraison

Entrepôt



Destinations

SourcesL1 L2 L3 L4 Disponibilités

R14) 3) 7) 2)

6 6

0

R23) 4) 5) 2)

9

R35)

6) 9) 7) 15

Demandes 10 8 5 71

Z=?



Destinations

SourcesL1 L2 L3 L4 Disponibilités

R23) 4) 5) 2)

1

9 8

R35)

6) 9) 7) 15

Demandes 10 8 5 10

Z=?



Destinations

Sources

L1 L2 L3Disponibilités

R23)

84) 5) 8

0

R35)

6) 9) 15

Demandes 102

8 5 Z=?



Destinations

SourcesL1 L2 L3

Disponibilités

R35) 2

6)

8

9)

515

0

Demandes 20

80

50

Z=?



Destinations

SourcesL1 L2 L3 L4

Disponibilités

R14) 3) 7) 2)

6 6

R23)

84) 5) 2)

1

9

R35)

2

6)

8

9)

5

7) 15

Demandes 10 8 5 7 Z=131



L’algorithme de stepping stone

Application:

Soit le tableau suivant traduisant les coûts pour chaque

unitée transférée entre les sources et les puits :



1- Recherche d’une solution de base


2- Amélioration de la solution de base

a/ Calculer les coûts marginaux notés pour chaque liaison non-affectéeb/ Si tous les sont positifs ou nuls Fin

Sinon, prendre le cycle de substitution associé au le plus petit.

c/ Retour en a

Les quantités constituent les couts marginaux unitaires.




Il faut prendre toutes les lignes non utilisées avec la solution de base déterminée en 1, et pour chacune d’elle essayer de faire passer une unité sur celle-ci tout en préservant l’équilibre original du graphe.



Détermination des coûts marginaux :



On détermine maintenant le cycle de substitution de :


On retourne maintenant à l’étape 1 de l’algorithme

On détermine donc les modifications à effectuer au final :



Problème d’affectation

Les problèmes d’affectation sont des cas

spéciaux du problème de transport où la

demande associée à chaque destination est

égale à 1. Il existe une méthode, “la méthode

hongroise” qui simplifie la résolution du

problème d’affectation.


Problème d’affectation Formulation


Problème d’affectation La méthode hongroise( algorithme de KHUN)

L’algorithme de résolution du problème d’affectation fut crée par Harold KUHN en 1955. Il est utilisé pour minimiser un cout ou maximiser une satisfaction suite à différentes affectations .

Il s'agit d'affecter :

- des famille de produits à des zones de stock,

- des commerciaux à des secteurs,

- des ouvriers sur des machines,

- ...


Problème d’affectation La méthode hongroise

Application : • Les coûts de fabrication des ouvriers sur les diverses

machines sont donnés par le tableau ci-dessous. • Chercher la meilleure affectation de manière à rendre le coût

de fabrication minimal



Etape 1: Obtention des zéros Créer une nouvelle matrice des coûts en choisissant le

coût minimal dans chaque colonne et en le soustrayant de chaque coût dans la colonne ( Idem pour les lignes ).



Etape 2:Recherche d’une solution optimale

- On cherche la ligne ou des lignes comptant le moins de zéro.

- On encadre un des zéros de cette ligne, puis on barre les zéros qui se trouvent sur la même ligne et dans la même colonne que les zéros encadrés.

- On répète le processus pour les lignes restantes. Un zéro encadré par ligne Solution optimale⇒



La ligne 4 ne contient pas un zéro encadré donc on va appliquer l’étape 3 et 4 de l’algorithme.



Etape 3:Recherche des rangées en nombre minimal contenant tous les zéros:

a. On marque d’une croix toute ligne ne contenant aucun zéro encadré.

b. On marque toute colonne qui a un zéro barré sur une ou plusieurs lignes marquées.

c. On marque toute ligne qui a un zéro encadré sur une ou plusieurs colonnes marquées.

d. On répète b) et c) jusqu’à ce qu’il n’y ait plus de colonne ou de ligne à marquer.

On trace un trait sur toute colonne marquée.

On trace un trait sur toute ligne non marquée.





Etape 4: Déplacement de certains zéros: -Tableau partiel : éléments traversés par aucun trait. - Le plus petit élément du tableau partiel est ajouté aux

éléments rayés deux fois et retranché des éléments du tableau.

- Retour à la phase 2.



Le plus petit élément est 2, ainsi on aura le tableau ci-dessous:






Le Problème de flots

DEFINITION DU FLOTUn flot dans un graphe est une

valuationdes arcs respectant la loi de

conservation des flux (loi de Kirchhoff)

u

uu

u


Le Problème de flots

Soit un graphe G=(X ,U),( , c, s, t) est réseau SSI :

est un graphe orienté connexe sans boucle;

Ce graphe est valué : chaque arc (u, v) du graphe a une capacité c(u, v);

la source s de degré entrant nul :

le puits t de degré sortant nul.

G


Le Problème de flots Un flot est complet si pour tout chemin

allant de la source au puits, il y a au moins un arc Saturé.P.S o Un flot complet n’est pas forcément Maximum.o Un flot maximum est forcément complet


On veut acheminer un produit à partir de 3 entrepôts (1,2,3) vers 4 clients (a,b,c,d) Quantités en stock : 45, 25, 25 Demande des clients : 30,10, 20, 30 Limitations en matière de transport d’un entrepôt

à un clienta b c d

1 10 15

- 20

2 20 5 5 -

3 - - 10 10

E

1

2

3

a

b

d

c

S

[0,10]

[0,15]

[0,20]

[0,20]

[0,5]

[0,5][0,10]

[0,10]

[0,45]

[0,25][0,25]

[0,30]

[0,10]

[0,20]

[0,30]

Le Problème de flotsExemple de flot complet


Le Problème de flotsExemple de flot complet

E

1

2

3

a

b

d

c

S

[0,10], 10

[0,15], 5

[0,20], 20

[0,20], 15

[0,5], 5

[0,5], 5

[0,10], 10

[0,10], 10

[0,45], 35

[0,25], 25

[0,25], 20

[0,30], 25

[0,10], 10

[0,20], 15

[0,30], 30

Valeur du flot = 80

Ce flot est un flot complet, c-à-d, tout chemin de E à S comporte au moins un arc saturé


Le Problème de flotsAlgorithme de Ford- Fulkerson

Cas d’utilisation :Problèmes de charge maximaleadmissible par des réseaux (électriques,

informatiques, routiers) Principe fondamental :A tout moment, la loi deKirchhoff doit être vérifiée sur chaque sommet x de G But : Augmenter le flot jusqu’à son maximum tout en respectant cette règle



Principe général : On part d’un flot compatible

(généralement 0)

On utilise deux fonctions alternativement Procédure de marquage Procédure d’augmentation du flot



Procédure de marquage But :

trouver une chaîne améliorante Principe :

Marquage des sommets selon deux critères : Delta (flot max que l’on peut faire parvenir au

sommet) Sommet de provenance



Procédure d’augmentation du flot But :

augmenter le flot dans le graphe selon la valeur et le marquage obtenu par la procédure de marquage

Principe : Parcours du graphe du puit vers la source suivant

les indications de provenance de la procédure de marquage



a

7

Capacité

b

c

d S P

e

10

8

3

3

8

4

2

3 4

7

6 4

Chercher le flot complet du réseau.



a (+S)

7

Capacité

b (+S)

c (+a)

d (+a)

S (+)

P (+c)

e (+b)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[0]

[0]

[0]

[0]

[0] [0]

[0]

[0] [0]

[0] [0]

[0]

[0]

1er marquage



4/ 11 vf

a (+S)

7

Capacité

b (+S)

c (+a)

d (+a)

S (+)

P (+c)

e (+b)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[0]

[4]

[4]

[0]

[0] [0]

[0]

[0] [0]

[0] [4]

[0]

[0] On remarque que le flot est complet dans , cet arc est saturé.

Pc

Le flot sur cette chaîne est maintenant F1=4



a (+S)

7

Capacité

b (+S)

c (+a)

d (+a)

S (+)

P (+d)

e (+b)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[0]

[4+3]

[4]

[3]

[0] [0]

[0]

[0] [0]

[0] [4]

[3]

[0]

Le flot sur cette chaîne est maintenant F2=3

:cet arc est saturé.aS



a (-c)

7

Capacité

b (+S)

c (+b)

d (+b)

S (+)

P (+d)

e (+b)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[3]

[7]

[4]

[3]

[0] [0]

[3]

[0] [0]

[0] [4]

[3+3]

[0]

F3=3

db Est saturé



a (-c)

7

Capacité

b (+S)

c (+b)

d (+b)

S (+)

P (+e)

e (+b)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[3+3]

[7]

[4]

[3]

[0] [0]

[3]

[3] [0]

[0] [4]

[6]

[3]

F4=3

eb Est saturé


a (-c)

7

Capacité

b (+)

S)

c (+b)

d (+c)

S

(+)

P (+d)

e (+d)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[6+1]

[7]

[4]

[3]

[0] [1]

[3]

[3] [0]

[1] [4]

[6+1]

[3]

F5=1

Pd Est saturé




a (-c)

7

Capacité

b (+S)

c (+b)

d (+c)

S (+)

P (+e)

e (+d)

10

8

3

3

8

4

2 3

4

7

6 4

[] Flot

() Marquage

[7+1]

[7]

[4]

[3]

[0] [1+1]

[3]

[3] [1]

[1+1] [4]

[7]

[3+1]

F6= 1

cb Est saturé15/)( vPSf


CONCLUSION

Documents

GESTION DU PROBLEME DE TRANSPORT Réalisé par : Salma ADNAN & Ghita ACHOUAK 2008-2009