40Graphe probabiliste, État stable, Algorithme de coloration55 min
France métropolitaine – La Réunion, septembre 2013
Graphes et matrices
Algorithmique
Exercice
6 ptsUne entreprise de produits cosmétiques fait réaliser une étude marketing sur une population donnée.
Cette étude montre que, lors de la sortie d’une nouvelle crème hydratante, la probabilité qu’une cliente l’achète lors de la première vente promotionnelle est de 0,2.
De plus, lorsqu’une cliente a acheté une crème hydratante lors d’une vente promotionnelle, la probabilité qu’elle en achète à nouveau lors de la vente promotionnelle suivante est de 0,8. Lorsqu’une cliente n’a pas acheté de crème hydratante, la probabilité pour qu’elle en achète à la vente promotionnelle suivante est de 0,3.
n étant un entier naturel non nul, on note :
● an la probabilité qu’une cliente achète une crème hydratante lors de la n-ième vente promotionnelle.
● bn la probabilité qu’une cliente n’achète pas une crème hydratante lors de la n-ième vente promotionnelle.
● la matrice ligne traduisant l’état probabiliste à la n-ième vente promotionnelle.
1 a. Déterminer P1.
b. Représenter la situation par un graphe probabiliste de sommets :
V quand il y a achat ;
quand il n’y a pas achat.
2 a. Écrire la matrice M de transition associée à ce graphe.
b. Calculer P2 et P3. D’après ces résultats, quel est l’effet de ces trois premières ventes promotionnelles ?
3 Justifier qu’il existe un état stable pour cette situation. Le déterminer.
4 L’étude marketing montre que certains produits ne sont jamais achetés simultanément. On représente les incompatibilités par le graphe suivant, où deux sommets reliés représentent deux produits qui ne sont jamais dans une même commande. Par exemple, les produits A et B, représentés par des sommets reliés, ne sont jamais dans une même commande.

L’entreprise souhaite répartir les produits dans des lots constitués de produits ne présentant aucune incompatibilité d’achat. Combien de lots doit-elle prévoir au minimum ? Justifier votre réponse à l’aide d’un algorithme et proposer une répartition des produits.
Voir le corrigé
ou aux acheteurs de livres ABC du Bac
Pour approfondir le thème...




