Groupe d’études et de recherche en analyse des décisions

G-89-12

Contribution à la programmation mathématique à deux niveaux

La programmation mathématique à plusieurs niveaux permet de modéliser adéquatement certaines structures de décision hiérarchisées. Cette thèse contribue au développement théorique et algorithmique de la programmation mathématique à deux niveaux (PDN) et présente une application réaliste dans le contexte de la cogénération aux États-Unis.

Dans un premier temps, les formulations "particulière" et "générale" du problème de PDN sont présentées. Les principales propriétés mathématiques obtenues pour la formulation particulière sont prolongées, sous des hypothèses affaiblies, à la formulation générale. Les difficultés de résolution du problème de PDN sont mises en évidence par d'une part, une discussion sur les principales difficultés liées à l'obtention de conditions d'optimalité pour le PDN et, d'autre part, par l'étude de la complexité algorithmique du problème PDN, que l'on montre fortement NP-difficile. Après avoir passé en revue les principaux algorithmes connus, une discussion vient préciser les différences fondamentales entre le problème de PDN et le problème, voisin, de Stackelberg.

Dans un second temps, nous proposons une nouvelle approche de résolution pour le problème de programmation linéaire à deux niveaux. Notre algorithme est basé sur l'élimination successive des variables de second niveau dans le cadre général d'une méthode d'énumération implicite. L'utilisation judicieuse de conditions d'optimalité du problème de second niveau, exprimées en terme de saturation des contraintes, permet la simplification et l'élimination de sous-problèmes. De plus, une série de tests, tels que ceux qu'on trouve habituellement dans les problèmes d'optimisation combinatoire, sont utilisés et combinés avec des pénalités semblables à celles exploitées en programmation entière linéaire mixte. Des tests numériques démontrent l'efficacité de notre algorithme.

Dans un troisième temps, nous proposons une approche originale au problème de planification des entreprises de service d'électricité américaines qui font face à un marché de cogénération. La réglementation américaine oblige ces entreprises à acheter, au coût marginal alors en vigueur, l'électricité excédentaire des cogénérateurs. Celles-ci doivent donc déterminer leur plan d'investissement en tenant compte de la réaction des cogénérateurs à l'annonce de la valeur marginale de l'électricité. Cette problématique est étudiée à l'aide d'un modèle à deux niveaux non linéaire où un algorithme de type "cobweb" est proposé pour sa résolution. Le modèle est illustré pour les états de la Nouvelle-Angleterre. Nous étudions l'impact d'une telle réglementation sur les plans de développement des entreprises de service d'électricité. Des résultats détaillés sont fournis sur les types et quantités des nouveaux investissements, les dividendes associés à la réglementation ainsi que sur les coûts moyens et marginaux de l'électricité.

, 158 pages