Remerciez-le!

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

Cor exercice s 4 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 C'est un graphe de sommets numérotés de à Les arcs sont tous les arcs possibles de i

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 C'est un graphe de sommets numérotés de à Les arcs sont tous les arcs possibles de i à j avec j i L'arc i j correspond à l'acquisition d'un véhicule en début de période i et à sa revente en ?n de période j Le coût correspondant à cet arc est donné par Prix d'achat entretien sur les périodes i j - Revente en ?n de période j Compte tenu des valeurs numériques les coût cij des arcs i j sont donnés dans le tableau suivant Il su ?t de calculer la première ligne qui correspond à ce qu'il en coûte de garder le véhicule ou ans puisque les coûts ne dépendent pas de la période Le graphe obtenu est sans circuit Pour résoudre le problème on peut appliquer l'algorithme de Bellman Sommet ? Sommet ? père Sommet prédécesseurs et ? Min père Sommet prédécesseurs ? Min père Sommet prédécesseurs ? Min père Sommet prédécesseurs ? Min Père ou Sommet prédécesseurs ? Min Père Par exemple pour le sommet on calcule Min ? l ? l ? l ? ? ? ont été calculés auparavant ? ? ? Les longueurs l i j sont lues dans le tableau Finalement le coût minimal est de Pour cela il faut garder le dernier véhicule ans père le précédent ans père et le premier ans Donc la politique optimale sur ans avec cette structure de coût est de remplacer le véhicule tous les ans Résolution de problèmes de plus court chemin exercices corrigé p CII Dans le cas a comme dans le cas b le graphe est sans circuit Pour résoudre le problème on utilise l'algorithme de Bellman On passe les sommets dans l'ordre chronologique ce qui fait que chacun est examiné après ses prédécesseurs Dans le premier cas le calcul est fastidieux Il est beaucoup plus rapide dans le second Il faut d'abord calculer le coût associé à chaque arc Par exemple pour Coût ?xe Coût variable unités avec un coût unitaire de production de Coût de stockage unités avec un coût unitaire de stockage de Pour idem sauf que le coût unitaire de production est passé à Application de l'algorithme de Bellman ? ? père ? Min ? Min père ? Min ? ? Min père ? Min ? ? Min père Le coût de la politique optimale est de a pour père qui a pour père Le plus court chemin de à est le chemin ?? - Il faut produire unités en période et unités en période III Les longueurs sont positives on pourrait appliquer l'algorithme de Moore Dijkstra mais on peut véri ?er que ce graphe est sans circuit auquel cas il vaut mieux appliquer l'algorithme de Bellman qui est plus performant L'ordre d'examen des sommets est s a d g b e h p Conseil indiquer à côté de chaque sommet