NASZVADI PÉTER
Load-flow jellegű feladat a villamos rendszerirányításban TDK dolgozat 2006
1
Előszó: Adott egy (villamosenergiaellátást biztosító) villamoshálózat, és ezen hálózathoz csatlakozó energiatermelők és fogyasztók. A modern rövid- és középtávú energiaigény-előrejelzések ismeretében az energiaellátást biztosító erőművek ütemezése egy determinisztikus optimalizálási feladatnak tekinthető, speciálisan parciális differenciálegyenlet-rendszernek. Egy ilyen ütemezést menetrendnek nevezünk. A gyakorlatban célszerű a diszkrét, ekvidisztáns időpontokban skalár ismeretlennek tekinteni az egyes termelők és fogyasztók által termelt/használt energiamennyiséget. E diszkrét relaxációval, a modellhez hozzáveendő korlátozó feltételekkel és az ezeket megoldó algoritmusokkal fogunk foglalkozni a dolgozatban megmutatva, hogy bizonyos speciális esetekben erősen polinomiális algoritmus adható nagyon jól közelítő modellel felírt feladatokra. A dolgozatban közlünk egy módszert, mellyel speciális esetben egészértékű megoldást találunk polinomidőben az optimális menetrend meghatározására. Majd összefoglaljuk azon korlátozó feltételeket, melyek modellbe való vételével már NP-nehéz vagy NP-teljes lesz a probléma.
2
1. fejezet: felhasznált matematikai eszközök Definíció.1: Egy mátrixot teljesen unimodulárisnak nevezünk, ha minden négyzetes részmátrixának determinánsa ±1 vagy 0 . Az ilyen mátrixot a továbbiakban TU -val jelöljük. Megjegyzés.2: TU mátrix csak ±1 vagy 0 elemekből állhat. Definíció.3: Egy halmazrendszert lamináris rendszernek nevezünk, ha tetszőleges két eleme vagy diszjunkt, vagy az egyik szigorúan bővebb a másiknál. A továbbiakban használatos rövidítés: LR .
Megjegyzés.4: Minden LR -hez konstruálható egy ki-fenyő az alábbi módon: legyenek a fenyő csúcsai a halmazrendszer tagjai, és két pont pontosan akkor van összekötve egy éllel, ha az él forrása a legszűkebb olyan halmaz, ami tartalmazza az él végpontjának megfelelő halmazt, és szigorúan bővebb nála. Triviális, hogy ez az irányított gráf egy alaphalmaz-forrású ki-fenyőt fog alkotni. Definíció.5: Egy A mátrix ún. hálózati mátrix, ha ∃G irányított gráf és ∃ F⊆G irányítatlan értelemben feszítő fa, melyekre igaz: F éleinek A sorai, G ∖ F éleinek A oszlopai feleljenek meg; i-dik él
a i , j=±1 , ha az oszlopnak megfelelő e élre F ∪{e } -beli körben az
e -vel megegyező/ellentétes irányítású (negatív, ha ellentétes); a többi esetben G ∖ F esetén feltesszük, hogy V F =V G . Az
Megjegyzendő, hogy
0 .
A hálózati
mátrixhoz tartozó G gráfot (a mátrixhoz tartozó) hálózati gráfnak nevezzük. Tétel.6: TU mátrix részmátrixa, transzponáltja TU ; hálózati mátrix részmátrixa hálózati mátrix. Megjegyzés.7: Hálózati mátrix transzponáltja nem feltétlen hálózati mátrix
(1) A≝
hálózati mátrix,
1 1 1 0 0 0 −1 0 0 1 1 0 0 −1 0 −1 0 1 0 0 −1 0 −1 −1
AT viszont nem az. A hálózati gráf pedig nem más, mint egy ötcsúcsú
körmentes turnament gráf, ahol a feszítőfa élek a(z egyetlen abszolút) győztesből indulnak kifele. Definíció.8: Pivotálás egy mátrix valamely nemzérus elemén: (2) A∈ℝ
m ×n
, A=
c b D
A=
1
c
−b
D−1 bc
, { D ,bc }⊂ℝ m −1 × n−1
Speciálisan hálózati mátrixoknál a pivotálás szemléletes jelentése nem más, mint egy feszítőfabeli élt kicserélni egy nem-fa élre. Tétel.9: A
TU , illetve a hálózati mátrixok invariánsak az alábbi műveletekre: tetszőleges
3
két sor/oszlop megkettőzése, tetszőleges két sor/oszlop felcserélése, tetszőleges sor/oszlop elemenkénti
negálása,
tetszőleges
sor/oszlop
nullával
való
beszorzása,
identitásmátrix
soraival/oszlopaival történő konkatenáció, pivotálás bármely nemnulla elemen. Tétel.10: Minden hálózati mátrix TU . Megfordítva nem igaz. Egy
A mátrix hálózati
mátrix akkor és csak akkor, ha előáll egy irányított gráf pont-él incidenciamátrixából véges sok pivotálás elvégzése után. Megjegyzés.11: TU , de nem hálózati mátrixok:
(3)
1 −1 0 0 −1 −1 1 −1 0 0 0 −1 1 −1 0 0 0 −1 1 −1 −1 0 0 −1 1
, illetve
(4)
1 1 1 1 1
1 0 1 1 0 1 0 0 1 1
0 0 1 1 1
1 0 0 1 1
Tétel.12: (Ghouila-Houri, [1]) (5)
A∈ℝ
m ×n
TU
⇔
n
n
m
∀ x ∈ {1,0 } ∃ x ∈ {±1,0 } : A x ∈ {±1,0 } ∧∀ i :∣xi∣=x i
Tétel.13: (Chandrasekaran, [2]) (6) A∈ℝm ×n TU
⇔
k
∀ D⊆A :det D≠0, D∈ℝ k×k ∀ y ∈ {±1,0 } : lnko Dy=1
Ahol lnko az argumentumában szereplő számok kitüntetett közös osztóját jelenti. Tétel.14: Lamináris rendszer mátrixa hálózati mátrix Bizonyítás: Triviális, rekurzív módon. Egyelemű halmaz karakterisztikus vektora egyetlen helyen 1 , a többi helyen 0 sorvektor, így ez a sor eltávolítható amennyiben van ilyen sor, a maradék sorok alkotta mátrix pontosan akkor hálózati mátrix, ha eredetileg is az volt. Ha meg nincs egyelemű halmaz, akkor van (legalább) két egyforma oszlop, amelyik közül az egyik eltávolítható, a maradék oszlopok által alkotott mátrix is pontosan akkor hálózati mátrix, ha eredetileg is az volt. Az előbbi két műveletet iteráljuk. 1 , illetve a
0 elemből álló egyelemű mátrixok hálózati
mátrixok. Q.E.D. Tétel.15: minden TU mátrixszal leírt egészértékű lineáris programozási feladat polinomidőben megoldható, ha egészértékűek a korlátozó vektorok. Bizonyítás: Khacsiján 1979-es eredményéből és Hoffman-Kruskal tételkörből következik triviálisan Tétel.16: minden hálózati mátrixszal leírt LP feladat ekvivalens egy áramfeladattal. Következmény.17: áramfeladat erősen polinomidőben megoldható (egészértékű korlátok esetén egészértékű lesz az optimális megoldás is). Tétel.18: Konvex abszolútértékes célfüggvényes lineáris korlátozó feltételes optimalizálási feladat átírható LP feladattá. Ha az eredeti feladat P-ben volt, akkor az új feladat is P-beli. 4
Bizonyítás: Tekintsük a feladatot: k
T T (7.a) f x ≝c x∑ ∣ci x∣ i=1
min f x (7.b) Ax≤b
Vezessünk be új változókat és korlátozó feltételeket: ciT x= z i−wi z i ≥0, wi ≥0
c1 (8) C≝ c2 ∈ℝ k×n , z≝ z , z ,⋯ , z , w≝ w , w ,⋯, w ,∈ℝ k 1 2 1 2 k k ⋮ ck
ahol
A∈ℝm ×n ; c , ci ∈ℝ n
Ekkor a feladat az alábbi módon írható le:
k
(9.a) min c x∑ z i w i
(9.b)
T
i=1
A 0 C −I k×k 0 I k×k 0 0
0 I k×k x 0 I k×k
≤b z w = 0 ≥0 ≥0
Látható, hogy a (9) egy LP probléma, mérete a (7) által meghatározott eredeti probléma méretének legföljebb kvadratikus polinomjával korlátozható felülről. És mivel ez egy LP feladat, ezért polinomidőben megoldható. Már csak azt kell belátni, hogy ∀ i : z i =0 ∨wi=0 minden
x , z , w optimális megoldás esetén. Valóban, ha feltesszük indirekt, hogy x , z , w optimális megoldás
és
∃i : z i 0, w i0 ,
akkor
r i≝min z i , w i bevezetésével
x 1 , x 2 ,⋯, x n , z 1 ,⋯, z i−1 , z i −r i , z i1 ,⋯, z k , w1 ,⋯, wi −1 , wi −r i , w i1 ,⋯, w k
is
megengedett
megoldás lesz, node szigorúan csökkent a célfüggvény érték, ami ellentmondás. Ezzel beláttuk, hogy (7) és (9) optimális megoldáshalmazai ekvivalensek. Q.E.D. Tétel.19: Részhalmaz-összeg feladat NP-teljes (lásd [5]). Jelölés.20: Bidiagonális, illetve tridiagonális mátrix:
a b 0 ⋱ ⋱ s×t ∈ℝ (10.a) bidiag s×t a ,b≝ a b 0 ⋱ ⋱ (10.b) bidiag s a , b≝bidiag s−1 × s a ,b 5
a b c 0 ⋱ ⋱ ⋱ ∈ℝ s×t (10.c) tridiag s×t a , b , c≝ a b c 0 ⋱ ⋱ ⋱ (10.d) tridiag s a ,b , c ≝tridiag s− 2 ×s a ,b ,c Jelölés.21: Mátrixok konkatenációit a szokásos módon jelöljük, viszont fontos az alábbi művelet, az átlós konkatenáció adott
A1 , A2 ,⋯, Ak nem feltétlenül azonos méretű mátrixokra:
A1 0 ⋯ 0 0 A2 ⋱ ⋮ (11) ∗ Ai≝ A1∗A2∗⋯∗Ak ≝ i=1 ⋮ ⋱ ⋱ 0 0 ⋯ 0 Ak k
6
2. fejezet: modellek leírása Konvenció: a továbbiakban minden megszámlálhatónál bővebb halmazon értelmezett függvényt folytonosnak és egy nullmértékű, sehol sem sűrű halmaz komplementerén analítikusnak tekintünk. Legyen egy optimalizálási feladat a következő: adott egy véges hosszú időtartam, véges darabszámú áramfogyasztó, illetve áramtermelő erőmű. Ismertek az energiaárak és a villamoshálózati meg az erőművek teljesítményeire vonatkozó korlátozó feltételek, továbbá az energiaigény, mint az idő függvénye. Mint minden gyakorlati optimalizálási feladat, ez is többcélfüggvényű; ilyenkor szokás a különböző célfüggvények kúpkombinációit célfüggvénynek tekinteni, a kúpkombinációból kimaradó célfüggvényeket minorálva/majorálva a korlátozó feltételek közé venni. Az erőművek/fogyasztók halmazát jelölje E , k ≝∣E∣ , k∞ , az időtartamot
pedig
jelölje T , T ≝[ 0, r ] , r ∞ Célunk
megadni
egy
minimális
költségű
menetrendet. Formálisan felírva kapjuk az alábbi függvényegyenletet: (12.a) min C x t (12.b) x t ∈F ahol
C skalárértékű költségfunkcionál,
F ≝∩ F i megengedettségi halmaz, x t : T ℝ k
pedig az erőművek/fogyasztók által megtermelt előjeles enerigaérték-vektorokba képező függvényt jelenti (, dimenziója MW). A nemzetközi energia-kereskedelemben elfogadott szokás, hogy
T
időtartamot diszkrét halmaznak tekintik, ekvidisztáns időpontokat kijelölve, egyenlő egymásba nem nyúló intervallumokra partícionálva; időpont helyett intervallum-végpontokra hivatkozva. Két szomszédos időpont távolsága megállapodás szerint tipikusan 1 óra, de használnak 30, 20, 15, 12, 10 és 1 perces beosztásokat is, illetve középtávú ütemezéseknél több órás távolságot is szoktak alkalmazni. Újradefiniáljuk a változóinkat: x t helyett egy r 1 ∗k dimenziós vektort értünk: x ∈ℝ r 1 ∗k (
r ,k ∈ℕ
rögzített pozitív egészek). Továbbá feltehető, hogy az általunk vizsgált
esetekben a költségfunkcionál lineáris. A (12) eképpen az alábbi alakúra fog módosulni: (13.a) min cT x (13.b) x ∈ F ⊆ℝ r 1 ∗k Még ebben az esetben is reménytelen megoldani a feladatot amennyiben csak egyetlen időpontunk van, k erőművünk/fogyasztónk,
k
és F 1≝× {0, a i } , i=1
{
k
F 2≝ x ∣ ∑ x i =b i =1
}
, F ≝F 1∩F 2 ,
akkor ez a részhalmaz-összeg feladat. Azaz ebben a speciális esetben NP-teljes (12.b) mint
7
megengedettségi feladat, a 19. tétel miatt. Ha viszont
{
k
F 2≝ x ∣ ∑ x i ≤b i =1
}
, akkor (13) nem más,
mint a hátizsák feladat, ami NP-nehéz. A célfüggvényünk már elkészült, most már a korlátozó feltételeket definiáljuk. Mivel minden erőmű/fogyasztó által leadható/felvehető villamosenergia-kapacitása korlátos, ezért: (14) b LO , e ,t ≤x e , t≤bUP ,e , t ∀
e∈ E , t ∈T . Azaz a megengedettségi halmazt elmetszük egy kompakt hipertéglával.
Következménye az, hogy korlátos a megengedett megoldások halmaza (ha nem üres). Az általánosság megszorítása nélkül feltehető, hogy t =0 időpontban b LO , e , 0=bUP ,e , 0 . A következő korlátozó feltételnek szemléletes fizikai jelentést tulajdonítunk. Tegyük fel, hogy egyetlen erőművünk van összesen, egy e -vel jelölt, szilárd tüzelőanyaggal működő, tüzelőanyagőrlést nem végző blokk, amely 50, illetve 200 MW közötti teljesítményekre képes. A valóságban elegendően kicsiny időegységet választva egy időegységnyi idő eltelte alatt nem tud 50 MW-ról 200 MW-ra ugrani. A kazán teljesítményeire vonatkozó fizikai összefüggés: ∂ (15) ∂t x t ∈[ g LO t , g UP t ]
ahol −∞g LO t ≤g UP t ∞ ∀ t ∈T . Szemléletesen ebből x t lipschitzessége következik a fejezet elején megemlített konvenció miatt (meg a folytonos függvényekre vonatkozó Weierstrasstételből). Diszkrét esetben a számlálómérték szerint vett jobboldali differenciahányados-függvényre adott korlátozás analogonnak veendő: (16.a) x e , t≝ x e ,t −x e , t −1 (16.b) g LO t ≤ x e ,t ≤g UP t ahol x e , t értelmes, azaz t ≥1 , amit hallgatólagosan feltettünk. Ismert a villamosenergia-igény, mint az idő függvénye. Ez folytonos esetben az alábbi korlátozó feltételt jelenti: (17)
∑ x t =D t e∈ E
ahol D t : T ℝ függvény. Diszkrét esetben az alábbi alakot fogja ölteni: k
(18)
∑ x e ,t =Dt e=1
∀ t ∈ [ 0, r ]∩ℤ .
Állítás.22: A (13.a), (14), (16.a), (16.b) és (18) által definiált lineáris programozási feladat mátrixa TU .
8
Bizonyítás (2004): A célfüggvény elhagyható triviális megfontolásokból (nem része a mátrixnak). A 9. tétel miatt (14) korlátozó feltétel által definiált mátrix-sorokat elhagyhatjuk, ők invariánsak a TU -ság szempontjából. Így elegendő csupán (16.a), (16.b), és (18) által definiált sorokat tekinteni a mátrixban, és az összefüggő sorok eltávolítása után az alábbi mátrix
TU -
ságát kell csak igazolni:
k∗r oszlop
I r 1 ; I r1 ; ⋯ ; I r 1
(19) A≝
k
∗ bidiag r1 −1,1
i =1
Belátjuk, hogy egyenletesen 2-sorszínezhető, ekkor ugyanis [1] miatt TU . Az A mátrix két részre bontható: (20.a) A=
1
(20.b) A1=
∣
(20.c) A2 =
−1
A1 A2
1
1
1
1 ⋱
1 −1 1 ⋱
⋱
1
∣
⋱ −1 1
∣
−1 1 ⋱
1
⋯
⋱
1
∣
⋱ −1 1
⋱
∣
−1 1 ⋱
1
∈ℝ
r 1× r 1∗k
r∗k × r 1 ∗k
∈ℝ
∣
⋱ −1 1
Tekintsük az A mátrix sorainak tetszőleges S részrendszerét. Vezessük be az alábbi jelölést: S 1≝ A1∩S , S 2≝S ∖ S 1 . Most már csak azt kell igazolni, hogy csupán A -beli sorok és
oszlopok ponálásával, illetve negálásával A2 azon oszlopaiban szereplő egyeseket negálni lehet, amely oszlopokban S 1 egyest tartalmaz úgy, hogy A többi eleme változatlan maradjon. Ez azért jó nekünk, mert ekkor rögzített S 1 esetén tetszőleges S 2 választásánál elegendő a kiválasztott sorokat összeadni, és ekkor TU vektort kapunk. Nézzük a következő eljárást: első lépésben kiválasztunk egy olyan j oszlopot, melyre S 1 nemnulla elemet tartalmaz, a i , j pedig azon. A2 -beli nemnulla elem, melyre i minimális. Második lépésben A minden olyan j oszlopát
9
negáljuk, melyre j mod r1 j mod r 1 , és A minden negatív elemet tartalmazó sorát negáljuk. Harmadik és egyben utolsó lépésben A2 minden olyan i sorát negáljuk, melyre i mod r ≤i mod r . Az eljárás során a i , j és minden vele azonos r 1 -es maradékú
oszlop-koordinátával rendelkező
A2 -beli nemzérus elemek közül a legkisebb sorindexűek
negálódnak, mert őket csak egyszer negáltuk, míg a többi nemzérus mátrixelemet páros sokszor. Az eljárást addig folytatjuk, míg a kívánt alakú nem lesz
A . Q.E.D.
Következmény.23: A 15. tétel miatt (13.a), (14), (16.a), (16.b) és (18) által meghatározott lineáris optimalizálási feladatnak egészértékű korlátozó vektorok esetén egészértékű optimális megoldása állítható elő polinomidőben (ha létezik). Egy szép eredményt kaptunk, viszont a benne szereplő modell azt feltételezte, hogy a távvezeték-hálózat egypontú. A következőkben bevezetünk (14) és (18) feltételeknek egy közös általánosítását, mellyek bizonyos távvezeték-hálózat topológiák is jobban kezelhetők, és az így kapott LP feladat hálózati mátrixszal rendelkezik (, ebből persze a 21. állítás is következik). Tekintsünk minden t ∈ [ 0 , r ] ∩ℤ esetén LR t : LRt ⊆2 E lamináris rendszereket. Egyelőre tegyük fel, hogy mindegyik lamináris rendszer tartalmazza az alaphalmazt ( E ∈LRt ∀ t ) és az egyelemű halmazokat, de majd később látni fogjuk, hogy ez megy az általánosság rovására. Jelölje ∣LR t∣×k az LR karakterisztikus vektoraiból álló mátrixot, L j az L mátrix t t t
Lt ∈ {0,1 }
j -dik
oszlopát. Jelölje továbbá x t ≝ x 1,t , x 2,t , , x k , t . Vezessük be az alábbi korlátozó feltételeket minden t -re: (21) bt ≤ Lt x t ≤ d t Állítás.24: A (13.a), (16), (21) által definiált LP feladat mátrixa hálózati. A bizonyítás előtt megjegyzendő, hogy nem jelentett megszorítást az, hogy hozzávettük Szigorúan konvex célfüggvények Lineáris célfüggvények Többcélfüggvényű optimalizálási feladatként való megfogalmazás és prioritási sorrend a célfüggvények között. Tétel: prioritási sorrendhez létezik célfüggvények affin kombinációjaként előálló célfüggvény. Tétel: algoritmus
10
Lépésszámbecslés (P-ben van), eltérésbecslés
11
Irodalomjegyzék: [1]
A. Ghouila-Houri. Charactérisation des matrices totalement unimodulaires. Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences (Paris), 254:1192-1194, 1962
[2]
R. Chandrasekaran. Total unimodularity of matrices. SIAM Journal of Applied Mathematics, 17:1032-1034, 1969
[3]
Deák István, Hoffer János, Mayer János, Németh Ágoston, Potecz Béla, Prékopa András, Strazicky Beáta: Nagyméretű, vegyesváltozós, matematikai modell termikus villamos energia-rendszer rövid távú, optimális menetrendjének meghatározására hálózati feltételek figyelembevételével, Alkalmazott Matematikai Lapok 9:221-337, 1983
[4]
Khachiyan L.G.: A polynomial algorithm in linear programming, Soviet Mathematics doklady, 20:191-194, 1979.
[5]
Lovász László: Algoritmusok bonyolultsága, 50-51, 4.5.6, Nemzeti tankönyvkiadó, 2001.
[6]
Kotnyek Balázs: A generalization of totally unimodular and network matrices. PhD thesis, London School of Economics, 2002
[7]
A. Hoffman and J. Kruskal. Integral boundary points of convex polyhedra. In H. Kuhn and A. Tucker, editors, Linear inequalities and Related systems, pages 223-246, Princeton University Press, Princeton, NJ, 1956
12
