Igen et glimrende afsnit af Numb3rs – men vi holder os jo til matematikken her, så ikke et ord om alt det andet!
Der var jo faktisk masser af matematik og lignende.
I starten eksperimenterede Larry og Charlie med en af de mystiske maskiner, man kan finde opskrift på rundt omkring på nettet. Mythbusters har haft den med for et halvt års tid siden (Episode 68, Antigravity device). Påstanden var, at man kunne slukke for tyngdekraften med den fikse trekantede konstruktion, men det kunne man ikke…
Grundlæggende handlede det om “Load Flow analysis” og andre metoder til at se på kraftværker i netværk. Charlie analyserede, hvilket kraftværk, man skulle tage ud, for med størst sandsynlighed at forårsage hele netværket til at lukke ned via en dominoeffekt; og der var en ingeniør (Lyle Donohue), der havde brugt Dantzig Wolfe dekomposition til at forudsige effekten af at sabotere forskellige dele af nettet.
Dominoeffekt eller Cascading failure: Problemet er, at man er nødt til at reagere hurtigt, hvis et kraftværk går ned. Vi så det på Sjælland og i det sydlige Sverige for et par år siden: Et kraftværk gik ned, et andet blev overbelastet og lukkede, hvorved endnu flere blev overbelastede etc. – man har relæer, der lukker ned, hvis der løber for meget strøm – ligesom vi har HFI relæ i private hjem. Så hvordan forebygger man den effekt? Man kan isolere hvert kraftværk og dets brugere, så der ikke er back up hvis et værk går ned. Det vil begrænse skaden, men er ikke ideelt der, hvor andre kraftværker kunne have leveret strømmen og dermed have holdt alle brugere forsynet. Desuden ønsker man at fordele belastningen, så man f.eks. kan få strømmen fra den billigste leverandør – måske er det billigere at køre med middelstor belastning på flere kraftværker end med høj belastning et sted og lav andre steder.
Man har altså et stort overordnet problem: Sørg for strøm til alle på nettet billigst muligt eller rettere med mest mulig profit. Problemet og diverse beslutninger (luk ned eller bliv på – skru op eller ned for forsyning fra et sted – sæt endnu en enhed i drift – luk et relæ…) skal distribueres til mindre enheder – de lokale kraftværker – som ikke har overblik over hele nettet, men kun kan se data fra dele af nettet. Man kan formentlig ikke nå at regne overordnet på hele nettet, hvis der er risiko for blackout. Hver enkelt enhed skal reagere hurtigt. Og beregningerne vil involvere rigtig mange variable.
Et andet problem er, at når et kraftværk aller bare en ledning falder ud, ser netværket pludselig helt anderledes ud – man mangler alle de forbindelser, der gik via det kraftværk eller den ledning. Derfor ser beregningerne pludselig fundamentalt anderledes ud. Det er ikke bare en konstant, der er blevet lidt større eller mindre, men nogen helt andre ligninger.
Se mere om netværk tidligere på bloggen. Der drejede det sig om sociale netværk, men man kan også tænke på det som kraftværker og ledninger. Man må så forestille sig, at ledningerne har forskellige kapacitet.
Kan man sørge for, at den samlede beslutning bliver optimal ved at fordele beslutningerne og informationerne rigtigt? Og kan man undgå, at systemet, som skal optimere profitten, vil give mørklægning af store områder.
Der findes tidsskrifter (IEEE Transactions on Power systems), som udelukkende beskæftiger sig med den slags problemer, så det vil være for omfattende at gå ind i detaljerne, men metoderne er ofte
Distribuerede beregninger, lineær programmering og Dantzig Wolfe:
At distribuere større beregninger er vanskeligt men væsentligt. Og med moderne parallelle processorer sker det hele tiden med større eller mindre held. Den algoritme, Charlie henviser til, Dantzig Wolfe, er fra 1960. George Dantzig, 1914-2005, var ophavsmand til simplex metoden i lineær programmering, som nok er et af de væsentligste bidrag til moderne beregningsmetoder – den er fra midt i 40’erne:
Et lineært programmeringsproblem er et problem af typen:
Find maksimum for funktionen f(x,y,z)=7x+3y+z under bibetingelserne x+y <=7, 3y<= 2 , x+z <= 7og både x,y og z positive. Der er altså et begrænset område, hvorfra vi må vælge x,y,z, og i et lineært programmeringsproblem er det afgrænset af planer, hvis vi har tre variable. Har vi kun to variable, er det afgrænset af linier.
Den slags problemer findes mange steder: En virksomhed har begrænsninger på leverancer, arbejdskraft i forskellige afdelinger, lånemuligheder etc. Eller som her: Der er begrænset kapacitet forskelige steder i nettet – i kraftværkerne eller i ledningsnettet.
Eftersom niveaumængderne for f(x,y,z) (de punkter hvor f(x,y,z)=2, er et eksempel på en niveaumængde) er planer, er der et hjørnepunkt, hvor funktionen er maksimal. (Der kan være flere løsninger, hvis funktionen er konstant på en af siderne/kanterne)
I simplexmetoden starter man i et hjørne. Så går man langs en kant til det nabohjørne, hvor funktionen f har højest værdi, og højere end der, hvor vi står. Og så fremdeles, indtil der ikke er sådan et hjørne. I så fald har vi nået et maksimum.
Det smarte ved metoden er, at man kan algoritmisere den, i.e., få en computer til at regne det ud, og den gør det effektivt i rigtig mange tilfælde. Man kan også finde worst cases, hvor det tager meget lang tid.
I Dantzig Wolfe metoden har man et meget stort problem af typen ovenfor. Man har rigtig mange variable, men der er visse dele, der er uafhængige af hinanden – begrænsninger der kun involverer få variable. Disse delproblemer foreslår nu løsninger til det oprindelige problem. For eksempel er de to bibetingelser x+y<= 7, y <= 2 uden z, så man kan optimere 7x+3y under de betingelser og finder x=7 og y=0 . Med det som input er det overordnede problem nu at maksimere f(7,0,z)=49+z under bibetingelsen 7+z<= 7, hvor man ser, at z=0. Det er mere indviklet – man skal bruge information om, hvor godt man udnytter sit råderum, i.e., om man har lighedstegn i ulighederne, eller man er tæt på, og det skal sammenlignes med den funktion, vi vil optimere- hvor meget den vokser i forskellige retninger.
I praksis bruges metoden også i virksomheder, hvor underafdelinger skal træffe beslutninger og hovedafdelingen skal koordinere dem.
For en dansk introduktion til lineær programmering og simplexmetoden kan man f.eks. se matnatverdensklasse
Optimeringsproblemer er selvsagt væsentlige i anvendelser. Fra gymnasiet kender man dem fra funktionsundersøgelser, hvor man differentierer for at finde kandidater til maksimum og minimum, og der er et utal af metoder. Ikke-lineære problemer (hvor afgrænsningerne ikke er (højere dimensionale) planer, og/eller niveaumængderne er mere indviklede, er meget vanskeligere end de lineære. Man kan så forsøge med at tilnærme problemet med et, der er lineært eller man kan bruge andre metoder a la den fra gymnasiet, hvor man skal differentiere, eller man kan bruge variationsregningsmetoder eller andet. Løsningsmetoden afhænger af, om man skal have en præcis løsning, et hurtigt svar eller en passende kombination.