Un chauffeur-livreur réside en Italie dans la ville d'Aoste.
Quatre fois par mois, son employeur l'envoie livrer du matériel informatique dans la ville de Florence.
Il est établi que le trajet en camion coûte, en carburant, 0,51 euro au kilomètre. Le chauffeur dispose d'un budget mensuel de 2200 euros pour son carburant. Ce qu'il réussit à économiser lui permet de toucher une prime P équivalente en fin de mois.
Il consulte donc la carte routière ci-dessous pour optimiser ses trajets.
Le graphe ci-dessous indique les distances entre différentes villes d'Italie : Aoste, Milan, Parme, Turin, Gènes, La Spézia, Bologne et Florence. Chaque ville est désignée par son initiale.
Les deux parties sont indépendantes.
Déterminer le trajet le plus court entre Aoste et Florence. (On indiquera les villes parcourues et l'ordre de parcours).
On détermine le trajet de poids minimal à l'aide de l'algorithme de Dijkstra :
| A | M | T | P | G | LS | B | F | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 174 (A) | 120 (A) | ∞ | ∞ | ∞ | ∞ | ∞ | T (120) | |
| 174 (A) | 366 (T) | 288 (T) | ∞ | ∞ | ∞ | M (174) | ||
| 300 (M) | 288 (T) | ∞ | ∞ | ∞ | G (288) | |||
| 300 (M) | 396 (G) | ∞ | ∞ | P (300) | ||||
| 396 (G) | 398 (P) | ∞ | LS (396) | |||||
| 398 (P) | 541 (LS) | B (398) | ||||||
| 502 (B) | F (502) |
Le sommet F étant marqué, pour lire la chaîne de poids minimal, on part de F et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court entre Aoste et Florence est Aoste(A) - Milan (M) - Parme (P) - Bologne (B)- Florence (F). La distance parcourue est de 502 km.
Déterminer le budget carburant nécessaire aux quatre voyages aller-retour du mois (le résultat sera arrondi à l'euro près).
En déduire le montant de la prime P qui lui sera versée en fin de mois, à l'euro près.
Le budget carburant nécessaire aux quatre voyages aller-retour du mois est
Le budget carburant nécessaire aux quatre voyages aller-retour du mois est d'environ 2048 euros. La prime qui sera versée en fin de mois est donc de 152 euros.
Durant son trajet, le chauffeur est obligé de traverser Parme et ses très nombreux feux tricolores. Lorsque le feu est orange, le chauffeur se comporte comme lorsqu'il est rouge, il s'arrête.
L'expérience lui a permis d'établir que s'il se présente à un feu, il se produit les évènements suivants :
Représenter la situation par un graphe probabiliste.
Notons V l'état probabiliste « Le feu est vert » et R l'état probabiliste « Le feu est orange ou rouge ». On considère que :
Arrivé au feu, si celui-ci est au vert (V), la probabilité que le suivant soit vert est de 0,85 d'où et
Arrivé au feu, si celui-ci est orange ou rouge (R), la probabilité que le suivant soit vert est de 0,30 d'où et
D'où le graphe probabiliste correspondant à cette situation :
Indiquer la matrice de transition M du graphe, en considérant les sommets dans l'ordre (V, R) en ligne comme en colonne.
La matrice de transition M du graphe en considérant les sommets dans l'ordre (V, R) est : .
Le premier feu rencontré est vert. La matrice donnant l'état initial est donc .
Déterminer les matrices et . (Le détail des calculs n'est pas demandé.)
L'état probabiliste au deuxième feu est :
L'état probabiliste au troisième feu est :
Ainsi, et .
Conclure quant à la probabilité p de l'évènement « Le chauffeur doit s'arrêter au troisième feu ».
L'état probabiliste au troisième feu est donc la probabilité p de l'évènement « Le chauffeur doit s'arrêter au troisième feu » est égale à 0,2325.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.