INTRODUCTION

• Nom: J. M (Mike) Robson; robson@labri.fr

• Emploi du temps: le plus souvent 2 heures de cours et 2 heures de TD par semaine

• fichiers de transparents et de TD (etéventuellement des corrigés):

http://dept-info.labri.fr/~robson/RO

• contrôle continu: projet de programmation et éventuellement de petites interrogations en TD

• R.O. branche de math; à voir avec décisions économiques • traitée ici d’une façon peu rigoureuse mais

...

• livres:

Méthodes d’Optimisation Combinatoire: Charon et al Programmation Linéaire: Guéret et al Exercices et problèmes Résolus de Recherche Opérationnelle tome 2, Roseaux Et pour l’histoire La Recherche Opérationnelle: Nobert et al

Matières: techniques

mathématiques de décision;

• où est la difficulté de prendre une décision?

• C’est plus difficile quand il s’agit de plusieurs décisions dépendantes? interaction entre mes décisions

• ou de décisions de politique à appliquer dans le long terme interaction entre mes décisions d’aujourd’hui et celles de l’avenir

• ou de décisions dans un monde nondéterministe interaction entre mes décisions et la nature • techniques qui dépendent de la construc-

tion d’un modèle: la solution donnée par une de ces techniques mathématiques n’est plus valable que notre modèle!

Les Chaînes de Markov (prochaines 3? semaines de

cours)

Modèles de systèmes quiévoluent dans le temps selon des transitions probabilistes

Exemple: jouer au Pile ou Face D’abord j’ai 3 euros et mon opposant a aussi 3 euros A chaque tour j’ai une probabilité p de gagner un euro et une probabilité 1 − p de perdre un euro mais un joueur sans argent ne peut plus miser L’“état” du système est combien d’argent j’ai (0,1,2,3,4,5 ou 6) Les transitions possibles sont:

1 → 2, 2 → 3, 3 → 4, 4 → 5, 5 → 6
1 → 0, 2 → 1, 3 → 2, 4 → 3, 5 → 4
0 → 0, 6 → 6

Les propriétés générales

Un ensemble E d’états possibles

Transitions à des moments de temps discrets

Probabilité de transition de l’état i à l’état j (à moment t) ne dépend pas de l’histoire (c-à-d des états antérieurs)

Ici on ne considère que les chaînes finies (nombre d’états fini) et homogènes (probabilité de transition d’état i à l’état j ne dépend pas de t).

Un deuxième exemple: Une

petite compagnie de livraison

de colis

On considère une compagnie qui possède 4 camions qui sont utilisés pour des livraisons entre Bordeaux et Paris. Selon les demandes reçues chaque matin 0, 1 ou plusieurs camions partent de chaque ville pour arriver dans l’autre ville le soir. Si la demande dépasse le nombre de camions disponibles, les derniers clients partent.

On veut savoir, par exemple, le pourcentage des demandes qui échouent (faute d’assez de camions dans la ville de la demande).

On suppose b_{i} la probabilité chaque jour d’une demande totale qui nécessite exactement i camions de Bordeaux à Paris et a_{i} la même probabilité dans la direction inverse.

Et on suppose que les demandes dans les 2 villes sont indépendantes.

Il y a 5 états selon le nombre de camions sur Bordeaux (la nuit).

La probabilité d’une transition de l’état i à l’état j: i = j = 0: a_{0} i = 0, j = 1: a_{1} i = 1, j = 0: a_{0}(b_{1} + b_{2} + b_{3} + b_{4}) i = 1, j = 1: a_{0}b_{0} + a_{1}(b_{1} + b_{2} + b_{3} + b_{4}) etc.

Les matrices de transitions

On note P_{i,j} la probabilité d’une transition de l’état i à l’état j à un moment et P la matrice de ces probabilités.

Une matrice vérifiant les deux propriétésévidentes: P_{i,j} ≥ 0 pour tout i, j et _{j}^{∑} P_{i,j} = 1 est une

matrice stochastique.

Toute matrice stochastique est la matrice d’une chaîne de Markov.

On note P_{i,j}^{(m)} la probabilité d’une transition de l’état i à l’état j dans m transitions et P^{(m)} la matrice de ces probabilités.

Classification des états

Un état i est persistant ou récurrent si la probabilité d’être une deuxième fois en i après être arrivé en i est 1. (Probabilité = 1 n’équivaut pas à certain!) (Pour les chaînes finies) celà équivaut à dire que s’il est possible d’aller de l’état i à un autre état j (éventuellement en plusieurs étapes), il est possible de rentrer de j à i. Sinon il est transitoire

Dans le jeu de Pile ou Face 0 et 6 sont des états persistants; les autres sont transitoires. Dans le système des camions ça dépend des probabilités: si a_{0} = b_{0} = 0 et les autres probabilités sont non-nulles, 0 et 4 sont des états transitoires et tous les autres sont persistants..

On parle aussi des états ergodiques, c’est-à-dire ceux pour lesquels le temps moyen du premier retour à l’état i après être arrivé une fois en i est fini. Pour les chaînes finies il n’y a pas de différence entre persistant et ergodique.

Unétat i est périodique avec période λ si chaque cycle de i à i comporte un nombre de transitions qui est un multiple de λ (et λ est l’entier maximum (supérieurà 1) avec cette propriété), c’est-à-dire le plus grand diviseur commun des longueurs de tous les cycles qui contiennent i.

Le graphe de transitions

Le graphe dirigé dont les sommets sont les états et les arcs sont les transitions possibles (P_{i,j} > 0) permet de trouver les états persistants etc.

Les chemins dans ce graphe correspondent aux transitions possibles en plusieurs étapes (ou 1 ou 0).

Important: les composants fortement connexes (ensemble maximal de sommets tel qu’il existe un chemin de chacun à chaque autre) Le système entrera (avec probabilité 1) dans un composant sans sortie et ensuite devra y rester; Lesétats d’un tel composant constituent une petite chaîne où tous les états sont persistants (donc ergodiques) S’il y a un seul composant fortement connexe la chaîne est irréductible Tous les états d’un composant sont du même type: tous persistants (une classe finale d’états) ou tous transitoires (une classe de passage);

Décomposition en chaînes

simples

Un autre graphe (sommets les composants du premier; arcs correspondant aux transitions entre composants) suffit pour montrer dans quels composants le système peut finir étant donné un état initial Si l’un desétats d’un composant est périodique avec période λ, c’est vrai pour tous.

En ce cas, on peut diviser lesétats en λ classes: C_{0}, C_{1}, ⋯ C_{λ−1}, de telle façon que chaque transition est d’une classe C_{i} à C_{i+1} (ou de C_{λ−1} à C_{0}); les chemins de longueur λ donnent une chaîne à l’intérieur de chaque C_{i} où tous les états sont persistants et apériodiques. L’étude du comportement du système a été réduite à deux questions: l’étude des systèmes ergodiques et apériodiques; et la question de dans quelle sous-chaîne on peut finir et avec quelle probabilité.