next up previous
Next: About this document ...

Recherche Opérationnelle

IUP-MIAGe 3

Mardi le 16 janvier 2001

Tous documents autorisés

  1. 10 points
    Pour le programme linéaire:


    $\displaystyle x_5 +
x_6$ $\textstyle \leq$ $\displaystyle 12$ (1)
    $\displaystyle x_4-x_5$ $\textstyle \leq$ $\displaystyle 2$ (2)
    $\displaystyle x_3-x_5-x_6$ $\textstyle \leq$ $\displaystyle 5$ (3)
    $\displaystyle x_2-x_4+x_5-x_6$ $\textstyle \leq$ $\displaystyle 10$ (4)
    $\displaystyle x_1-x_2-2x_5+x_6$ $\textstyle \leq$ $\displaystyle -2$ (5)
    $\displaystyle -x_2+x_3+x_5-x_6$ $\textstyle \leq$ $\displaystyle 0$ (6)
    $\displaystyle -x_1+x_2-x_4+2x_5-x_6$ $\textstyle \leq$ $\displaystyle 5$ (7)
    $\displaystyle x_1,x_2,x_3,x_4,x_5,x_6$ $\textstyle \geq$ $\displaystyle 0$ (8)
    $\displaystyle {\rm maximiser}~z$ $\textstyle =$ $\displaystyle -6x_1+5x_2-5x_4+13x_5-3x_6$ (9)

    1. 4 points $(0,0,0,0,0,0)$ n'est pas une solution réalisable. Donnez un programme auxiliaire qui aide à la recherche d'une solution réalisable de base. Quelle est une solution réalisable de base de votre programme auxiliaire?
    2. 2 points Quel est le dual du programme initial?
    3. 2 points Du fait que $(1,2,3,4,5,6)$ est une solution réalisable du programme initial avec valeur $z=31$, que pouvez-vous déduire sur les solutions réalisables du dual?
    4. 2 points Du fait que $(1,2,3,4,5,6)$ et $(6,5,4,3,2,1)$ sont deux solutions réalisables du programme initial, avec valeurs $31$ et $-3$ de la fonction objective $z$, déduisez une autre solution réalisable et expliquez pourquoi elle ne pourrait pas être optimale.
      (Dans votre raisonnement vous n'utiliserez pas directement ni les contraintes ni la fonction objective.)

  2. 10 points
    Dans les questions suivantes, quand un exemple d'un type de chaîne de Markov est demandé, il faut donner un exemple non-trivial, c'est-à-dire oú le comportement de la chaîne n'est pas complètement évident sans aucune analyse.
    1. 2 points Donnez un exemple d'une chaîne de Markov irréductible et apériodique et expliquez comment vous trouvez un système d'équations pour calculer sa distribution limite.
    2. 3 points Donnez un exemple d'une chaîne de Markov possédant au moins $3$ classes finales et expliquez comment vous trouvez un système d'équations pour calculer la probabilité de finir dans une classe finale donnée à partir d'un état initial.
    3. 3 points Donnez un exemple d'une chaîne de Markov possédant une seule classe finale qui est périodique avec période $3$ et expliquez comment vous trouvez un système d'équations pour calculer la probabilité asymptotique d'être dans une sous-classe donnée de cette classe après un nombre de transitions qui est multiple de $3$ à partir d'un état initial.
    4. 2 points Donnez un algorithme pour décider dans une chaîne possédant une classe finale, si les états de cette classe sont périodiques et pour déterminer leur période.



next up previous
Next: About this document ...
Mike ROBSON
2001-09-11