Réalisation d'un système expert d'aide à la répartition économique des puissances dans un réseau électrique

Conclusion

L'importance du modèle est grande dès lors où toute autre projection finira par un résultat qu'il faut juger par sa justesse et exactitude. Les chemins mathématiques entrepris pour arriver à destination d'un éventuel résultat qualité par une côte positive ou le contraire l'algorithme en dépendant.

La projection de ces modèle mathématiques se traduira par la naissance d'un modèle vivant et équivalent sur, en méme temps, l'écran et la mémoire d'un ordinateur.

6 Références

1 A.Feliachi, A.P.Meliopoulos, "Modeling and Simulation of Large Scale Interconnected Systems", Advances in Modeling & Simulation, AMSE Press, Vol. 1, No. 1, pp. 33-49, 1984.

2 Sheble G.B.; Real-time economic dispatch and reserve allocation using merit order loading and linear programming rules; IEEE Transactions on Power Systems, Vol. 4, No. 4, October 1989.

3 Liu D., Cai Y.; Taguchi Method for Solving the Economic Dispatch Problem with Nonsmooth Cost Functions; IEEE transaction on power system, VOL. 20, NO. 4, November 2005.

4 Liu D., Cai Y.; Taguchi Method for Solving the Economic Dispatch Problem with Nonsmooth Cost Functions; IEEE transaction on power system, VOL. 20, NO. 4, November 2005.

5 L.L. Grigsby, A.P. Hanson R.A. Schlueter and N. Alemadi; «Power Systems»; The Electrical Engineering handbook 063, CRC Press LLC, 2000.

6 Tamali M.; Conception d'un logiciel de modélisation et simulation des réseaux électriques NMSS; Master thesis equivalent diploma; presented in 1995.

7 A.J. Pansini; «Guide to Electrical Power Distribution Systems»; Sixth Edition; THE FAIRMONT PRESS, INC; ISBN: 0-88173-505-1; [TK3001.P284 2005].

8 G.W Stagg & A.H. El Abiadh: "Computer Methods in Power System Analysis" Edition McGraw Hill, 1968.

9 M. Rahli: " La commande optimale des puissances actives par la programmation linéaire " Thèse de Magister soutenue le 3 juillet 1985, USTO.

THÉORIE DES

GRAPHES

CHAPITRE III

III. Théorie des graphes

Introduction

L'histoire de la théorie des graphes débute avec les travaux d'Euler au XVIIIème siècle et trouve son origine dans l'étude de certains problèmes, tels que celui des ponts de Königsberg (Fig. III ), la marche du cavalier sur l'échiquier ou le problème de coloriage de cartes.

Fig.III Les sept ponts de Königsberg

La théorie des graphes s'est alors développée et intégrée dans diverses disciplines telles que la chimie, la biologie, les sciences sociales et sans oublier les réseaux d'ordinateurs et de télécommunication. Depuis le début du XXe siècle, elle constitue une branche à part entière des mathématiques, grace aux travaux de König, Menger, Cayley puis de Berge et d'Erdös .

De manière générale, un graphe permet de représenter la structure, les connexions d'un ensemble complexe dit `système' (S) en exprimant les relations entre ses éléments tel que les réseaux de communication, les réseaux routiers, interaction de diverses espèces animales, circuits électriques, en programmation et le plus intéressant son application aux sciences de l'Internet.

Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété de problèmes en se ramenant à l'étude de sommets et d'arcs Les derniers travaux en théorie des graphes sont souvent effectués par des informaticiens, du fait de l'importance que revét l'aspect algorithmique

Définitions relatives à la théorie des graphes

a. Définition du graphe simple Un graphe simple noté G est un couple formé de deux ensembles liés par une application

mathématique. L'un d'eux est l'ensemble X={x ,x ,...,x_n} dont les éléments sont appelés `sommets', l'autre est l'ensemble A={a ,a ,...,a<sub>m</sub>}, partie de l'ensemble P (X) des parties à deux éléments (couple de sommets) de X, dont les éléments sont appelé `les arêtes'. On notera cette relation G=(X,A).

Lorsque a={x,y}EA, on dit que a est l'arête de G d'extrémités x et y, ou que a joint x et y, ou que a passe par x et y. Les sommets x et y sont dits adjacents dans G.

Fig III : Graphe G(X,A)

b. Définition du multi-graphe Un multi-graphe G = (X,A,f) est déterminé par:

· L'ensemble X des sommets

· L'ensemble A, cette fois abstrait

· L'application f : A [P (X)]

Fig III. : Exemple de multi-graphe

Dans cet exemple, x, y, z, t sont les sommets du multi-graphe et :

f(a )=f(a )=f(a )=f(x,t); f(a )=f(x,y}; f(a )=f(x,z}; f(a6)=f(z,t).

Un multi-graphe avec boucles est un triplet (X, A, f) où f est une application de A dans P (X)uP (X), en d'autres termes, un multi-graphe avec boucles peut comprendre des arêtes multiples entre deux sommets donnés ainsi que des boucles multiples en un sommet.

Exemples :

i. Le graphe d'un tournoi, T=(X,A) où :

X est l'ensemble des participants au tournoi

A est l'ensemble des paires de joueurs se rencontrant dans le tournoi.

ii. Le graphe discret d'ordre n, Dn,=(X, 0).

iii. Le graphe complet d'ordre n, Knn où X , ,...,n} et A = P2(X)

Fig. III. : Types de graphes

iv. Le graphe biparti-complet _Kpq où X={x ,x ,...,x_p,yl,y ,...,y_q} et A=f(xi,yj}/ =i=p et =j=q}

Fig. III. : Exemple de graphe biparti 4, 2

v. d. Le cycle _Cnn où X={ ,2....,n} et A={{ ,2},{2,3},...,{n- ,n},{n, }}

Fig. III. : Exemple de graphe cycle

c. Définition du degré des sommets Soit G=(X,A) un graphe simple, et x un sommet de ce graphe. Le degré de x, noté d(x), est

le nombre d'arêtes incidentes à x, c'est-á-dire contenant x. Lorsque d(x)=0, on dit que le sommet x est isolé, lorsque x = , il est dit pendant.

Exemples :

si x est un sommet de _Cnn d(x)

si x est un sommet de _Kpq, d(x)=n-

d. Définition du graphe régulier Un graphe simple est dit régulier de degré r, lorsque tous ses sommets sont de degré r.

e. Définition du graphes orientés

Un graphe orienté G_n est formé de deux ensembles: un ensemble X={x ,x ,...,x_n} dont les

éléments sont appelés sommets, et un ensemble A={al,a ....,a._n), partie du produit cartésien X×X, dont les éléments sont appelés arcs. On notera

G_n=(X,A)

Fig. III. : Graphe orienté

Si a=(x,y) est un arc du graphe G, x est l'extrémité initiale de a et y l'extrémité finale de a. Remarque

? 1 ( )

s i x

À tout graphe orienté G_n(X,A), on associe le graphe simple G(X,B) où: {x,y}EB?((x,y)EA ? 0 ( )

i x x A

?

ou (y,x)EA))

f. Définition du degré de sommet d'un noeud de G_n Soit x un sommet d'un graphe orienté On note d⁺(x) le nombre d'arcs ayant x comme

extrémité initiale, et d^-(x)le nombre d'arcs ayant x comme extrémité finale. Ainsi, on a:
d(x)=d+(x)+ d-(x) Eq. III.

g. Définition de la matrice d'adjacence Soit G=(X,A) un graphe orienté, avec X={x ,x ,...,x_n}. La matrice XJLXjLIfnIf du graphe G

est la matrice N1(G) dont les coefficients _mi,j sont définis par:

Eq. III.

h. Définition de la distance Soit G=(X,A) un graphe orienté. Pour tout (x,y)EX , la distance entre le sommet x et le

sommet y est le nombre d(x,y) défini par:

s'il n'existe pas de chemin de x à y d(x,y)=min{l(c)/c est un chemin de x à y}

l(c) désigne la longueur du chemin c. La matrice des distances du graphe G est la matrice D={d(i,j)=(d(xi,xj)}.

Fig. III 8 : Graphe G_n et calcul de la matrice D

Eq. III.

La matrice des distances de G est :

i. 2. Algorithme de Moore

Soit x et y deux sommets d'un graphe G (X,A) L'algorithme suivant calcule la distance

d(x,y) :

On étiquette les sommets de G en observant les règles suivantes :

· le sommet x reçoit l'étiquette

· si (u, v) E A et a est étiqueté k :

i. si v n'est pas étiqueté, alors v reçoit l'étiquette k

ii. si v est étiqueté l, alors l'étiquette de v est remplacée par min(l, k+ ) Si, à la fin, y à une étiquette k, alors d(x,y)=k, sinon d(x,y)=oo

Fig. III.9 : Graphe G_n et calcul de distance On a dans cet exemple: d(x,y) ~

j. Définition des graphes valués et problème du plus court chemin

Beaucoup de problèmes peuvent être modélisés en utilisant des graphes valués. Les

problèmes de cheminement dans les graphes, en particulier la recherche du plus court chemin,
comptent parmi les problèmes les plus anciens de la théorie des graphes et les plus importants
par leurs applications: coût de transport, temps de parcours, problème de trafic. Les

algorithmes de recherche de plus court chemin seront différents selon les caractéristiques du graphe. Un graphe valué est un graphe orienté G_n (X,A), muni d'une fonction C appelée fonction de coût.

Fig. III.10 : Graphe valué de modélisation d'un réseau aérien

k. Definitions du coût d'un chemin

si i _j

Le cofit d'un chemin est la somme des coûts des arcs de ce chemin On peut définir la j matrice des cotits du graphe, c'est la matrice C _={ci,j} où : c est le coût de arête (i

Eq. III.

i
·

DEFINITION La matrice de coût minimum, M = (mij), est définie par ^:tr m n

Eq. III.

l. Definition de l'arbre Un arbre est un graphe simple connexe ne possédant pas de cycle simple.

Fig. III.11 : Graphe ARBRE.

Fig. III.12 : Exemple d'obtention d'un arbre à partir du graphe G(X,A)

m. Définition de l'arbre partiel de coût minimum

Fig. III.13 : Graphe simple Fig. III.14 : Arbre du graphe simple

Le problème consiste à construire un graphe partiel, connexe, comprenant un nombre minimal d'arêtes Le graphe (Fig. VI.13) contient 6 sommets, le sous-graphe cherché doit donc contenir 5 arêtes (Fig. VI. ) Il s'agit donc de construire un arbre de recouvrement du graphe (On peut montrer que la relation I A=X- caractérise les arbres parmi les graphes simples connexes).

n. Algorithme de SOLLIN-CALESTAGNE G=(X,A,v) est un graphe simple connexe valué.

Tab. III.1 : Algorithme de SOLLIN

) a ={x ,y } est une arête de coût minimum. On pose S={x ,y } et T={a1}. Passer à (2) ) Si S X, alors l'arbre (S,T) est l'arbre cherché, sinon, passer en )

) On choisit une arête a={x,y} de coût minimum ayant un sommet dans S et l'autre dans le complémentaire de S dans X. On remplace S par Su{x, y} et T par Tu{a}; Passer en

)

o. C Terminologie

Tab. III.2 : Terminologie de la théorie des graphes

Sous-graphe : H = (Y, B) est un sous-graphe de G = (X, A) si Y C_ X et CA .

Graphe partiel :H = (Y, B) est un graphe partiel de G = (X, A) si Y = X et CA .

Ordre d'un graphe l'ordre d'un graphe est le nombre de sommets de ce graphe Chaîne : suite finie de sommets reliés entre eux par une arête.

Chaîne simple : chaîne qui n'utilise pas deux fois la même arête.

Chaîne eulérienne : chaîne simple passant par toutes les aretes d'un graphe Chaîne hamiltonienne : chaîne simple passant par tous les sommets d'un graphe une et une seule fois.

Chemin : suite de sommets reliés par des arcs dans un graphe orienté.

Cycle : chaîne qui revient à son point de départ.

Cycle eulérien : cycle simple passant par toutes les aretes d'un graphe une et une seule fois. Cycle hamiltonien : cycle simple passant par tous les sommets d'un graphe une et une seule fois.

Graphe connexe : un graphe G est dit connexe si pour toute paire de sommets f X _I Y} de G, il existe une chaîne de premier terme x et de dernier terme y.

Arbre : graphe connexe sans cycle simple et sans boucle.

Graphe eulérien : graphe qui possède un cycle eulérien.

Graphe semi-eulérien : graphe qui possède une chaîne eulérienne.

Graphe hamiltonien : graphe qui possède un cycle hamiltonien.

Graphe semi-hamiltonien: graphe qui possède une chaîne hamiltonienne.

Graphe valué : graphe oil des réels sont associés aux arêtes. Dans cet exposé, on ne considérera que des valuations positives.

Longueur d'une chaîne nombre des arêtes qui composent la chaîne.

Valeur d'une chaîne somme des valeurs des aretes (arcs) d'une chaîne d'un graphe valué. Distance entre deux sommets : longueur de la plus courte chaîne joignant ces deux sommets.

Diamitre d'un graphe maximum des distances entre les sommets d'un graphe Indice chromatique : nombre minimal de couleurs permettant de colorier les sommet

Quelques idées pour publication

· Modélisation des réseaux par la topologie des graphes

· Application du théorème de recherche du plus court chemin au problème de planification des sessions de maintenance dans les réseaux de transport de l'énergie électriques

· Algorithme de Dijkstra et recherche du plus court chemin.

· Simulation visuelle des réseaux électrique dans NMSS par la topologie des graphes

Références bibliographiques

. E.SIGWARD; `Introduction à la théorie des graphes', [e-mail] J LABELLE; `Théorie des graphes'; Edition MODULO; ISBN - 9 ; 9 '