Logiciel pour décisions optimales dans les systèmes de grandes dimensions

02/08/2016
OAI : oai:www.see.asso.fr:545:2009-3:17207
DOI :

Résumé

Logiciel pour décisions optimales dans les systèmes de grandes dimensions

Métriques

69
10
180.9 Ko
 application/pdf
bitcache://3fbb1f4bb32c15cf93d0f1cbf841b5751ca5da53

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2009-3/17207</identifier><creators><creator><creatorName>Mihaela Mateescu</creatorName></creator><creator><creatorName>Florin Filip</creatorName></creator></creators><titles>
            <title>Logiciel pour décisions optimales dans les systèmes de grandes dimensions</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2016</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 2 Aug 2016</date>
	    <date dateType="Updated">Tue 2 Aug 2016</date>
            <date dateType="Submitted">Mon 10 Dec 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">3fbb1f4bb32c15cf93d0f1cbf841b5751ca5da53</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>28951</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Logiciel pour décisions optimales dans les systèmes de grandes dimensions MIHAELA MATEESCU 1 , FLORIN FILIP 2 1 Centre de l’économie des industries et des services Calea 13 Septembrie nr.13, sect. 5, Bucarest, Roumanie 2 Académie Roumain Calea 13 Septembrie nr.13, sect.5, Roumanie mateescuadina@yahoo.com Résumé— On présente les procédés nécessaires à l’utilisation du paquet de programmes SISCON conçu en vue de l’évaluation des décisions. Ces systèmes ont généralement une structure complexe et, par conséquent, on ne peut pas y utiliser efficacement un calcul global si on le peut du tout. Au début on exécute la décomposition des problèmes de grandes dimensions. Ensuite, on résout les sous problèmes en utilisant des techniques standard d’optimisation. SISCON offre des possibilités de résoudre des problèmes de programmation mathématique non-linèaire et d’évaluer en décisions optimales dans le contrôle des systèmes de grandes dimensions. Tout d’abord, SISCON évalue les modèles mathématiques obtenus à partir des données expérimentales auxquelles on a appliqué la méthode des moindres carrés pour des systèmes linéaires et non-linèaires et ensuite il calcule la solution pour la décision optimale en résolvant des problèmes de programmation mathématique non-linéaire. Mots clés— systèmes de grandes dimensions, programmation non-linèaire, problèmes d’optimisation, paquet de programmes. I.INTRODUCTION La théorie de l’optimisation et, en particulier, celle de la programmation non-linèaire ont constitué la préoccupation de plusieurs scientifiques, tels que : Rosen, Fletcher, Reeves, Powell, Lasdon, Himelblau. Au cours des années 1970, beaucoup de chercheurs ont considère la théorie de l’optimisation comme un environnent opérationnel propice ou développement d’autres théories concernant les systèmes de contrôle (identification des systèmes). Au début des années 1980, le travail dans ce domaine a été orienté vers la réalisation des décisions optimales dans les opérations de contrôle et de surveillance. De nos jours, ce domaine présente encore beaucoup d’intérêt, car les techniques d’optimisation sont utilisées par des produits de logiciel spécialisés tels que Matlab, Simulink pour le contrôle des processus, l’identification des systèmes, les décisions optimales. Les systèmes de grandes dimensions sont représentes comme une collection de sous-systèmes qui observent quelques schémas donnés d’arrangement et d’interconnexion. Chaque sous-système est décrit par un model spécifique. Les interconnexions des sous-systèmes représentent des contraintes. La gestion du système global est très compliqué et nécessite des techniques de décomposition et d’organisation. Ainsi, le problème original est transformé dans un problème équivalent afin de distribuer et ainsi de réduire l’effort fait dans le calcul d’optimisation (Himelblau, 1974 ; Ghaoui, 1997). La décision calculée du système est la solution d’un problème mathématique standard linéaire ou non-linèaire de forme suivante : 1 2{ ( ) ( , ,..., )}Nopt F x F x x x= (1) avec les contraintes : ( ) 0, 1,..., ( ) 0, 1,..., i j g x i m g x j s = = ≤ = (2) où Nxxx ,...,, 21 sont les sous-vecteurs du vecteur x des variables de décision. SISCON détermine la solution optimale * x par des techniques de calcul numérique sélectionnées selon les caractéristique des fonctions-critère et des contraintes. Le reste de cet ouvrage est organisé de manière suivante. D’abord on décrit trois méthodes de décomposition. Ensuite on présente une amélioration de la solution ayant le gradient avec la plus grande pente. Les cas de décomposition décrits ci-dessus sont accompagnés de trois exemples pour mieux illustrer l’utilisation de SISCON. II.TROIS TECHNIQUES DE DÉCOMPOSITION Il y a beaucoup de méthodes pour la décomposition des problèmes de grandes dimensions. Selon les caractéristiques et les moyens de séparation du problème global, on peut utiliser les suivants types de décomposition (Lasdon, 1975 ; Roberts, 2001 ; Oshuga, 1993) : • Problèmes avec structure diagonale-bloc associés aux systèmes de couplage faible ; • Problèmes avec séparation additionnelle dépendantes de fonctions-critère et des contraintes ; • Techniques de relaxation et de partition. Leur présentation va préparer le terrain pour l’utilisation de SISCON dans l’environnement des problèmes de grandes dimensions. A. Le cas de la diagonale-bloc Ce cas s’applique aux problèmes linéaires de la manière suivante : 0 , min( )T T x y c x c y+ (3) avec les contraintes de couplage : 0 0Ax D y b+ = (4) e-STA Copyright 2009 by see Volume 6, N°3, pp 26-30 Bx Dy b+ = (5) où 1 2[ | |...| ]Nx x x x= est un ensemble des xi- vecteurs de dimension in et y est le vecteur de couplage des sous- systèmes, 0,,...,1,0 ≥=≥ yNixi . 1 2[ | |...| ]Nc c c c= est l’ensemble des coefficients correspondantes ; 1 2[ | |...| ]NA A A A= est un ensemble des matrices iA de dimensions ( 0 im x n ) ; 0D est une matrice ( 0 0m x n ) ; 1 2 N 0 0 0...... 0 0 B 0 0...... 0 ................................... 0 0 0 0....... B B B      =       est une matrice bloc-diagonale ayant n matrices Bi plus petites (de dimension i im x n ) sur la diagonale principale. La matrice D peut être partitionnée en N matrices plus petites telles que 1 2[ | |...| ]ND D D D= , avec Di de dimension ( i 0m x n ). Le vecteur b est composé de N sous-vecteurs tels que 1 2[ | |...| ]Nb b b b= , avec bi vecteurs de dimension ni. Dans le cas général la solution est donnée par la méthode de partition de Ritter et pour le cas particulier 0y = , par la méthode linéaire de Rosen. Les problèmes non-linèaires : , min( ( ))T x y c x f y+ (6) avec les contraintes de couplage: ( )Ax F y b+ ≥ et 0x ≥ , où 1 2[ | |...| ]Nx x x x= est un ensemble de xi vecteurs des dimensions in et y est le vecteur de couplage des sous-systèmes, 0, 1,..., , 0ix i N y≥ = ≥ , 1 2[ | |...| ]Nc c c c= est l’ensemble des cœfficients correspondants, 1 2[ | |...| ]NA A A A= est l’ensemble des matrices iA des dimensions ( 0 im x n ), f est une fonction scalaire non-linèaire de y; F Є Rm dont les composantes sont des fonctions de y; S est un sous-ensemble admissible en p E , sélectionné selon les contraintes fonctionnelles. B. Sous-problèmes avec séparation additionnelle Cette deuxième catégorie comprend des problèmes définis comme suit : ( , ) max ( , ) x m F x m (7) Soumis aux contraintes d’entrée-sortie et de couplage suivantes : ( , ) i=1, 2, ..., Ni i i i z G m x= (8) 1 2 ( , , ..., )i i N x H z z z= (9) Le problem original est additionnellement separable par rapport aux functions-critère et aux contraintes, 1 ( , ) ( , ) N i i i i F x m f m x = = ∑ (10) où ( , )i i i f m x est la fonction-critère des sous-système Si et chaque sous-système Si est déterminé par les relations d’entrée-sortie et par les contraintes d’interconnexion, respectivement : ( , ) i=1, 2, ..., Ni i i i z G m x= 1 2 ( , , ..., )i i N x H z z z= Par consequent, la function de Lagrange associée à ce problème est: 1 1 1 ( , ) ( ) ( ) ( ) ( ) N N i i i i T i i i i N i T i i i L f m x G z H x = = = = + µ − + ρ − ∑ ∑ ∑ (11) où ,i i µ ρ représentent les multiplicateurs de Lagrange. Le Lagrangien est additionnellement décomposable et le problème global peut être transformé en N sous-problèmes d’optimisation tels que : ( , ) max ( , )i i i i i x m f x m (12) ( , ) i=1, 2, ..., Ni i i i z G m x= (13) 1 2 ( , , ..., )i i N x H z z z= (14) Avec les contraintes precedents. C. Relaxation et partition La troisième catégorie comprend des problèmes d’optimisation avec beaucoup de contraintes et/ou beaucoup de variables. La partition s’applique lorsqu’on a beaucoup de variables. Soit l’optimisation définie comme : Sxmixgpour xf i ∈=≥ ;,...,10)( )(max (15) où , if g sont des fonctions concaves du vecteur x de dimension N, S est un sous-ensemble de l’espace Euclidian à N dimensions EN ; x est un vecteur suffisamment grand pour produire des difficultés pendant la résolution du problème. Ce procédé divise les variables du problème en deux sous- ensembles. Il agit d’abord sur les variables appartenant à un sous-ensemble et puis sur les variables de l’autre. On utilise la relaxation s’il y a beaucoup de contraintes. Soit le problème : Sxmixgpour xf i ∈=≥ ;,...,10)( )(max (16) où , if g sont des fonctions concaves du vecteur x de dimension N, S est un sous-ensemble de EN , ( ) 0ig x ≥ , des contraintes qui produisent des difficultés pendant la résolution du problème. Le procédé de relaxation consiste dans l’élimination temporaire de quelques contraintes et dans la résolution du problème avec celles qui y restent. Si la solution satisfait les contraintes relaxées, alors la solution est optimale. Si non, une on plusieurs contraintes sont imposées et le procédé est réitéré. e-STA Copyright 2009 by see Volume 6, N°3, pp 26-30 III.LE CALCUL DE LA DIRECTION DE RECHERCHE DANS LES METHODES DE GRADIENT Les méthodes de gradient ne peuvent être utilisées qu’après la décomposition des problèmes de grandes dimensions. Ces techniques sont utilisées pour résoudre des problèmes d’optimisation représentés en forme standard (programmation non-linèaire). L’algorithme standard pour toutes les méthodes de gradient comprend les phases importantes suivantes : • La sélection des données d’entrée (fonctions-critère, point de départ, conditions d’arrêt, initialisations additionnelles) ; • L’évaluation de la direction de recherche kd , dans le space d’optimisation ; • Le calcul de la longueur optimale du pas ks ; • Le calcul d’un point nouveau avec la relation ; • Si la condition est satisfaite, l’algorithme s’arrête. Notre contribution est la nouvelle façon globale d’aborder le calcul de recherche de la direction kd du gradient. En construisant nos outils-logiciel nous avons utilisé cette façon originale d’aborder le calcul de la direction de recherche dans l’optimisation par le méthode du gradient. Soit ( )F x la fonction-critère qu’on doit minimiser et définissons la distance entre deux points 1x et 2x dans l’espace Hilbert N χ par : 2 1 2 1 2 1 2( , ) ( ) ( )T d x x x x A x x= − − (17) où ][ NxNA est une matrice définie positive, qui assure 1 2 1 2( , ) 0, ( )d x x x x> ∀ ≠ . Le lieu géométrique des points N x χ∈ placé à une distance d du point fixe kx est un ellipsoïde avec le centre en kx , qui est décrit par l’équation suivante : 2 ( ) ( ) ( )T T k kd x x A x x x A x= − − = ∆ ∆ (18) où kx x x∆ = − . Maintenant, on peut déterminer le déplacement de kx vers un point de l’ellipsoïde, x , où la valeur de ( )F x est la plus petite. Ce point est k kx x x= + ∆ qui est, en fait, le suivant 1kx + utilisé dans l’algorithme récurrent standard 1k k kx x x+ = + ∆ . Après, on résout le problème d’optimisation : 2 min{ ( )| ( ) }T x F x x A x d∆ ∆ = (19) Si une approximation de ( )F x par une série Taylor autour de kx est acceptée et cette série est coupée après sa part linéaire, alors : ( ) ( ) ( ) ( )T k kF x F x x F x≅ + ∆ ∇ (20) et (19) est réduite à 2 min{ ( ) ( ) ( ) | ( ) }T T k k x F x x F x x A x d+ ∆ ∇ ∆ ∆ = (21) On peut observer que (21) est un problème d’optimisation avec contraintes qu’on peut résoudre en utilisant les multiplicateurs de Lagrange. Maintenant on va construire la fonction Lagrange : 2 ( , ) ( ) ( ) ( ) [ ( ) ]T T k kL x F x x F x d x A xλ = + ∆ ∇ + λ − ∆ ∆ (22) Les conditions stationnaires sont : ( ) 2 0k L F x A x x ∂ = ∇ − λ ∆ = ∂ (23) 2 ( ) 0T L x A x d ∂ = ∆ ∆ − = ∂ λ (24) De la condition (23) on obtient : 1 1 ( ) 2 kx A F x− ∆ = ∇ λ (25) et on peut écrire : 1 1 1 ( ) 2 k k kx x A F x− + = + ∇ λ (26) Cela est la solution de la relation (19), c’est-à-dire la direction qui doit être suivie pour minimiser ( )F x . Cette direction est : 1 ( )k kd A F x− = ∇ (27) et satisfait la condition de descente : 1 ( ), ( ) ( ( )) , ( ) 0T k k k kd F x F x A F x− ∇ = ∇ ∇ < (28) avec 1 0A− > . Pour une sélection adéquate de la matrice A, on doit tenir compte des méthodes de gradient déjà connues : • Si A=I , où I est la matrice unité, ( )k kd F x= − ∇ , on a la méthode du gradient du premier ordre (Cauchy) ; • Si 1 kA I− = β avec 1 1 ( ) ( ) ( ) ( ) T k k k T k k F x F x F x F x− − ∇ ∇ β = ∇ ∇ (29) alors : ( )k k kd I F x= − β ⋅ ⋅ ∇ , on a les méthodes du gradient conjugué ; • Si A-1 =Hk, avec Hk>0, alors ( )k k kd H F x= − ∇ , on a les méthodes de gradient à métrique variable ; • Si 1 kA I− = θ , alors ( )k k kd I F x= − θ ∇ , on a les méthodes de projection du gradient ; • Si A-1 = Hess-1 (F(xk)), alors 1 ( ( )) ( )k k kd Hess F x F x− = − ∇ , on a des méthodes de gradient du second ordre (de Newton Raphson). IV.LE PAQUET DE LOGICIEL SISCON L’interface du paquet de logiciel SISCON est flexible et permet une très facile des données. Les programmes sont conçus de telle manière qu’on puisse suivre les algorithmes d’une étape à l’autre. Les algorithmes noyaux sont implémentés en bibliothèques liées de manière dynamique afin de permettre qu’il soit appelés de divers modules (ex. Les algorithmes SIMPLEX et BOXE ou NEWTON RAPHSON) et d’avoir un contrôle plus rigoureux des applications. Cette implementation a aussi l’avantage de pouvoir mieux gestioner les resources de l’ordinateur (ex. la gestion des operations d’empilement afin que chaque function puisse être tirée de la pile). Les algorithmes sont rangés en classes dans la bibliothèque et pour chaque classe on a des procédés d’initialisation, de contrôle et d’effacement de la mémoire. Puisqu’on utilise des techniques orientées sur l’objet, on peut étalonner des algorithmes nouveaux en se basant sur ceux qui existent déjà. Les programmes sont écrits en langage C++. Dans ce qui suit on présente l’utilisation de SISCON pour les trois cas de décomposition décrits dans la section II. e-STA Copyright 2009 by see Volume 6, N°3, pp 26-30 Pour le premier cas de décomposition décrit dans la section II, applique la technique de Rosen comme il résulte de la fig.1. Fig.1 Exemple de procédé d’optimisation du logiciel en utilisant la technique de Rosen On fait entrer les fonctions-critère et les contraintes. Ainsi, le problème initial est changé dans un problème avec structure diagonale-bloc. L’utilisateur doit définir : • le nombre des blocs et le nombre de contraintes de couplage ; • les variables du système diagonale-bloc pour chaque bloc ; • le nombre de contraintes qui correspond à chaque bloc. Les variables de la structure diagonale-bloc sont partitionnées et ensuite visualisées. Pour effectuer la partition, les tableaux de base initiaux qui correspondent à chaque bloc sont déterminés en résolvant les sous-problèmes : min T i ic x relativement à i i iB x b= . Le problème est réduit à la forme canonique pour les variables de base de chaque bloc, en exécutent une série d’opérations pivot utilisant ces bases. Ensuite, on peut visualiser le système angulaire résulté et le problème réduit. On résout ce dernier et puis on effectue un test d’optimalité. Si ce teste échoue le système angulaire initial est pivoté encore une fois, et il en résulte un nouveau système. On peut visualiser ce nouveau système angulaire et aussi le problème réduit. Le pivotement est répété jusqu’à ce que le test d’optimalité soit satisfait. Alors la solution finale est visualisée. Pour la coordination par les multiplicateurs de Lagrange on doit faire entrer : le nombre des sous-systèmes, la fonction- critère pour chaque sous-système, le nombre maximum d’itérations et les conditions d’arrêt. Aussi, pour chaque sous- système, on doit faire entrer le nombre des contraintes du modèle est et des contraintes de couplage, le modèle et les contraintes de couplage, les valeurs initiales des multiplicateurs ρ et le nombre de contraintes technologique implicites et explicites. Au niveau local, les problèmes d’optimum sont résous en utilisant l’algorithme de Box. Les solutions sont transmises au niveau ordinateur où on détermine un nouveau vecteur ρ . Le procédé est réitéré jusqu’à ce que le critère de convergence soit satisfait. Pour la troisième cas de ècomposition décrit dans la section II, on suggère l’utilisation de la technique de Bender. On fait entrer la fonction-critère et les contraintes et le problème primal est transformé dans un problème dual qu’on peut visualiser, comme on peut voir dans la fig. 2. Le problème primaire devient linèaire en prenant le vecteur de départ y. On résort le problème dual et on visualise les solutions. On construit le problème réduit et on le visualise. Les solutions qui en résultant sont testées et le procédé est réitéré si les contraintes ne sont pas satisfaites. Fig.2 Exemple de procédé d’optimisation du logiciel en utilisant la technique de Benders La fonction-critère peut montrer n’importe quelle non-linèarité parce que l’analyseur syntactique prend la suite de caractères et transforme en appels de fonctions du langage C++. L’interface de l’utilisateur permet que le procédé de recherche soit gardé dans un fichier et que les valeurs de la fonction- critère et la valeur individuelle de chaque variable de la fonction-critère soient visualisées. Avant de résoudre le problème globale d’optimisation SISCON détermine aussi les modèles mathématique de décision des systèmes. Ceux-ci peuvent être linèaires ou non- linèaires, ou à l’analyseur syntactique, qui lit et interprète les fonctions, ce programme permet d’ôter presque tout type de non-linèarité. Aussi il donne la possibilité de sélectionner les variables d’entrée ou d’engendrer automatiquement des combinassions des variables d’entrée afin de trouver la combination qui détermine le modèle le plus proche de la réalité. Les données peuvent être retirées d’un fichier ou introduites directement en utilisant le clavier. V.CONCLUSIONS Le contrôle des systèmes de grandes dimensions est encore considéré une tâche complexe et un problème ouvert pour la recherche future. On a présenté ici quelques résultats obtenus dans la conception d’un paquet de logiciel SISCON, consacré e-STA Copyright 2009 by see Volume 6, N°3, pp 26-30 aux problèmes de décision optimale et qui utilise les techniques de gradient. Ce paquet de logiciel peut être intégré dans la classe des stratégies pour le contrôle des décisions dans les systèmes industriels et économiques de grandes dimensions. SISCON rend meilleur l’appuie des décisions dans les applications relatives au contrôle et à la surveillance. Quelques tentatives récentes d’implémenter ce logiciel dans l’industrie du ciment afin de réduire le coût de fabrication du ciment et, en même temps, d’améliorer le rendement ont donné des résultats satisfaisants. Le même logiciel a été utilisé aussi dans l’optimisation du processus de combustion dans les installations de préchauffage du haut fourneau. Dans ce moment ce logiciel est utilisé dans l’évaluation de la demande pour la consommation alimentaire en Roumanie. Nous prennons comme les données empiriques les tendances des consommations réelles au cours de la période 1985-2007 et les restrictions dans le modèle, deux variantes de la croissamce économique et une variante de l ‘élasticité de la demande alimentaire en fonction de revenu réel des employés. VI.RÉFÉRENCES [1] Ghaoui, El. (1997) Multi objective robust measurement – scheduling for discrete time systems: an LMI Aapproach, Proceedings of the fourth IFAC Conference, pp.66-72, Bucharest [2] Himelbau, D. (1974). Decomposition of Large Scale Problems, Mc.Grew-Hill Book Company [3] Lasdon, L. (1975). Optimisation Theory for Large System, Engineering Publishing House, Bucharest [4] Oshuga, S (1993). How can knowledge-based systems solve large scale problems - model-based decomposition and problem solving, Knowledge-Based Systems, vol.6, pp.38-62. [5] Roberts, P.D. (2001). Control using integrated system optimisation and prameter estimation, Preprints of IFAC Symposium Large Scale System Theory and Application, Bucharest. [6] Serbanescu, M., D. Popescu and M. Alexandru (1999). Optimal decisions in multi model systems, CSCC99 Conference, Athens e-STA Copyright 2009 by see Volume 6, N°3, pp 26-30