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
 
Unit 1 - | Corpus Sujets - 1 Sujet
 
Trajet minimal et feux tricolores
 
 

Matrices et graphes • Graphes probabilistes

Corrigé

38

Ens. de spécialité

matT_1306_07_06C

 

France métropolitaine • Juin 2013

Exercice 4 • 5 points

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 2 200 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.

Partie A

Étude du trajet

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

>2. 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. (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’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 :

  • 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.

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

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

>3. Le premier feu rencontré est vert. La matrice donnant l’état initial est donc (1 0).

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

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

Les thèmes en jeu

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

Les conseils du correcteur

Partie A

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

Partie B

>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’une ligne est égale à 1.

>3.b) La probabilité  de l’événement « Le chauffeur doit s’arrêter au troisième feu » est la probabilité que le troisième feu soit orange ou rouge ; c’est l’un des coefficients de la matrice .

Corrigé

Partie A

>1. Déterminer un trajet minimal sur un graphe

Pour déterminer le trajet le plus court entre Aoste et Florence, on utilise l’algorithme de Dijkstra qui peut être résumé par le tableau suivant :

 

A

M

P

T

G

LS

B

F

0 (A)

174 (A)

120 (A)

174 (A)

366 (T)

288 (T)

300 (M)

288 (T)

300 (M)

396 (G)

396 (G)

398 (P)

398 (P)

541 (LS)

502 (B)

 
 

Notez bien

Il existe d’autres trajets en 4 étapes d’Aoste à Florence, mais ils sont plus longs ; par exemple : Aoste – Turin – Gênes – La Spezia – Florence (541 km) ou Aoste – Turin - Parme – Bologne – Florence (568 km).

Le trajet le plus court d’Aoste à Florence est donc :

 

Aoste – Milan – Parme – Bologne – Florence.

Ce trajet comporte 4 étapes.

Sa longueur totale est 502 km.

>2. Calculer le prix de revient d’un déplacement

Si le chauffeur fait 4 voyages aller-retour Aoste-Florence (soit 8 trajets) par le chemin le plus court, il parcourt 8 fois 502 km, soit 4 016 km.

.

Le budget carburant est donc 2 048 € à l’euro près.

.

Le chauffeur touche donc en fin de mois une prime de 152 € à l’euro près.

Partie B

>1. Représenter une situation par un graphe probabiliste

La situation peut être représentée par le graphe probabiliste suivant :


 

>2. Déterminer la matrice de transition d’un graphe probabiliste

La matrice de transition du graphe est : 

>3.a) Déterminer deux états probabilistes associés à un graphe

b) Déterminer une probabilité associée à un graphe probabiliste

D’après le calcul de la matrice P3, la probabilité p de l’événement « le chauffeur doit s’arrêter au troisième feu », c’est-à-dire la probabilité que le troisième feu soit orange ou rouge est 0,2325.