[PDF] [PDF] Chapitre 6 Problèmes de transport

View - Download [PDF] 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.

quotesdbs_dbs35.pdfusesText_40

[PDF] exos corrigés problème d'affectation recherche opérationnelle

[PDF] développement limité fonction plusieurs variables

[PDF] recherche opérationnelle exercices corrigés gratuit

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule