Recherche Opérationnelle

IUP-MIAGe Master 1

janvier 2004

1. 6 points Quel est le calcul qui permet de déterminer la distribution stationnaire d'une chaîne de Markov qui a une seule classe finale si cette classe est apériodique?

   Expliquer pourquoi ce calcul n'est pas valable dans les autres cas.

   Décrire un algorithme pour trouver les classes d'une chaîne et de décider si elles sont finales et/ou périodiques.

2. 6 points Décrire comment un programme linéaire exprimé par des contraintes ≤ peut être transformé dans la forme utilisée par l'algorithme du simplexe (avec des contraintes d'égalité et les contraintes que toutes les variables soient ≥ 0).

   Expliquer le processus du choix d'un pivot dans l'algorithme du simplexe et pourquoi ce choix du pivot garantit que la valeur de la fonction objective ne peut pas être réduite.

   Pourquoi une opération de pivotage avec ce choix du pivot est-elle garantie de préserver les conditions utilisées par votre réponse à la question précédente?

3. 4 points Par un exemple d'un programme en 2 variables, démontrer que c'est possible qu'un Programme Linéaire en Nombres Entiers est faisable mais la solution optimale de son programme relaxé ne peut pas être transformée en solution réalisable entière en arondissant chaque variable soit vers le haut soit vers le bas.
4. 4 points Expliquer comment la programmation dynamique peut aider à résoudre le problème suivant:

   Je veux calculer le meilleur chemin pour conduire du point Sud-ouest au point Nord-est d'une ville en voyageant toujours vers le nord ou vers l'est. La ville est dans la forme d'un carré de 1 km par 1 km est il y a des routes du sud au nord et de l'ouest à l'est tous les 100 mètres; à chaque intersection il y a des feux tricolores et j'ai un tableau donnant le temps moyen d'attente à chaque intersection dans les quatre cas possibles (arrivée du sud ou de l'ouest, départ vers le nord ou l'est). Je conduis toujours à une vitesse de 50 km/h. Je veux trouver le chemin qui minimise le temps total moyen.