[PDF] by Fulin Zhuang B.Sc.Eng. (Shanghai Jiao Tong University) M.Sc

View - Download by Fulin Zhuang B.Sc.Eng. (Shanghai Jiao Tong University) M.Sc

Previous PDF

Next PDF

OPTIlIAL GDEIlATIOR UNIT COIHIITIIKNT

IN THERHAL ELECTRIC POWER SYSTEMS

by

Fulin Zhuang

B.Sc.Eng. (Shanghai Jiao Tong University)

M.Sc.Eng. (University of New Brunswick)

A thesis submitted to the faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of

Doc tor of Philosophy

Department of Electrical Engineering

McGill University

Montréal, CANADA

@ December, 1988

ABSTRACT

This thesis is devoted to tne optimal commitment of generation units in an all-thermal, single or multiple area, power systEm. 'l'he problem, known as unit commitment, 1s a non} inear mixed program typicaU y with thousands of 0-1 integer variables and diverse constraints. An optimal solution to the problem is only possible via (explicit or implicit) enumeration, which requires a prohibitively long computation time for large problem instances. Two optimization approaches, Lagrangian relaxation and simulated annealing, are explored in this thesis for efficient and near-optimal unit commitment Lagrangian relaxation combines the solution of the dual of thE.' unit commitment problem with feasibility search to obtain priMal feasible solutions. The feasibility search is necessary because a solution to the dual seldom solves the primal, and because little the ory is available to bridge the optimal dual and primal solutions. In this thesis, several new feasibility search procedures to find a near-optimal primal feasible solution from the dual solution are developed and tested. These prol!edures are indepenrlent of the data constituting different proble:n instances, and are morE.' rigorous and systE.'matic than the existing ones. With these procedures, Lagrangian relaxatl.on is suc:cessfully and efficiently applied to both single and multiple area unit commitment. Simulated annealing exploits the resemblance between a minimization process and the cooling of a molten metal. The method generates feasible solution points randomly and moves among these points following a strategy which leads to a global minimum in a statistical i sense. Simulated annea1ing is very flexible for handling diverse comp1icated constraints, such as those typical of the unit commitment problem. Simulated annealitlg is analyzed, evaluated and irnplemented for unit commitment in this thesis. Five major algorithms, proposed in this thesis for unit and reserve-constrained economic dispatch. are extensively tested and compared by numerical simulation on sample power systems of 10 ta 100 units. The simulation results show the efficiency of the tested a1gorithms for 1arge-scale unit commitment and demonstrate the gl3neral applicabi1ity of simulated annealing. A compari.son with the priority list method and a study of the convergence rates of the subgradient type a1gorithms are a1so inc1uded in the simulation. li

RESUME

Cette thèse se penche sur la question d'établir 1 'horaire optimal des unités de production d'un réseau électrique à production entièrement thermique, pour des réseaux isolés ou inter-reliés. Le calcul du plan de production, qui fait appel à la programmation nonlinéaire en variables mixtes, est rendu très difficlle par la présence de milliers de variables entières et de contraintes. Sa solution exacte ne serait possible qu'en énumerant (explicitement ou implicitement) toutes les solutions, a .. , coût d'un temps de calcul excessif. Deux techniques sont retenues pour générer des solutions quasi optimales, soient la relaxation Lagrangie:nne et la simulation du recuit (simulated annealing). La relaxation Lagrangienne combine la solution du problème duel à un processus heuristique pour assurer la réalisabilité du problème primaI correspondant. Cette deuxième étape est necessaire car le duel génere d'habi tude un solution irréalisable pour le primaI, n'y a pas de théorie pour rapprocher les deux. et p"'ésentement i.l

Nous proposons et

vérifions ici plusieurs processus nouveaux pouvant mener à des solutions primales quasi-optimales. Ceux-ci sont plus généraux et plus rigoureux que la pl upart des processus précédents, car il ne dépendent pas des particularités des données. Munie de ces algorithmes, la relaxation Lagrangienne peut résoudre efficacement le calcul du plan de production à simple ou à multiples régions. La simulatlon du recuit exploite l'analogie entre ce processus métallurgique et calcul de l'optimisation. Cette technique gér.ère aléatoirt'!ment des solutions réalisables, pour ensuite identifier parmi Hi ('elles-ci un minimum global dans le sens statistique. Cette technique très flexible permet d'inclure les contraintes complexes de notre problème. Ainsi, cette thèse presente l'analyse, l'application et l'évaluation de cette technique au calcul du plan de production. Cinq algoritmes majeurs ont testés et compares. Ils portent sur le calcul du plan de production et du dispatching, incluant les réserves de production, pour des réseaux ayant de 10 à 100 unit('>s de production. Les résultats confirment l'efficacité des tpchniques de relaxation Lagrangienne, ainsi que l'utilité de la ter.hnique de la simulation du recuit pour ce problème. De plus. nous fournissons une discussion sur les propriétés de convergence de calcul du duel base sur le sous-gradient. On compare ensuite nos résultats à ceux obtenus par la technique des listes prioritaires. iv ._----------

ACICROWLEOOEHENT

1 wish to express my sincere gratitude to Professor F. D. Galiana

for his expert guidance, constant encouragement and unfailing support as the thesis supervisor, and as a friend.

1 am deep1y indebted to Dr. Maurice Hunea1t and Dr. Ranend··s

Ponrajah for their generous sharing of knowledge and ever ready he1ping hands. Dr. Hunealt prooE-read the first three Chapters of this manuscript and prepared the French translation of its abstracto

1 would a1so like to extend my special appreciations to Ors. A.

Vojdani and L.A.F.M. Ferreira of Pacifie Gas and E1ectric Company for their generous of expertise and stimu1ating discussions.

1 am very gratefu1 to Professors B.T. Ooi and H.C. Lee for their

generosityand support. My fellow graduate students and co11eagues in the power engineering group have been a constant source of friendship. 1 would like to mention particularly Juan Dixon, Jean-Pierre Bernard, Jinan Huang, Li Fan, Hafid Hellal, Lester Loud, Xiao Wang and Jian Liu. Many thanks are a1so due to my undergraduate teachers, Professors Guangcen Yang and Jisun

Wu, whose 1etters a1ways brightened my days.

The financia1 supports from the Natura1 Sciences and Engineering Research Council of Canada, Fonds pour la Formation de Chercheurs et l'Aide à la Recherche of Province Québec and McGill Universiry are gratefu1ly acknow1edged. Finally, 1 would like to thank my parents and my wife tor their un1imited understanding, supryort and inspiration, and the many sacrifices they made on my beha1f, which made this thesis possible. v

TABLE OF CONTENTS

i , Ut

ABSTRACT ...•..•..............•.....•.••.•••.• .•.••.•.. , .•.•...••••

RESUME ." •.....••.....•..........•.•......•..••.....•

ACKNOWLEDGEHENT ........•........••....•................••..•..•

TABLE OF CONTEftS ..................•.....•..••........ '. .•••...... <

LIST OF TABLES ..................•.••.....•••.•.•..••....

LIST OF FIGURES ....................•..••......••...•....••••

LIST OF ALGORITliMS .....•..•.•••.•••••••..•..••

LIST OF ABBREVIATIONS ..............•......•.•....•..•.....• , .....•

LIST OF SYMBOLS ............••...•...•....•..•.....••.....••

v vi xi xiii xvii xviii xix

CBAPTEB. 1 INTRODUCTION. . . . . • . . . . . • . . . . . . • . . • . . . . . . . . . . . . . . . . • • . . . . 1

1.1 Power System Generation Unit Commitment ................. 2

1.2 The Necessity 3

1.3 The Operation Planning Problem ........... ...... ......... 6

1.4 Nature of the Problem ............ , . . . . . . . . . . . . . . . . . . . . .. 10

1.4.1

1.4.2 Explicit enumeration 1s impracticaJ ............. .

Rounding method does not even give a so1util>n ... . 11 13

1.5 Historieal Review ....................................... 15

1. 5.1

1. 5.2

1. 5.3

1. 5.4

1. 5.5

1. 5.6

1. 5.7

Priority list based methods ..................... .

Dynamic

programming ............................. . Branch-and-bound method ......................... . Benders decomposition ........................... . Lagrangian relaxation ................... ...... . Difficulties due to time coupling constraints ... . Summary ......................................... . 16 17 18 19 20 22
23

1.'5 The Present Thesis ...................................... 24

1.6.1 Motivation ....................................... 24

1.6.2 Thesis outline ................................... 27

CBAPTEB. 2 HATBEHATICAL MODELS OP' UNIT COJDIITHENT PROBLEHS IN A ELECTRIC POWER SYSTEM ......................... 32

2.0 Introductory Remark .... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 32

2.1 A Basic Single-Area Unit Commitment Problem ............. 34

2.1.1

2.1. 2

Thèrmal generation units ..... , .................. . Normal operation modes of a thermal unit ........ . vi 34
34

2.1. 3

2.1.4

2.1. 5

2.1.6

2.1. 7

2.1.8 Production cost of a thermal unit ............... . variables ......................•......... Constraints ............................. -....... . The planning horizon . . ......................... . The state of a unit ............................. . The basic single are a unit commitment problem ... . 35
42
42
44
44
46

2.2 Other Single Area Unit Gommitment Problems .............. 54

2.2.1 Single area unit commitment considering

maximum unit reserve contributions ............... 55

2.2.2 Single area unit commitment with banking and

load shedding .................................... 56

2.2.3 Time coupling constraints on continuous

variables ........................................ 58

2.3 A Multiple Area Unit Commitment Problem ................. 59

2.4 Concluding Remark ., . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 65

GHAPTER 3 A CRITICAL REVIIN OF SOLUTION TECHNIQUES FOR POVER GENERATION UNIT COMKITMENT .............................. 66

3.0 Introductory Remark ........................... ,......... 66

3.1 Priority List Based Hethods ............................. 66

3.1.1

3.1. 2

General comments on the priority 1ist methods ... . Counter examp1es ................................ . 67
68

3.2 Dynamic Programming .................................. ,.. 76

3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 A forward dynan, Jrogramming algorithm ......... .

Dynamic programmlng for static unit

commitment ...................................... .

Dynamic programming for dynamic unit

commitment .. , ................................... . Combatting the "curse of dimensionality" ........ . States versus "states" .......................... . 78
ao 82
84
87

3.3 Branch-and-Bound Hethods ................................ 88

3.4 3.5 3.3.1 3.3.2 Synopsis of branch-and-bound methods ............ . Application to unit comm:ïtment prob1ems ......... .

Linear Programming

Lagrangian Relaxation

89
90
93
98
3.5.1 3.5.2 The prima1 and the Lagrangian dual ............... 99 Properties of the Lagrangian dual ................ .101 vii 3.5.3 3.5.4 3.5.5 3.5.6 3.5.7 3.5.9

3.5.10

Lagrangian relaxation applied to SMP ............ . relaxation in unit commitment ........ . Smooth approximation of the dual function ....... . Variable metric rnethod .......................... . Constructing near-optirnal primal solutions ...... . Crew constraints ................................ . Time coupling constraints on continuous variables ....................................... . 106
107
109
111
112
116
117

3.6 Other Solution Techniques ............................... 1l.9

3.6.1 3.6.2 Benders decornposition ............................ 119 Discrete maximum principle ....................... 121

3.7 Concluding Rernark ....................................... 122

CHAPTER 4 APPLICATION OF LAGRANGIAN RELAXATION TO SINGLE AREA UNIT COHMITMENT PROBLEMS ................................ J25

4.0 Introductory Remark ..................................... 125

4.1 Solving the Basic Single Area Unit Commitment

Prob1em ..................................... . 127 4.1.1 4.1.2

4.1. 3

4.1.4 4.1.5 4.l.E Lagrangian dual of the BUCP ...................... 127

Maxirnizing the dual function by subgradient

methods .......................................... 131 An aggregate subgradient algorithrn ............... 133 Solving the minirnization sub-problem ............. 141 Solving the Lagrangian dual ...................... 147 Searching primal feasible solutions .............. 149

4.2 Solving the UCP ....................................... . 166

4.2.1 4.2.2 4.2.3 4.2.4 4.2.5 An equivalent form of the UCP .................... 167 The Lagrangian dual of the UCP ................... 168 Solving the Lagrangian dual of the UCP .......... 171

Reserve feasibility ....................... 172

Reserve-constrained econornic dispatch ............ 178

4.3 Banking Mode and Start-Up Trajectory Constraints ........ 187

4.4 Difficul t Constraints ................................... 186

4.5 Concluding Rernark ..... ................ ........ ....... 189

4.6 Proofs of Lemmas, Theorems and Forrnulae ................. 188

4.6.1 4.6.2 4.6.3 Proof of Lemma 4.4 ............................... 190 Proof of Lemma 4.5 ............................... 192 Proof of Theorem 4. 2 ............................. 193 viii

CHUTER 5

4.6.4 4.6.5 Proof of Theorem 4.3 ............................. 194 Proof of (4.71) and (4.72) ....................... 195

HULTIPLE A1OEA UNIT COMHITMENT BY LAGRANGIAN

RELAXATION .............................................. 198

5.0 Introductory Remark ..................................... 198

5.1 The Lagrangian Dual Problem ............................. 199

5.1.1

5.1. 2

5.1. 3

The dual ......................................... 199 Thequotesdbs_dbs43.pdfusesText_43

[PDF] Le réchauffement de la planète Rapport

[PDF] M. Jean-Yves Le Drian, Ministre de la défense. Discours pour les vingt ans du lancement du satellite Hélios IA

[PDF] Le PERP Generali Patrimoine

[PDF] Nos services. pour vous! 100% dématérialisés. Des offres adaptées. www.urssaf.fr

[PDF] Th_Math2 - Banque d'exercices n 5 - Problèmes JMC - Version Août 2009. Mathématiques au cycle II (GS - CP - CE1) Banque d'exercices n 5.

[PDF] Inforum 27 mars 2012 à l Event Center, Ramada Encore, La Praille Genève

[PDF] CONSEIL NATIONAL DE LA COMPTABILITÉ Recommandation n 2004-R.01 du 23 juin 2004. 2 Définition du périmètre du patrimoine d affectation d un PERP

[PDF] PERP D AXA : Pour réduire vos impôts tout en préparant votre retraite.

[PDF] INSCRIPTION EN LIGNE. Réunion d information. 3 janvier 2013

[PDF] Niveau d admission : Année 1 pour les titulaires d un Bac +2

[PDF] Rencontres nationales du Transport Public

[PDF] SUR LA SITUATION ECONOMIQUE

[PDF] Administration en Ligne e-démarches. Console du gestionnaire. Guide utilisateur. Aout 2014, version 2.1

[PDF] DEVELOPPEMENT RURAL ALSACE 2014-2020

[PDF] GRILLE D OBSERVATION ET D ÉVALUATION