Les différentes parties de cet exercice peuvent être traitées de façon indépendante.
Le graphe pondéré ci-dessous représente les différents lieux A, B, C, D, E, F, G et H dans lesquels Louis est susceptible de se rendre chaque jour. Le lieu A désigne son domicile et G le lieu de son site de travail.
Le poids de chaque arête représente la distance, en kilomètres, entre les deux lieux reliés par l'arête.
Déterminer le chemin le plus court qui permet à Louis de relier son domicile à son travail. On pourra utiliser un algorithme. Préciser la distance, en kilomètres, de ce chemin.
Pour déterminer le trajet le plus court pour aller du sommet A au sommet G, on utilise l'algorithme de Dijkstra.
A | B | C | D | E | F | G | H | Sommet sélectionné |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
47 (A) | 56 (A) | ∞ | 23 (A) | 30 (A) | ∞ | ∞ | E (23) | |
43 (E) | 56 (A) | 65( E) | 30 (A) | ∞ | 63 (E) | F (30) | ||
43 (E) | 56 (A) | 65( E) | ∞ | 58 (F) | B (43) | |||
53 (B) | 65( E) | ∞ | 58 (F) | C (53) | ||||
65( E) | ∞ | 58 (F) | H(58) | |||||
65( E) | 81 (H) | D (65) | ||||||
80 (D) | G (80) |
Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on remonte la chaîne en suivant les prédécesseurs. .
Le chemin le plus court qui permet à Louis de relier son domicile à son travail est A - E - D - G, la distance parcourue est de 80 kilomètres.
Afin de réduire son empreinte énergétique, Louis décide d'utiliser lors de ses trajets quotidiens soit les transports en commun, soit le covoiturage.
Louis décide de mettre en place ces résolutions au 1er janvier 2018.
Pour tout entier naturel n, on note :
La matrice ligne traduit l'état probabiliste n jour(s) après le 1er janvier 2018.
Le 1er janvier 2018, Louis décide d'utiliser le covoiturage.
remarque
Pour la cohérence de l'exercice, on considère que sur une même journée Louis ne change pas de type de tansport pour les différents trajets qu'il effectue pendant la journée.
Préciser l'état probabiliste initial .
Le 1er janvier 2018, Louis décide d'utiliser le covoiturage donc .
Traduire les données de l'énoncé par un graphe probabiliste. On notera « C » et « T » ses deux sommets :
Si Louis a utilisé les transports en commun lors d'une journée, il utilisera le covoiturage le lendemain avec une probabilité de 0,53 d'où et .
D'où le graphe probabiliste correspondant à cette situation :
Déterminer la matrice de transition du graphe probabiliste en considérant ses sommets dans l'ordre alphabétique.
La matrice ligne traduit l'état probabiliste n jour(s) après le 1er janvier 2018 donc :
la matrice de transition du graphe probabiliste telle que pour tout entier naturel n, est : .
Calculer l'état probabiliste et interpréter ce résultat dans le cadre de l'exercice.
soit :
. Le 3 janvier, Louis utilisera le covoiturage avec une probabilité proche de 0,46.
Soit la matrice ligne associée à l'état stable du graphe probabiliste.
Calculer les valeurs exactes de x et de y puis en donner une valeur approchée à 0,01 près.
L'état stable est avec et tel que :
D'où x et y vérifient la relation . Comme d'autre part, on en déduit que x et y sont solutions du système :
L'état stable du système est soit avec des valeurs approchées à 0,01 près, .
Selon ce modèle, peut-on dire qu'à long terme, Louis utilisera aussi souvent le covoiturage que les transports en commun ? Justifier la réponse.
Les termes de la matrice de tansition M d'ordre 2 ne sont pas nuls, alors l'état probabiliste converge vers l'état stable . C'est à dire qu'à long terme, Louis utilisera le covoiturage dans environ 40 % de ses déplacements.
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.