Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Le problème du plus court chemin /exercices/corrigé/p1 Le problème du plus cour

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 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 - ct = coût de production unitaire de la période t - ht = 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 Kt - Quantité produite lorsque j > i-2 : 2 + (j - i) donc coût variable de production : ct ( 2 + j-i) - Coût de stockage = ht i Par exemple en période 2 : (1,0) -> (2,0) : K2 + 2 c2 on produit 2 unités – pas de stock à la fin (1,0) -> (2,1) : K2 + 3 c2+ h2 c2 on produit 3 unités – une unité en stock à la fin (1,0) -> (2,2) : K2 + 4 c2 + 2 h2 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) : K2 + c2 + h2 (1,2) -> (2,2) : K2 + 2 c2 + 2 h2 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 : 0 1 2 3 4 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 ) : K2 + 2 c2 , pour l'arc (1,3) : K2 + 4 c2 + 2 h2 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,h h 7(h) // e e // a b c d e f g h 4 5 2 1 1 2 2 6 3 2 4 2 1 0 3 7 1 6 6 4 2 uploads/Industriel/ cor-exercice-s-3 1 .pdf