[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, posonsquotesdbs_dbs2.pdfusesText_2

[PDF] problème de transport stepping stone

[PDF] exercice corrige résolution du problème de transport en recherche opérationnelle

[PDF] transport et probléme d affectations

[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