[PDF] Chapitre 6 Problèmes de transport

Chapitre 6 Problèmes de transport

Exemple6 3 1 Considérons le problème de transport suivant les notations adoptées précédemment D 1 D 2 D 3 S 1 8 10 6 100 S 2 7 4 9 80 S 3 13 12 8 45 90 60 75 225

Problème de flot, d’affectation et de transport

Problème de transport Présentation: Un problème de transport peut être défini comme l’action de transporter depuis "m origines" vers "n destinations" des matériaux, au moindre coût Donc, la résolution d’un problème de transport consiste à organiser le transport de façon à minimiser son coût Formulation : = production ou offre

TRANSPORTATION OPTIMIZATION FOR THE COLLECTION OF END-OF-LIFE

coûts totaux de transport Le rendement des méthodes proposées est évalué à l’aide de données recueillies auprès de l’entreprise Mots-clés : Logistique inverse, problème de tournées de véhicules, heuristique, fenêtres de temps, flotte hétérogène, routes multiples, plusieurs transporteurs externes, séquences de chargement

Optimisation des problèmes de transport multimodal

Optimisation des probl emes de transport multimodal Mod elisation et simulation Universit e du Havre, 2016 Fran˘cais < NNT : 2016LEHA0005 > HAL Id: tel-01327923

OPTIMISATION DU RÉSEAU ALGÉRIEN DE TRANSPORT DE BRUT ET DE

A Smati et al / Optimisation du réseau algérien de transport de brut et de condensat représentation mathématique de l’ensemble du système,

%NVUEDELOBTENTIONDU %0$5035%& -6/*7&34*5² %&506-064&

L’optimisation de l’exploitation d’un réseau de transport de gaz naturel (RTGN) est typiquement un problème d’optimisation multiobjectif, faisant intervenir notamment la minimisation de la consommation énergétique dans les stations de compression, la maximisation du rendement, etc

Optimisation de l’indice de consommation du poulet de chair ROSS

Optimisation de l’indice de consommation du poulet de chair ROSS Résumé Introduction L’Indice de Consommation (IC) est le ratio qui mesure la conversion de la quantité d’aliment consommé en poids vif corporel De légères différences d’IC peuvent avoir un impact sur la marge financière

[LES COÛTS D’ENTREPÔT]

d’un centre de distribution, par exemple, un système de suivi et d’étiquetage à l’infrarouge Les coûts de la formation sur les principes de base et les activités d’apprentissage continu relativement à l’entreposage Coûts liés à la manutention : En termes de coût, il faut dans certaines situations choisir entre

[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

[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é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.

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 3D

4Offre

S

140050450

S

240050450

S

3500250750

Demande400450550250

Les variables de base sont

x

11;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ésentation

6.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 3D

4Offre

Squotesdbs_dbs35.pdfusesText_40