Troisime partie

Le problme de transport7 Dfinition et exemples Un produit doit tre transport de sources (usines) vers des destinations (dpts, clients). Objectif : dterminer la quantit envoye de chaque source chaque destination en minimisant les cots de

transport. Les cots sont proportionnels aux quantits transportes. Contraintes doffre limite aux sources et de demande satisfaire au destinations.

Sources Destinations1

2

1

2

m n

a1

a2

am

b1

b2

bncm n xm n

Exemple 18 (Modle de transport). Une firme automobile a trois usines Los Angeles, Detroit et New Orleans, et deux centres de distribution

Denver et Miami. Les capacits des trois usines sont de 1000, 1500 et 1200 respectivement, et les demandes aux centres de

distribution sont de 2300 et 1400 voitures. Cots :

Denver MiamiLos Angeles 80 215

Detroit 100 108New Orleans 102 68

Formulation

min z = 80x11 +215x12 +100x21 +108x22 +102x31 +68x32s.c.

(Los Angeles) x11 +x12 = 1000(Detroit) x21 +x22 = 1500

(New Orleans) x31 +x32 = 1200(Denver) x11 +x21 +x31 = 2300(Miami) x12 +x22 +x32 = 1400

x11, x12, x21, x22, x31, x32 0

Reprsentation tableau

30

Denver Miami OffreLos Angeles 80 215 1000

1000Detroit 100 108 1500

1300 200New Orleans 102 68 1200

1200Demande 2300 1400

Problmes non balancs Si loffre nest pas gale la demande : modle non balanc. Introduction dune source ou destination artificielle.

Denver Miami OffreLos Angeles 80 215 1000

1000Detroit 100 108 1300

1300New Orleans 102 68 1200

1200Artif. 0 0 200

200Demande 2300 1400

VariantesLe modle de transport nest pas limit au transport de produits entre des sources et destinations gographiques.

Exemple 19 (Modle de production). Une socit fabrique des sacs dos, pour lesquels la demande arrive de mars juin et est de 100, 200, 180 et

300 units, respectivement. La production pour ces mois est de 50, 180, 280 et 270, respectivement. La demande peut tre satisfaite

1. par la production du mois courant ($40 / sac) ;

2. par la production dun mois prcdent (+ $0.5 / sac / mois pour le stockage) ;

3. par la production dun mois suivant (+ $2 / sac / mois de pnalit de retard).

Correspondances avec le modle de transport

Transport Production - stocksSource i Priode de production i

Destination j Priode de demande jOffre la source i Capacit de production la priode i

Demande la destination j Demande pour la priode jCot de transport de i j Cot unitaire (production + stock + pnalit)

pour une production en priode i pour la priode j

8 Algorithme pour le problme de transport

Algorithme pour le problme de transportBas sur lalgorithme du simplexe en tenant compte de la structure du problme.

1. Dtermination dune solution de base admissible.

2. Dtermination de la variable entrant en base.

31

3. Dtermination de la variable sortant de base.

Exemple 20 (Algorithme pour le problme de transport).

1 2 3 4 Offre1 10 2 20 11 15

2 12 7 9 20 25

3 4 14 16 18 10

Demande 5 15 15 15

Dtermination dune solution de base admissible Heuristiques "gloutonnes", pas besoin de mthode des deux phases. Variantes :

1. Coin Nord-Ouest

2. Mthode des moindres cots

Coin Nord-OuestPartir du coin suprieur gauche du tableau.

1. allouer le plus possible la cellule courante et ajuster loffre et la demande ;

2. se dplacer dune cellule vers la droite (demande nulle) ou le bas (offre nulle) ;

3. rpter jusquau moment o toute loffre est alloue.

Exemple 21 (Coin Nord-Ouest).

1 2 3 4 Offre1 10 2 20 11 15

5 102 12 7 9 20 25

5 15 53 4 14 16 18 10

10Demande 5 15 15 15

Cot : 520

Moindres cotsSlectionner la cellule de cot minimum.

1. allouer le plus possible la cellule courante et ajuster loffre et la demande ;

2. slectionner la cellule de cot minimum ayant une demande et une offre non nulles ;

3. rpter jusquau moment o toute loffre est alloue.

Exemple 22 (Moindres cots).

1 2 3 4 Offre1 10 2 20 11 15

152 12 7 9 20 25

15 103 4 14 16 18 10

5 5Demande 5 15 15 15

Cot : 475

32

Formulation

min z =

mi=1

nj=1

cijxij

s.c. (ui)n

j=1

xij = ai i = 1, . . . ,m

(vj)

mi=1

xij = bj j = 1, . . . , n

xij 0 i = 1, . . . ,m, j = 1, . . . , n

Problme dual

max w =

mi=1

aiui +

nj=1

bjvj

s.c. ui + vj cij i = 1, . . . ,m, j = 1, . . . , n

Adaptation du simplexeCritre doptimalit :

ui + vj cij 0Complmentarit :

xij > 0 ui + vj cij = 0Trois tapes : 1. dtermination des variables duales (multiplicateurs) ;

2. vrification du critre doptimalit et dtermination de la variable entrante ;3. dtermination de la variable sortante pour prserver ladmissibilit et pivotage.

Dtermination des variables duales1. m+ n 1 quations m+ n inconnues : fixer u1 = 0.2. Rsoudre rcursivement le systme

ui + vj cij = 0 pour tout xij > 0.

Exemple 23 (Dtermination des variables duales).

1 2 3 4 Offre1 10 2 20 11 15

5 102 12 7 9 20 25

5 15 53 4 14 16 18 10

10Demande 5 15 15 15

u1 = 0u1 + v1 = 10 v1 = 10u1 + v2 = 2 v2 = 2u2 + v2 = 7 u2 = 5u2 + v3 = 9 v3 = 4u2 + v4 = 20 v4 = 15u3 + v4 = 18 u3 = 3

33

Vrification du critre doptimalit et dtermination de la variable entrante

1 10 2 2 3 4 4 15 Offre1 10 2 20 11 150 5 10 -16 42 12 7 9 20 255 3 5 15 53 4 14 16 18 103 9 -9 -9 10

Demande 5 15 15 15

Dtermination de la variable sortante pour prserver ladmissibilit et pivotage

Objectifs : 1. loffre et la demande doivent continuer tre satisfaites ;2. les quantits transportes doivent rester positives.

Mthode : 1. construction dun cycle parcourant des variables en base en partant de et revenant la variableentrante ;

2. dplacement le long de lignes et colonnes en alternant ajout et retrait dune mme quantit.

1 10 2 2 3 4 4 15 Offre1 10 2 + 20 11 150 5 10 -16 42 12 7 9 20 + 255 3 5 15 53 4 + 14 16 18 103 9 -9 -9 10

Demande 5 15 15 15

= 5

1 1 2 2 3 4 4 15 Offre1 10 2 20 11 + 150 -9 15 -16 42 12 7 + 9 20 255 -6 0 15 103 4 14 16 18 103 5 -9 -9 5

Demande 5 15 15 15

= 10

1 -3 2 2 3 4 4 11 Offre1 10 2 20 11 150 -13 5 -16 102 12 7 9 20 255 -10 10 15 -43 4 14 16 18 107 5 -5 -5 5

Demande 5 15 15 15

9 Le problme de transbordement Extension du modle de transport : il est parfois ncessaire (ou moins cher) dutiliser des noeuds intermdiaires

pour le transport. Deux usines P1 et P2 servent 3 vendeurs D1, D2 et D3, via deux centres de transit T1 et T2.

34

1000

1200

P1

P2

D1

D2

D3

800

900

500

3

5

8

6

4

9

2

4

T1

T2

7

5

3

Transformation en problme de transport 3 types de noeuds :

Noeuds doffre purs : arcs sortants uniquement. offre = offre originaleNoeuds de demande purs : arcs entrants uniquement. demande = demande originaleNoeuds de transbordement : arcs entrants et sortants. offre/demande = offre/demande originale + buffer

Les noeuds de transbordement sont la fois sources et destinations pour le problme de transport. Buffer : quantit ncessaire pour transporter toute la demande travers le noeud de transbordement. Dans notre exemple : B = 2200.

T1 T2 D1 D2 D3 OffreP1 3 4 M M M 1000P2 2 5 M M M 1200T1 0 7 8 6 M 2200T2 M 0 M 4 9 2200D1 M M 0 5 M 2200D2 M M M 0 3 2200

Demande 2200 2200 3000 3100 500

35