Trajet minimal et feux tricolores

Merci !

Annales corrigées
Classe(s) : Tle ES | Thème(s) : Matrices et graphes
Type : Exercice | Année : 2013 | Académie : France métropolitaine
&nbsp
Unit 1 - | Corpus Sujets - 1 Sujet
&nbsp
Trajet minimal et feux tricolores
&nbsp
&nbsp

Matrices et graphes &bull Graphes probabilistes

Corrigé

38

Ens. de spécialité

matT_1306_07_06C

&nbsp

France métropolitaine &bull Juin 2013

Exercice 4 &bull 5 points

Un chauffeur-livreur réside en Italie dans la ville d&rsquo Aoste.

Quatre fois par mois, son employeur l&rsquo 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&rsquo un budget mensuel de 2 200 euros pour son carburant. Ce qu&rsquo 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 &shy d&rsquo Italie : Aoste, Milan, Parme, Turin, Gènes, La Spézia, Bologne et Florence. Chaque ville est désignée par son initiale.


&nbsp

Les deux parties sont indépendantes.

Partie A

Étude du trajet

&gt 1. Déterminer le trajet le plus court entre Aoste et Florence. (On indiquera les villes parcourues et l&rsquo ordre de parcours). (1,25 point)

&gt 2. Déterminer le budget carburant nécessaire aux quatre voyages aller-retour du mois (le résultat sera arrondi à l&rsquo euro près).

En déduire le montant de la prime P qui lui sera versée en fin de mois, à l&rsquo euro près. (0,75 point)

Partie B

Traversée de Parme

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&rsquo il est rouge, il s&rsquo arrête.

L&rsquo expérience lui a permis d&rsquo établir que, s&rsquo il se présente à un feu, il se produit les événements suivants :

  • Arrivé au feu, celui-ci est au vert (V) : la probabilité que le suivant soit vert est de 0,85.
  • Arrivé au feu, celui-ci est orange ou rouge (R) : la probabilité que le suivant soit vert est de 0,30.

&gt 1. Représenter la situation par un graphe probabiliste. (0,75 point)

&gt 2. Indiquer la matrice de transition du graphe, en considérant les sommets dans l&rsquo ordre (V, R) en ligne comme en colonne. (0,5 point)

&gt 3. Le premier feu rencontré est vert. La matrice donnant l&rsquo état initial est donc (1&ensp 0).

a) Déterminer les matrices et . (Le détail des calculs n&rsquo est pas demandé.) (1 point)

b) Conclure quant à la probabilité  de l&rsquo événement &laquo  le chauffeur doit s&rsquo arrêter au troisième feu &raquo . (0,75 point)

Les thèmes en jeu

Graphe pondéré &bull Graphe probabiliste &bull Matrice associée à un graphe.

Les conseils du correcteur

Partie A

&gt 1. Le trajet le plus court ne comporte pas nécessairement un nombre minimal d&rsquo arêtes. Utilisez l&rsquo algorithme de Dijkstra.

Partie B

&gt 2. Les coefficients de la matrice de transition associée à un graphe probabiliste sont les probabilités portées par les arêtes de ce graphe  la somme des coefficients d&rsquo une ligne est égale à 1.

&gt 3.b) La probabilité  de l&rsquo événement &laquo  Le chauffeur doit s&rsquo arrêter au troisième feu &raquo est la probabilité que le troisième feu soit orange ou rouge  c&rsquo est l&rsquo un des coefficients de la matrice .