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
Chapitre 7. Le problème de transport classique - Solutions
Le tableau suivant décrit les trois solutions de base rencontrées lors de la résolution de ce problème. La. 1re représentée à gauche
Problème de transport: Modélisation et résolution
particulière dans la Recherche Opérationnelle. Il est probablement le problème de programmation linéaire spécial le plus important en termes de fréquence
COURS N°10 : Problème de transport
Résolution du Problème de transport. Comme dans la méthode du simplexe la résolution se déroule en deux parties : 1. Recherche d'une solution de base réalisable.
La Recherche Tabou
16/11/2004 les avantages de la RT dans le problème de transport. • L ... • Présentation de la résolution d'un problème de job shop dans. Excel à l'aide ...
RECHERCHE OPERATIONNELLE
Application numéro 8 : EXERCICES AUTO CORRIGES. Page 21. RECHERCHE ○ Le sujet n'aborde pas la résolution du problème posé par l'usage matriciel.
Étude et résolution exacte de problèmes de transport à la demande
10/11/2010 ... Recherche Opérationnelle . . . . 16. 2 Optimisation du calcul des tournées de véhicules : « Dial-A-Ride Problem ». 21. 2.1 Étatdel'art ...
Livret dexercices Théorie des Graphes et Recherche Opérationnelle
29/08/2016 (Exercices et problèmes résolus de recherche opérationnelle Dunod) dont ... Proposez une modélisation par graphe de la résolution du problème.
Un problème de transport détaillé.pdf
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.
INTRODUCTION À LA RECHERCHE OPÉRATIONNELLE
problème traditionnel de recherche opérationnelle dont la résolution rapide permet un tel codage. On reconnaît un problème du type problème de transport de ...
Chapitre 7. Le problème de transport classique - Solutions
Le tableau suivant décrit les trois solutions de base rencontrées lors de la résolution de ce problème. La. 1re représentée à gauche
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
RECHERCHE OPERATIONNELLE
1 - Programmation linéaire : Résolution par le graphique le simplexe et le calcul matriciel. 2 - Problèmes d'ordonnancement de projet : Modélisation du
Problèmes de transport - formulation des problèmes daffectation
31 mar. 2009 solution est en entier aussi mais la résolution n'est pas plus difficile. • Le mieux est de donner un exemple. Page 4. Problèmes de Transport ...
Exercice de recherche opérationnelle Probl`eme de transf`erement
On pourrait ainsi tout `a fait le traiter en modélisant le graphe de transport (graphe biparti) et en utilisant les algorithmes classiques de calcul de flot
Étude et résolution exacte de problèmes de transport à la demande
10 nov. 2010 Spécialité : Informatique recherche opérationnelle et géomatique. Étude et résolution exacte de problèmes de transport.
Problème de transport
3.1.4 Algorithme général de résolution de problème de transport . linéaire est un outil trés puissant de la recherche opérationnelle.ckest un.
Un problème de transport détaillé.pdf
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.
Modelisation et resolution de problemes doptimisation combinatoire
11 mai 2005 apports de méthodes exactes issues de la Recherche Opérationnelle – en particulier ... comme les problèmes de transport sont plus complexes.
Théorie des graphes et optimisation dans les graphes Table des
Exercice : Dessiner un graphe non orienté complet à 4 sommets. Remarque : de nombreux problèmes en recherche opérationnelle consistent à chercher un che ...
[PDF] Chapitre 6 Problèmes de transport
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 matricielle
[PDF] Chapitre 7 Le problème de transport classique - Solutions
6 Résolution de problèmes de transport (a) Le tableau suivant décrit les deux solutions de base rencontrées lors de la résolution de ce problème
Exercices corrigés sur les problèmes de transport
Cette page présente plusieurs exercices corrigés sur les problèmes de planification et d'ordonnancement automatisés plus particulièrement sur les problèmes
[PDF] Problème de transport: Modélisation et résolution
La programmation linéaire est un outil très puissant de la recherche opérationnelle C'est un outil générique qui peut résoudre un grand nombre de problèmes En
Exercices Problème de Transport PDF Stockage de lénergie
Exercice 1 : Il sagit de planifier la production pour les mois de janvier fvrier et mars · 1/ Dterminer une solution ralisable pour ce problme laide de
[PDF] Problèmes de transport - formulation des problèmes daffectation - FR
31 mar 2009 · Problèmes de Transport Solution des problèmes de transport Problèmes d'affectation Problème de transbordement Conclusion
probleme de transport Exercices Corriges PDF
probleme de transport Exercices Corriges PDF Exercice de recherche opérationnelle Probl`eme de transf`erement exercice corrigé logistique
[PDF] Problème de transport
La programmation linéaire est un outil trés puissant de la recherche opérationnelle ckest un outil générique qui peut résoudre un grand nombre de problème
[PDF] Un problème de transport détaillé
Un problème de transport détaillé On doit transporter des marchandises de points d'offre vers les points de demande La matrice des données du problème est
[PDF] RECHERCHE OPERATIONNELLE - FORPROS
Description de l'Enseignement : 1 - Programmation linéaire : Résolution par le graphique le simplexe et le calcul matriciel 2 - Problèmes d'ordonnancement
Quels sont les problèmes liés au transport ?
Les bruits liés aux transports sont, pour les Fran?is, la première cause de gêne (aéroport, camion, deux-roues, train, métro, trafic urbain, etc.). Ils entraînent la fatigue, des troubles du sommeil, de l'inattention, de l'agressivité, voire des troubles psychologiques ou physiologiques plus important.Quels sont les solutions de transport ?
Transports urgents. ROUTIER propose des solutions de fret modernes conçues pour assurer un transport rapide et sûr des marchandises. Transport maritime. Transport aérien. ROUTIER CUSTOMIZED.- Une solution transport est le croisement d'un (ou plusieurs) mode(s) de transport et de ses modalités contractuelles d'utilisation. Pour aller d'un continent à l'autre, on peut choisir entre transport maritime et transport aérien.
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.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 3D4Offre
S1450450
S2450450
S3400100250750
Demande400450550250
Les variables de base sont
x12;x23;x31;x33;x34
avec un total de5<6 =m+n1variables de base. Donc la solution de base estdé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ésentationqui 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.4001475012134455245024140015350102312450
451364500557250285750
4004505502501650
On évalue les coûts duauxcij=ui+vjde la manière suivante c11=u1+v1()147 = 0 +v1=)v1= 147;
c12=u1+v2()121 = 0 +v2=)v2= 121;
c22=u2+v2()153 =u2+ 121 =)u2= 32;
c23=u2+v3()102 = 32 +v3=)v3= 70;
c33=u3+v3()557 =u3+ 70 =)u3= 487;
c34=u3+v4()285 = 487 +v4=)v4=202:
Il est pratique d"ajouter ces informations dans le tableau40014750121344552450u1= 024140015350102312450u
2= 32451364500557250285750u
3= 4874004505502501650
v1= 147v
2= 121v
3= 70v
4=2026.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 4S140050450
S240050 +450
S3500250750
400450550250
Le choix dedoit repecter la contrainte de positivité 40000 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 4S140050450
S2450450
S3400100250750
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)552450u1= 0(62)24140015350102(482)312450u
2= 32(183)451(244)364500557250285750u
3= 4874004505502501650
v1= 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(+)552450u1= 0(+)241(+)153450102(+)312450u
2=212(+)451400364100557250285750u
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