Masalah Perbaikan (Repair Problem)

Misalkan ada  sebuah sistem yang membutuhkan tepat n buah mesin, dan tidak boleh kurang dari n. Jika kurang maka system ini tidak dapat berfungsi alias gagal.

Untuk menjaga agar sistem ini dapat terus beroperasi dengan baik, maka disediakanlah mesin cadangan. Ketika ada sebuah mesin yang rusak, maka seketika itu pula mesin cadangan langsung digunakan, dan mesin yang rusak tadi langsung dibawa ke bengkel perbaikan mesin. Bengkel tersebut hanya bisa memperbaiki 1 (satu) buah mesin dalam satu waktu, selebihnya harus antri untuk diperbaiki kemudian. (Lihat gambar)

Semua lamanya waktu perbaikan adalah variabel random independent dengan distribusi G (Gamma). Setiap kali mesin digunakan, maka waktu yang dihabiskan sampai akhirnya mesin tersebut rusak adalah variabel random dan independent berdistribusi F (poisson).

Sistem ini dikatakan gagal apabila terjadi kondisi sebuah mesin rusak dan tidak ada mesin cadangan yang tersedia untuk menggantikannya.

Asumsikan bahwa pada awalnya terdapat n + s mesin yang berfungsi dengan baik, n buah yang beroperasi dan s buah sebagai cadangan, kita akan mensimulasikan sistem ini, demikian juga sebagai pendekatan E[T], dimana T adalah waktu ketika sistem nya gagal operasional.

Untuk mensimulasikan hal ini, kita akan menggunakan variabel berikut :

  1. Variabel waktu : t
  2. Variabel Status Sistem : r ( banyaknya mesin yang rusak pada waktu t)

Variabel Status sistem dapat berubah kapanpun, baik karena sebuah mesin yang sedang bekerja saat itu menjadi rusak, atau ketika suatu mesin yang rusak ternyata sudah selesai diperbaiki, dengan kata lain dikatakan bahwa sebuah kejadian terjadi ketika salah satu atau kedua persistiwa ini terjadi.

Untuk mengetahui kapan kejadian berikutnya akan terjadi, kita perlu terus mengikuti saat-saat ketika mesin yang sedang beroperasi menjadi rusak dan suatu saat ketika suatu mesin yang sedang diperbaiki ternyata sudah selesai dan siap beroperasi kembali.

Kita membutuhkan informasi tersebut untuk menentukan waktu terkecil dari n buah waktu kejadian mesin rusak, simpan informasi ini dalam sebuah daftar terurut. 

Daftar kejadian :  \( t_1\leq t_2\leq t_3 \leq …\leq t_n ,t^* \)

Dimana t1 , … , tn adalah waktu (berurutan) dimana  n buah mesin yang sekarang sedang beroperasi akan rusak, dan t* adalah waktu dimana mesin yang saat itu sedang diperbaiki akan selesai diperbaiki dan siap beoperasi lagi, jika tidak ada mesin yang sedang di perbaiki maka t* = \( \infty \)

Mari sekarang kita lakukan simulasinya :

Inisialisasi

Tentukan \(t=r=0, t^{*}=\infty \) ,

Bangkitkan \( X_1, … , X_n \) variabel independent yang memiliki distribusi F. Urutkan nilai-nilai ini dan \( t_i \) adalah nilai terkecil yang ke-i, i = 1, … , n.

Buat daftar kejadian : \( t_1, . . . , t_n , t^*\)

Selanjutnya kita akan berhadapan dengan dua kasus berikut :

Case 1 \( t_1 < t^*\)

Atur kembali : \( t = t_1\).

Atur : r = r + 1 (karena mesin yang lain ada yang rusak)

Jika r = s + 1, hentikan proses ini dan ambil data dari T = t ( ketika ada s + 1 mesin rusak, dan tidak ada cadangan)

Jika r < s + 1, bangkitkan variabel random X yang berdistribusi F. Variabel random ini akan menampilkan waktu kerja dari bengkel perbaikan yang akan digunakan kembali saat ini. Sekarang urutkan kembali nilai-nilai \( t_2,t_3,\cdots, t_n , t + X \) dan jadikan \( t_i \) sebagai nilai terkecil ke-i dari nilai-nilai tersebut, dimana i = 1, … , n.

Jika r = 1, bangkitkan variabel random Y yang mempunyai fungsi distribusi G dan atur t* = t + Y (hal ini diperlukan karena dalam kondisi ketika sebuah baru saja rusak adalah satu-satunya mesin yang beroperasi, dan dengan demikian perbaikan agak segera dilakukan padanya. Y akan menjadi lamanya waktu perbaikan dan karenanya perbaikan akan selesai pada saat t + Y).

Case 2 \( t^* \leq t_1\)

Atur: t = t*

Atur: r = r – 1

Jika r > 0, bangkitkan variabel random Y yang memiliki fungsi distribusi G, dan tampilkan kembali lamanya waktu perbaikan dari mesin yang baru saja masuk ke bengkel perbaikan, dan atur \( t^* = t + Y\)

Jika r = 0, atur \( t^* = \infty \).

Aturan di atas diilustrasikan pada gambar berikut :

<Gambar>

Setiap kali kita berhenti (yaitu pada saat r = s + 1), kita katakan bahwa sebuah operasi selesai dilakukan. Output dari operasional ini adalah nilai dari waktu gagal operasional T. Kita nanti kemudian akan memulai lagi dari awal dan mensimulasikan operasional berikutnya. Secara keseluruhan, misalkan kita melakukan kali operasional dengan ouput masing-masing \( t_1, T_2, … , T_k \), karena semua variabel random adalah independent dan setiapnya mewakili waktu kegagalan sistem, rata-ratanya \( \sum_{i=1}^{k}T_i/k \) adalam estimasi dari E[T], mean dari waktu kegagalan sistem.

 

Simulasi dengan perantara Kejadian Diskrit

Elemen kunci dari simulasi kejadian diskrit adalah variabel-variabel dan kejadian-kejadian . Untuk melakukan simulasi kita secara kontinyu mengamati beberapa variabel tertentu. Secara umum, ada tiga jenis variabel yang sering digunakan, variabel waktu, variabel penghitung (counter),dan variabel status sistem (system state).

Variabel

[table id=1 /]

Ketika sebuah kejadian muncul, nilai dari variabel-variabel di atas akan berubah atau diperbaharui, dan kita akan mengambilnya sebagai keluaran untuk suatu data pengamatan. Untuk tujuan menentukan kapan kejadian berikutnya akan muncul, kita akan memelihara sebuah “daftar kejadian”, yang akan berisi daftar kejadian masa depan terdekat yang akan terjadi dan kapan kejadian tersebut dijadwalkan akan terjadi.

Ketika sebuah peristiwa terjadi, kita akan mengatur kembali waktu dan semua status serta variabel penghitung, serta mengambil data yang terkait. Dengan cara ini , kita akan dapat menelusuri/mengikuti sistem selama sistem itu berproses sepanjang waktu tertentu.

Dalam semua model antrian, kita mengambil anggapan bahwa para pelanggan akan datang mengikuti suatu proses poisson nonhomogeneous dengan fungsi intensitas terbatas \(\lambda (t), t > 0\). Ketika mensimulasikan model ini, kita akan menggunakan subrutin berikut ini untuk membangkitkan nilai dari variabel acak \( T_s \), ditentukan sama waktunya dengan kedatangan pertama kalinya setelah satuan waktu berlalu.

Misalkan \(\lambda \) sedemikian sehingga \(\lambda (t)\leq \lambda \) untuk semua t. Asumsikan bahwa \(\lambda (t), t > 0\), dan  \(\lambda \) sudah ditentukan, subrutin berikut ini akan membangkitkan nilai dari \( T_s \).

Subrutin untuk membangkitkan Ts

[table id=2 /]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Pendekatan Simulasi Kejadian Diskrit (The Discrete Event Simulation Approach)

Mensimulasikan suatu model probabilistik akan melibatkan pembangkitan mekanisme stokastik dari model yang bersangkutan dan kemudian melakukan pengamatan terhadap aliran resultante dari model tersebut sepanjang waktu tertentu.

Berdasarkan kepada alasan pembuatan simulasi tersebut, akan ada beberapa kuantitas pengamatan tertentu yang akan kita cari. Tetapi , walaupun demikian karena evolusi model yang mengikuti waktu itu sering kali melibatkan suatu struktur logis yang rumit dari elemen-elemennya, karenanya tidak selalu mudah untuk melakukan penelusuran/mengikuti perjalanan dari evolusi tersebut, demikian juga dalam menentukan kuantitas yang akan diamati.

Sebuah kerangka kerja (framework) umum, dibangun seputar ide dari “kejadian diskrit”, telah dibuat untuk membantu kita untuk mengikuti sebuah model sepanjang waktu dan menentukan kuantitas pengamatan yang relevan/wajar. Pendekatan pada simulasi yang berdasarkan pada kerangka kerja ini sering disebut dengan Pendekatan Simulasi Kejadian Diskrit.

Sistem Antrian dengan 2 (dua) Server Paralel

Sistem ini terdiri dari 2 (dua) server, dimana ketika pelanggan datang pada saat kedua server dalam keadaan sibuk, maka pelanggan tersebut akan masuk dalam antrian. Dan ketika salah satu server kosong/bebas, maka segera pelanggan yang datang lebih dahulu dalam antrian akan masuk ke dalam server yang kosong/bebas itu, tidak tergantung server nomor berapa yang sedang kosong. Distribusi layanan dari server ke i adalah \( G_i \), i=1,2 (lihat gambar)

2 paralel server

Misalkan kita akan mensimulasikan model ini, sambil mengamati waktu yang dihabiskan oleh setiap pelanggan didalam sistem dan banyaknya layanan yang diberikan/dilakukan oleh setiap server.

Karena disini kita memiliki lebih dari satu server, maka akan berdampak bahwa nanti ketika pelanggan meninggalkan sistem, urutannya mungkin tidak sama dengan urutan ketika dia datang. Karenanya untuk mengetahui pelanggan mana yang akan meninggalkan sistem pada saat layanannya selesai kita akan mencermati pelanggan mana saja yang sedang dalam sistem.

Kita akan memberi nomor pada setiap pelanggan yang baru saja sampai di sistem, yang pertama kali datang diberi nomor 1, berikutnya 2, dan selanjutnya. Kita akan menggunakan variabel-variabel berikut :

Variabel waktu  t

System State Variable  (SS)

Variabel yang mencatat kondisi sistem (System State) pada waktu tertentu.

( \( n, i_1, i_2, . . ., i_n \) )  jika ada n pelanggan di dalam sistem  \(i_1\) akan bersama dengan server 1, \(i_2 \) akan bersama dengan server 2, \( i_3 \) akan bersama dengan server 3 dan seterusnya.

Catatan : SS = (0) ketika sistem kosong/bebas, dan SS = (1,j,0) atau (1,0,j) ketika hanya pelanggan j dan dia sedang dilayani di server 1 atau server 2.

Counter Variables (variabel penghitung)

\( N_A \) : banyaknya kedatangan dalam waktu t .

\( C_j \) : banyaknya pelanggan yang dilayani oleh j, j= 1,2, dalam waktu t .

Output Variables

Variabel yang mencatat kejadian apa saja dan berapa yang dihasilkan dari sistem.

A(n) : waktu kedatangan dari pelanggan n, \( n \geq 1\)

D(n) : waktu keberangkatan pelanggan n, \( n \geq 1\)

Event list \( t_A , t_1 , t_2\)

Dimana \( t_A \) adalah waktu kedatangan berikutnya, dan \( t_1 \) adalah waktu penyelesaian dari pelanggan yang pada saat itu sedang dilayani oleh server i, i = 1, 2. Jika tidak ada lagi pelanggan yang saat itu berada di server i, maka kita jadikan \( t_i = \infty \), i = 1, 2. Berikut ini, daftar kejadian akan selalu berisi tiga variabel yaitu \( t_A , t_1 , t_2 \).

Untuk memulai simulasi, kita berikan nilai awal pada variabel-variabel dan daftar kejadian tersebut sebagian berikut :

Pemberian nilai awal (Initialize)

Set t = \( t_A = C_1 = C_2 = 0\)

Set SS = (0)

Bangkitkan \( T_0\), dan set \( t_A = T_0, T_1 = t_2 =\infty \).

Untuk mengupdate sistem. kita bergerak dalam waktu tertentu hingga kita mencapai event/kejadian berikutnya. Pada kasus-kasus berikut, $latex Y_i $ selalu berasal dari variabel acak yang berdistribusi \( G_i , i=1,2\)

Kasus 1 \( SS = (n, i_1, i_2, … , i_n) \) dan \( t_A = min (t_A, t_1, t_2 )\)

Reset : \( t = t_A\)

Reset : \( N_A = N_A + 1\)

Bangkitkan \( T_t \) dan reset \( t_A = T_t\)

Ambil output data \( A(N_A) = t\)

Jika SS = (0):

Reset : \(SS = (1, N_A,0)\)

Bangkitkan \( Y_1 \) dan reset \( t_1 = t + Y_1\)

Jika SS = (1, j, 0) :

Reset : \( SS = (2, j, N_A)\)

Bangkitkan \(Y_2 \) dan reset \(t_2\)

[ Sumber : Simulation, Sheldon M. Ross]

Variabel Acak Geometri (Geometric Random Variables)

Misalkan ada suatu percobaan yang independent . Setiap kali percobaan itu akan memiliki kemungkinan sukses (probabilitas) sebesar p.

Jika X mewakili banyaknya percobaan awal sebelum akhirnya sebuah sukses terjadi, maka :

Sebenarnya rumus di atas dapat mudah dipahami bahwa untuk mendapatkan sukses yang ke-n maka pastilah (n-1) percobaan sebelumnya adalah gagal. Rumus ini berlaku dengan syarat setiap percobaan terjadi secara independent. (percobaan sebelumnya tidak mempengaruhi percobaan berikutnya).

Sebuah Variabel Acak yang memiliki probability mass function seperti di atas disebut Variabel Acak Geometri dengan parameter p.

Mean dari variabel acak geometri ini diperoleh dengan cara sebagai berikut :

dimana persamaan diatas tersebut menggunakan identitas alajabar untuk 0<x<1,

Sehingga dengan demikian tidak lah sulit untuk menghitung variansinya yaitu :

Metode Penolakan (Rejection Method) pada Variabel Acak Diskrit

Misalkan kita telah memiliki sebuah metode yang efisien untuk mensimulasikan variabel acak. Model tersebut memiliki fungsi probabilitas massa (Probability Mass Function) \(\{ q_{j},j\geq 0 \}\) . Kita bisa menggunakan metode ini sebagai basis simulasi dari distribusi yang memiliki fungsi massa \inline \left \{ p_{j},j \geqslant 0 \right \} dengan cara mensimulasikan terlebih dahulu sebuah variabel acak Y yang memiliki fungsi massa \inline \left \{ q_{j} \right \} dan kemudian menerima nilai simulasi ini dengan probabilitas proporsional \( p_{y}/q_{y} \)

Read more

Menghitung Integral dengan menggunakan Bilangan Acak

Misalkan g(x) adalah sebuah fungsi. Kita ingin menghitung \( \theta \) yaitu :

\dpi{100} \theta = \int_{0}^{1} g(x) dx

Apa yang menjadi dasar bahwa integral di atas dapat dihitung dengan menggunakan bilangan  random \( \theta \)

Penjelasan :

Ambil U suatu bilangan acak yang terdistribusi secara uniform dan independent di interval (0,1).

Kemudian misalnya kita nyatakan \( \theta \) sebagai :

\theta = E[g(U)]

Jika \(U_{1}, … , U_{k}\) adalah variabel random yang independent dan uniform di interval (0,1), maka menjadikan juga \(g( u_{i} )\) adalah sebagai variabel random yang independent dan terdistribusi secara identik dengan mean \( \theta \). Karena itu, dengan menggunakan dasar hukum kuat dari bilangan besar (the strong law of large numbers), mengikuti ketentuannya dengan probabilitas 1.

\(\large \sum_{i=1}^{k}\frac{g(U_{i})}{k} \to E[g(U)]= \theta \;\;\;\; ketika \; k \to \infty\)

Karena itu kita dapat mendekati \( \theta \) dengan cara membangkitkan sebanyak mungkin bilangan random \( u_{i}\) dan mengambilnya sebagai pendekatan kita terhadap nilai rata-rata (average) dari \(g( u_{i} ) \). Pendekatan semacam ini sering disebut sebagai pendekatan Monte Carlo.

Berikut ini adalah contoh algoritma dari bahasa BASIC yang dapat digunakan untuk mendekati nilai \( \theta \) :


10 RANDOMIZE
20 INPUT K
30 S = 0
40 FOR I = 1 TO k
50 U = RND
60 S = S + g(U)
70 NEXT
80 PRINT S/K

Nilai yang dihasilkan dari alogoritma ini adalah nilai dari \( \theta = \int_{0}^{1} g(x) dx \).

Kasus 1 :

Jika kita ingin menghitung :

\( \theta = \int_{a}^{b} g(x) dx \)

maka kita menggunakan substitusi \( y = (x-a)/(b – a), dy = dx / (b-a) \), sehingga :

dimana h(y) = (b – a) g(a + [b – a] y ).

Dengan demikian kita dapat mendekati nilai \( \theta \) dengan membangkitkan bilang random secara kontinyu dan mengambil nilai rata-rata (average) dari h yang dihitung pada bilangan-bilangan random tadi.

Kasus 2 :

Jika kita ingin menghitung :

kita bisa menggunakan substitusi

Substitusi ini menggambarkan bahwa

  1. ketika \( x \to 0\) maka \( y \to 0\)
  2. ketika \( x \to \infty \) maka \( y \to 1\)

Catatan : ingat sifat integral tertentu :

selanjutnya karena :

kemudian

sehingga didapatkan identitas :

dimana


Pembangkit Bilangan Acak Pesudo

Salah satu pendekatan yang sering digunakan dalam membangkitkan bilangan acak pseudo (pseudorandom numbers) adalah memulainya dengan sebuah nilai awal x0 yang sering disebut sebagai bibit/seed, kemudian komputer akan membangkitkan bilangan nilai-nilai berikutnya yaitu xn, \(n\geq 1\) secara rekursif, dengan cara memisalkan :

\(x_{n}= a x_{n-1} \; modulo \; m\) … (3.1)

dimana dan adalah bilangan bulat positif yang sudah ditentukan, dan dimana hal diatas artinya bahwa \(a x_{n-1}\) dibagi dengan dan sisa baginya diambil sebagai nilai dari  \( x_{n}\). Dengan demikian setiap  \( x_{n}\) bisa bernilai salah satu diantara \(0,1,\cdots,m-1\) dan kuantitas dari \(x_{n}/m\) – disebut sebuah bilangan acak pseudo (pseudorandom number)- diambil sebagai nilai pendekatan untuk nilai dari variabel acak uniform (0,1).

Pendekatan yang ditentukan dengan persamaan 3.1 dalam membangkitkan bilangan acak tersebut sering disebut Multiplicative Congruential Method. Karena setiap angka  \( x_{n}\) yang  akan bernilai salah satu dari  \(0,1,\cdots,m-1\), pada suatu saat setelah sejumlah  pembangkitan tertentu akan terjadi perulangan; dan seketika ini terjadi, keseluruhan deret bilangan akan kembali berulang. Dengan demikian, kita seyogyanya ingin memilih konstanta a dan m sedemikian sehingga, untuk sembarang seed  \( x_{0}\), banyaknya variable yang dapat dibangkitkan sebelum terjadi perulangan terjadi cukup besar.

Secara umum konstanta dan dapat dipilih untuk memenuhi 3 kriteria :

  1. Untuk sembarang nilai awal seed , deretan hasil memiliki pemunculan deret variable acak yang independent uniform (0,1)
  2. Untuk sembarang nilai awal seed , banyaknya variable yang dapat dibangkitkan sebelum terjadi perulangan cukup besar.
  3. Nilai-nilai ini dapat dihitung secera efisien dengan menggunakan komputer

Untuk memenuhi ketiga kondisi tersebut di atas, sebaiknya m dipilih dari bilangan prima yang cukup besar, biasanya disesuaikan dengan kemampuan komputer yang digunakan dan ukuran word. Untuk mesin 32 bit (dimana bit pertama digunakan sebagai bit penanda / sign bit), pemilihan m = \( 2^{31} – 1\) dan \( a = 7^5 = 16807\) menghasilkan hasil yang diinginkan.

Pembangkit bilangan acak lainnya adalah :

\(x_{n}= (a x_{n-1}+c) \; modulo \; m\)

pembangkit ini diberi nama mixed congruential generators. Pembangkit ini dianggap lebih baik hasilnya dari pembangkit sebelumnya.

Kebanyakan bahasa pemrograman komputer sudah menyediakan pembangkit bilangan acak nya sendiri. Misalnya dalam bahasa BASIC, bahasa ini menggunakan 2 (dua) buah perintah yaitu :

1 RANDOMIZE

2 U = RND

Contoh program yang menghasilkan 10 (sepuluh) buah bilangan acak :

10  RANDOMIZE

20  FOR I = 1 TO 10

30  U = RND

40  PRINT U

50  NEXT

 

 

Ruang Sample dan Kejadian

Mari kita bayangkan andai ada sebuah percobaan yang kejadian yang mungkin terjadi nya belum kita ketahui pada saat awal.

Semua kejadian yang mungkin terjadi pada percobaan tersebut lalu kita kumpulkan menjadi sebuah kumpulan atau himpunan. Maka kumpulan atau himpunan semacam ini kita sebut dengan Ruang Sample dari suatu percobaan dan biasanya ditandai dengan notasi  S.

Contoh, Misalkan ada sebuah balapan kuda yang diikuti oleh 7 ekor kuda.  Masing-masing kuda yang diberi nomor punggung 1 hingga 7, maka :

S = {  semua urutan dari  (1, 2, 3, 4, 5, 6, 7) }

Pemunculan urutan  (3,4,1,7,6,5,2) akan berarti bahwa, kuda dengan nomor punggung 3 akan datang paling dulu, baru kemudian disusul oleh kuda nomor 4 dan seterusnya.

Semua himpunan bagian A dari Ruang Sampel disebut sebagai kejadian (event). Karena itu, sebuah kejadian adalah sebuah kumpulan yang mengandung peristiwa yang mungkin muncul dalam suatu percobaan. Jika peristiwa kejadian yang muncul dalam percobaan itu terdapat di dalam A, kita katakan bahwa  kejadian A terjadi.

Contoh : A = { semua kejadian di S yang didahului oleh 5 }

Maka A adalah semua peristiwa, dimana kuda nomor 5 yang masuk finish paling dulu.

Untuk sembarang kejadian A dan B, misalkan kita menentukan kejadian baru \(A\cup B\)  , yang disebut juga union/gabungan A dan B, gabungan ini mengandung semua kejadian yang mungkin muncul yang mungkin saja berada di dalam A atau di dalam B atau berada dikeduanya A dan B. Sejalan dengan hal tersebut, kita tentukan kejadian, AB, yang disebut sebagai irisan/ intersection dari A dan B, dimana kejadian AB terjadi jika A dan B juga terjadi. Kita juga bisa menentukan gabungan dan irisan untuk lebih dari 2(dua) kejadian. Gabungan dari kejadian-kejadian \(A_1, \cdots , A_n\) ditulis \(\bigcup_{i=1}^{n} = A_i\)  ditentukan memuat semua kejadian yang berada di sembarang \(A_i\). Begitu pula dengan irisan dari kejadian-kejadian \(A_1, \cdots , A_n\)  ditulis dengan \(A_1A_2 \cdots A_n\)  yang mengandung semua kejadian yang mungkin muncul (outcome) berada di semua \(A_i\).

Untuk semua kejadian A ada kejadian yang disebut \(A^c\)  , sering disebut sebagai komplemen dari A. mengandung semua kejadian di ruang sample S tapi tidak berada di A. Karena itu, \(A^c\) terjadi jika dan hanya jika tidak terjadi. Karena kejadian yang mungkin muncul haruslah berada di ruang sample S, akibatnya \(S^c\) tidak mengandung kejadian apapun, karenanya tidak muncul apapun. Kita sebut \(S^c\) himpunan null dan ditulis dengan \small \inline \o  . Jika \small \inline AB =\o, dikatakan bahwa A dan B mutualy exclusive

1 2