Recherche Opérationnelle

IUP-MIAGe Master 1

janvier 2004

1. 6 points Donner la matrice de probabilités de transition pour une chaîne de Markov de 12 états qui a les trois classes d'états suivantes: une classe finale de 4 états périodique avec période 4, une classe de passage de 5 états périodique avec période 3, une classe finale apériodique de 3 états.
   Les probabilités de transitions doivent toutes être strictement inférieures à 1.

   Donner un algorithme, valable pour les chaînes avec une seule classe, qui décide si la chaîne est périodique et, si oui, calcule sa période.

2. 6 points Donner un exemple d'un programme linéaire sur 4 variables et contenant 5 contraintes explicites où le programme est faisable mais (0,0,0,0) n'est pas une solution réalisable.

   En utilisant cet exemple, décrire comment construire un programme auxiliaire dont une solution optimale (si elle existe) donnera une solution réalisable de base du programme de départ; décrire aussi comment trouver une solution de base réalisable de ce programme auxiliaire; ensuite transformer ce programme auxiliaire dans la forme utilisée par l'algorithme du simplexe (où toutes les contraintes explicites sont des équations).

3. 4 points Par un exemple d'un programme en 2 variables, démontrer que c'est possible qu'un Programme Dynamique en Nombres Entiers n'est pas faisable mais son programme relaxé a des solutions réalisables sans borne sur la fonction objective.
4. 4 points

   Expliquer comment la programmation dynamique peut aider à résoudre le problème suivant:

   Je veux calculer le coût minimum du carburant pour effectuer un voyage de 1000 kilomètres. Mon véhicule a une autonomie de 300 kilomètres et je sais qu'il y a une station de service chaque 100 kilomètres sur la route. Je dispose d'un tableau qui me donne le prix de carburant dans chaque station. (Je ne suis pas obligé de faire le plein quand j'achète.)