xij = ai ≥ 0 =⇒ 0 ≤ xij ≤ ai Par conséquent, le problème admet une solution optimale 6 1 Propriétés de la matrice A Le problème de transport s'écrit de manière
Previous PDF | Next PDF |
[PDF] Chapitre 6 Problèmes de transport
xij = ai ≥ 0 =⇒ 0 ≤ xij ≤ ai Par conséquent, le problème admet une solution optimale 6 1 Propriétés de la matrice A Le problème de transport s'écrit de manière
[PDF] Chapitre 7 Le problème de transport classique - Solutions
Chapitre 7 Le problème de transport classique - Solutions 1 La méthode du coin nord-ouest U1 E1 E2 E3 E4 E5 21 17 12 15 16 125 125 U2 14 18 9
[PDF] Problème de transport
3 1 4 Algorithme général de résolution de problème de transport 31 à optimiser en fonction des variable du problème z φ n 3 j(" cjxj φ c"x" + c#x# +
[PDF] Problèmes de transport - Thèses
Dans à la deuxième partie de cette thèse, nous abordons le problème de K- clusters dans un graphe biparti, qui est aussi un problème de l'optimisation com-
[PDF] Le problème de transport
Exemple 17 (Modèle de transport) – Une firme automobile a trois usines à Los Angeles, Detroit et New Orleans, et deux centres de distribution à Denver et
[PDF] Problèmes de transport - formulation des problèmes daffectation - FR
31 mar 2009 · Formulez le problème pour minimiser le coût pour alimenter toutes les villes Page 5 Problèmes de Transport Solution des problèmes de
[PDF] Optimisation des flux dans les réseaux de transport pour - OATAO
réseaux de transport et le problème du flot de coût minimum sont définis Les caractéristiques, la composition, ainsi que les dynamiques des systèmes
[PDF] Un problème de transport détaillé
Dans un premier temps on va utiliser la méthode de Ballas Hammer pour trouver une solution réalisable en tenant compte des coûts Pour cela on va calculer
[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] telecharger exercices de recherche operationnelle
[PDF] recherche opérationnelle exercices corrigés gratuit
[PDF] cours de recherche operationnelle gratuit pdf
[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
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éalQuébec
ChicoutimiSherbrooke
Drummondville
St-Georges
Rimouski
12CHAPITRE 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 contraintesOffre :
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 jCeci implique
mX i=1a i=nX j=1b j6.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 =bjDe 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 6666666641 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1 11 1 13
777777775
La somme des n premières lignes donne
L1+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
L1+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, posons2L2+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=ctx6.2. DUAL DU PROBLÈME DE TRANSPORT5
sous les contraintes8i= 1;2;:::;mPn
j=1xij=ai()A1x=a8j= 1;2;:::;nPm
i=1xij=bj()A2x=b x ij0()x0Sous forme compact, ceci s"écrit
minz=ctx 2 6 64A1 A1 A 2 A23 7 75x2
6 64a
a b b3 7 75
x0:
Le dual est
maxz=atu+atu+btv+btvAt1At1At2At22
6 64uu 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) = 0On 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-
portVoici 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 3D4Offre
S140050450
S240050450
S3500250750
Demande400450550250
Les variables de base sont
x11;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ésentation6.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.