Le problème du plus court chemin : exercices- corrigé
Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus court chemin : exercices- corrigé I 0 0 1 0 2 0 3 0 4 0 1 2 1 1 2 2 2 1 3 2 3 1 Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse, il peut être de 0, 1 ou 2 Les arcs sont associés aux décisions Initialement, le stock est
Résolution des problèmes de plus court chemin – exercices
Le plus court chemin de 0 à 4 est le chemin 0 – 2 - 4 Il faut produire 4 unités en période 1 et 4 unités en période 3 III Les longueurs sont positives, on pourrait appliquer l'algorithme de Moore Dijkstra, mais on peut vérifier que ce graphe est sans circuit auquel cas il vaut mieux appliquer l'algorithme de Bellman qui
Exercices“Pluscourtschemins” :Correction
Exercices“Pluscourtschemins” :Correction 19 octobre 2016 1 2 3 Ilsuffitd’appliquerlafonctionlog surlespoids 4 L’algorithme reste le même, mais on met à jour l’étiquette d’un sommet v en faisant (v) :=
TD9 : plus court chemin dans un graphe
TD9 : plus court chemin dans un graphe Exercice 1 Un graphe orient e pond er e G est donn e par la matrice d’incidence sui-vante, ou les sommets du graphe sont s;a;b;c;d et t et ou il existe une ar^ete du sommet s 1 vers le sommet s 2 si et seulement si la case situ ee a l’intersec-tion de la ligne s 1 et de la colonne s
Lycée JANSON DE SAILLY Année 2017-2018 GRAPHES PLUS COURT
Année 2017-2018 GRAPHES: PLUS COURT CHEMIN Tle ES 4 EXERCICE 1 Le graphe ci-dessous indique les différentes liaisons entre plusieurs lieux Le long de chaque arête figure la distance en kilomètres séparant les différents lieux En précisant la méthode utilisée, déterminer le plus courtchemin possible pour aller deAàL A E I B F J C
SUJET + CORRIGE
Exercice 4: Variantes plus court chemin à origine unique (8 points) L’algorithmedeDijkstra Initialisation (G, s){ // G(S,A,w) oriente pour u dans S faire
Recherche Opérationnelle - LORIA
–soit ce plus court chemin passe par le sommet k+ 1 Dans ce cas il ne peut y passer qu’une seule fois (sinon il y a un circuit, de valuation totale positive par hypothèse sur le graphe, que l’on pourrait éliminer pour construire un chemin entre iet jplus court, ce qui serait absurde)
Algorithmes de Graphes, HLIN501 Ann ee 2016-2017 L3 Info, L3
a Un sous-chemin d’un plus court chemin est un plus court chemin b Si r est un sommet d’un graphe orient e D pond er e par des longueurs positives toutes distinctes, alors D poss ede une unique arborescence des plus courts chemins issue de r c Dans tout graphe G non orient e, connexe et valu e positivement sur ses ar^etes, il existe un
Th´eorie des graphes et algorithmes - LACL
– plus court chemin – d´etection de circuit dans un graphe orient´e , d´etermination des composantes fortement connexes d’un graphe orient´e , tri topologique – ordonnancement remarque : dans les algorithmes qui seront d´ecrits, le terme FIN signifie une sortie du pro-gramme en cours d’ex´ecution 1
Travaux Diriges RO03
existe un chemin de k arcs entre i et j et 0 sinon 2 2 : On définit de même Bk la puissance k-ème matricielle Booléenne de B et l'on pose : B ^ k=I B B 2 B3 Bk Montrer que : B ^ k ij=1 s'il existe un chemin de k arcs au plus entre i et j et 0 sinon Montrer que l'on peut définir B ^ =limB ^ k pour k tend vers ∝ 2 3 : On pose de
[PDF] plus court chemin+exercices corrigés
[PDF] plus de suggestion d'amis sur facebook
[PDF] Plus de tant, il est tant
[PDF] plus fait douceur que violence
[PDF] plus grand centre commercial d'ile de france
[PDF] Plus grand commun diviseur
[PDF] plus grand commun diviseur pgcd
[PDF] Plus grand diviseur commun (devoir maison)
[PDF] PLUS GRAND DIVISEUR COMMUN ; NOMBRES PREMIERS ET NOMBRES PREMIERS ENTRE EUX
[PDF] plus grand ouragan de l'histoire
[PDF] plus grand roi de france taille
[PDF] plus grande colonie au 19 siecle
[PDF] Plus grande hauteur, avec une feuille CANSON!
[PDF] plus grande zone commerciale d'europe
Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus court chemin : exercices- corrigé I 0.0
1.02.0
3.04.0
1.2 1.12.22.1
3.2 3.1Les sommets correspondent à l'état du stock à la fin de chaque période : par hypothèse, il peut être de
0, 1 ou 2.
Les arcs sont associés aux décisions.
Initialement, le stock est nul. On doit produire 2, 3 ou 4 unités pour faire face à la demande.
Selon le cas, on terminera la première période avec un stock de 0, 1 ou 2 unités.On fait de même pour chaque sommet.
Par exemple : le sommet 1.1 correspond à une unité en stock à la fin de la première période.
Compte tenu de la demande de 2, il faut produire 1, 2 ou 3 unités. On se retrouvera avec 0, 1 ou 2 unités en stock, en fin de période 2 d'où les 3 arcs :1.1 -> 2.0 (production d'une unité)
1.1 -> 2.1 (production de 2 unités)
1.1 -> 2.2 ( production de 3 unités)
La valuation des arcs doit tenir compte des différents coûts :On note :
- Kt = coût fixe de la période t - c t = coût de production unitaire de la période t - h t = coût unitaire de stockage de la période t Pour un arc de (t-1, i) à (t , j), les coûts sont les suivants :- Si j = i - 2 il n'y a pas eu de production, le stock a diminué de la demande, sinon il faut compter un
coût de K t - Quantité produite lorsque j > i-2 : 2 + (j - i) donc coût variable de production : ct ( 2 + j-i) - Coût de stockage = h t iPar exemple en période 2 :
(1,0) -> (2,0) : K 2 + 2 c 2 on produit 2 unités - pas de stock à la fin (1,0) -> (2,1) : K 2 + 3 c 2 + h 2 c 2 on produit 3 unités - une unité en stock à la fin (1,0) -> (2,2) : K2 + 4 c
2 + 2 h 2 on produit 4 unités - deux unités en stock à la fin (1,2 ) -> (2,0) : 0 on ne produit pas - pas de stock à la fin (1,2) -> (2,1) : K 2 + c 2 + h 2 (1,2) -> (2,2) : K 2 + 2 c 2 + 2 h 2 Le problème du plus court chemin /exercices/corrigé/p2 Il n' y a plus qu'à remplacer par les valeurs numériques. Le problème du plus court chemin /exercices/corrigé/p3b) Dans ce cas, puisqu'on fait l'hypothèse qu'on ne produit que lorsque le stock s'est annulé, on peut
modéliser le problème en considérant comme décision à prendre le nombre de périodes pour
lesquelles on doit produire.La production ayant, sur cet exemple, été limitée à 4 unités, on a le schéma suivant :
01 234
Un arc (t , t' ) correspond à la décision de produite à la t+1ème période la quantité nécessaire pour
couvrir la demande des périodes t +1 à t'.Le coût associé est égal à la somme du coût fixe, du coût variable de production et du coût de
stockage:Par exemple, pour l'arc ( 1,2 ) : K
2 + 2 c 2 , pour l'arc (1,3) : K 2 + 4 c 2 + 2 h 2NB : On peut sans peine généraliser ceci dans le cas où la quantité demandée dépend de la période.
II Soient 3 tailles i , j , k avec i < j < k , on exclut d'office, ce qui ne serait sûrement pas optimal, de
fabriquer une taille i dans une taille k si la taille j est fabriquée ! Le regroupement de commandes concernera donc des tailles consécutives.On peut alors représenter le problème en considérant comme décisions les suites de taille à regrouper.
Ceci peut se représenter par un graphe dont les sommets correspondent à la taille des différentes
boites rangées par ordre croissant, complété par un sommet 0.Un arc allant du sommet i au sommet j indique que toutes les tailles commandées entre i+1 et j sont
livrées en taille j. Par exemple, l'arc (0,1) correspond à la demande pour la taille 1 fabriquée en taille 1. L'arc (1,4) correspond à la demande pour les tailles 2, 3 et 4 fabriquées en taille 4. Tous les arcs (i,j) avec j>i sont susceptibles d'exister.( Le graphe est exactement du même type que celui de remplacement de véhicule vu dans le cours).
Le coût associé à l'arc (i,j) comprend :
- le coût fixe associé à la production de la taille j- le coût variable : nombre total de boites fabriquées pour les tailles de i+1 à j, multiplié par le coût de
fabrication d'une boite de type j.Exemple :
Arc (0,1) : 2000 + 200*34
Arc (1,4 ) : 2000 + (400+200+700) *48
Une fois le graphe décrit, il suffit de d'appliquer l'algorithme adapté pour résoudre le problème.
Le problème du plus court chemin /exercices/corrigé/p4 III S = sommets à examiner dont la marque est finie ( on ne peut choisir un sommet de marque infinie)S Sommet
choisi a b c d e f g h0 + + + + + + +
a a // 4(a) 2(a) 1(a) b, c, d d // 7(d) b, c, g c 3(c) // 4(c) b, f, g b // 8(b) f, g, e f // 6(f) 6(f) g, e , h g // e, 7(h) // e e // ab c de f gh 452 11 2 2 63
2 421
0 37
16 6 4 2quotesdbs_dbs48.pdfusesText_48