Člankom o Monte Carlo metodi rep.hr otvara novu rubriku 'Stručni članci' unutar koje će se objavljivati stručni tekstovi s područja Računalstva i ekonomije.
Monte Carlo metode danas su u upotrebi u različitim područjima znanosti: od numeričke matematike, fizikalne kemije i statističke fizike, pa sve do razvoja poluvodiča, računalne grafike i financija. No, također se koriste za rješavanje svakodnevnih problema kao što je npr. izračun moguće dobiti nekog posla ili procjenjivanje trajanja projekta.
Od nasumičnog do realnog
Naziv Monte Carlo odnosi se na široki spektar matematičkih modela i algoritama čija je glavna značajka upotreba slučajnih brojeva u rješavanju različitih problema. Najčešće je riječ o matematičkim problemima čija se rješenja ne mogu odrediti analitički ili za to ne postoje učinkoviti numerički algoritmi. Uz to, često se koriste i za provjeru rezultata dobivenih analitičkim ili drugim metodama. Zbog velikog broja matematičkih operacija i ponavljanja, Monte Carlo metode ulaze u široku upotrebu tek s naglim razvojem računala u posljednjim desetljećima dvadesetog stoljeća. Općenito govoreći, da bi se nešto prozvalo Monte Carlo eksperimentom, dovoljno je koristiti nasumične brojeve da bi se ispitali mogući rezultati eksperimenta.
Samo ime Monte Carlo uveli su Stanislaw Ulam, John von Neumann i Nicholas Metropolis 1946. godine, iako je ta ideja bila poznata i ranije. Enrico Fermi upotrijebio je slične metode 1930. godine kako bi odredio svojstva tada tek otkrivenog neutrona. Američka vojska koristila ih je intenzivno 40-ih i 50-ih godina prilikom razvoja nuklearne, a zatim i hidrogenske bombe, unatoč vrlo ograničenoj snazi tadašnjih računala. Tek nakon pojave elektroničkih računala počinje detaljno proučavanje Monte Carlo metoda. Danas su u upotrebi u različitim područjima znanosti: od numeričke matematike, fizikalne kemije i statističke fizike, sve do razvoja poluvodiča, računalne grafike i financija.
Svaki matematički model u Monte Carlu odvija se po istom uzorku:
1. Odrediti domenu ulaznih podataka
2. Generirati ulazne podatke nasumično iz domene
3. Izvesti determinističku računicu koristeći ulazne podatke
4. Pronaći srednju vrijednost svake pojedine računice
Primjeri Monte Carlo metode
Izračun broja π
Ideju iza Monte Carlo metode pokazat ćemo na vrlo jednostavnom primjeru – pokušat ćemo odrediti iznos Ludolfovog broja π. Grčkim slovom π obilježava se omjer opsega i promjera kruga.
Ako nasumce biramo točku u kvadratu stranice 2r, u kojem se nalazi krug polumjera r, vjerojatnost da se ona nalazi unutar kruga je π/4:
Pk/Pč = r2π/4r2 = π/4
Međutim, tu vjerojatnost možemo i procijeniti. Zakon velikih brojeva govori nam da će omjer broja točaka koje su završile unutar jedinične kružnice i ukupnog broja točaka biti približno jednak traženoj vjerojatnosti; naravno, ako izaberemo dovoljno velik broj točaka. Što je veći broj odabranih točaka, to je i naš rezultat bliže točnoj vrijednosti. Dakle, jedina nepoznanica u gornjoj jednadžbi je broj π. Možemo napisati:
π = 4n/i
gdje je n broj točaka unutar jedinične kružnice, a i ukupan broj odabranih točaka. Na slici 1.1. prikazan je ishod jedne simulacije uz tisuću odabranih točaka. Dobiveni rezultat:
π = 3,108
govori da ovakav način procjene nije vrlo precizan. Algoritam možemo poboljšati odaberemo li npr. sto tisuća točaka. Takvim algoritmom dobivamo π = 3,1420, što je već precizniji rezultat. Ako stotinu puta ponovimo algoritam sa sto tisuća točaka, pohranimo svaki dobiveni rezultat i uzmemo srednji rezultat svih ponavljanja, dobit ćemo vrijednost π = 3,141519, što je vrlo dobar rezultat, pogotovo ako su nam dovoljne prve tri ili četiri decimale.
Procjena zarade
Monte Carlo metoda nam može poslužiti kao pomoć u donošenju poslovnih odluka. Primjerice, ako proizvodimo čestitke, kroz istraživanje tržišta saznali smo da su šanse za prodaju točnog broja čestitki u sljedećim postocima:
Prodajna cijena čestitke je 4 kn, a trošak izrade je 1,5 kn. Čestitke koje se ne prodaju moraju se odbaciti po cijeni od 0,20 kn. Koliko čestitaka moramo proizvesti da bismo ostvarili najveću zaradu?
Načelno, simuliramo potražnju za svaku od proizvodnih količina (10.000; 20.000; 40.000; 60.000) u 1000 ponavljanja. Nakon toga pogledamo koja od proizvedenih količina daje najveći prosjek u tih 1000 ponavljanja. Izvođenje ovih simulacija obavit ćemo u Excelu. Postavke za ovu simulaciju u Excelu prikazane su na slici 1.3.
Slika 1.3
U polje „proizvedeno” unesemo broj komada koji želimo proizvesti. Zavisno o nasumičnom broju koji se sam generira u polju C2, sustav odabire broj komada koji će se prodati iz ćelija E3:F6. Na temelju proizvedenih komada u ćeliji C1 i prodanih u ćeliji C3, možemo izračunati očekivanu zaradu u ćeliji C11.
Da bismo mogli usporediti rezultate, napravit ćemo 1000 ponavljanja za svaki slučaj koji nas zanima. Nakon toga jednostavno izračunamo prosjek tih 1000 ponavljanja za svaki naš slučaj. Na slici 1.4 vidimo da proizvodnja 40.000 čestitaka uvijek daje najveću dobiti (ćelija D13).
Upotreba Monte Carlo metode za procjenjivanje trajanja projekta
S obzirom da se Monte Carlo metoda zasniva na nasumce odabranom broju (slučaju, scenariju), ako uzmemo dovoljno velik broj integracija moguće je dobiti jako dobru procjenu trajanja nekog projekta, kao što se i vidi u gornjim primjerima.
Procjenjivanje trajanja projekta pomoću Monte Carlo metode može se uzeti kao pouzdan podatak, ako su ulazni podaci dovoljno točni. Konkretno, to bi značilo sljedeće: na primjer, ako nam poslovni konzultant procijeni posao na n sati, moramo znati koliki je postotak sigurnosti da će se taj posao stvarno napraviti za tih n sati. Naravno, potrebno je znati i kolike su šanse da se taj isti posao završi ranije, odnosno kasnije.
U obzir treba uzeti i da li isti konzultant koji je dao procjenu radi taj posao. Različitim konzultantima trebat će različit broj sati da naprave isti posao. Ako se mijenja konzultant za kojeg se radila procjena pomoću Monte Carlo metode, mora se izvršiti nova računica s novim ulaznim podacima. Ili, prilikom prvog računanja treba uzeti u obzir da bi zadani posao mogao obavljati i netko drugi, i na osnovu toga povećati postotak optimistične/pesimistične procjene.
U obzir bi trebalo uzeti i kvalitetu dokumentacije po kojoj će se procijenjeni posao izvoditi.
Usporedba Monte Carlo metode s PERT metodom
PERT (Program Evaluation and Review Technique) je metoda u project managementu kojom se može predstaviti trajanje aktivnosti u danom projektu. Temelji se na davanju 3 procjene za svaku aktivnost: optimistično, normalno i pesimistično vrijeme. Očekivano vrijeme trajanja aktivnosti TE dobije se iz formule
TE = (TO + 4× TN + TP) / 6
Za primjer smo uzeli jednu aktivnost i dodijelili joj sljedeće procjene: TO = 3 sata; TN = 5 sati; TP = 9 sati. Po gornjoj formuli za PERT metodu, dobivamo procijenjeno vrijeme trajanja TE = 5,33 sata. Ako iste vrijednosti pokušamo staviti u Monte Carlo metodu, s postocima sigurnosti koji se koriste u PERT metodi (16,67% šanse da se ostvari optimistično i pesimistično vrijeme trajanja aktivnosti, i 66,67% šanse da se ostvari normalno vrijeme trajanja aktivnosti), i simuliramo 10.000 ponavljanja, dobit ćemo vrlo slične vrijednosti u obje metode. To smo i dokazali u primjerima u 2. poglavlju.
Iz formule TE = (TO + 4× TN + TP) / 6 vidimo da je procijenjeno vrijeme TE = (3 + 4 × 5 + 9) / 6 = 5,33 sati.
Dolje, na slici 2.1, prikazana je ista procjena pomoću Monte Carlo metode.
Slika 2.1: Procjenja trajanja aktivnosti pomoću Monte Carlo metode
Autor članka Marko Posavec ovjereni je voditelj projekta u Omega softwareu s položenom C razinom prema međunarodnom sustavu ovjere projektnog managementa. U svom dosadašnjem radu stekao je veliko iskustvo u vođenju nekih od ključnih projekata od kojih svakako treba istaknuti uvođenje bolničkog informacijskog sustava u specijalnu bolnicu Akromion, informatizaciju konzervatorskih odjela u Ministarstvu kulture te mnogobrojne projekte iz područja Business Intelligence-a.
