Année 2004-2005 Session de Septembre 2005

GU : Master 1 MIAGe UE : MIG715 Épreuve de : Recherche Opérationnelle Date : 1 septembre 2005, 8h Durée : 1h30

Documents autorisés

Épreuve de Monsieur Robson

1 [7 points]

i. Dans la chaîne de Markov dont la matrice de probabilités de transition est donnée (les + marquent les éléments positifs), donner

(a) une classe finale périodique

(b) une classe finale apériodique

(c) une classe de passage périodique

(d) une classe de passage apériodique

a b c d e f g h i j k l m

\begin{matrix}a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \\ j \\ k \\ l \\ m \end{matrix} ( \begin{matrix}. & . & + & . & . & . & + & . & . & . & . & . & . \\ . & . & . & . & . & + & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & + & . & . & . & . & . \\ . & . & . & . & + & . & . & . & . & . & . & . & . \\ . & . & . & . & . & . & . & . & . & . & . & . & + \\ . & + & . & . & . & . & . & . & . & . & . & + & . \\ . & . & . & . & . & . & . & . & + & . & . & . & . \\ . & . & . & . & . & . & . & . & . & + & . & . & . \\ . & . & . & . & . & . & + & . & . & . & + & . & . \\ . & . & + & + & . & . & . & + & . & . & . & . & . \\ + & + & . & + & . & . & . & . & . & + & . & . & . \\ . & + & . & . & . & . & . & . & . & . & . & . & . \\ . & . & . & + & . & . & . & . & . & . & . & . & . \end{matrix} )

ii. Dans la chaîne :

( \begin{matrix}0 & 0.5 & 0 & 0 & 0 & 0.5 & 0 \\ 0.4 & 0 & 0 & 0 & 0 & 0.6 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0.2 & 0 & 0.8 & 0 & 0 \\ 0 & 0 & 0.3 & 0 & 0.3 & 0.6 & 0 \\ 0 & 0.5 & 0 & 0 & 0 & 0 & 0.5 \\ 0 & 0 & 0 & 0 & 0 & 0.7 & 0.3 \end{matrix} )

il y a une seule classe finale et cette classe est apériodique ; donner un système d’équations permettant de calculer la distribution limite de cette classe (vous n’êtes pas obligé de résoudre les équations.)

1/2 2 [5 points] On doit maximiser les profits d’une entreprise pour l’année 2006 en choisissant la bonne politique

de publicité. Au début de chaque mois on a la possibilité de lancer ou non une campagne de publicité à un cout de K; une étude a trouvé qu’une campagne de publicité va incrémenter le nombre de clients (maximum 1000) mais que ce nombre va diminuer sans campagne ; plus concrètement cette étude a fourni deux tableaux qui donnent le nombre de clients dans le mois en fonction du nombre dans le mois précédent (tableaux P UB et AUCUNE_P UB pour les deux cas.) Un client pendant un mois apporte à l’entreprise une bénéfice de client. A la fin de 2005 le nombre de clients sera c_2005. Expliquez comment la programmation dynamique peut aider à décider la bonne politique de publicité.

3 [8 points] Pour le programme linéaire

\begin{aligned}2x_{1} & +3x_{2} & −2x_{3} & +x_{4} & ≤ 20 \\ 5x_{1} & −2x_{2} & +4x_{3} & +2x_{4} & ≤ 30 \\ 4x_{1} & −3x_{2} & +x_{3} & +2x_{4} & ≤ 10 \\ −2x_{1} & +4x_{2} & +5x_{3} & −2x_{4} & ≤ 25 \end{aligned}

x_{1}, x_{2}, x_{3}, x_{4} ≥ 0, maximiser 3x_{1} + x_{2} + 4x_{3} − 2x_{4}

i. Quel est la forme du programme après l’ajout des variables d’écart utilisées par l’algorithme du

simplexe ? ii. expliquez le choix d’un pivot pour la première itération de l’algorithme du simplexe ; iii. quel est le résultat d’une itération avec le pivot choisi ? iv. quelle est la solution réalisable de base trouvée par cette première itération ? v. quelle est la valeur de la fonction objective à cette nouvelle solution ?

2/2