Modèles stochastiques Processus de décisions markoviens

Modèles stochastiques

Processus de décisions markoviens

Considérons un système qui peut être modelisé comme un processus stochastique

discret avec la propriété markovienne (i.e., chaîne de Ma

Processus de décisions markoviens

rkov discrete). En tout

moment, l ( ) { }e système se retrouve dans un des 1 états possibles: 0, , .

À chaque fois que nous observons le système (processus), il faut prendre une

, et cette décision fait partie d'un ensedécision mble de déci

M M

k

+ …

{ }

{ }

sions disponibles

1, , .

Notons que pour certains états du processus, certaines des décisions 1, , ne

peuvent s'appliquer.

K

K

…

…

Considérons que le système est dans l'état au moment de l'observation.

Supposons qu d

Analyse du s

écisioe la prise es

ystème

t dénot

de dé

é

cision

e pn ar .i

i

d k=

Les conséquences de cette décision :

découlant de cette décision:

la déci

coût

nouvelles probabilités de transision entraîne de entre les états

t

du syt

ions

ème

i

ik

d k

C

=

i

i

Déterminer une politique optimale relativement à un critère de coût qui doit

être spécifié par

Objectif du

l'agent de

problème:

décision.

Critère de coût qui est souvent utilisé est

coût moy en par u nité de temps

( ) ( )( )0

Une est une spécification de la décison à prendre pour

chaque état possible du

politique de décision

systèm

,

e:

,M

R

R d R d R= …

En observant une machine de production, nous pouvons constater 4 états possibles:

états condition de la machine

Exemple d'un système de productio

0 comme une ne

n

uve

1 utilisable avec détérioration mineure

2 utilisable avec détérioration majeure

3 inutilisable

En utilisant des donnees historiques, nous sommes en mesure de spécifier les

transitions suivantes entre les états d'une semaine à l'autre

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Chaîne de Markov discrète en invoquant

la perte de mémoire du passé;

i.e., les transitions ne dépendent pas des

états des semaines antérieures

Considérons que lors d'une observation 3 décisions différentes peuvent être prises:

Décision Action

1 Rien faire

2 Mise au point (retour à l'état 1)

3 Remplacement de machine (retour à l'état 0)

k

Considérons que lors d'une observation 3 décisions différentes peuvent être prises:

Décision Action États où la décision

k

est applicable

1 Rien faire 0, 1, 2

2 Mise au point (retour à l'état 1) 2

3 Remplacement de machine (retour à l'état 0) 1, 2, 3

Les conséquences de cette décision :

découlant de cette décision:

la dé

coût

nouvelles probabilités de transitionscision entraîne de entre les états

sytème

ik

i

C

d k=

i

i

b) Coût de maintenance:

coût de mise au point $2000

coût de remplacement d'une machine $4000

=

=

c) Coût de perte de production par semaine:

lors d'une mise au point $2000

lors du remplacement d'une machine $2000

=

=

a) Si nous décidons de rien faire (décision 1), alors le coût moyen de perte par

semaine pour les produits défectueux depend de l'état de la m

Coût découl

achine util

ant de

isée:

s décisio

ns

état coût moyen des produits défectueux

0 $0

1 $1000

2 $3000

b) Coût de maintenance:

coût de mise au point $2000

coût de remplacement d'une machine $4000

=

=

c) Coût de perte de production par semaine:

lors d'une mise au point $2000

lors du remplacement d'une machine $2000

=

=

a) Si nous décidons de rien faire (décision 1), alors le coût moyen de perte par

semaine pour les produits défectueux depend de l'état de la m

Coût découl

achine util

ant de

isée:

s décisio

ns

état coût moyen des produits défectueux

0 $0

1 $1000

2 $3000

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

1-rien faire 0 0 x x 0

1 1000 x x 1000

2 3000 x x 3000

2- mise au point 2 x 2000 2000 4000

3-remplacement 1, 2, 3 x 4000 2000 6000

( ) ( ) ( ) ( )0 1 2 3Politique Description

Considérons les 4 politiques de décision différentes

Remplacer dans l'état 3 1 1 a

R d R d R d R d R

R 1 3

Remplacer dans l'état 3, 1 1 2 3

mise au point dans l'état 2

Remplacer dans les

b

c

R

R états 2 et 3 1 1 3 3

Remplacer dans les états 1, 2 et 3 1 3 3 3d

R

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmeR

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d

R

R

Remplacer dans l'état 3, 1 1 2 3

mise au point dans l'état 2

Remplacer

dans les ét

3

at

b

c

R

R s 2 et 3 1 1 3 3

Remplacer dans les états 1, 2 et 3 1 3 3 3d

R

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmea

R

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 0

13 0

2

0 02 2

P

=

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d R

R

Remplacer dans l'état 3, 1 1 2 3

mise au point

3

Rempla

d

c

a

er dans les état

ns l'état 2 b

c

R

R s 2 et 3 1 1 3 3

Remplacer dans les états 1, 2 et 3 1 3 3 3d

R

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmeb

R

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

0 1 0 0

12

0 0 03

P

=

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d R

R 3

Remplacer dans l'état 3, 1 1 2 3

mise au point dans

Remplacer d

l'éta

ans

t 2

les état

b

c

R

R

Remplacer dans les ét

s 2 et 3 1 1

ats 1, 2 et 3 1 3

3

3

3

3

dR

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmec

R

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

1 0 0 0

12

0 0 03

P

=

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d R

R 3

Remplacer dans l'état 3, 1 1 2 3

mise au point dans l'état 2

Remplacer dans les état

b

c

R

R

Remplacer dans les ét

s 2 et 3 1 1

ats 1, 2 et 3 1 3

3

3

3

3

dR

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmed

R

[ ]états 0 1 2 3

0 7 1

1

10

8 16 16

1

2

3

0 0 0

1 0 0 0

1 0 0 0

P

=

Nous sommes dans un contexte markovien puisque étant donnés l'état actuel du

systéme et la décision prise, toute affirmation sur le futur du système n'est pas

affecté par l'information passée (le processus est sans mémoire):

les nouvelles probabilités de transition dépendent uniquement de l'état actuel

et de la décision prise

le coût moyen (à long terme) dépend uniquement de l'état actuel et de la

i

i

décision prise

Déterminer une politique optimale relativement à un critère de coût qui doit

être spécifié par

Objectif du

l'agent de

problème:

décision.

Critère de coût qui est souvent utilisé est

coût moy en par u nité de temps

( ) ( )( )0

Une est une spécification de la décison à prendre pour

chaque état possible du

politique de décision

systèm

,

e:

,M

R

R d R d R= …

Propriétés des politiques de décision:

politique : étant donné l'état du système, la règle pour prendre

une décision ne dé

stationna

pend pas

ire

du m

ii

(nous utilisons de telles politi

oment où on

l'applique

politique : étant donné l'état du système, la décisiodéte n esrministe t unique

ques

)

t

ii

i politique : étant donné l'état du système, la décision est prise

selon une distributi

probabil

on aléat

iste

oire

i

Déterminer une politique optimale relativement à un critère de coût qui doit

être spécifié par

Objectif du

l'agent de

problème:

décision.

Critère de coût qui est souvent utilisé est

coût moy en par u nité de temps

Identification d'une politique déterministe optimale par résolution exhaustive:

Évaluer le coût de chaque politique et choisir celle ayant la plus petite valeur.

Considérons le critère défini par

coût moyen pa r unité de t emps

( )

{ }

( )

Soit un processus stochastique étant une chaîne de Markov irréductible

et ergotic.

Considérons une fonction de coût définie par une variable aléatoire définie

pour les valeurs des états 0, , :

0 , ,

tC X

M

C C

…

… ( )

( ) ( )

.

Supposons que la fonction soit indépendante du temps; i.e., reste la

même pour tous les temps .t

M

C C X

t

i

( )1

Le coût moyen associé à pour les premières périodes:

1.

n

t

t

C n

E C Xn =

∑

( ) ( )

1

1 0

coût moyen (à lon

Utilisant le résulta

g terme) par unité d

t que

1lim =

on peut démontrer que le

est donné par

e temps

1lim

nk

ij jn

k

n M

t jn

t j

pn

C X C jn

π

π

→∞=

→∞= =

=

∑

∑ ∑

Rappel

( ) ( )

( )

1 0

Pour calculer le

1lim

nous considérons les coûts d'exécution

coût moyen (à long terme) par unité de temps

associés aux états et les probabilités

d'équilibre obtenues e

n M

t jn

t j

j

C X C jn

C j j

π

π

→∞= =

=

∑ ∑

n considérant les nouvelles probabilités de transition

résultant de l'exécution la politique.

Cons

Exem

idér

ple d'un

ons la d

système de prod

euxième politiqu

uction

e b

R

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer dans l'état 3 1 1

Remplacer dans l

1

é

3

' tab

a

R d R d R d R d R

R

R

t 3, 1 1 2 3

mise au point dans

Remplacer dans les états 2 et 3 1 1

l'é

ta

3

t

2

cR 3

Remplacer dans les états 1, 2 et 3 1 3 3 3dR

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmeb

R

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

0 1 0 0

12

0 0 03

P

=

Cons

Exem

idér

ple d'un

ons la d

système de prod

euxième politiqu

uction

e b

R

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

0 1 0 0

12

0 0 03

P

=

0

0

Les probabilités d'équilibre

1

j

M

j i ij

i

M

j

j

p

π

π π

π

=

=

=

=

∑

∑

0 3

1 0 1 2

2 0 1

3 0 1

0 1 2 3

7 3

8 41 1

16 81 1

16 81

π π

π π π π

π π π

π π π

π π π π

= = + +

= +

= +

= + + +

0 1 2 3

Résolvant ce système d'équations:

2 5 2 2, , ,

21 7 21 21π π π π= = = =

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

0-rien faire 0 0 0 0 0

1 1000 0 0 1000

2 3000 0 0 3000

2- mise au point 2 0 2000 2000 4000

3-remplacement 1, 2, 3 0 4000 2000 6000

Évaluons les coûts associés à la politique pour les différents états.C

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer dans l'état 3, 1 1 2 3

mib

R d R d R d R d R

R

se au point dans l'état 2

( ) ( ) ( ) ( )0 1 2 30 1000 4000 6000C b C b C b C b= = = =

0 1 2 3

Probabilités d'équilibre:

2 5 2 2, , ,

21 7 21 21π π π π= = = =

( ) ( ) ( ) ( )0 1 2 3

Coûts associés à la politique pour les différents états:

0 1000 4000 6000

C

C b C b C b C b= = = =

( ) ( )1 0

Coût moyen (à long terme) par unité de

1li

ps

m

temn M

t jn

t j

C X C jn

π→∞

= =

=

∑ ∑

0 1 2 3

Coût moyen(à long terme) pour la politique :

0 1000 4000 6000

2 5 2 20 1000 4000 6000 1667

21 7 21 21

bR

π π π π+ + + =

+ + + =

Tableau des coûts moyens (à long terme) pour les 4 politiques

( ) [ ]

[ ]

[ ]

0 1 2 3Politique , , , , en milliers de $

2 7 2 2 1 25 , , , 2 0 7 1 2 3 2 6 1.923

13 13 13 13 13 13

2 5 2 2 1 35 , , , 2 0 15 1 2 4 2 6 1.667

21 7 21 21 21 21

2 7 1 1 1 , , , 2 0 7 1 1

11 11 11 11 11

a

b

c

E C

R

R

R

π π π π

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ +

[ ]

[ ]

196 1 6 1.727

11

1 7 1 1 1 96 , , , 16 0 14 6 1 6 1 6 3

2 16 32 32 32 32dR

⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

0-rien faire 0 0 0 0 0

1 1000 0 0 1000

2 3000 0 0 3000

2- mise au point 2 0 2000 2000 4000

3-remplacement 1, 2, 3 0 4000 2000 6000

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d

R

R

Remplacer dans l'état 3, 1 1 2 3

mise au point dans l'état 2

Remplacer

dans les ét

3

at

b

c

R

R s 2 et 3 1 1 3 3

Remplacer dans les états 1, 2 et 3 1 3 3 3dR

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmea

R

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 0

13 0

2

0 02 2

P

=

Tableau des coûts moyens (à long terme) pour les 4 politiques

( ) [ ]

[ ]

[ ]

0 1 2 3Politique , , , , en milliers de $

2 7 2 2 1 25 , , , 2 0 7 1 2 3 2 6 1.923

13 13 13 13 13 13

2 5 2 2 1 35 , , , 2 0 15 1 2 4 2 6 1.667

21 7 21 21 21 21

2 7 1 1 1 , , , 2 0 7 1 1

11 11 11 11 11

a

b

c

E C

R

R

R

π π π π

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ +

[ ]

[ ]

196 1 6 1.727

11

1 7 1 1 1 96 , , , 16 0 14 6 1 6 1 6 3

2 16 32 32 32 32dR

⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

0-rien faire 0 0 0 0 0

1 1000 0 0 1000

2 3000 0 0 3000

2- mise au point 2 0 2000 2000 4000

3-remplacement 1, 2, 3 0 4000 2000 6000

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d R

R 3

Remplacer dans l'état 3, 1 1 2 3

mise au point dans

Remplacer d

l'éta

ans

t 2

les état

b

c

R

R

Remplacer dans les ét

s 2 et 3 1 1

ats 1, 2 et 3 1 3

3

3

3

3

dR

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmec

R

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

1 0 0 0

12

0 0 03

P

=

Tableau des coûts moyens (à long terme) pour les 4 politiques

( ) [ ]

[ ]

[ ]

0 1 2 3Politique , , , , en milliers de $

2 7 2 2 1 25 , , , 2 0 7 1 2 3 2 6 1.923

13 13 13 13 13 13

2 5 2 2 1 35 , , , 2 0 15 1 2 4 2 6 1.667

21 7 21 21 21 21

2 7 1 1 1 , , , 2 0 7 1 1

11 11 11 11 11

a

b

c

E C

R

R

R

π π π π

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ +

[ ]

[ ]

196 1 6 1.727

11

1 7 1 1 1 96 , , , 16 0 14 6 1 6 1 6 3

2 16 32 32 32 32dR

⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

0-rien faire 0 0 0 0 0

1 1000 0 0 1000

2 3000 0 0 3000

2- mise au point 2 0 2000 2000 4000

3-remplacement 1, 2, 3 0 4000 2000 6000

( ) ( ) ( ) ( )0 1 2 3Politique Description

Remplacer d

Considérons 4 politique

ans l'état 3

s de décision différentes

1 1 1 a

R d R d R d R d R

R 3

Remplacer dans l'état 3, 1 1 2 3

mise au point dans l'état 2

Remplacer dans les état

b

c

R

R

Remplacer dans les ét

s 2 et 3 1 1

ats 1, 2 et 3 1 3

3

3

3

3

dR

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

Politique entraîne de nouvelles probabilités de transitions entre les états du sytèmed

R

[ ]états 0 1 2 3

0 7 1

1

10

8 16 16

1

2

3

0 0 0

1 0 0 0

1 0 0 0

P

=

Tableau des coûts moyens (à long terme) pour les 4 politiques

( ) [ ]

[ ]

[ ]

0 1 2 3Politique , , , , en milliers de $

2 7 2 2 1 25 , , , 2 0 7 1 2 3 2 6 1.923

13 13 13 13 13 13

2 5 2 2 1 35 , , , 2 0 15 1 2 4 2 6 1.667

21 7 21 21 21 21

2 7 1 1 1 , , , 2 0 7 1 1

11 11 11 11 11

a

b

c

E C

R

R

R

π π π π

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ +

[ ]

[ ]

196 1 6 1.727

11

1 7 1 1 1 96 , , , 16 0 14 6 1 6 1 6 3

2 16 32 32 32 32dR

⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

0-rien faire 0 0 0 0 0

1 1000 0 0 1000

2 3000 0 0 3000

2- mise au point 2 0 2000 2000 4000

3-remplacement 1, 2, 3 0 4000 2000 6000

Tableau des coûts moyens (à long terme) pour les 4 politiques

( ) [ ]

[ ]

[ ]

0 1 2 3Politique , , , , en milliers de $

2 7 2 2 1 25 , , , 2 0 7 1 2 3 2 6 1.923

2 5 2 2 1 35, , , 2 0 15 1 2 4 2 6 1.667

21 7

13 13 13 13 13 13

2 7 1 1 1 , , , 2 0 7 1 1

11 11

21 2

11 1

1

1 11

21 21

a

c

bR

E C

R

R

π π π π

⋅

⋅ + ⋅ + ⋅ + ⋅ = =

⋅ + ⋅ +

+ ⋅ + ⋅ + ⋅ = =

[ ]

[ ]

196 1 6 1.727

11

1 7 1 1 1 96 , , , 16 0 14 6 1 6 1 6 3

2 16 32 32 32 32dR

⋅ + ⋅ = =

⋅ + ⋅ + ⋅ + ⋅ = =

(qui est La meilleu en fait opre p timaol leitique ) b

R

Déterminer une politique optimale relativement à un critère de coût qui doit

être spécifié par

Objectif du

l'agent de

problème:

décision.

Critère de coût qui est souvent utilisé est

coût moy en par u nité de temps

Identification d'une politique déterministe optimale par la programmation linéaire:

Identification d'une politique déterministe optimale par la programmation linéaire:

( ) ( )( )

( )

0

Dans la méthode précédente de résolution exhaustive nous identifions une

politique optimale : , ,

où est la décision si le syst

determin

ème est dans l'éta

t

s

t

i eM

i

R d R d R

d R i

…

( )Politique déter

Exemple d'un sy

ministe optimal

stème

e

de production

: 1, 1, 2, 3bR

( )

[ ]

01 02 0

11 12 1

1 2

Représentation d'une politique de décision à l'aide d'un

Décisions

1 2

0

1ét

tablea

s

u

at

K

K

M M MK

R

k

K

D D D

D D

D

Di

M D D D

R

…

…

…

� � � �

…

{ } { }

( )

Dans le cas de

1 si la décision est prise dans l'état 0, , , 1, ,

0 sinon

et chaque ligne de la

politiqu

matrice ne comporte qu'un seul élément é

e de

gal

terministe

à 1

ik

k iD i M k K

i D R

= ∀ ∈ ∈

… …

( )

[ ]

01 02 0

11 12 1

1 2

Représentation d'une politique de décision à l'aide d'un

Décisions

1 2

0

1ét

tablea

s

u

at

K

K

M M MK

R

k

K

D D D

D D

D

Di

M D D D

R

…

…

…

� � � �

…

( )

[ ]

: 1, 1, 2, 3

Décisions

1 2 3

0 1 0 0

1 1 0 0état

Exemple d'un système

s 2 0 1 0

3 0 0 1

de production

bR

k

i

( )

[ ]

01 02 0

11 12 1

1 2

Représentation d'une politique de décision à l'aide d'un

Décisions

1 2

0

1ét

tablea

s

u

at

K

K

M M MK

R

k

K

D D D

D D

D

Di

M D D D

R

…

…

…

� � � �

…

( )Notons que peut aussi être utilisée pou polr i r tiepré que senter u probabil tne is eD R

[ ]

Décisions

1 2 3

0 1 0 0

1 0.5 0 0.5états

2 0.3 0.2 0.5

3 0 0 1

k

i

( ) ( )

( )

( )

( )

dec. 1 état 1 dec. 3 état 1 0.5

dec. 1 état 2 0.3

dec. 2 état 2 0.2

dec. 3 état 2 0.5

P P

P

P

P

= =

=

=

=

( )

[ ]

01 02 0

11 12 1

1 2

Représentation d'une politique de décision à l'aide d'un

Décisions

1 2

0

1ét

tablea

s

u

at

K

K

M M MK

R

k

K

D D D

D D

D

Di

M D D D

R

…

…

…

� � � �

…

( )

Pour formuler le problème de nous utilisons la

représentation de la matrice pour représenter la

programmation linéair

politique de décis

e

ion.D R

Or puisque la programmation linéaire travaille avec des variables continues, alors

déterminer une

nous considéro politique probans l bilie problème ste optimde ale.

Heureusement, nous avons la chance que la politique optimale générée avec la

programmation linéaire est en fait déterministe.

( )

( )

Variables de décison: état est & décision est

Utilisant les propriétés des probabili

Formulation du

tés conditionn

problème de programmation l

elles:

état est &décision

inéaire:

est

ik

iky

y P i k

P i k

=

������( ) ( )décision est état est état est

ik i ik

iikD

P k i P i

y D

π

π

=

=

� ������ ������������������

1 1

1 1

De plus

puisque 1

K K

il i ik

l k

K K

i ik i ik

k k

y D

D D

π

π π

= =

= =

=

= = =

∑ ∑

∑ ∑

1

Donc

ik ikik K

iil

l

y yD

yπ

=

= =

∑

Contraintes du problème de programmation linéaire (en termes des :)ik

y

1 1

1 1

puisque 1

K K

il i ik

l k

K K

i ik i ik

k k

y D

D D

π

π π

= =

= =

=

= = =

∑ ∑

∑ ∑0 0 1

1. 1 1M M K

i ik

i i k

yπ= = =

= ⇒ =∑ ∑∑

( )

( )

0 1 0 1

2. Se référant à la définition des probabilités à l'équilibre:

0, ,

où les sont les probabilités de transitions suite à la décision

M K M K

j i ij jk ik ij

i k i k

ij

p y y p k j M

p k k

π π= = = =

= ⇒ = =∑ ∑ ∑∑ …

3. 0 0, , ; 1, ,ik

y i M k K≥ = =… …

( )0 1 0 1

coût moyen à long terme par unité

Fonction économiqu

de temps

e:

M K M K

i ik ik ik ik

i k i k

E C C D C yπ= = = =

= =∑∑ ∑∑

ik i iky Dπ=( ) ( )

( )

1 0

1lim

où sont les coûts d'exécution associés

coût moyen (à long terme) pa

aux états

r unité de tempsn M

t in

t i

C X C in

C i i

π→∞

= =

=

∑ ∑ ( )

1

K

ik ik

k

C i C D=

=∑

Problème de programmation linéaire (en termes des )ik

y

( )

( )

0 1 0 1

0 1

1 0 1

Min

Sujet à 1

0, ,

0 0, , ; 1, ,

M K M K

i ik ik ik ik

i k i k

M K

ik

i k

K M K

jk ik ij

k i k

ik

E C C D C y

y

y y p k j M

y i M k K

π= = = =

= =

= = =

= =

=

= =

≥ = =

∑∑ ∑∑

∑∑

∑ ∑∑ …

… …

( )

nombre de contraintes 2

nombre de variables = 1

M

K M

= +

+

( )0 1 0 1

: les contraintes pour déterminer les probabilités à l'équilibre

2. 0, ,

comporte une contrainte

Rapp

redonda t

l

n

e

e

M K M K

j i ij jk ik ij

i k i k

p y y p k j Mπ π= = = =

= ⇒ = =∑ ∑ ∑∑ …

( )Donc le nombre de contraintes linéairement indépendantes se réduit à 1 .M +

( )

( )

0 1 0 1

0 1

1 0 1

Min

Sujet à 1

0, ,

0 0, , ; 1, ,

M K M K

i ik ik ik ik

i k i k

M K

ik

i k

K M K

jk ik ij

k i k

ik

E C C D C y

y

y y p k j M

y i M k K

π= = = =

= =

= = =

= =

=

= =

≥ = =

∑∑ ∑∑

∑∑

∑ ∑∑ …

… …

( )Donc le nombre de contraintes linéairement indépendantes se réduit à 1 .M +

{ }

{ }

Pour tout indice 0, , (i.e., pour tout état ), il doit nécessairement

exister au moins un indice 1, , tel que 0jk

j M j

k K y

∈

∈ >

…

…

{ }1

1

Par contradiction,

si =0 pour tout indice 1, , 0

et alors dans l'évaluation de

nous diviserions par 0.

k

jk jk

k

ik ikik K

iil

l

y k K y

y yD

yπ

=

=

∈ ⇒ =

= =

∑

∑

…

( )Il s'ensuit qu'il y a 1 variables de base dans toute solution de base.M +

( )

( )

0 1 0 1

0 1

1 0 1

Min

Sujet à 1

0, ,

0 0, , ; 1, ,

M K M K

i ik ik ik ik

i k i k

M K

ik

i k

K M K

jk ik ij

k i k

ik

E C C D C y

y

y y p k j M

y i M k K

π= = = =

= =

= = =

= =

=

= =

≥ = =

∑∑ ∑∑

∑∑

∑ ∑∑ …

… …

( )Donc le nombre de contraintes linéairement indépendantes se réduit à 1 .M +

{ }

{ }

Pour tout indice 0, , (i.e., pour tout état ), il doit nécessairement

exister au moins un indice 1, , tel que 0jk

j M j

k K y

∈

∈ >

…

…

( )Il s'ensuit qu'il y a 1 variables de base dans toute solution de base.M +

{ } { } 0, , , une et une seule décision

Par conséqu

ent,

1, , telle q e 0

.u >jkj M k K y∀ ∈ ∃ ∈… …

1

Rappel:

ik ikik K

iil

l

y yD

yπ

=

= =

∑

{ } { } 0, , , une et une seule décision

Par conséqu

ent,

1, , telle q e 0

.u >jkj M k K y∀ ∈ ∃ ∈… …

{ }

1

Il s'ensuit que pour tout état 0, ,

0

la politique optimale est donc déterministe

1

et .

jk jk jk

jk jk K

j jkjl

l

j M

y y yy D

yy

π

=

∈

> ⇒ = = = =

∑

…

Exemple d'un système de production

Decision État Produits Maintenance Perte de Coût total

défectueux

Table des

pro

coûts

duction par semaine

1-rien faire 0 0 0 0 0

1 1000 0 0 1000

2 3000 0 0 3000

2- mise au point 2 0 2000 2000 4000

3-remplacement 1, 2, 3 0 4000 2000 6000

02 12 32

03

31 32

décision 2 ne s'applique qu'à l'état 2 0

décision 3 ne s'applique pas à l'état 0 0

décisions 1 et 2 ne s'applique pas à l'état 3 0

y y y

y

y y

⇒ = = =

⇒ =

⇒ = =

( ) 11 13 21 22 23 330 1

Fonction économique

1000 6000 3000 4000 6000 6000M M

ik ik

i k

E C C y y y y y y y= =

= = + + + + +∑∑

( ) 11 13 21 22 23 330 1

Fonction économique

1000 6000 3000 4000 6000 6000M M

ik ik

i k

E C C y y y y y y y= =

= = + + + + +∑∑

01 11 13 21 22 23 330 1

Contraintes:

1M K

ik

i k

y y y y y y y y= =

= + + + + + + =∑∑

02 12 32

03

31 32

décision 2 ne s'applique qu'à l'état 2 0

décision 3 ne s'applique pas à l'état 0 0

décisions 1 et 2 ne s'applique pas à l'état 3 0

y y y

y

y y

⇒ = = =

⇒ =

⇒ = =

( )

( ) ( ) ( )( ) ( ) ( ) ( )( )

( ) ( ) ( )( ) ( ) ( ) ( )( )

3 3 3

0 01 0 1

01 02 03 01 00 02 00 03 00 11 10 12 10 13 10

21 20 22 20 23 20 31 30 32 30 33 30

Contraintes:

1 2 3 1 2 3

1 2 3 1 2 3

k ik i

k i k

y y p k

y y y y p y p y p y p y p y p

y p y p y p y p y p y p

= = =

= ↔

+ + = + + + + +

+ + + + +

∑ ∑∑

02 12 32

03

31 32

0

0

0

y y y

y

y y

= = =

=

= =

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02

3 appliquée à état 3

1 0 0 02 2

3

k

P

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

20 0 0 1

3 appliquée à l'état 2

1 0 0 0

3

k

P

=

=

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

2

2 appliquée à état 2

0 1 0 0

0 0 0 13

P

k

=

=

[ ]états 0 1 2 3

7 1 10 08 16 161

1 11 02

3 appliquée à l'état 1

1 0

2 23 0 0 0 1

0 0

k

P

=

=

( )

( )

0 1 0 1

2. Se référant à la définition des probabilités à l'équilibre:

0, ,

où les sont les probabilités de transitions suite à la décision

M K M K

j i ij jk ik ij

i k i k

ij

p y y p k j M

p k k

π π= = = =

= ⇒ = =∑ ∑ ∑∑ …

( ) ( ) ( )( ) ( ) ( ) ( )( )

( ) ( ) ( )( ) ( ) ( ) ( )( )

01 02 03 01 00 02 00 03 00 11 10 12 10 13 10

21 20 22 20 23 20 31 30 32 30 33 30

1 2 3 1 2 3

1 2 3 1 2 3

y y y y p y p y p y p y p y p

y p y p y p y p y p y p

+ + = + + + + +

+ + + + +

02 12 32

03

31 32

0

0

0

y y y

y

y y

= = =

=

= =

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02

3 appliquée à état 3

1 0 0 02 2

3

k

P

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

2

2 appliquée à état 2

0 1 0 0

0 0 0 13

P

k

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

20 0 0 1

3 appliquée à l'état 2

1 0 0 0

3

k

P

=

=

[ ]états 0 1 2 3

7 1 10 08 16 161

1 11 02

3 appliquée à l'état 1

1 0

2 23 0 0 0 1

0 0

k

P

=

=

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

( ) ( )3 3 3

0 0 01 13 23 331 0 1

0k ik i

k i k

y y p k y y y y= = =

= ↔ − + + =∑ ∑∑

( )3 3 3

1 1 11 13 01 11 221 0 1

Contraintes:

7 30

8 4k ik i

k i k

y y p k y y y y y= = =

= ↔ + − + + =

∑ ∑∑

02 12 32

03

31 32

0

0

0

y y y

y

y y

= = =

=

= =

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02

3 appliquée à état 3

1 0 0 02 2

3

k

P

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

2

2 appliquée à état 2

0 1 0 0

1 0 0 03

P

k

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

20 0 0 1

3 appliquée à l'état 2

1 0 0 0

3

k

P

=

=

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

[ ]états 0 1 2 3

7 1 10 08 16 161

1 11 02

3 appliquée à l'état 1

1 0

2 23 0 0 0 1

0 0

k

P

=

=

( )3 3 3

2 2 21 22 23 01 11 211 0 1

Contraintes:

1 1 10

16 8 2k ik i

k i k

y y p k y y y y y y= = =

= ↔ + + − + + =

∑ ∑∑

02 12 32

03

31 32

0

0

0

y y y

y

y y

= = =

=

= =

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02

3 appliquée à état 3

1 0 0 02 2

3

k

P

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

20 0 0 1

3 appliquée à l'état 2

1 0 0 0

3

k

P

=

=

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

2

2 appliquée à état 2

0 1 0 0

0 0 0 13

P

k

=

=

[ ]états 0 1 2 3

7 1 10 08 16 161

1 11 02

3 appliquée à l'état 1

1 0

2 23 0 0 0 1

0 0

k

P

=

=

( )3 3 3

3 3 33 01 11 211 0 1

Contraintes:

1 1 10

16 8 2k ik i

k i k

y y p k y y y y= = =

= ↔ − + + =

∑ ∑∑

02 12 32

03

31 32

0

0

0

y y y

y

y y

= = =

=

= =

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02

3 appliquée à état 3

1 0 0 02 2

3

k

P

=

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

20 0 0 1

3 appliquée à l'état 2

1 0 0 0

3

k

P

=

=

[ ]états 0 1 2 3

7 1 10 08 16 163 1 1

1 04 8 8

1 10 02 2 2

3 0 0 0 1

P

=

[ ]états 0 1 2 3

0 7 1 10

8 16 161 3 1 1

04 8 8

2

2 appliquée à état 2

0 1 0 0

0 0 0 13

P

k

=

=

[ ]états 0 1 2 3

7 1 10 08 16 161

1 11 02

3 appliquée à l'état 1

1 0

2 23 0 0 0 1

0 0

k

P

=

=

( )

( )

11 13 21 22 23 33

01 11 13 21 22 23 33

01 13 23 33

11 13 01 11 22

21 22 23 01 11 21

33 01 11

Min 1000 6000 3000 4000 6000 6000

Sujet à 1

0

7 30

8 4

1 1 10

16 8 2

1 1

16 8

E C y y y y y y

y y y y y y y

y y y y

y y y y y

y y y y y y

y y y

= + + + + +

+ + + + + + =

− + + =

+ − + + =

+ + − + + =

− + + 21

10

2

0 0, ,3; 1, ,3ik

y

y i k

=

≥ = =… …

Problème de programmation linéaire (en termes des )ik

y

( ) ( )01 11 13 21 22 23 33

Solution optimale:

2 5 2 2, , ,0 , , , , 0, ,0 ,

21 7 21 21y y y y y y y

= = = =

( ) ( )01 11 13 21 22 23 33

Solution optimale:

2 5 2 2, , ,0 , , , , 0, ,0 ,

21 7 21 21y y y y y y y

= = = =

Combinant avec l'information à priori

02 12 32

03

31 32

0

0

0

y y y

y

y y

= = =

=

= =

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

( )

01 02 03 01 02 03

11 12 13 11 12 13

21 22 23 21 22 23

31 32 33

nous obtenons les valeurs optimales suivantes :

2, , ,0,0 , , 1,0,0

21

5, , ,0,0 , , 1,0,0

7

2, , 0, ,0 , , 0,1,0

21

2, , 0,0,

21

y y y D D D

y y y D D D

y y y D D D

y y y

= ⇒ =

= ⇒ =

= ⇒ =

=

( ) ( )31 32 33, , 0,0,1D D D⇒ =

1

Rappel:

ik ikik K

iil

l

y yD

yπ

=

= =

∑