TUGAS IIBILANGAN RANDOMTUGAS DIBUAT UNTUK MEMENUHI MATA KULIAH SIMULASI KOMPUTER DOSEN PENGAMPU:GOENAWAN TRIDJOKO PRIJONO, IR. MTDISUSUN OLEH :MARWAH TIFFANI(080411012)PROGRAM STUDI TEKNIK INDUSTRIFAKULTAS TEKNIKUNIVERSITAS MUHAMMADIYAH CIREBON20111. PEMBANGKIT BILANGAN RANDOM1.1Random Number Generation Random Number Generationadalah suatu algoritma yang digunakan untuk menghasilkan urutan urutan atau sequence dari angka angka sebagai hasil dari perhitungan dengan komputer yang diketahui distribusinya sehingga angka angka tersebut muncul secara random dan digunakan terus menerus.Dari definisi tersebut dapat ditarik tiga pokok pengertian, yaitu sebagai berikut :1.2 Sequence atau urutan Yang dimaksud dengan sequence disini adalah bahwa random numbertersebut harus dapat dihasilkan secara urut dalam jumlah yang mengikuti algoritma tertentu dan sesuai drengan distribusi yang akan terjadi atau yang dikehendaki.1.3Distribution atau distribusiPengertian distribusi berhubungan dengan distribusi probabilitas yang dipergunakan untuk meninjau atau terlibat langsung dalam penarikan random number tersebut . Pada umumnya distribusi probabilitas untuk random number ini adalah Uniform Variate yang dikenal dengan distribusi Uniform.Seperti pada random sequence, , ... , dan pada setiap random sequence ini masing masing mempunyai , , ... yang merupakan subsequence yang berhubungan tetapi terpisah atau dengan lainnya, yang dikenal dengan Jointly Independent , dan masing masing juga mempunyai probabilitas distribusUniform antar 0 dan n. (0,n). Bila sequence ini terputus maka akan merusak atau mengurangi arti dari kegiatan simulasi yang berjalan.1.4 Deskripsi Random NumberDalam penentuan random number pada umumnya terdapat beberapa sumber yang dipergunakan, antara lain :a. Tabel random number Tabel random numberini sudah banyak ditemukan mulai dari enam digit samapi dengan dua belas digit.b. Electronic Random NumberElectronic Random Number ini banyak juga di pergunakan dalam percobaan penelitian.c. Congruential Pseudo Random NumberGeneratorRandom NumberGenerator ini terdiri dari tiga bagian : Additive ( Aritmatic ) Random NumberGenerator Multiplicative Random Number Generator Mixed CongruentialRandom Number GeneratorDi dalam penarikan random number pada komputer, yang sering digunakan adalah CongruentialRandom Number Generator dengan sifat sifatnya yang terpenting adalah sebagai berikut :1.6IndependentPengertian independent ini berarti masing masing komponen atau variabel variabelnya harus bebas dari ketentuan ketentuan tersendiri.Seperti := Merupakan hasil akhir = Merupakan angka pertama yang bebas tertentua. = Merupakan angka konstan yang dapat bebas dengan ketentuan ketentuannya tersendiri.b. = Merupakan angka bebas tetapi tidak ada hibungan tertentu dengan m ( modulo )1.7 UniformPengertian Uniform disini merupakan suatu distribusi yang umum yakni distribusi probabilitas yang sama untuk semua besaran yang dikeluarakan / diambil. Ini berarti probabiliotasnya diusahakan sama untuk setiap penarikan random number tersebut.1.8 DensePengertian dense disini merupakan maksud dari density Probabilitas Distribution yang tentunya harus mengikuti syarat probabilitas yaitu terletak antara 0 dan 1. Ini berarti dalam penarikan angka angka yang dibutuhkan dari Random Number Generator cukup banyak dan dibuat sedemikian rupa sehingga 0 R . N . 1.1.9 EfficientPengertian Efficient disini di maksud dapat cukup sederhana dan dalam menggunakan cara ini harus telebih dahulu memilih angka angka untuk variabel variabelnya yang cocok. Ini berarti dalam penari9kan random numbertersebut harus dapat menentukan angka angka untuk variabelnya yang sesuai sehingga dapat berjalan terus menerus.2. PENYELESAIAN R.N.GPada Congruental Pseudo RandomNumber Generator dapat dijelaskan untuk masing masing formula atau rumus sebagai berikut :2.1 Additive / Aritmathic RNGBentuk rumusnya : ( mod. mDengan catatan : Angka Random Number yang baruAngka Random Number yang lama / yang semulac.=Angka konstan yang bersyaratm. =Angka moduloBagi Additive RNG ini diperlukan perhaytian syarat- syaratnya sebagai berikut :a. Konstan a harus lebih besar dari.Dan biasanya dinyatakan dengan syarat : b. Untuk konstan c harus berangka ganjil apabila m bernilai pada dua. Tidak boleh nilai berkelipatan dari m.c. Untuk modulo m harus bilangan prime atau bilngan tidak terbagikan, sehingga memudahkan atau memperlancar perhitungan perhitungan didalam komputer dapat berjalan dengan mudah dan lancar.d. Untuk pertama harus merupakan angka integer dan juga ganjil dan cukup besar.2.2 Multiplicative RNGAngka Random Number yang semulaAngka Random Number yang baruA > 1 ; c = 0 ; m > 1Syarat-syarat yang lainnya adalah sama dengan Additive RNG.Dalam perunusan multiplicative ini terdapat tiga variabel yang menentukan untuk nilai nilai Random Number yang dapat diperoleh seterusnya dengan tidak ada pengulangan pada angka angkanya. Dan untuk pemilihan nilai nilai yang terbaik dijabarkan sebagai berikut :a. Pemilihan nilai : m (modulo) merupakan satu angka integer yang cukup besar dan merupakan satu kata (word) dari yang dipakai pada komputer. Sebagai contoh : Dalam komputer IBM 360/370 sistem sebuah kata adalah 32 bits panjangnya, berarti angka integer yang terbesar dalam satu kata komputer ( komputer words ) adalah :21474886471 2 1 231 1 32 Maka nilai m harus lebih satu integer, atau :648 . 483 . 21471 21 32+ m Untuk mesin computer system 1130/1800 IBM yang dikenal dengan 16 BITS Words maka untuk memilih m adalah :768 . 32 21 16 m Sedangkan untuk memilih microcomputer dengan 8 BITS akan digunakan :128 21 8 m Dengan nilai m ini akan merupakan pembagi dari nilai (a x ZI ) yang mengikuti operasi modulo.Hal ini akan menjadikan mesin computer hanya dapat tertinggi dengan integer m- 1 dan apabila produk produknya lebih besar dari nilai nilai ini akan mengakibatkan overflow atau hang.b. Pemilihan konstanta multiplier : a harus tepat Pemilihan nilai a harus bilangan prima terhadap m. A juga harus bilangan ganjil ( Odd ). Pemilihan yang terbaik adalah dengan rumus322 t ba

yang lebih mendekat pada ketepatan. Untuk sistem IBM 1130/1800 dengan : Bits akan Diperoleh259 3 2321628 + t a Dan untuk mikro komputer dengan 8 Bits, maka akan diperoleh :19 3 16 3 232824 + + t a Untuk kebanyakan mikro komputer.c. Pemilihan untuk 0Z , yang dikenal dengan : SEED = 0Z mengharuskan relative belakangan prima terhadap m.Hal ini dapat diperhatikan dengan mudah apabila dicari untuk m adalah angka berpangkat 2 ( dua) angka exporer dari angka 2. Dengan demikain untuk 0Z adalah setiap angka angka yang ganjil ( odel number ) seperti :0Z ISEED = 12357Dapat diambil sembarang asalkan bilangan ganjil, dan biasanya cukup besar.d. Bilangan c yang dipilih harus bukan merupakan kelipatan dari m dan juga harus bilangan ganjil.Sebgai contoh 1 =m c Z a Zimod1 1+ +Bila digunakan mikrokomputer dengan 8 bits. Jadi : 2371281912357cmaZoOperasi module = Random Number 128 mod ) 237 12357 19 ( 1 x x Z = 235020 235008= 1209375 . 0128121 R128 mod 237 12 192+ x Z = 465 384 = 816328 . 0128812 R128 mod 237 81 193+ x Z= 1776 1664= 112 875 . 01281123 R, dan seterusnya.2.3 Mixed Pseudo RNG Pseudo Random Number ini dapat dirumuskan dengan :) . mod ( .11m CaaZ a Znonn+ a. Rumus Pseudo Rando Number Generator ini adalah dengan syarat utama n harus sejumlah bilangan integer ( bulat ) dan lebih besar dari nol, rumus ini dikenal juga dengan nama Linier Congruential R>N>G .b. Namun apabila nilai C = 0 maka akan diperoleh rumus yang dikenal : Multiplicative Congruen RNG. Rumus Multiplicative ini cukup baik untuk masa masa yang akan dating karena sedikit sekali stronge memori yang dibutuhkan.c. Penjelasan : MIXED CONGRUENTAL GENERATORDengan beberaapa kondisi syrat syaratnya sebagai berikut : C = adalah bilangan relative prima terhadap n a = 1 ( mod.q ) untuk setiap faktor prima q dari m a = 1 ( mod 4 ) apabila 4 adalah suatu faktor dari md. Kondisi 1 berarti bahwa pembagi umum yang terbesar dari c dan m adalah satu. Dan kondisi ini mudah dapat dicapai.3e. Kondisi 2 berarti : a- q 1

,_

qaApabila : k =

,_

qa akan dapat diperoleh untuk : aA = 1 + qkDimana q adalah faktor Prima dari m.f. Kondisi 3 : berarti a = 1 + 4kApabila : m/4 = adalah integerArtinya m bilangan bulat dapat dibagi 43. Pembangkit Bilangan RandomDalam simulasi, terutama dalam proses memodelkan sistem yang mempunyai sifat probabilistik, penggunaan bilangan random sangat menentukan jalannya proses tersebut. Variabel yang mempunyai sifat probabilistik ditirukan sifat acaknya (randomness) melalui urutan bilangan random (i 2 1u , , u , u ) yang mempunyai sifat saling bebas (independent) dan terdistribusi seragam (uniform) dalam interval (0,1) (Watson dan Blackstone, 1989; Rubinstein dan Melamed, 1998; Law dan Kelton, 2000).Pada awal perkembangan simulasi, urutan bilangan random yang memiliki sifat acak tersebut dibangkitkan dengan cara-cara manual seperti melemparkan mata uang, melemparkan dadu, menarik kartu, memutar rolet. Kemudian dalam perkembangan selanjutnya digunakan alat-alat mekanis-fisis-elektronis, seperti Noise Diode dan Geiger Counter yang terhubung dengan komputer, untuk menirukan sifat acak tersebut. Hal ini berkembang karena adanya pandangan umum yang menyatakan bahwa hanya peralatan elektronis atau mekanis saja yang bisa menghasilkan bilangan random yang memiliki sifat acak yang sebenarnya. Meskipun sampai sekarang peralatan tersebut masih dipakai untuk alat-alat perjudian dan lotere, tetapi peralatan seperti itu tidak digunakan lagi untuk keperluan simulasi, karena terlalu lama dalam pembangkitannya, urutan bilangan yang dihasilkan tidak dapat diulang, dan urutan bilangan yang dihasilkan menunjukkan sifat yang tidak saling bebas dan bias (Rubinstein dan Melamed, 1998).Perkembangan terakhir yang digunakan untuk membangkitkan urutan bilangan random adalah dengan menggunakan persamaan rekursif tertentu, yang lebih dikenal dengan nama pembangkit bilangan random (Random Number Generator). Penggunaannya dalam program komputer sangat disukai karena sangat cepat, dapat mengulang hasil urutan bilangan yang diperoleh, dan hanya membutuhkan sumber daya yang kecil. Karena persamaan yang digunakan tetap, pembangkit bilangan random dalam kenyataannya menghasilkan urutan yang tetap pula. Akan tetapi karena urutan tersebut mempunyai sifat statistik tertentu yang dapat menirukan bilangan random yang sebenarnya, urutan bilangan random yang dihasilkan tetap dapat digunakan untuk menirukan sifat acak. Oleh karena itu pula, urutan bilangan random yang dihasilkan oleh pembangkit bilangan random sering diberi nama bilangan random semu (pseudorandom number). (Rubinstein dan Melamed, 1998; Law dan Kelton, 2000).Saat ini terdapat beberapa jenis pembangkit bilangan random yang biasa digunakan, antara lain: Linear Congruential Generator (LCG), Multiple Recursive Generator (MRG), dan Non Linear Generator (NLG). Untuk membangkitkan urutan bilangan random i 2 1u , , u , u , MRG menggunakan persamaan rekursif dengan bentuk umum:( ) m mod x a x a x a a xk i k i i i + + + + 2 2 1 1 0(1)mxuii(2)0xsering disebut sebagai Seed dari urutan bilangan random tersebut. Untuk 1 k , persamaan 1 akan berubah menjadi:( ) m mod c ax xi i+ 1(3)merupakan bentuk umum persamaan rekursif LCG. Sedangkan dalam persamaan rekursif terdapat bentuk nonlinear, pembangkit bilangan random itu digolongkan dalam NLG (LEcuyer, 2001).Untuk setiap jenis pembangkit bilangan random, penentuan besarnya parameter yang digunakan (misal: a, c, m, dan 0x dalam LCG) merupakan hal yang penting untuk menghasilkan urutan bilangan random yang memiliki sifat saling bebas dan seragam (Law dan Kelton, 2000).3.1 Uji Empiris-Statistik Bilangan Random Secara umum, Bilangan Random yang baik harus memiliki sifat-sifat : periode perulangan yang panjang, lolos uji empiris-statistik yang menunjukkan keseragaman dan kebebasan, mudah diaplikasikan ke bahasa pemrograman tingkat tinggi standar, dan urutan bilangan tersebut bisa diulang kapan dan di mana pun (LEcuyer, 1997).Dalam melakukan uji keseragaman dan kebebasan terdapat kontradiksi antara asumsi bahwa urutan bilangan tersebut saling bebas dan seragam dengan kenyataan bahwa urutan bilangan tersebut dibangkitkan dengan persamaan yang tertentu sehingga menghasilkan urutan yang deterministik dengan periode perulangan yang deterministik pula. Hal ini yang menyebabkan terdapat banyak sekali uji empiris-statistik yang bisa dilakukan untuk menunjukkan kedua hal tersebut, dan dengan lolos dari uji-uji tersebut tidak dapat menjamin bahwa suatu pembangkit bilangan random merupakan pembangkit yang sempurna (LEcuyer, 1997).Semakin banyak suatu pembangkit bilangan random lolos dari bermacam uji yang dilakukan hanya memperbesar keyakinan penguji bahwa pembangkit tersebut merupakan pembangkit yang diduga baik. Dapat dikatakan bahwa pembangkit yang jelek adalah pembangkit yang tidak lolos dari uji empiris sederhana dan pembangkit yang baik adalah pembangkit yang hanya tidak lolos dari uji empiris yang kompleks (LEcuyer, 1998). Dua jenis uji empiris sederhana yang cukup dikenal adalah uji keseragaman (uniformity test) dan uji kebebasan (independence test). Yang termasuk uji keseragaman antara lain adalah uji frekuensi (frequency test) seperti uji Kolmogorov-Smirnov dan uji Chi-Square. Sedangkan yang digolongkan sebagai uji kebebasan adalah uji jalan (runs test) : naik dan turun (runs up and runs down), di atas dan di bawah mean (runs above and below mean), dan uji autokorelasi (autocorrelation test) (Banks, et. al, 2001). a. Uji Kolmogorov-SmirnovUji ini membandingkan antara c.d.f. distribusi uniform kontinu, ( ) x F, dengan c.d.f distribusi empiris dari N pengamatan, ( ) x SN. Secara definisi,( ) x x F , 1 0 x(4)( )( )Nx R nx SiN(5)Uji ini didasarkan pada harga terbesar dari nilai mutlak selisih dari distribusi empiris dan teoritis dalam interval batas distribusi tersebut, yaitu :( ) ( ) x S x F max DN (6)Hipotesis bahwa distribusi empiris merupakan sampel dari distribusi teoritis akan ditolak apabila D D >, dengan adalah besarnya tingkat keyakinan.b. Uji Chi-SquareUji ini membandingkan antara jumlah bilangan yang berada pada kelas-i (iO) dengan ekspektasinya (iE), yang menggunakan statistik berikut ini : ( )ni ii iEE O122(7)Untuk distribusi uniform, jumlah kelas n dan jumlah bilangan N, nilai ekspektasi seluruh kelas dapat ditentukan dengan :nNEi(8)Distribusi sampling dari statistik 2 adalah distribusi chi-square dengan n 1 derajat bebas. c. Uji Runs Up and Runs DownUji ini membandingkan antara jumlah total run naik dan turun dari suatu urutan bilangan dengan urutan bilangan yang benar-benar random. Suatu run didefinisikan sebagai urutan kejadian yang sama yang diawali dan diakhiri dengan kejadian yang berbeda. Sebuah run naik terdiri dari serangkaian bilangan yang semakin lama semakin besar, sedangkan run turun terdiri dari serangkaian bilangan yang semakin mengecil.Jika a adalah jumlah total run dalam urutan random yang saling bebas sejumlah N bilangan, mean dan varians dari a adalah3 1 2 Na(9)9029 162Na(10)Untuk N yang besar (20 N), distribusi dari a adalah distribusi normal. Sehingga untuk menguji urutan bilangan tersebut merupakan urutan random atau bukan digunakan statistik berikut ini :aaaZ 0(11)dengan 0Zterdistribusi normal standar. Sehingga hipotesis bahwa suatu urutan bilangan random saling bebas akan ditolak bila 2 0 /Z Z> atau 2 0 /Z Z atau 2 0 /Z Z atau 2 / 0Z Z