`: `; `! `?  

Figure

    Année 2004-2005 Session de Septembre 2005
   GU : Master 1 MIAGe UE : MIG715
   Épreuve de : Recherche Opérationnelle
   Date :

Durée : 1h30
   Documents autorisés
   Épreuve de Monsieur Robson

Figure





1
[7 points]

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

    1. une classe finale périodique
    2. une classe finale apériodique
    3. une classe de passage périodique
    4. une classe de passage apériodique
    a
    b
    c
    d
    e
    f
    g
    h
    i
    j
    k
    l
    m
    a
    b
    c
    d
    e
    f
    g
    h
    i
    j
    k
    l
    m
    (
    .
    .
    +
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    +
    .
    .
    .
    .
    +
    +
    .
    .
    .
    +
    .
    .
    .
    .
    .
    +
    +
    .
    +
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    .
    +
    .
    .
    .
    .
    .
    .
    .
    .
    .
    )
  2. Dans la chaîne:
    (
    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
    )
    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.)

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 PUB et AUCUNE_PUB 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
2x1
+3x2
-2x3
+x4
20
5x1
-2x2
+4x3
+2x4
30
4x1
-3x2
+x3
+2x4
10
-2x1
+4x2
+5x3
-2x4
25

x1, x2, x3, x4   0, maximiser 3x1+x2+4x3-2x4

  1. Quel est la forme du programme après l'ajout des variables d'écart utilisées par l'algorithme du simplexe?
  2. expliquez le choix d'un pivot pour la première itération de l'algorithme du simplexe;
  3. quel est le résultat d'une itération avec le pivot choisi?
  4. quelle est la solution réalisable de base trouvée par cette première itération?
  5. quelle est la valeur de la fonction objective à cette nouvelle solution?




File translated from TEX by TTH, version 3.05.
On 14 Dec 2006, 11:22.