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] Problèmes de transport - formulation des problèmes daffectation - FR
31 mar 2009 · transport • Certains problèmes en programmation linéaire ont une structure particulière que l'on peut exploiter ; • On peut les résoudre comme
[PDF] Chapitre 5 : Le problème de transport
L'algorithme du simplexe est valable pour tout problème de programmation linéaire ; mais il n'est pas nécessairement le plus efficace pour traiter des problèmes
[PDF] INFO-F-310 - Algorithmique 3 et Recherche Opérationnelle
4 3 Forme standard et forme canonique d'un programme linéaire 8 8 Algorithme pour le problème de transport 31 9 Le problème de
[PDF] Problèmes de transport - Thèses
linéaire (noté : PL) lorsque sa fonction-objectif et ses contraintes sont linéaires Un problème de programmation linéaire consiste à minimiser (ou à maximiser)
[PDF] Chapitre 7 Le problème de transport classique - Solutions
minimaux Pour obtenir l'autre, on a effectué une itération de l'algorithme du transport : (3,1) fut (a) Le problème de transport considéré admet une seule solution optimale, car les coûts marginaux des cases hors 600 12 Modèle linéaire
[PDF] Problème du transport - Faculté des Sciences
COURS N°10 : Problème de transport 1 10 L Amrani 1) Introduction Le problème du transport est un programme linéaire qui a une structure particulière
[PDF] probleme de transport exercices corrigés pdf
[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
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
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 : ij=quantité transportée deSiàDj, ij=coût unitaire du transport deSiàDj, i=offre de la sourceSi, 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 :
j=1x ij=ai08i= 1;2;:::;m;Demande :
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 i=1a i=nX j=1b Démonstration:Sixest une solution qui vérifie les contraintes, on a que j=1x ij=ai=)X i;jx ij=mX i=1a i=1x ij=bj=)X i;jx ij=nX j=1bCeci implique
i=1a i=nX j=1b6.1. PROPRIÉTÉS DE LA MATRICEA3
Inversement, si
i=1ai=Pn j=1bj=T, on pose ij=aibjT Montrons que ce choix dexvérifie les contraintes. En effet j=1x ij=1T j=1a ibj=aiP j=1bjT =ai i=1x ij=1T i=1a ibj=bjP 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=2666666641 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1 11 1 13
77777775
La somme des n premières lignes donne
1+L2++Ln= (1;1;:::;1):
4CHAPITRE 6. PROBLÈMES DE TRANSPORT
Aussi, aa somme des lignesn+ 1àn+mdonne
n+1+Ln+2++Ln+m= (1;1;:::;1):Si on combine ces deux résultats, on obtient
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, 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 ij0()x0Sous forme compact, ceci s"écrit
minz=ctx 64AA23 75x2
64a
x0:
Le dual est
maxz=atu+atu+btv+btvAt1At1At2At22
64u75c
+;u;v+;v0: