[PDF] 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

Résolution des problèmes de plus court chemin – exercices- corrigé I Le graphe qui permet de modéliser ce problème est analogue à celui vu dans le cours

[PDF] Le problème du plus court chemin : exercices- corrigé - AUNEGE

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

[PDF] TD9 : plus court chemin dans un graphe

Exercice 1 Un graphe orienté pondéré G est donné par la matrice d'incidence sui- vante, o`u les sommets du graphe sont s, a, b, c, d et t et o`u il existe une

[PDF] Corrigé TD N° 2

Le graphe de l'exercice est planaire car on peut le représenter de la façon suivante : C un problème de plus courts chemins d'un sommet vers tous les autres,

[PDF] SUJET + CORRIGE

Exercice 1: Automates de recherche de motifs Exercice 2: Parcours en profondeur de graphes Exercice 4: Variantes plus court chemin à origine unique

[PDF] TD dalgorithmique avancée Corrigé du TD 11 : Plus courts chemins

Corrigé du TD 11 : Plus courts chemins pour tout couple de sommets (la récursion portera ici sur le nombre d'arcs d'un plus court chemin) Pour m = 0 il existe

[PDF] Exercices “Plus courts chemins” : Correction - Educnet

Exercices “Plus courts chemins” : Correction 19 octobre 2016 1 2 3 Il suffit d' appliquer la fonction log sur les poids 4 L'algorithme reste le même, mais on met

[PDF] GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir

Le nombre chromatique de ce graphe est donc égal à 4 4) On utilise l'algorithme du plus court chemin de Dijkstra pour déterminer une chaîne qui minimise la

[PDF] AMD5 TD no 6 : Algorithmes de plus courts chemins II - IRIF

TD no 6 : Algorithmes de plus courts chemins II Exercice 1 : Dijkstra vs Bellmann Ford 1 Ecrire l'un à côté de l'autre les deux algorithmes de Bellmann-Ford et

[PDF] TD 5 Plus courts chemins - LIRMM

Utiliser l'algo de Dijkstra pour calculer une arborescence des plus courts chemins issue de a 2 La longueur de l'arc ge est en fait -8 Refaire la question

1.02.0

3.04.0

1.2 1.1

2.22.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 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 i

Par 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) : K

2 + 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é/p3

b) 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 2

NB : 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 h

0 + + + + + + +

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 45
2 11 2 2 63
2 421
0 37
16 6 4 2quotesdbs_dbs11.pdfusesText_17

[PDF] [PDF] Le problème du plus court chemin : exercices- corrigé - AUNEGE

[PDF] Résolution de problèmes de plus court chemin/exercices/corrigé/p1