metoda prosedur berurutan eka - likmi

Media Informatika Vol. 5 No. 2 (2006)

43

METODA PROSEDUR BERURUTAN LAW DAN CARSON

Ekabrata Yudhistyra

Sekolah Tinggi Manajemen Informatika dan Komputer LIKMI

Jl. Ir. H. Juanda 96 Bandung 40132

Abstract Kesulitan dalam menggunakan metoda replikasi dan metoda rata-rata batch pada simulasi komputer adalah pada penentuan ukuran sampel yang dibutuhkan untuk memperoleh cakupan interval kepercayaan yang diinginkan, sehingga deorang simulator sukar mengetahui cakupan sebenarnya dari interval kepercayaan yang diinginkannya. Dalam makalah ini ditunjukkan bahwa metoda prosedur berurutan yang dikembangkan oleh Law dan Carson dapat secara otomatis memperbesar ukuran sampel awal sampai diperoleh cakupan interval kepercayaan yang mendekati/ sama dengan cakupan yang diinginkan dengan memberikan nilai penghenti (stopping value=c) tertentu (umumnya ≤ 0,4) dan juga presisi relatif γ yang diinginkan. Key Word : prosedur, berurutan, Law & Carson

1. LANDASAN TEORI

Metoda rata-rata batch pada simulasi komputer dapat memberikan hasil yang

cukup baik bila ukuran batch (m) dibuat cukup besar. Namun ukuran batch yang cukup

besar bagi suatu sistem yang disimulasikan belum tentu cukup besar bagi sistem yang lain.

Sumber kesalahan terbesar untuk membentuk 90% interval kepercayaan bagi μ

adalah adanya bias pada ),(ˆ mkσ jika ukuran batch (m) terlalu kecil.

Hal ini sebenarnya mudah dimengerti, sebab:

])([)]}([ˆ{2

2

nnsEnXE =σ

)]([1

1)](/[ 2 nXn

nan σ−

−=

dengan cara yang sama seperti pada pembuktian rumus di atas, dapat dibuktikan

)]},([ˆ{ 2 mkXE σ atau )],(ˆ[ 2 mkE σ berbentuk:

)],([),()]},([ˆ{ 22 mkXmkbmkXE σσ =

44 Ekabrata Yudhistyra/ Metoda Prosedur Berurutan Law dan Carson

dengan:

1

1)]}()/1(21/[{),(

1

1

−

−−+=

∑−

=

k

mkikmkb

k

iiρ

Untuk m → ∞ , maka 0)( →miρ sehingga b(k,m) → 1.

Dengan demikian:

)],([)]},([ˆ{ 22 mkXmkXE σσ →

Sehingga )],([ˆ 2 mkXσ dapat dianggap sebagai estimator yang tidak bias terhadap

)],([2 mkXσ untuk ∞→m .

Dengan demikian bila kita dapat menemukan suatu cara untuk mengetahui pada m

yang berapa besarnya 0)( →miρ , maka ukuran sampel m dari batch tersebut dapat kita

gunakan sebagai pendekatan untuk menghitung )],([ˆ mkXσ yang akan digunakan untuk

membentuk 90% interval kepercayaan bagi μ .

Salah satu pendekatan yang ada dalam literatur adalah yang dilakukan oleh Gross

dan Harris . Mereka menetapkan suatu banyak batch tertentu (k) dan kemudian

memperbesar ukuran batch (m) sehingga estimasi bagi koefisien korelasi lag-1 antara

)(mX j (j=1,2,…,k) cukup kecil, katakanlah kurang dari 0.05. Kesulitan dalam

menggunakan pendekatan ini adalah bahwa estimator bagi koefisien korelasi umumnya

bias dan untuk nilai k yang kecil memiliki varian yang besar.

Misalkan untuk proses stokastik }1,{ ≥iDi untuk antrian M/M/1 dengan ρ =0.9,

dimana iD adalah waktu tunggu langganan ke-I dalam antrian.

Law melakukan 100 kali simulasi yang independen untuk proses ini, masing-

masing dengan ukuran sampel 14400 pengamatan. Masing-masing simulasi dibagi atas 30

batch yang panjangnya 480. Jadi k = 30 dan m = 480. Koefisien korelasi lag-1, )480(1ρ

diestimasi dengan Jackknifed estimator )480,30(~1ρ yang didefinisikan sebagai:

2/)],2/(ˆ),2/(ˆ[),(ˆ2),(~ 21

1111 mkmkmkmk ρρρρ +−= ……. (1)

dengan:

∑

∑

=

−

=

+

−

−−= k

jj

k

jjj

mkXmX

mkXmXmkXmXmk

1

2

1

11

1

)],()([

)],()()][,()([),(ρ̂ ……. (2)

Media Informatika Vol. 5 No. 2 (2006) 45

dan:

),2/(ˆ 11 mkρ = estimator koefisien korelasi lag-1 yang biasa untuk n/2 batch yang pertama

),2/(ˆ 21 mkρ = estimator koefisien korelasi lag-1 yang biasa untuk n/2 batch yang terakhir

Dari 100 kali simulasi tersebut diperoleh hasil bahwa:

- 23 buah 1~ρ (30,480) lebih kecil dari 0.05

- 22 buah lebih kecil dari 0.

Namun dapat ditunjukkan oleh Daley bahwa 1ρ (480) seharusnya bernilai 0.284 dan

b(30,480) = 0.597.

Penelitian empiris selanjutnya yang banyak dilakukan oleh para ahli simulasi

menunjukkan bahwa metoda prosedur berurutan yang didasarkan pada estimasi langsung

terhadap nilai )(1 mρ untuk sebarang banyak batch yang jumlahnya kecil akan

memberikan interval kepercayaan dengan cakupan yang lebih rendah daripada yang

diinginkan . Law dan Carson juga menemukan bahwa untuk suatu sistem tertentu, banyak

batch (k), haruslah sebesar 400 agar diperoleh estimasi yang cukup teliti bagi )(1 mρ .

Namun tentu saja untuk ukuran batch yang cukup besar jumlah pengamatan yang

diperlukan menjadi bertambah banyak.

Law dan Carson kemudian menempuh cara lain.

Mereka mengusulkan menggunakan batch sebanyak lk )2( ≥l yang masing-

masing panjangnya m untuk memperkirakan apakah batch yang banyaknya k dengan

ukuran batch = lm, mendekati saling tidak berkolerasi.

Tentu saja untuk melakukan hal ini mereka perlu meneliti hubungan antara )(1 mρ

dan )(1 lmρ . Dalam penelitian yang mereka lakukan, mereka mengamati 34 proses

stokastik dengan nilai )(1 mρ dan b(k,m) yang dapat dihitung secara analitik.

Proses stokastik yang mereka pelajari adalah:

1. }1,{ ≥iDi untuk sistem antrian M/M/1 dengan ρ = 0.5, 0.8 dan 0.9. Lihat Daley.

2. ,{ iE i > 1} untuk suatu sistem inventory (s,S), dengan iE adalah pengeluaran pada

periode ke-i. Lihat Law.

3. Tiga puluh buah model deretan waktu (time series) AR(1), AR(2) dan ARMA(1,1)

(lihat Box dan Jenkins, hal 46) dengan parameter yang dipilih untuk seluruh interval

nilai yang mungkin.


Dari 34 proses stokastik tersebut, mereka menemukan adanya 3 sifat utama dari

)(1 mρ sebagai fungsi dari m.

Ketiga hubungan )(1 mρ sebagai fungsi dari m tersebut dapat dilihat pada gambar

berikut:

Proses Stokastik Jenis-1

Proses Skotastik Jenis-2

Proses Stokastik Jenis-3


Untuk proses stokastik yang termasuk dalam jenis yang pertama koefisien korelasi

lag-1 ( )(1 mρ ) menurun drastis menuju nol. Sebagai contoh jika kita pilih 1 = 10 dan k =

40, maka untuk suatu nilai m tertentu, jika )(1 mρ < 0.4, maka )10(1 mρ < 0.05 dan 0.9 <

b(40,10m) < 1. Ini ternyata berlaku untuk semua proses stokastik yang termasuk dalam

jenis yang pertama.

Sistem antrian M/M/1 termasuk dalam jenis yang pertama ini, hal ini dapat dilihat

dari nilai )(~1 mρ dan b(k,m) untuk berbagai nilai m dengan ukuran batch (k) = 400 pada

tabel 1. tampak bahwa bila )(~1 mρ → 0, maka nilai b(k,m) → 1. Grafik untuk data-data

pada tabel 1 tersebut dapat dilihat pada grafik-1 dan grafik-2.

Untuk proses stokastik jenis kedua, )(1 mρ berubah arah (naik/turun) dan kemudian

menurun drastis menuju nol, seperti pada proses stokastik jenis pertama. Kita ambil

contoh untuk 1 = 10 dan k = 40. Jika untuk suatu nilai m tertentu, )(1 mρ < 0.4 dan

)'(1 mρ menurun untuk mm ≥' maka 05.0)10(1 <mρ dan 0.9 < b(40,10m) < 1. Ini berlaku

untuk semua proses skotastik yang termasuk dalam jenis kedua, dengan sebuah

perkecualian dimana )(1 mρ < 0.4 dan )'(1 mρ menurun untuk mm ≥' namun memberikan

059.0)10(1 =mρ dan b(40,10m) = 0.894. Beberapa model deret waktu (time series)

termasuk dalam jenis kedua ini.

Untuk proses stokastik jenis ketiga, )(1 mρ < 0 dan b(40,10m) > 1 untuk semua m.

Dalam kasus ini )10( mX j mungkin berkorelasi, tetapi menurut penelitian empiris yang

telah dilakukan selama ini oleh Law dan Carson, cakupan dari interval


KOEFISIEN KORELASI LAG-1 DAN NILAI B SISTEM ANTRIAN M/M/1 DENGAN

ρ = 0.5

Perhitungan dirata-ratakan sebanyak : 50 kali

Banyak batch : 400 buah

Tabel-1


GRAFIK KOEFISIEN KORELASI LAG-1

Grafik-1

GRAFIK HUBUNGAN KOEFISIEN KORELASI

Grafik-2

kepercayaannya masih cukup besar. Proses inventory/sistem persediaan (s,S) termasuk

dalam jenis ketiga ini.


Law dan Carson tidak menyatakan bahwa hanya ada 3 macam karakteristik )(1 mρ

terhadap m, jadi mungkin saja ada suatu proses stokastik dengan karakteristik )(1 mρ yang

berbeda dari ketiga macam yang telah disebutkan di atas. Pada beberapa model deret

waktu yang mereka pelajari, ternyata ada )(1 mρ yang bernilai positip dan ada yang

negatip. Namun jika untuk suatu m tertentu berlaku:

- Bila 0 < )(1 mρ < 0.4, maka )10(1 mρ < 0.050 (sesuai dengan proses stokastik jenis

pertama).

- Bila )(1 mρ < 0, maka b(40,10m) < 1 (sesuai dengan proses stokastik jenis ketiga).

Pembahasan di atas didasarkan pada )(1 mρ yang diketahui, padahal )(1 mρ harus

diestimasi. Untuk itu kita gunakan estimator Jackknifed yang telah didefinisikan

sebelumnya. Kita gunakan estimator Jackknifed ),(~1 mkρ sebab estimator ini lebih tidak

bias dibandingkan estimator ),(ˆ1 mkρ untuk mengestimasi )(1 mρ (lihat Miller [13]).

2. ALGORITMA PROSEDUR BERURUTAN

Sekarang marilah kita ikuti langkah-lagkah daripada algoritma prosedur berurutan

Law dan Carson :

Langkah 1: Tetapkan suatu nilai l,k, 10 ,nn (lk genap, lk/2 genap, 0n < 1n < 10 ,2 nn dan

02n masing-masing dapat dibagi lk), nilai penghenti c > 0 dan presisi

relatif γ > 0.

Tetapkan nilai i = 1, dan kumpulkan in pengamatan.

Sebagai contoh:

Ambillah l = 10, k = 40, 0n = 600, 1n = 800, c = 0.4 serta γ = 0.15.

Langkah 2 : Bagilah in pengamatan ke dalam lk batch dengan ukuran m = in /lk. Hitung

),(~1 mlkρ dari )(mX j (j = 1,2,...,lk). Jika ),(~

1 mlkρ ≥ c (lihat catatan 1),

pergi ke langkah 5. Jika ),(~1 mlkρ ≤ 0 (lihat catatan 2), pergi ke langkah 4.

Jika tidak, pergi ke langkah 3.

Langkah 3 : Bagilah in menjadi lk/2 batch dengan ukuran 2m. Hitung )2,2/(~1 mlkρ

dari )2( mX j (j = 1,2,...,lk/2), (Lihat catatan 3). Jika )2,2/(~1 mlkρ <

),(~1 mlkρ (lihat catatan 4), pergi ke langkah 4. Jika tidak, pergi ke langkah

5.


Langkah 4 : Bagilah in menjadi k batch berukuran lm. Hitung ),( lmkX dan

2/1,1 αδ −−= kt )],([ˆ 2 lmkXσ dari )(lmX j (j = 1,2,...,k). (Lihat catatan 3).

Jika δ /| ),( lmkX | γ≤ (lihat catatan 5), gunakanlah ),( lmkX dan δ untuk

membentuk 100 (1-α )% interval kepercayaan bagi μ dengan rumus (1)

pada Bab V untuk 1.0=α , kemudian selesai. Jika tidak, pergi ke langkah

5.

Langkah 5 : Ganti i dengan i+1, in = 22 −in (lihat catatan 6), kumpulkan )( 1−− ii nn

pengamatan lagi yang dibutuhkan, kemudian kembali ke langkah 2.

Catatan:

1. Pemeriksaan ini untuk proses stokastik jenis pertama.

2. Pemeriksaan ini untuk proses stokastik jenis ketiga.

3. Sejumlah )(mX j dapat dirata-ratakan untuk menghitung )2( mX j atau )(lmX j .

4. Pemeriksaan ini untuk proses stokastik jenis kedua. Kita periksa apakah )'(1 mρ

menurun untuk mm ≥' dengan memeriksa apakah )2(1 mρ < )(1 mρ .

5. Pemeriksaan tambahan ini memungkinkan kita untuk memperoleh presisi relatif

interval kepercayaan (setengah panjang interval kepercayaan dibagi estimatornya),

lebih kecil daripada nilai γ tertentu.

6. Ukuran sampel adalah ,...4,4,2,2, 10101 nnnnn Sehingga ukuran sampel selalu

dikalikan 2 setiap kali iterasi dilakukan.

3. HASIL PERCOBAAN

Untuk sistem antrian M/M/1 dengan 5.=ρ , diperoleh hasil yang berbeda-beda

tergantung pada nilai c dan γ . Hasil selengkapnya dapat kita lihat pada tabel-tabel 2, 3

dan 4. Jika hasil tersebut kita rangkumkan, diperoleh tabel berikut:

c γ Ukuran sampel

rata-rata

Ukuran batch

rata-rata

Nilai presisi

relatif rata-rata

90% interval

kepercayaan bagi ρ̂

0.8

0.4

0.4

0.15

0.30

0.15

3336

3448

3984

84

87

100

0.1323557

0.1316105

0.1278009

0.79 ± 0.07

0.85 ± 0.06

0.91 ± 0.05


Perhatikan bahwa untuk nilai c = 0.8, γ = 0.15, 90% interval kepercayaan bagi ρ̂

(proporsi banyak 90% interval kepercayaan yang mengandung waktu tunggu analitik d =

0.5) masih belum mencakup 0.9 (90%).

Namun untuk nilai c = 0.4 dan γ = 0.3 atau γ = 0.15, 90% interval kepercayaan

bagi ρ̂ sudah mencakup 0.9 (90%). Jadi hasilnya sudah baik.

DIAGRAM ALIR METODA BERURUTAN LAW DAN CARSON


Keterangan : BB = Banyak Batch

UB = Ukuran Batch

Catatan : Keterangan mengenai arti variabel-variabrl yang lainnya dapat dilihat

pada algoritma metoda prosedur pada halaman sebelumnya.


METODA BERURUTAN

Banyak batch tiap simulasi : 40

Batas nilai penghenti (c) : 0.8

Batas presisi relatif (γ ) : 0.15

Tabel-2a





(lanjutan) Tabel-2b





(lanjutan) Tabel-2c

Proporsi banyak interval yang mengandung waktu tunggu rata-rata yang dihitung secara

analitik (=0.5) adalah : 79%

90% interval kepercayaan bagi proporsi tersebut : 0.79 ± 0.07

Banyak pengamatan (ukuran sampel) rata-rata : 3336

Banyak pengamatan (ukuran) batch rata-rata : 84

Nilai presisi relatif rata-rata adalah : 0.1323557


METODA BERURUTAN




Tabel-3a





(lanjutan) Tabel-3b





(lanjutan) Tabel-3c








METODA BERURUTAN




Tabel-4a





(lanjutan) Tabel-4b





(lanjutan) Tabel-4c







4. DAFTAR PUSTAKA

1. Box, G.E.P dan G.M. Jenkins, Time Series Analysis: Forecasting and Control,

Holden-Day, San Fransisco, 1970.

2. Daley, D.J., The Serial Correlation Coefficients of Waiting Times in a Stationary

Single Server Queue, J. Austral. Math. Soc. 8, 683-699, 1968.

3. Gross, D. Dan C.M. Harris, Fundamentals of Queueing Theory, Wiley, New York,

1974.

4. Law, Averill M., Confidence Intervals in Discrete Event Simulation: A Comparison of

Replication and Batch Means, Naval Research Logistic Quart. 24, 667-678, 1977.

5. Law, Averill M. Dan John S. Carson, A Sequential Procedure For Determining The

Length of A Steady-State Simulation, Technical Report No. 77-12, Department of

Industrial Engineering, University of Wisconsin, Madison, 1978.

6. Miller, R.G., The Jackknife – A Review, Biometrika 61, 1-15, 1974

metoda prosedur berurutan eka - likmi

Documents