Arkadiusz Jadczyk Arkadiusz Jadczyk
786
BLOG

Kwestia optymalizacji

Arkadiusz Jadczyk Arkadiusz Jadczyk Kultura Obserwuj notkę 16

Kto z nas nie optymalizuje? Jak kupić najtaniej? Jak awansować jak najwyżej pracujac przy tym jak najmniej? Jak sprzedać najdrożej? Jak odwiedzić wszystkie wybrane punkty i dotrzeć do celu w najkrótszym czasie? Z jaką prędkością jechać, by zużyć najmniej paliwa? Lub bardziej geometryczne: mając daną długość sznurka jak otoczyć nim możliwie największą powierzchnię. Czy będzie to kwadrat czy trójkąt, czy może elipsa? Znajdowaniem metod rozwiązywania tego typu zagadnień zajmują się dwa działy matematyki: rachunek wariacyjny i optymalizacja. Ten drugi dział jest szerszy, bowiem rachunek wariacyjny ma do czynienia jedynie z zagadnieniami „gładkimi”, optymalizacja zaś dopuszcza zagadnienia dyskretne, gdzie rozwiązania problemu mogą zawierać nagłe zmiany kierunku, prędkości itd. Z drugiej strony rachunek wariacyjny wychodzi poza czyste problemy optymalizacji, stosuje się szeroko w fizyce gdzie szukamy czasem rozwiązań „ekstremalnych” lub „stacjonarnych”, bo wierzymy, że z tajemniczych powodów Przyroda właśnie je lubi.

 

Typowym, historycznym przykładem jest tzw. Problem brachistochrony. Z Wikipedii podkradłem ten obrazek:

Brachistochrona

Ta kulka spadająca pionowo jest nieco tajemnicza. Jak rozumiem spada pionowo i odbija się od ukośnej ścianki (nie ma jej na rysunku) po czym toczy się poziomo ze stałą prędkością jaką osiągnęła w czasie spadania. Ten przypadek (nagła zmiana kierunku) wykracza poza rachunek wariacyjny i należy właśnie do optymizacji.

 

Dlaczego zaś o optymalizacji dziś nawijam? Robię to dlatego, że mamy do rozwiązania problem geometryczny: jak znaleźć najkrótszą drogę pomiędzy dwoma punktami na pofałdowanej robótce przedstawiającej nieeuklidesową geometrię Bolyai-Łobaczewskiego?

Geometria nieeuklidesowa

Gdyby pomiędzy punktami A i B była rozciągnięta gumka – sam wybrałaby najkrótszą drogę. My chcemy to zrobić w naszych głowach, bez gumki, za to z ołówkiem i kartką papieru, używając do tego celu metryki Riemanna. Mamy bowiem wzór na element długości:

 

ds2 = g11(x,y) (Delta x)2 + g12(x,y) Delta x Delta y + g21(x,y) Delta y Delta x + g22(x,y) (Delta y)2

 

a w naszym przypadku, gdy

 

g21(x,y) = g12(x,y) = 0, g22(x,y) = 1/y2

 

mamy pop prostu:

 

ds2 = 1/y2 (dx2 + dy2)

 

lub

 

ds = (1/y) (dx2 + dy2)1/2

 

Przypuśćmy, że chcemy znaleźć najkrótszą drogę pomiędzy punktami A i B, np. A = (0,1), B= (1,2).

 

Jaką drogę wybrać? Czy większe y, tym mniejsze 1/y, tym mniejsze ds, zatem opłaca nam się iść nie prosto a trochę w górę. Ale nie za bardzo w górę, bo chcemy dojść do punktu B na wysokości y=2. Musi więc być droga optymalna. Dobrze zacząć od czegoś prostszego, czegoś, co możemy rozwiązać metodami ze szkoły. Rozważmy więc taki problem, problem zapożyczony z książeczki Jakuba Perelmana „Zajmująca matematyka”:

Perelman - rzeka

Są miasteczka A i B. A leży nad rzeką. B jest w odległości a kilometrów wzdłuż rzeki i w odległości d od rzeki. Z A do B przewozi się towary. Można przewozić po wodzie i po lądzie. Przewóz po wodzie jest dwa razy tańszy (za tono-kilometr) niż przewóz po lądzie. Zdecydowano więc położyć nową drogę z B do rzeki. Jak optymalnie wybrać docelowy punkt D na brzegu rzeki?

 

Przytoczę, za Perelmanem, rozwiązanie tego zagadnienia. Zmieniłem trochę obrazek i oznaczenia, by lepiej odpowiadały sytuacji z geometrią Łobaczewskiego. Płynąć w górę się bardziej opłaca, ale z drugiej strony krócej iść na skos niż po bokach trójkąta. Gdzie jest więc optimum? Rozumujemy tak:

 

Oznaczmy odległość AD przez y, zaś długość szosy DB – przez x. Oznaczmy odległość AC przez a, zaś odległość BC przez d.

 

Skoro przewóz po szosie jest dwa razy droższy niż przewóz po rzece, to suma:

 

y+2x

 

winna być jak najmniejsza. Interesuje nas więc wartośc

 

m = y + 2x

 

Ale y = a -DC, zaś DC = (x2 – d2)1/2. Nasze równanie ma zatem postać:

 

m = a - (x2 – d2)1/2 + 2x.

 

Odległość a jest dana. By m było jak najmniejsze, to co następuje po a musi być jak najmniejsze. Nazwijmy je p:

 

p =2x - (x2 – d2)1/2

 

Od tego miejsca nie całkiem rozumiem Perelmana, bo ten rozumuje wielce sprytnie. Może ktoś mi pomoże? Wyjaśni lepiej, inaczej?

 

Perelman argumentuje tak:

 

Chcemy pozbyć się pierwiastka, przenosząc na drugą stronę:

 

(x2 – d2)1/2 = 2x - p

 

Podnosimy obie strony do kwadratu

 

x2 – d2 = (2x – p)2

 

Jak się to wyliczy, przeniesie na jedną stronę dostajemy:

 

3x2 - 4px + p2 + d2 =0

 

Możemy zastosować znane ze szkoły wzory by stąd wyliczyć x:

 

x = (2p +/- (p - 3d2)1/2)/3

 

I teraz Perelman pisze: by x było rzeczywiste, wyrażenie pod pierwiastkiem musi być nieujemne. Najmniejsze możliwe p przy którym x jest rzeczywiste, to p= d31/2. Wtedy

x = 2d 31/2/3.

Wtedy sinus kąta BDC wynosi d/x t.j. 31/2/2. Zatem kąt BDC wynosi 60 stopni. Innymi słowy drogę należy poprowadzić pod katem 60 stopni do rzeki.

 

No dobrze, a co jeśli A leży tak blisko C, że droga pod katem 60 stopni sięgałaby za A?

Wtedy nasze rozumowanie się nie stosuje. Wtedy należy poprowadzić drogę wprost z B do A i o rzece w ogóle zapomnieć.

Naukowiec, zainteresowany obrzeżami nauki. Katalog SEO Katalog Stron map counter Życie jest religią. Nasze życiowe doświadczenia odzwierciedlają nasze oddziaływania z Bogiem. Ludzie śpiący są ludźmi małej wiary gdy idzie o ich oddziaływania ze wszystkim co stworzone. Niektórzy ludzie sądzą, że świat istnieje dla nich, po to, by go pokonać, zignorować lub zgasić. Dla tych ludzi świat zgaśnie. Staną się dokładnie tym co dali życiu. Staną się jedynie snem w "przeszłości". Ci co baczą uważnie na obiektywną rzeczywistość wokół siebie, staną się rzeczywistością "Przyszłości" Lista wszystkich wpisów  

Nowości od blogera

Komentarze

Inne tematy w dziale Kultura