Un enfoque formal para la optimización de sistemas a eventos discretos

Abstract

Cette thése est centrée sur I'optimisation de systemes dynamiques a événements discrets sur un domaine fini. Deux approches fondamentales de l'optimisation sont considérées : le príncipe du mínimum et la programmation dynamique. Dans chaque cas une méthode de calcul formei est développée pour l'optimisation d'une forme polynomiale sur un domaine de définitich fini. Le résultat de l'approche basée sur le principe du minimum est établí sons la forme d'un théoreme dans lequel la condition (nécessaire) d'optimalité est définie en terme d'une inégallité variationnelle sons une forme séparable par rapport aux etapes (instants). Celle-ci est explicitement fonction de la variable de commande á l'instant courant, (commande courante), de la forme paramétrée de celle-ci et de l'etat du systéme auquel peuvent s'ajouter des paramétres exogénes impliqués dans le modéle d'évolucion. La résolution de cette ínégalíté variationnelle paramétrique est développée selon une procédure de type Min-Max avec une minimisation par rapport aux commandes courantes et une maximisation par rapport aux autres commandes. L'algorithme correspondant est désigné par le symbole SCDO (Symbolic Computation for Discrete Optimisation). L'approche basée sur la programmation dynamique exploite le caractére paramétrique de cette méthode de décomposition. L'intégration de l'algorithme SCDO dans les deux phases de ce processus d'optimisation permet ici encore d'exprimer la séquence de commandes optimales sous une forme explicite de l'état du systeme et des autres parametres exogénes. Dans ce mémoire, nous considérons également le principe de relaxation pour transformer le probléme discret en un probleme continu de résolution classique. Ainsi, pour une famille particulíere de processus discrets línéaires par rapport a l'état et de fonction de cout concave, nous obtenons une condition de type principe du minimum, équivalente pour l'optimum relaxé et l'optimum de probleme original. Dans le cas de fonctions de cout linéaires, la condition obtenue est celle du principe du mínimum classique.

El desarrollo de esta tesis se centra en la optimización de Sistemas Dinámicos a Eventos Discretos sobre dominios finitos. Para tal fin se abordaron los dos principios básicos para tal optimización. El Principio de Mínimo" y "la Programación Dinámica", Sobre cada uno de ellos, una extensión basado en el cálculo formal se realizó considerando dominios de definición finitos y parámetros exógenos de evolución. El resultado del enfoque basado sobre el principio está dado en la forma de un teorema, en donde la condición (necesaria) de optimalidad es definida en términos de una desigualdad variacional sobre un forma separable en etapas (instantes).. Esta es una función explicita de la variable de control en el instante actual (control actual) en forma paramétrica de esta y el estado del sistema el cual puede contener parámetros exógenos en el modelo de evolución La resolución de esta desigualdad variacional paramétrica es desarrollada según un procedimiento del tipo Min-Max con una minimización en función del control de la etapa actual y una maximización en función del control óptimo de esa etapa. El algoritmo correspondiente para realizar la minimización es designado por el símbolo SCDO (Symbolic computation for Discrete Optimization), y obtiene mínimos (parametrizados) de una función definida sobre un el híper-cubo con vértices en {-1,1}. El enfoque basado sobre la Programación Dinámica explota el carácter parametrito de este método de descomposición. La integración del algoritmo SCDO en las dos fases de este proceso de optimización permite expresar la secuencia de controles óptimos bajo una forma explícita del estado del sistema y los otros parámetros exógenos. En ésta memoria nosotros también consideramos el principio de relajación para transformar el problema discreto en un problema continuo de resolución clásica. Así para una familia particular de procesos discretos lineales en el estado y una función de coto cóncava, obtenemos una condición del tipo principio de mínimo para la condición de equivalencia entre el óptimo relajado y el óptimo del problema original. Para el caso donde la función de costo es lineal, la condición de equivalencia obtenida es una condición del tipo principio de mínimo clásico.