Application de méthodes de programmation dynamique stochastique au problème de planification de la production d'hydroélectricité

La planification de la production d'hydroélectricité est un problème complexe qui se situe au croisement de plusieurs branches des mathématiques appliquées. La prise de décisions optimales ou quasi-optimales passe par l'optimisation, parfois déterministe et en nombre entiers (planification court-terme), parfois stochastique et continue (planification moyen- et long-terme). La maîtrise de l'aspect stochastique des apports hydriques naturels et/ou des prix de l'énergie passe par l'utilisation et le développement de modèles statistiques probabilistes. La modélisation des fonctions de production des centrales hydroélectriques passe par l'optimisation non-linéaire et des méthodes de calcul numériques. Dans ce mémoire, deux volets sont étudiés : méthodes l'approximation concave des fonctions de production des centrales hydroélectriques et méthodes d'optimisation stochastique appliquées au problème de planification moyen-terme de la production d'hydroélectricité sous incertitude portant sur les apports hydriques naturels. Les fonctions de production des centrales hydroélectriques dépendent du débit turbiné et de la hauteur de chute. Ces fonctions ne sont ni linéaires ni même concaves. Pour les incorporer à un modèle mathématique linéaire de maximisation, il faut au préalable les approximer par des fonctions concaves linéarisables. Pour ce faire, on propose deux méthodes : approximation de la fonction objectif par enveloppe concave et approximation par une fonction concave linéaire par morceaux. La dernière étant en deux variantes : construction d'hyperplans d'ajustement avec le critère des moindres carrés ou le critère de minimisation de l'erreur maximale par rapport à la vraie fonction de production. On conclut que les deux méthodes sont à peu près équivalentes en matière d'erreur-type mais que la deuxième méthode est meilleure sur le temps d'exécution des modèles de planification de la production utilisés. Le problème de planification moyen-terme de la production d'hydroélectricité sous incertitude peut être approché et résolu par différentes méthodes. Les méthodes de programmation dynamique stochastique restent les plus rigoureuses en matière et de formulation et d'algorithmes de résolution et de prise en compte de l'incertitude. On se propose d'appliquer deux méthodes basées sur la programmation dynamique stochastique : la programmation dynamique duale stochastique (SDDP) et une méthode de programmation dynamique stochastique approchée (ASDP) dont l'idée centrale est de discrétiser l'espace des états en hyper-rectangles. On compare les deux méthodes sur un cas d'étude réel : La Grande Rivière, la rivière la plus importante du parc hydroélectrique du Québec.

Abstract

The hydro-power generation planning is a complex problem implicating different fields of applied mathematics. Optimal or almost-optimal decisions are taken after optimization. This optimization is sometimes deterministic with integer variables (short-term planning), sometimes it is stochastic and continuous (mid or long-term planning). In order to master the randomness of parameters such as inflows or spot prices one must use and develop statistical and probabilistic models. Hydro-plants' power generation functions are modeled using nonlinear optimization, numerical calculating methods. etc. This thesis focuses on two main subjects: concavation methods of hydro-plants' power generation functions and stochastic optimization methods applied to a mid-term hydro-power generation planning problem under uncertainty that lies on natural inflows. Hydro-plants' power generation functions depend on the turbined outflow and water head, they are consequently not linear nor concave. These functions must be approximated by concave, piecewise linear functions, so they can fit into a linear mathematical programming model. There are two methods to do so: approximation of the objective function by a concave hull and approximation by a concave piecewise linear function. The second approach has two variants: fitting hyperplanes construction with the least squares criterion or the criterion of minimizing the maximal error to the real generation function. We conclude that these two methods are almost equivalent according to their root-mean square error, but the second method has less impact on planning algorithms' running time. There are many methods that can be used to solve the mid-term hydro-power generation planning under uncertainty. Stochastic dynamic programming-based methods are still the most rigorous with respect to their formulation, the solution algorithms used and the way in which uncertainty is represented. Two of these methods are compared in this thesis: Stochastic Dual Dynamic Programming (SDDP) and a variant of Approximate Stochastic Dynamic Programming (ASDP), which is mainly based on a state space discretization into hyper-rectangles. These two methods are compared on a real case-study: La Grande Rivière, the most important river in Quebec hydroelectricity system.