[PDF] Chapitre 6 Problèmes de transport

View - Download Chapitre 6 Problèmes de transport

Previous PDF

Next PDF

Chapitre 6

Problèmes de transport

Il s"agit de déterminer la façon optimale d"acheminer des biens à partir de m entrepôts et de

les transporter vers n destinations et cela à moindre coût. Nous allons faire l"hypothèse que

toute la marchandise de tous les entrepôts doit être acheminer vers les différentes destina-

tions.

Nous allons illustrer ce problème à partir de l"exemple suivant.EntrepôtSherbrookeDrummondvilleSt-GeorgesRimouskiOffre

Montréal147 $121 $344 $552 $450 T

Québec241 $153 $102 $312 $450 T

Chicoutimi451 $364 $557 $285 $750 T

Demande400 T450 T550 T250 T1650 T

On notera que l"offre totale est bien égale à la demande ce qui est conforme à l"hypothèse

ci-dessus.Montréal

Québec

ChicoutimiSherbrooke

Drummondville

St-Georges

Rimouski

1

2CHAPITRE 6. PROBLÈMES DE TRANSPORT

Mise en équation

Le problème général de transport sous l"hypothèse que l"offre totale égale la demande,

s"énonce comme suit. Notons les sources parS1;S2;:::;SmetD1;D2;:::;Dnles destina- tions. On introduit les notations suivantes : x ij=quantité transportée deSiàDj, c ij=coût unitaire du transport deSiàDj, a i=offre de la sourceSi, b j=demande de la destinationDj. On suppose que lesaisont positifsai0et de même pour lesbj0. Il s"agit de minimiser le coût de transport. La fonction objective s"écrit : z=X i;jc ijxij sous les contraintes

Offre :

nX j=1x ij=ai08i= 1;2;:::;m;

Demande :

mX i=1x ij=bj08j= 1;2;:::;n;

Positivité :xij0:

Proposition

6.0.1 Une condition nécessaire et suffisante pour que le problème de trans-

port admet une solution optimale est que m X i=1a i=nX j=1b j: Démonstration:Sixest une solution qui vérifie les contraintes, on a que n X j=1x ij=ai=)X i;jx ij=mX i=1a i m X i=1x ij=bj=)X i;jx ij=nX j=1b j

Ceci implique

mX i=1a i=nX j=1b j

6.1. PROPRIÉTÉS DE LA MATRICEA3

Inversement, si

Pm i=1ai=Pn j=1bj=T, on pose x ij=aibjT 0: Montrons que ce choix dexvérifie les contraintes. En effet n X j=1x ij=1T n X j=1a ibj=aiP n j=1bjT =ai et mX i=1x ij=1T m X i=1a ibj=bjP m i=1aiT =bj

De plus, l"ensemble des solutions réalisables est borné. Il suffit d"observer que, pour une paire

d"indices i et j,nX j=1x ij=ai0 =)0xijai Par conséquent, le problème admet une solution optimale.6.1 Propriétés de la matriceA Le problème de transport s"écrit de manière matricielle minz=ctx; Ax=d; x0:(6.1) oùx= (x11;x12;:::;x1n;x21;:::;x2n;:::xmn). C"est-à-dire que l"on déroule la matricexij suivant les lignes. On fait de même pourc= (c11;:::;c1n;c21;:::;cmn). Il y anmvariables etn+mcontraintes. Le vecteurdcorrespond àd= (a1;a2;:::;am;b1;b2;:::;bn).

Illustrons la matriceApourm= 3etn= 4.

A=2 6

666666641 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 13

7

77777775

La somme des n premières lignes donne

L

1+L2++Ln= (1;1;:::;1):

4CHAPITRE 6. PROBLÈMES DE TRANSPORT

Aussi, aa somme des lignesn+ 1àn+mdonne

L n+1+Ln+2++Ln+m= (1;1;:::;1):

Si on combine ces deux résultats, on obtient

L

1+L2++LnLn+1Ln+2 Ln+m= 0

Ceci implique que

rg(A)< m+n:

Proposition

6.1.1 On a les propriétés suivantes pour la matriceA.

Chaque colonne contient exactement deux entrées non nulles et qui sont égales à 1.

Le rang deAest égal àm+n1.

Chacune des lignes est une combinaisons linéaire des autres lignes. Il y a toujours une ligne de trop que l"on peut éliminer. Il y a exactementm+n1variables de base réalisables. Donnons une idée de la preuve que le rang deAestm+n1. En renumérotant si nécessaire, il suffit de montrer que les lignesL2;L3;:::;Lm+nsont linéairement indépendantes. Pour cela, posons

2L2+3L3++m+nLm+n= 0:

A cause de la structure particulière de la matrice, ceci implique immédiatement que m+1=m+2==m+n= 0:

Par la suite, on aura les relations

2+m+1= 0 =)2= 0;

3+m+1= 0 =)3= 0;...

m+m+1= 0 =)m= 0:

6.2 Dual du problème de transport

Un problème de transport est de la forme

minz=X i;jc ijxij=ctx

6.2. DUAL DU PROBLÈME DE TRANSPORT5

sous les contraintes

8i= 1;2;:::;mPn

j=1xij=ai()A1x=a

8j= 1;2;:::;nPm

i=1xij=bj()A2x=b x ij0()x0

Sous forme compact, ceci s"écrit

minz=ctx 2 6 64A
1 A1 A 2 A23 7 75x2
6 64a
a b b3 7 75
x0:

Le dual est

maxz=atu+atu+btv+btv

At1At1At2At22

6 64u
u v v 3 7 75c
u +;u;v+;v0:

C"est-à-dire avecu=u+uetv=v+v, on obtient

maxz=atu+btv A t1u+At2vc u;vlibres Or A t1u+At2vc()ui+vjcij Supposons quexsoit la solution optimale du problème. Selon les conditions KKT, on a x t(cAt1uAt2v) = 0

On a les relations

u i+vj=cij8xi;j>0 Sixest solution de base non dégénéré, on a bien la décompositionui+vj=cijpour les indices des variables de base.

6CHAPITRE 6. PROBLÈMES DE TRANSPORT

6.3 Méthode du simplexe appliquée au problème de trans-

port

Voici la démarche qui sera utilisée :

a)

T rouverune solution réalisable de b ase.

b) Commen tpasser à une autre solution de base adjacen te. c)

Déterminer si la solution est optimale.

6.3.1 Détermination d"une solution réalisable de base

A.Méthode du coin nord-ouest

Démarche :

a) On débu tepar la case (1;1)(coin nord-ouest). Allouer à cette case la quantité la plus grande possible afin de satisfaire la demandejou bien d"épuiser la sourcei. b) Si la source iest épuisée, rayer la lignei. Si la demandejest satisfaite, rayer la colonnej. c) On recommence l"étap e(a )à partir de la sous-matrice.

Par exemple :D

1D 2D 3D

4Offre

S

140050450

S

240050450

S

3500250750

Demande400450550250

Les variables de base sont

x

11;x12;x22;x23;x33;x34

pour un total de6 =m+n1variables carm= 3etn= 4. Le coût associé à cette solution estz= 480;900. En terme de graphe, on obtient la représentation

6.3. MÉTHODE DU SIMPLEXE APPLIQUÉE AU PROBLÈME DE TRANSPORT7

qui est un arbre partiel générateur du graphe biparti (non orienté) associé au problème

de transport. Ce qui montre bien quexest une solution de base.

Remarque 6.3.1

métho defacile, ne tien tpas compte des coûts de transp ort, loin de la solution optimale, la moins efficace.

B.Méthode de l"entrée minimale

Démarche :

a) Choisir la case (i;j)de coût minimal. Allouer à cette case la quantité la plus grande possible afin de satisfaire la demandejou bien d"épuiser la sourcei. b) Si la source iest épuisée, rayer la lignei. Si la demandejest satisfaite, rayer la colonnej. c) O nrecommence l"étap e(a )à partir de la sous-matrice.

Par exemple :D

1D 2D 3D

4Offre

S

1450450

S

2450450

S

3400100250750

Demande400450550250

Les variables de base sont

x

12;x23;x31;x33;x34

avec un total de5<6 =m+n1variables de base. Donc la solution de base est

dégénérée. Le coût associé à cette solution estz= 407;700. Ceci est mieux que la

solution du coin nord-ouest. En terme de graphe, on obtient la représentation

qui est un arbre partiel générateur du graphe biparti (non orienté) associé au problème

de transport. Toutefois, ce sous-graphe n"est pas connexe. Il faut lui ajouter une arête, par exemple celle associée à la variablex22. Ce qui montre bien quexest une solution de base.

8CHAPITRE 6. PROBLÈMES DE TRANSPORT

6.3.2 Passage à une solution de base adjacente

Nous allons utiliser la technique des coûts duaux telle que présentée à la section 6.2. Etant

donné une solution de basex, la méthode consiste à déterminer une décomposition des coefficientscij(les coûts de transport) de la forme c ij=ui+vj pour les indices correspondants à ceux de la solution de base. Il y am+n1équations pourm+ninconnues. Dans la pratique, on poseu1= 0et on résoud pour les autres variables. Reprenons notre exemple du début. Pour chaque case, on affiche le coefficientcijqui est sont encadré et la solution de base. La case est vide si la variable est hors-base. Démarrons avec la solution fournie par la méthode du coin nord-ouest.40014750121344552450

24140015350102312450

451364500557250285750

4004505502501650

On évalue les coûts duauxcij=ui+vjde la manière suivante c

11=u1+v1()147 = 0 +v1=)v1= 147;

c

12=u1+v2()121 = 0 +v2=)v2= 121;

c

22=u2+v2()153 =u2+ 121 =)u2= 32;

c

23=u2+v3()102 = 32 +v3=)v3= 70;

c

33=u3+v3()557 =u3+ 70 =)u3= 487;

c

34=u3+v4()285 = 487 +v4=)v4=202:

Il est pratique d"ajouter ces informations dans le tableau40014750121344552450u

1= 024140015350102312450u

2= 32451364500557250285750u

3= 4874004505502501650

v

1= 147v

2= 121v

3= 70v

4=202

6.3. MÉTHODE DU SIMPLEXE APPLIQUÉE AU PROBLÈME DE TRANSPORT9

Faisons entrer la variablex32dans la base. Il faudra identifier la variable qui sortira de la base et calculer la valeur de cette variablex32=.D 1D 2D 3D 4S

140050450

S

240050 +450

S

3500250750

400450550250

Le choix dedoit repecter la contrainte de positivité 4000
0 5000

50 +0=)400

Si on choisit= 400, la case(2;2)devient nulle et donc la variablex22sort de la base. La nouvelle solution de base estD 1D 2D 3D 4S

140050450

S

2450450

S

3400100250750

400450550250

Nous allons évaluer de combien la fonction objectiveza changé par unité de. Pour cela, on suit le cycle (3;2)!(3;3)!(2;3)!(2;2)

Suivant ce trajet, la variation s"écrit

z=c32c33+c23c22 =c32(u3+v3) + (u2+v3)(u2+v2) =c32u3v2 Dans notre exemple, ceci correspond àz=c32u3v2= 364487121 =244. Par conséquent, il est profitable de faire entrer dans la base la variablex32car la valeur dez diminue.

10CHAPITRE 6. PROBLÈMES DE TRANSPORT

Démarche :

a) A une solution de base donnée, év aluerles coûts duaux ui+vj=cij. b) P ourtoutes les cases hors-base, év aluerla quan titéz=cijuivj. c)

La solution de base sera optimale si tous les z0.

d) Sinon, c hoisirla ca sequi minimise la v aleurde z <0et recommencer le processus. Appliquons cette démarche à partir de la la solution fournie par la méthode du coin nord-

ouest. Nous avons déjà calculer les coûts duaux. Il suffit d"ajouter le valeurs (entre parenthèse)

z=cijuivjpour les cases hors-base40014750121(274)344(754)552450u

1= 0(62)24140015350102(482)312450u

2= 32(183)451(244)364500557250285750u

3= 4874004505502501650

v

1= 147v

2= 121v

3= 70v

4=202Suivant cette approche, c"est bien la case(3;2)qui diminuer le plus rapidement la fonction

objectivez. Autrement dit, la solution de base calculée avec la valeur de= 400est bien celle fournie par l"algorithme.

Poursuivons les calculs à partir de cette étape. On doit mettre à jour les coûts duaux avec

la nouvelle base. On obtient le tableau40014750121(+)344(+)552450u

1= 0(+)241(+)153450102(+)312450u

2=212(+)451400364100557250285750u

3= 2434004505502501650

v

1= 147v

2= 121v

3= 314v

4= 42qui montre qu"il est optimal. Donc la solution optimale sera

D 1D 2D 3D 4S

140050450

S

2450450

S

3400100250750

400450550250

avecz= 383;300comme valeur minimale.

6.3. MÉTHODE DU SIMPLEXE APPLIQUÉE AU PROBLÈME DE TRANSPORT11

Exemple

6.3.1 Considérons le problème de transport suivant les notations adoptées

précédemmentD 1D 2D 3S

18106100

S

274980

S

31312845

906075225

a) On démarre a vecla solution du coin nord-ouest et on év alueles co ûtsduaux. D 1D 2D 3S

19081010(9)6100u

1= 0S

2(5)750430980u

2=6S

3(12)13(9)1245845u

3=7906075225

v 1= 8v

2= 10v

3= 15b)La case (1;3)entre dans la base. On doit trouver celle qui quitte.D

1D 2D 3S

19010100

S

250 +3080

S 34545

906075225

Donc= 10ce qui conduit à la solution de baseD

1D 2D 3S

19010100

S

2602080

S 34545

906075225

12CHAPITRE 6. PROBLÈMES DE TRANSPORT

Les coûts duauxD

1D 2D 3S

1908(9)10106100u

1= 0S

2(4)760420980u

2= 3S

3(2)13(8)1245845u

3= 3906075225

v 1= 8v 2= 1v

3= 6c)La case (2;1)entre dans la base. On doit trouver celle qui quitte.D

1D 2D 3S

19010 +100

S

2602080

S 34545

906075225

Donc= 20ce qui conduit à la solution de baseD

quotesdbs_dbs47.pdfusesText_47

[PDF] Mise En Mouvement ( Arts Plastique )

[PDF] mise en oeuvre de l'échellle de teintes

[PDF] mise en page d'un scénario

[PDF] mise en page d'une dissertation

[PDF] mise en page d'une lettre

[PDF] mise en page définition

[PDF] mise en page design graphique

[PDF] mise en page design inspiration

[PDF] mise en page design word

[PDF] mise en page exemple

[PDF] mise en page graphique epuré

[PDF] mise en page livre open office

[PDF] mise en page magazine gratuit

[PDF] mise en page magazine indesign

[PDF] mise en page mémoire marge