12 januára 2009

Slnečné kolektory: riešenie

Problém "slnečné kolektory", ktorý som pre Vás vymyslel pred pár dňami, sa so silným ohlasom veru nestretol. Nuž, čím bližšie majú úlohy k praktickým aplikáciám, tým je obvykle ťažšie vyriešiť ich len pomocou dôvtipu; nie sú to už tie elegantné matematické hlavolamy z Gardnerovych kníh. Hľadanie riešenia "inžinierskych" úloh však má tiež svoje čaro a práve o tom by som Vás chcel tak trochu presvedčiť v tomto príspevku. Takže ako riešiť úlohu o optimálnej konfigurácii kolektorov?

Je zrejmé, že prvoradou úlohou je vedieť pre zadanú konfiguráciu a pre zadaný smer lúčov slnka vypočítať úhrnnú šírku kolektorov, na ktorú dopadá svetlo, t.j. veľkosť tieňa, ktorý by vrhala sústava štyroch kruhov s priemermi 1 meter a so stredmi v osiach kolektorov:


Napísať analytický predpis pre veľkosť tieňa v závislosti od polohy slnka je veľmi ťažké, avšak programík (napríklad pre prostredie R) na numerický výpočet je raz dva (procedúry, ako tá nasledujúca, môžete úplne kľudne preskočiť; sú tu len pre tých, ktorí by chceli vedieť podrobnosti):

shadow<-function (x,b){
# x ... uhol smeru kolmeho slnecne luce
# b ... suradnice osi v poradi x1,x2,x3,x4,y1,y2,y3,y4
h<-b[1:4]*cos(x)+b[5:8]*sin(x)
h<-sort(h); L<-h[4]-h[1]+1
for(i in 2:4) if(h[i]-h[i-1]>1){L<-L-(h[i]-h[i-1]-1)}
L }


Minimálnu veľkosť tieňa počas dňa potom určíme pomocou jednorozmernej minimalizačnej procedúry, ktorú nám poskytuje používaný software; v prípade programu R je to funkcia optimize. Treba si dať samozrejme pozor na to, že naša minimalizovaná funkcia môže obsahovať lokálne minimá; lepšie je preto rozbiť množinu smerov na viacero podintervalov, napríklad takto:

minshadow<-function b="" br=""># b ... suradnice osi v poradi x1,x2,x3,x4,y1,y2,y3,y4
 s<-seq(0,pi,length=11); res<-rep(Inf,10)
 for(i in 1:10){
  res[i]<-optimize(f=shadow,interval=c(s[i],s[i+1]),b=b)$objective}
 -min(res) }


Teraz už máme program, ktorým môžeme testovať "podozrivé" konfigurácie. Napríklad ak odskúšame konfiguráciu, ktorú navrhol Lev v komentári k predošlému príspevku, t.j. takú, v ktorej osi kolektorov ležia vo vrcholoch a v ťažisku najväčšieho rovnostranného trojuholníka, ktorý sa daného štvorca zmestí, dostaneme hodnotu minimálneho tieňa približne 2598 mm.

Je Levova konfigurácia optimálna? Aby som zodpovedal túto otázku, urobil som si krátky programík na maximalizáciu samotnej funkcie minshadow, ktorý je v zásade genetický algoritmus bez rekombinácie, čiže jednotlivé konfigurácie, čoby "jedinci populácie", produkujú potomkov "asexuálne", výlučne náhodnými mutáciami svojich vlastných polôh osí, aka "chromozómov". Všimnite si, aký je tento program doslova triviálny:

function(k,s,N) {
# k ... velkost populacie (volil som 500)
# s ... inicialna velkost mutacii (0.4)
# N ... pocet generacii (35)
 cents.mut<-cents k="" matrix="" ncol="k,nrow=8)<br" runif=""> vals<-rep br="" k=""> for(i in 1:N){
  for(j in 1:k){vals[j]<-minshadow br="" cents="" j="">  o<-order br="" cents="" o="" vals="">  for(r in 1:k){
   cents.mut[,r]<-pmax cents="" k="" pmin="" prob="(k:1)^5)]<br" sample="">     +(s/i)*rnorm(8),1),-1)}
  cents<-cents .mut="" br="">}


Polohy osí jednotlivých konfigurácií kolektorov som nechal vykreslovať červenými bodkami a spojnice medzi osami jednotlivých konfigurácií modrými spojnicami. Najlepšiu konfiguráciu v každej generácii som vyznačil čiernymi spojnicami a celý priebeh "vývoja" som zachytil na nasledovnom videu:



Iniciálna populácia je vygenerovaná úplne náhodne (rovnomerne na celom štvorci). Po úvodnej fáze divokého experimentovania sa vytvoria zhluky chromozómov podieľajúcich sa na "úspešných" konfiguráciách. Neskôr sa vytvoria oddelené "subpopulácie", z ktorých predposledná úplne vymizne až v 26. generácii. Ako vidíme, výsledná konfigurácia pôsobí akoby bola navrhnutá "inteligentne" a naviac je dostatočná na splnenie zadania našej pôvodnej úlohy; jej minimálna veľkosť je 2617 mm.

Všimnime si výslednú konfiguráciu bližšie. Tri body, označme si ich A,B,C, ležia veľmi blízko pri okraji štvorca a štvrtý bod, D, niekde vo vnútri. Ak by bola optimálna poloha bodu A presne (-1,-1), bodu B presne (1,0) a bodu C presne (-1,1), aká bude optimálna poloha bodu D? Netreba dlho uvažovať, kým si človek uvedomí, že minimálna veľkosť tieňa bude maximalizovaná vtedy, keď vzdialenosť bodu D od všetkých troch strán trojuholníka ABC bude rovnaká. To znamená, že bod D bude stredom do ABC vpísanej kružnice. Je už záležitosťou elementárnej matematiky dopočítať presnú polohu bodu D a výslednú hodnotu d minimálnej veľkosti tieňa:


Pochopiteľne, všetky štyri "rotácie" tohto riešenia sú takisto optimálne. Ak Vás tento problém zaujal, môžete sa ešte pokúsiť zodpovedať nasledovnú otázku: Existuje aj optimálna konfigurácia, ktorá nie je len rotáciou tej našej? ;-)

6 komentárov:

Michal Lehuta povedal(a)...

pekne..

rasto povedal(a)...

Presne tak: pekné. Proste to video bolo pekné, keby sa vybralo zopár framov (resp. stavov), tak by z toho bola séria pekných moderných obrazov:-)

Celkom zaujímavá a pekná je minimálna plocha tieňa tohto najlepšieho usporiadania - 2,618033987... povedomé číslo, však? Je to hodnota zlatého rezu +1.

Radoslav Harman povedal(a)...

Som rád, že sa Vám to páči chalani.

Inak to s tým zlatým rezom som si neuvedomil, dobrý postreh!

Skutočne; vzdialenosť bodu D od strán štvorca je zlatý rez mínus 1 (alebo aj 1 lomeno zlatý rez) a minimálna veľkosť tieňa je zlatý rez plus 1 (alebo aj zlatý rez na druhú).

Pozoruhodná "náhoda"...

Lev bez hrivy povedal(a)...

No, nebol som daleko :-) ale nebolo to ono :-(

X povedal(a)...

Mne osobne sa tento problem velmi paci, len skoda, ze som tu dlhsie nebol a presvihol som to. Najviac sa mi na tom paci prave to, ze to nie je len matematika, ktora sluzi pre dalsiu matematiku. Tiez sa mi paci ta aplikacia genetickych algoritmov. Takyto problem by urcite zaujal aj laikov.

Peter Richtárik povedal(a)...

Fantastický príspevok Rado!!!