L ABORATOIRE d’ I NGÉNIERIE des S YSTÈMES A UTOMATISÉS EA 4014 – Université d’Angers

LABORATOIRE d’INGÉNIERIE des SYSTÈMES AUTOMATISÉS

EA 4014 – Université d’Angers

Institut des Sciences et Techniques de l’Ingénieur d’Angers

Master2 RechercheSpécialité : Systèmes Dynamiques et Signaux

ALGORITHME DE FOURIER – MOTZKIN. APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS.ALGORITHME DE FOURIER – MOTZKIN. APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS.

SUJET :

Réalisé par :

Codjo Hermann ZANNOU

Suivi par :

Mr Philippe DECLERCK Maître de Conférences à l’université d’Angers

Juin 2007

PLAN PLAN

OBJECTIF GÉNÉRALOBJECTIF GÉNÉRAL

1 - ALGORITHME DE FOURIER-MOTZKIN1 - ALGORITHME DE FOURIER-MOTZKIN

2 – QUELQUES RAPPELS SUR LES RÉSEAUX DE PETRI2 – QUELQUES RAPPELS SUR LES RÉSEAUX DE PETRI

3 – APPLICATION DE L’ALGORITHME DE FOURIER-MOTZKIN AUX GRAPHES D’ ÉVÉNEMENTS TEMPORISÉS3 – APPLICATION DE L’ALGORITHME DE FOURIER-MOTZKIN AUX GRAPHES D’ ÉVÉNEMENTS TEMPORISÉS

CONCLUSION ET PERSPECTIVESCONCLUSION ET PERSPECTIVES

OBJECTIF GÉNÉRAL

1. un algorithme de résolution des systèmes d’inéquations Ax≤b 1. un algorithme de résolution des systèmes d’inéquations Ax≤b

Analyser :Analyser :

2. une démarche de calcul de trajectoire des graphes d’événements temporisés

2. une démarche de calcul de trajectoire des graphes d’événements temporisés

Partie1 : Algorithme de Fourier-MotzkinPartie1 : Algorithme de Fourier-Motzkin

ALGORITHME DE FOURIER-MOTZKIN

Objectif

m contraintes

n variables

Applicable à des systèmes d’inégalités Ax ≤ b

mnmnm

n

n

x

x

x

.

.

.

.

......

...

...

....

....

2

1

2

1

1

22221

11211

ALGORITHME DE FOURIER-MOTZKIN

Objectif

Elle permet de :

Tester l’existence de solution des systèmes Ax ≤ b. Trouver une solution lorsqu'elle existe.

Elle permet de :

Tester l’existence de solution des systèmes Ax ≤ b. Trouver une solution lorsqu'elle existe.

Principe

ALGORITHME DE FOURIER-MOTZKIN

La méthode comporte deux phases :La méthode comporte deux phases :

Une phase de descente Une phase de descente

Une phase de remontée Une phase de remontée

ALGORITHME DE FOURIER-MOTZKIN

Principe

Descente

Après classement nous avons le système suivant :

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

mnmnm

n

n

x

x

x

.

.

.

.

......

...

...

....

....

2

1

2

1

1

22221

11211

m contraintes

n variables

Etape1: classement

ALGORITHME DE FOURIER-MOTZKIN

Principe

Descente

Etape2 : calcul des bornes

'm i 1

' 1

''1'

'

Sx

ia

ibMinx

mjm

jbx

jaMaxI

(4)(1) et (2) →

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii (1)(2)

(3)

ALGORITHME DE FOURIER-MOTZKIN

Principe

Descente

Etape3 : élimination

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

(3)(2)(1)

Répéter la procédure sur la variable x2

mmibxa

mmjmibbxaa

ii

jiji

,....,1,

,.....,1 ; ,...,1,

'''

'''''(5)

I ≤ S

(4) et (3)

'm i 1

' 1

''1'

'

Sx

ia

ibMinx

mjm

jbx

jaMaxI

(4)(1) et (2) →

ALGORITHME DE FOURIER-MOTZKIN

Principe

Remontée

Connaissant la condition sur la variable xn et en lui

attribuant une valeur, on peut remonter à la condition sur

la variable xn-1 ainsi de suite on remonte à la variable x1.

Connaissant la condition sur la variable xn et en lui

attribuant une valeur, on peut remonter à la condition sur

la variable xn-1 ainsi de suite on remonte à la variable x1.

ALGORITHME DE FOURIER-MOTZKIN

Existence de solution

Le test d’existence de solution est réalisé après élimination des (n-1) premières variables du système d’inéquations linéaires Ax ≤ bLe test d’existence de solution est réalisé après élimination des (n-1) premières variables du système d’inéquations linéaires Ax ≤ b

Il suffit de vérifier si la borne inférieure de la dernière variable est inférieure ou égale à sa borne supérieure.

Il suffit de vérifier si la borne inférieure de la dernière variable est inférieure ou égale à sa borne supérieure.

ALGORITHME DE FOURIER-MOTZKIN

Exemple

Descente

bxx

xx

xx

xx

xx

xx

21

21

21

21

21

21

80

10

02

120

3

22

Pour b = 15

Existence de solution

158

2 , 3 , 221 , 2

1

2

2212

x

xxMinxxMax (7)

(6)

bxx

xx

xx

xx

xx

xx

21

21

21

21

21

21

80

10

02

20

3

22 (1)

(4)

(3)

(5)

(6)

(2)

ALGORITHME DE FOURIER-MOTZKIN

ExempleDescente

8

1521

31

221

4

26

44

2

2

2

2

22

22

x

x

x

x

xx

xx

8

1521

22

34

23

4

2

2

2

2

2

2

x

x

x

x

x

x

8

15,2,4,2

2

3,

3

42

MinxMax

8

15,2

2

32

Minx

Existence de solution

158

2 , 3 , 221 , 2

1

2

2212

x

xxMinxxMax (7)

(6)

158

21

31

221

22

1

32

1

222

1

2

2

2

2

22

22

x

x

x

x

xx

xx

(6)

ALGORITHME DE FOURIER-MOTZKIN

ExempleDescente

cohérentx : 8

15

2

32

Remontée

1 11 2,2

3,11,

4

3111

xxMinxMax

En prenant x2= 3/2 on a :

[1 1.5]T est donc une solution quelconque

Existence de solution

ALGORITHME DE FOURIER-MOTZKIN

Exemple

bxx

xx

xx

xx

xx

xx

21

21

21

21

21

21

80

10

02

20

3

22

Descente

bxx

xx

xx

xx

xx

xx

21

21

21

21

21

21

80

10

02

120

3

22

118

2 , 3 , 221 , 2

1

2

2212

x

xxMinxxMax

Pour b = 11

Existence de solution

ALGORITHME DE FOURIER-MOTZKIN

ExempleDescente

118

21

31

221

22

1

32

1

222

1

2

2

2

2

22

22

x

x

x

x

xx

xx

8

1121

31

221

4

26

44

2

2

2

2

22

22

x

x

x

x

xx

xx

8

1121

22

34

23

4

2

2

2

2

2

2

x

x

x

x

x

x

8

11,2,4,2

2

3,

3

42

MinxMax

8

11,2

2

32

Minx

Existence de solution

ALGORITHME DE FOURIER-MOTZKIN

ExempleDescente

impossibleest qui ce 8

11

2

3

8

11,2

2

322

xMinx

Donc le système n’admet pas de solution pour b =11Donc le système n’admet pas de solution pour b =11

Existence de solution

ALGORITHME DE FOURIER-MOTZKIN

Analyse des itérations

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

itération borneinférieure

Bornesupérieure

Nouveau système après élimination de la variable courante

(1) et (2) finie finie Dépend de (1) et (2)

(3) - ∞ + ∞ Dépend de (3)

(1) et (3) - ∞ finie Dépend de (3)

(2) et (3) finie + ∞ Dépend de (3)

(1) - ∞ finie Arrêt de la descente

(2) finie + ∞ Arrêt de la descente

(1)

(3)(2)

ALGORITHME DE FOURIER-MOTZKIN

Analyse des itérations

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

itération borneinférieure

Bornesupérieure

Nouveau système après élimination de la variable courante

(1) et (2) finie finie Dépend de (1) et (2)

(3) - ∞ + ∞ Dépend de (3)

(1) et (3) - ∞ finie Dépend de (3)

(2) et (3) finie + ∞ Dépend de (3)

(1) - ∞ finie Arrêt de la descente

(2) finie + ∞ Arrêt de la descente

(1)

(3)(2)

ALGORITHME DE FOURIER-MOTZKIN

Analyse des itérations

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

itération borneinférieure

Bornesupérieure

Nouveau système après élimination de la variable courante

(1) et (2) finie finie Dépend de (1) et (2)

(3) - ∞ + ∞ Dépend de (3)

(1) et (3) - ∞ finie Dépend de (3)

(2) et (3) finie + ∞ Dépend de (3)

(1) - ∞ finie Arrêt de la descente

(2) finie + ∞ Arrêt de la descente

(1)

(3)(2)

ALGORITHME DE FOURIER-MOTZKIN

Analyse des itérations

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

itération borneinférieure

Bornesupérieure

Nouveau système après élimination de la variable courante

(1) et (2) finie finie Dépend de (1) et (2)

(3) - ∞ + ∞ Dépend de (3)

(1) et (3) - ∞ finie Dépend de (3)

(2) et (3) finie + ∞ Dépend de (3)

(1) - ∞ finie Arrêt de la descente

(2) finie + ∞ Arrêt de la descente

(1)

(3)(2)

ALGORITHME DE FOURIER-MOTZKIN

Analyse des itérations

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

itération borneinférieure

Bornesupérieure

Nouveau système après élimination de la variable courante

(1) et (2) finie finie Dépend de (1) et (2)

(3) - ∞ + ∞ Dépend de (3)

(1) et (3) - ∞ finie Dépend de (3)

(2) et (3) finie + ∞ Dépend de (3)

(1) - ∞ finie Arrêt de la descente

(2) finie + ∞ Arrêt de la descente

(1)

(3)(2)

ALGORITHME DE FOURIER-MOTZKIN

Analyse des itérations

0

'''

1

''''

1

''

1

, ),....,1(,0

, ),...1(,

, ),,.........1(,

Immibxax

Immibxax

Imibxax

ii

ii

ii

itération borneinférieure

Bornesupérieure

Nouveau système après élimination de la variable courante

(1) et (2) finie finie Dépend de (1) et (2)

(3) - ∞ + ∞ Dépend de (3)

(1) et (3) - ∞ finie Dépend de (3)

(2) et (3) finie + ∞ Dépend de (3)

(1) - ∞ finie Arrêt de la descente

(2) finie + ∞ Arrêt de la descente

(1)

(3)(2)

ALGORITHME DE FOURIER-MOTZKIN

Guide utilisateur

Le programme Scilab développé comprend quatres parties :Le programme Scilab développé comprend quatres parties :

un programme principal « Optim »un programme principal « Optim »

un sous-programme « elimination »un sous-programme « elimination »

un sous programme « remontee »un sous programme « remontee »

un sous programme « affichage »un sous programme « affichage »

Partie2 : Rappels les Réseaux de PetriPartie2 : Rappels les Réseaux de Petri

RAPPELS SUR LES RESEAUX DE PETRI

Définition

Un réseau de Pétri est un moyen de :Un réseau de Pétri est un moyen de :

Modélisation du comportement des systèmes à événements discrets Modélisation du comportement des systèmes à événements discrets

Description des relations existantes entre des conditions et des événements Description des relations existantes entre des conditions et des événements

RAPPELS SUR LES RESEAUX DE PETRI

Description

Figure2 : Réseau de Petri

RAPPELS SUR LES RESEAUX DE PETRI

Graphe d’événements

Figure2 : Réseau de Petri

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Partie 3

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Objectifs

Modéliser les graphes d’Événements Temporisés sous forme algébrique simplifiée Ax ≤ b

Modéliser les graphes d’Événements Temporisés sous forme algébrique simplifiée Ax ≤ b

Ensuite appliquer Fourier-Motzkin pour tracer les trajectoires temporelles .Ensuite appliquer Fourier-Motzkin pour tracer les trajectoires temporelles .

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

La forme algébrique simplifiée Ax ≤ b s’obtient en dupliquant les places qui contiennent plus d’un jeton.

La forme algébrique simplifiée Ax ≤ b s’obtient en dupliquant les places qui contiennent plus d’un jeton.

Cela se fait au prix d’une extension du vecteur d’état x(k) Cela se fait au prix d’une extension du vecteur d’état x(k)

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

Toute place située entre deux transitions internes doit contenir au maximum un jeton Toute place située entre deux transitions internes doit contenir au maximum un jeton

Illustration:

Après transformation nous avons le graphe suivant :

Démarche

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

Toute place située entre une transitions source et une transition interne doit être sans jeton

Toute place située entre une transitions source et une transition interne doit être sans jeton

Illustration :

Après transformation nous obtenons le graphe suivant :

Démarche

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

exemple

Description aux dateurs , algèbre (max,+)

)(8)(

)1(4)(

)1(5)(2)(

2

12

21

kxky

kxkx

kxkukx

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

exemple

Description aux dateurs , algèbre (max,+) Description aux dateurs , algèbre ordinaire

)()(21

kxkx )()(21

kxkx

)()(21

kxkx ))( , )(max(21

kxkx

)1(5)(2)(21

kxkukx

)1(5)(

)(2)(

21

1

kxkx

kukx

)(8)(

)1(4)(

)1(5)(2)(

2

12

21

kxky

kxkx

kxkukx

)(8)(

)1(4)(

)1(5)(

)(2)(

2

12

21

1

kxky

kxkx

kxkx

kukx

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

exemple

)(8)(

)1(4)(

)1(5)(

)(2)(

2

12

21

1

kxky

kxkx

kxkx

kukx

(1)

8)(.0)( 10)(.1

4

5

2

)(

0

0

1

)1(

01

10

00

)(

00

00

00

)(

10

01

01

kukxky

kukxkxkx

(2)

yy

xuxx

BkuDkCxkyA

BkuAkxAkxAkxA

)(.)()(

)()1()()( 1'''

(3)

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Modèle algébrique

Forme générale

Forme généraleForme générale

)(

)('' bkyA

bkAx (4)

(5)

yy

xuxx

BkuDkCxkyA

BkuAkxAkxAkxA

)(.)()(

)()1()()( 1'''

(3)

yy

xuxx

BkuDkCxkA

BkxAkxAkxAA

)(.)()(

)()1()( 1'''

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Systèmes monotones

Un système d’inégalités linéaires de la forme Ax ≤ b est dit sup-monotone (respectivement inf-monotone) si chaque ligne de la matrice A a au maximum un élément strictement positif (respectivement strictement négatif)

Un système d’inégalités linéaires de la forme Ax ≤ b est dit sup-monotone (respectivement inf-monotone) si chaque ligne de la matrice A a au maximum un élément strictement positif (respectivement strictement négatif)

Définitions

Nous avons montré qu’un graphe d’Événements Temporisés modélisé sous forme Ax ≤ b est un système inf- monotoneNous avons montré qu’un graphe d’Événements Temporisés modélisé sous forme Ax ≤ b est un système inf- monotone

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Applications

)(8)(

)1(4)()(.0

)1(5)(.0)(

)(2)(.0)(

2

121

221

21

kxky

kxkxkx

kxkxkx

kukxkx

exemple

SkykxI

SkxkxI

SkxkxkuMaxI

)()(8

)()1(4

)()1(5 , )(2

2

21

12

)(8)(

4

5

2

)(

0

0

1

)1(

01

10

00

)(

10

01

01

2kxky

kukxkx

(1)

(2)

(3)

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Applications

On va représenter la sortie y(k), k = {1 , 10}. Pour cela, on prend l’entrée sur un l’horizon [1 10]On va représenter la sortie y(k), k = {1 , 10}. Pour cela, on prend l’entrée sur un l’horizon [1 10]

k 1 2 3 4 5 6 7 8 9 10u(k) 28 28 67 76 76 115 124 124 172 +∞

0

0)0( ; 28)1( xu

SyI

SxI

SxI

)1(12

)1(4

)1(30

2

1

12)1( , 4

30)1(

yx

exemple

APPLICATION AUX GRAPHES D’ÉVÉNEMENTS TEMPORISÉS

Applications

k 1 2 3 4 5 6 7 8 9 10

x1(k) 30 30 69 78 78 117 126 126 174 +∞

x2(k) 4 34 34 73 82 82 121 130 130 178

k 1 2 3 4 5 6 7 8 9 10y(k) 12 42 42 81 90 90 129 138 138 186

exemple

Conclusion et perspectivesConclusion et perspectives

CONCLUSION ET PERSPECTIVES

Conclusion

Nous avons développé un programme Scilab basé sur l’algorithme de Fourier-Motzkin qui :Nous avons développé un programme Scilab basé sur l’algorithme de Fourier-Motzkin qui :

teste l’existence de solution pour les systèmes linéaires Ax ≤ b.

teste l’existence de solution pour les systèmes linéaires Ax ≤ b.

calcule une solution quelconque des systèmes linéaires Ax ≤ b. calcule une solution quelconque des systèmes linéaires Ax ≤ b.

Maximise ou minimise une fonction objective sous Ax ≤ b. Maximise ou minimise une fonction objective sous Ax ≤ b.

calcule les trajectoires temporelles des graphes d’événements. calcule les trajectoires temporelles des graphes d’événements.

CONCLUSION ET PERSPECTIVES

Perspectives

Le programme développé peut être utiliser pour :Le programme développé peut être utiliser pour :

résoudre les inégalités aux compteurs résoudre les inégalités aux compteurs

la commande des systèmes linéaires la commande des systèmes linéaires

le calcul du taux de production le calcul du taux de production

Merci de votre attentionMerci de votre attention