Abstracts
Résumé
Le modèle mathématique décrit dans cet article a pour tâche de choisir les sites sur une rivière où des installations hydro-électriques seront aménagées, puis de trouver la taille optimale de ces installations. La solution de ce problème dépend naturellement du montant d'argent que la compagnie est prête à investir sur la rivière. Toutefois, ce montant n'est pas connu au départ puisqu'il est lui-même fonction de ce que les installations pourront produire. Il est donc nécessaire de résoudre le problème pour tous les niveaux possibles de production étant donné qu'on ne connaît pas le niveau qui sera choisi. Ce problème est résolu dans cet article par une méthode très efficace qui regroupe l'énumération implicite, la programmation linéaire successive et l'analyse paramétrique. De façon succincte, l'énumération implicite fait le choix des sites qui seront aménagés pour un niveau de production donné. La programmation linéaire successive, quant à elle, se charge de déterminer la taille optimale des installations. Enfin, l'analyse paramétrique montre comment la taille des installations varie avec le niveau de production. L'efficacité de cette méthode vient du fait que l'algorithme d'énumération implicite, qui consomme beaucoup de temps de calcul, est appelé un nombre minimal de fois.
Mots-clés:
- Programmation linéraire successive,
- énumération implicite,
- analyse paramétrique,
- approximation linéaire par partie
Abstract
The purpose of the work described in this paper was to find a method for identifying the development scheme of a valley that will allow a utility to meet its electrical energy need at minimum cost. Suppose, for instance, that the utility wishes to build hydroelectric power plants in a virgin river valley so as to produce D gigawatthours of firm energy each year, and that preliminary surveys of the river show n possible sites. The first step is to select the sites and then to determine, for each, the dam height and hence size of the reservoir, elevation of the water inlet, elevation of the water outlet, and capacity of the power plant. The selection has to be clone in terms of minimizing the investment cost.
One of the utility's major difficulties with the above problem is to determine the value of D and hence the amount of money to invest in the valley. The solution depends on the alternatives to such an investment : a nuclear or thermal power plant or development of another valley, for example. In fact, the only completety reliable way to determine the value of D is to consider all the investment possibilities. The question is how do it without overly magnifying the problem ? One way, and incidentally the easiest, is to use a two-step solution : first, determine the optimal development scheme for each river for ail possible values of D, then find the optimal investment policy among the valleys and hence the optimal value of D. In this paper, only the first step is solved.
Determination of the optimal development scheme of a valley for ail possible values of D is formulated here as a parametric mixed-integer linear programming problem, which takes the form:
minimize cx
subject to
ax ≽ b + Ɵh
x ≽ 0
x-= 0 or 1
where c and x are n vectors, A is an m by n matrix, b is an m vector, h is a change vector of dimension m, and 0 is a scalar that is varied continuously. x is a subvector of x containing those elements that must be 0 or 1. This formulation was chosen despite the nonlinearity of the real problem, in order to take advantage of the relative computational efficiency of mixed-integer linear programming as offered by IBM's MPSX/370 package. The nonlinear functions, like the costs, the production, and the relation between reservoir level and content, were linearized using separable programming in some cases and successive linear approximation in others. Since MPSX/370 inhibits the simultaneous use of separable and mixed-integer programming, the author wrote his on branch-and-bound algorithm. The parametric analyses are clone in such a way that the branch-and-bound algorithm, which consumes most of the computer time, is called a minimum number of times.
Keywords:
- Successive linear programming,
- separable programming,
- branch-and-bound,
- parametric analysis,
- hydropower development