Bab 2 LANDASAN TEORI. 2.1 Pengantar Proses Stokastik

Bab 2 LANDASAN TEORI Pada bab ini akan diberikan penjelasan singkat mengenai pengantar proses stokastik dan rantai Markov, yang akan digunakan untuk analisis pada bab-bab selanjutnya.

2.1

Pengantar Proses Stokastik

Proses stokastik adalah suatu barisan kejadian yang memenuhi hukum-hukum peluang. Proses stokastik banyak digunakan untuk memodelkan evolusi suatu sistem yang memuat suatu ketidakpastian atau sistem yang dijalankan pada suatu lingkungan yang tak dapat diduga, dimana model deterministik tidak lagi cocok untuk menganalisis sistem. Secara formal, proses stokastik X = {X(t), t ∈ T } didefinisikan sebagai suatu barisan peubah acak, yaitu untuk setiap t ∈ T terdapat peubah acak X(t). Seringkali indeks t diinterpretasikan sebagai waktu, karena banyak sekali proses stokastik yang terjadi pada suatu selang waktu. Nilai peubah acak X(t) dinamakan keadaan pada saat t. Himpunan T disebut ruang parameter atau ruang indeks dari proses stokastik X dan himpunan semua nilai X(t) yang mungkin dinamakan ruang keadaan dari X. Setiap realisasi dari X dinamakan sample path dari X. Proses-proses stokastik dapat diklasifikasikan berdasarkan jenis ruang parameternya

7

BAB 2. LANDASAN TEORI

8

(diskrit atau kontinu), ruang keadaannya (diskrit atau kontinu), dan kaitan antara peubah-peubah acak yang membentuk proses stokastik tersebut. Yang paling sering dilihat adalah klasifikasi proses-proses stokastik berdasarkan jenis ruang parameter dan ruang keadaannya.

2.2

Rantai Markov

Misalkan proses stokastik {Xn , n = 0, 1, · · · } mempunyai ruang keadaan berupa himpunan berhingga atau himpunan terbilang. Secara umum, ruang keadaan ini dapat dinotasikan sebagai himpunan {0, 1, · · · }. Jika pada waktu n proses tersebut berada di keadaan i, maka kejadian ini dituliskan sebagai Xn = i . Proses stokastik dinamakan rantai Markov jika untuk tiap n = 0, 1, 2, · · · , berlaku P {Xn+1 = j|X0 = i0 , · · · , Xn−1 = in−1 , Xn = i} = P {Xn+1 = j|Xn = i}

(2.2.1)

untuk semua i0 , · · · , in−1 , i, j dan semua n ≥ 0 . Untuk selanjutnya, persamaan (2.2.1) disebut sifat Markov.

2.2.1

Matriks Peluang Transisi

Misalkan proses stokastik {Xn , n = 0, 1, · · · } adalah suatu rantai Markov. Matriks peluang transisi (satu langkah) dari {Xn , n = 0, 1, · · · }, dinotasikan P, adalah suatu matriks dengan elemen ke (i, j)nya adalah  p p  00 01   p10 p11 P=   p20 p21  .. .. . .

pij . Jadi,  p02 · · · p12 p22 .. .

  ···  .  ···   .. .

(2.2.2)

Elemen-elemen dari matriks P bernilai tak negatif (pij ≥ 0 untuk i, j ≥ 0) dan jumlah elemen-elemen pada satu baris di matriks peluang transisi ini haruslah sama P dengan satu ( ∞ j=0 pij = 1, i = 0, 1, 2, · · · ). Matriks transisi ini digunakan dalam


9

menganalisis kelakuan rantai Markov dalam beberapa langkah ke depan dan juga setelah proses berjalan lama (long run behaviour dari rantai Markov).

2.2.2

Persamaan Chapman-Kolmogorov

Misalkan pnij menyatakan peluang proses berada pada keadaan i akan berada pada keadaan j setelah proses mengalami n transisi. Jadi, pnij dapat dituliskan pnij = P {Xn+m = j|Xm = i}, m ≥ 0, i, j ≥ 0.

(2.2.3)

Dapat dilihat bahwa p1ij = pij . Selanjutnya, dengan menggunakan law of total probability, untuk smua n, m ≥ 0, dan semua i, j ≥ 0, pn+m =P {Xn+m = j|X0 = i} ij = =

∞ X k=0 ∞ X

P {Xn+m = j|Xn = k, X0 = i}P {Xn = k|X0 = i}

(2.2.4)

n pm kj pik .

k=0

Persamaan (2.2.4), yang dikenal dengan nama persamaan Chapman-Kolmogorov, akan memberikan suatu metode untuk menghitung peluang transisi dalam n langkah. Misalkan P(n) adalah matriks dengan elemen-elemennya merupakan peluang transisi dalam n langkah (pnij ). Dari persamaan (2.2.4) diperoleh P(n) = P(n−1+1) = P(n−1) P(1) = P(n−2) P(1) P(1) = · · · = Pn . Dengan kata lain, matriks peluang transisi dalam n langkah dapat diperoleh dengan mengalikan matriks peluang transisi satu langkah P sebanyak n kali. Suatu rantai Markov yang pada awalnya berada pada keadaan i setelah satu transisi akan berada pada keadaan j dengan peluang yang diberikan oleh suku (i, j) dari matriks P. Secara umum, jika kita definisikan vektor baris π 0 = (π10 , π20 , · · · ),


10

dengan πi0 menyatakan peluang rantai Markov berada di keadaan i pada permulaan proses, maka peluang setelah satu transisi rantai Markov tersebut berada di keadaan j (dengan notasi πj1 ) diberikan oleh πj1

=

∞ X

πk0 pki , i = 0, 1, · · · .

k=0

Definisikan π n = (π1n , π2n , · · · ), n = 1, 2, · · · sebagai vektor distribusi peluang dari keadaan rantai Markov setelah n transisi. Dengan menggunakan persamaan Chapman-Kolmogorov di atas diperoleh π n = π 0 Pn .

2.2.3

(2.2.5)

Distribusi Peluang Stasioner

Suatu distribusi peluang {πj , j ≥ 0} dikatakan distribusi stasioner dari suatu rantai Markov dengan matriks peluang transisi P = (pij ) jika πj =

∞ X

πi pij , j ≥ 0.

(2.2.6)

i=0

Distribusi peluang stasioner {πj , j ≥ 0} merupakan solusi tunggal dari sistem persamaan πj = X

∞ X

πi pij

i=0

πj = 1.

j

Jika keadaan dari suatu rantai Markov dengan matriks peluang transisi P = (pij ) mempunyai distribusi peluang P {X0 = j}, j ≥ 0, atau dengan kata lain sama dengan distribusi stasionernya, maka P {X1 = j} =

∞ X

P {X1 = j|X0 = i}P {X0 = i}

i=0

=

∞ X k=0

πi pij = πj .


11

Secara induksi, dapat dibuktikan bahwa P {Xn = j} =

∞ X

P {Xn = j|Xn−1 = i}P {Xn−1 = i}

i=0

=

∞ X

πi pij = πj .

k=0

Jadi, jika distribusi peluang dari keadaan awal suatu rantai Markov adalah sama dengan distribusi stasionernya, maka Xn akan mempunyai distribusi peluang yang sama untuk semua n.

2.3

Teori Pengambilan Keputusan Markov

Misalkan suatu sistem dikontrol secara berkala agar tetap dalam kondisi yang baik dengan cara melakukan pemeriksaan. Misalkan pula sistem tersebut diperiksa pada waktu n = 0, 1, 2, · · · dengan jarak antarwaktu pemeriksaan sama. Pada setiap pemeriksaan, sistem tersebut diklasifikasikan ke dalam suatu keadaan dari sejumlah keadaan yang mungkin kemudian dipilih suatu tindakan tertentu untuk memperbaiki keadaan sistem tersebut. Misalkan I menyatakan ruang keadaan yang mungkin ditemukan sistem saat pemeriksaan dan A(i) menyatakan himpunan tindakan yang mungkin bisa diambil pada saat sistem dalam keadaan i, i ∈ I (dalam hal ini, i dan A(i) berhingga). Pengambilan suatu tindakan diatur oleh suatu kebijakan stasioner, sebut R. Suatu kebijakan staasioner R merupakan suatu peraturan yang menyatakan tindakan apa yang harus dilakukan jika pada waktu pemeriksaan sistem berada dalam suatu keadaan tertentu. Misalkan tindakan a diambil pada keadaan i, maka akan dimiliki aturan Ri = {a}, a ∈ A(i), artinya jika sistem berada dalam keadaan i maka tindakan a harus dilakukan. Sebagai konsekuensi dari pengambilan tindakan tersebut adalah munculnya biaya, yaitu ci (a) yang merupakan ekspektasi biaya yang diperlukan apabila tindakan a dilakukan pada keadaan i. Pada pengambilan keputusan berikutnya,


12

sistem akan berada dalam keadaan j dengan peluang pij (a) dimana X

pij (a) = 1, i ∈ I.

j∈I

Sistem yang dikontrol ini dinamakan Model Keputusan Markov bila sifat Markov (persamaan (2.2.1)) dipenuhi.

2.3.1

Kebijakan Stasioner

Definisikan Xn sebagai keadaan sistem pada waktu keputusan ke-n, untuk n = 0, 1, 2, · · · . Peluang transisi satu langkah di bawah kebijakan stasioner Ri yang diberikan adalah P {Xn+1 = j|Xn = i} = pij (Ri ). Jadi, dibawah kebijakan stasioner Ri yang diberikan, proses stokastik {Xn , n = 0, 1, · · · } merupakan rantai Markov dan peluang transisi satu langkah pij (Ri ). Rantai Markov ini akan menimbulkan biaya sebesar ci (Ri ) apabila tindakan Ri dilakukan pada saat keadaan i. Peluang transisi n langkah dari rantai Markov {Xn , n = 0, 1, · · · } adalah (n)

pij (R) = P {Xn = j|X0 = i}, i, j ∈ I, n = 1, 2, 3, · · · (1)

dengan pij (R) = pij (Ri ) dan memenuhi (n)

pij (R) =

X

(n−1)

pik

(R)pkj (Rk ).

(2.3.1)

k∈I

Setiap kebijakan stasioner biasanya memiliki sifat unichain, yaitu untuk setiap kebijakan stasioner R, terdapat suatu keadaan r (mungkin bergantung pada R) yang dapat dicapai dari sebarang keadaan di bawah kebijakan R. Dengan demikian, untuk setiap kebijakan stasioner R m

1 X (n) pij (R) m→∞ m n=1

πj (R) = lim

ada dan tidak bergantung pada keadaan awal X0 = i.

(2.3.2)


13

Distribusi stasioner {πj , j ∈ I} merupakan solusi tunggal dari sistem persamaan berikut.

X

πj (R) =

pkj (Rk )πk (R)

k∈I

X

πj (R) = 1.

(2.3.3)

j∈I

2.3.2

Biaya Rata-rata dari Kebijakan Stasioner yang Digunakan

Misalkan Vn (i, R) menyatakan ekspektasi biaya total pada n waktu keputusan pertama bila X0 = i (keadaan awalnya adalah i) dan kebijakan R digunakan. Ekspektasi biaya pada waktu keputusan ke-t dengan X0 = i dan kebijakan R digunakan adalah

X

(t)

pij (R)cj (Rj ).

j∈I

Dengan demikian, Vn (i, R) dapat dituliskan sebagai berikut. Vn (i, R) =

n−1 X X

(t)

pij (R)cj (Rj )

(2.3.4)

t=0 j∈I (0)

(0)

dengan pij (R) = 1 untuk j = i dan pij (R) = 0 untuk j 6= i. Definisikan fungsi biaya rata-rata, gi (R), sebagai 1 Vn (i, R), i ∈ I. n→∞ n

gi (R) = lim

(2.3.5)

Karena limit di atas ada, maka biaya rata-rata tidak bergantung pada keadaan awal sistem sehingga dapat dituliskan gi (R) = g(R), i ∈ I.


14

g(R) menyatakan biaya rata-rata jangka panjang per satuan waktu. 1 Vn (i, R), i ∈ I n→∞ n n−1 1 X X (t) = lim pij (R)cj (Rj ) n→∞ n t=0 j∈I

g(R) = lim

=

X j∈I

=

X

n−1

1 X (t) cj (Rj ) lim pij (R) n→∞ n t=0 cj (Rj )πj (R).

j∈I

Jadi, g(R) =

X

cj (Rj )πj (R).

(2.3.6)

j∈I

Dari persamaan (2.3.6) dapat dilihat bahwa g(R) memiliki hubungan linier dengan πj (R), artinya, semakin besar peluang suatu sistem berada di keadaan j dengan kebijakan R digunakan, maka akan semakin besar biaya rata-rata yang harus dikeluarkan untuk melakukan kebijakan R tersebut. Jadi, masalah pengambilan keputusan Markov adalah meminimumkan biaya ratarata jangka panjang per satuan waktu (g(R)) terhadap kendala-kendala yang ada (yaitu sifat-sifat dari distribusi peluang stasioner yang dituliskan pada persamaan (2.3.3).

2.3.3

Program Linier dan Metode Simpleks

Program linier merupakan salah satu alat untuk menyelesaikan masalah optimasi (maksimasi atau minimasi). Perumusan masalah program linier beserta pemecahannya secara sistematis baru dimulai pada tahun 1947 ketika George B. Dantzig merancang suatu metode yang dikenal dengan nama metode simpleks untuk keperluan angkatan udara Amerika Serikat. Program linier merupakan suatu program matematika yang dapat digunakan untuk mengidentifikasi suatu titik ekstrim (maksimum atau minimum) pada suatu


15

fungsi f (X1 , X2 , . . .) yang selanjutnya memenuhi suatu himpunan kendala, misalnya h(X1 , X2 , . . .) ≥ 0. Fungsi f dinamakan fungsi tujuan atau fungsi objektif, sedangkan fungsi g dinamakan kendala. Fungsi f dan fungsi h harus bersifat linier. Suatu solusi dikatakan fisibel apabila solusi tersebut memenuhi himpunan kendala. Suatu solusi dikatakan optimal apabila solusi tersebut fisible dan menghasilkan nilai maksimum atau minimum pada fungsi objektifnya. Suatu masalah optimasi dapat memiliki lebih dari satu solusi yang menghasilkan nilai optimal. Bentuk baku dari program linier untuk meminimumkan fungsi objektif dapat dituliskan sebagai berikut. min terhadap

c1 x1 + c2 x2 + · · · + cn xn a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. . am1 x1 + am2 x2 + · · · + amn xn = bm x1 ≥ 0, x2 ≥ 0, · · · , xn ≥ 0.

Dalam bentuk vektor, bentuk baku dari program linier dapat dituliskan sebagai berikut. min terhadap

cT x Ax = b x ≥ 0.

Metode simpleks merupakan suatu metode yang dapat digunakan dalam menyelesaikan masalah optimasi. Dalam menyelesaikan suatu masalah optimasi dengan menggunakan metode simpleks, beberapa kriteria berikut harus terpenuhi. 1. Seluruh pembatas (kendala) berbentuk persamaan (=) • Jika pembatas bertanda ≤ atau ≥ dapat dijadikan pembatas yang bertanda = dengan cara menambahkan atau mengurangkan dengan suatu


16

variabel (dinamakan slack variable). Jika tanda pada pembatas tersebut adalah ≤ maka pembatas tersebut ditambahkan dengan slack S1 > 0 dan jika pembatas tersebut bertanda ≥ maka pembatas tersebut dikurangkan dengan slack S2 > 0. Contoh : X1 + 2X2 ≤ 6 −→ X1 + 2X2 + S1 = 6 X1 + 2X2 ≥ 6 −→ X1 + 2X2 − S2 = 6 • Ruas kanan dari persamaan pada suatu pembatas (kendala) dapat dijadikan bilangan non negatif jika kedua ruas dikalikan dengan -1. • Arah ketidaksamaan dapat berubah jika kedua ruas dikalikan dengan -1. • Pembatas (kendala) dengan ketidaksamaan yang ruas kirinya berada dalam tanda mutlak dapat diubah menjadi dua ketidaksamaan. Contoh : |a1 X1 + a2 X2 | ≤ b → a1 X1 + a2 X2 ≤ b atau a1 X1 + a2 X2 ≥ −b |a1 X1 + a2 X2 | ≥ b → a1 X1 + a2 X2 ≥ b atau a1 X1 + a2 X2 ≤ −b 2. Seluruh variabel merupakan variabel non negatif. 3. Fungsi objektif (fungsi tujuan) berupa maksimum atau minimum. Meskipun demikian, kadang-kadang masih diperlukan perubahan dari satu bentuk ke bentuk lannya (misalnya, dari maksimum ke minimum dan sebaliknya). Solusi yang diperoleh disebut sebagai solusi basis. Jika suatu solusi basis dapat memenuhi pembatas-pembatas (kendala-kendala) non negatif, maka solusi tersebut disebut sebagai solusi basis fisibel. Variabel-variabel yang dinolkan disebut sebagai variabel non basis dan yang lainnya disebut variabel basis. Jumlah iterasi maksimum dalam metode simpleks adalah sama dengan jumlah maksimum solusi basis dalam bentuk standar (bentuk yang memenuhi kriteria-kriteria di atas). Dengan demikian, jumlah iterasi pada metode simpleks ini tidak akan lebih dari : n = Cm

n! (n−m)!m!

persamaan.

dengan n menyatakan jumlah variabel dan m menyatakan jumlah


17

Berikut ini algoritma simpleks untuk kasus maksimasi. 1. Konversikan masalah optimasi ke dalam bentuk formula yang standar. 2. Cari solusi basis fisibel dengan cara menambahakan slack variabel ke dalam ketidaksamaan (≤/≥) agar menjadi persamaan (=). 3. Jika seluruh variabel non basis pada fungsi objektif memiliki nilai yang positif maka solusi basis fisibel sudah optimal. Jika pada baris fungsi objektif masih terdapat variabel dengan koefisien yang bernilai negatif, pilih salah satu variabel yang mempunyai koefisien paling kecil pada baris tersebut. Variabel ini akan masuk status variabel basis, karena itu variabel ini disebut entering variable (EV). 4. Hitung rasio dari ruas kanan (koefisien EV) pada setiap baris pembatas (kendala) dimana EV-nya mempunyai koefisien positif. Variabel basis pada baris pembatas (kendala) dengan rasio positif terkecil akan berubah status menjadi variabel non basis. Variabel ini kemudian disebut sebagai leaving variable (LV). 5. Lakukan operasi baris elementer untuk membuat operasi EVpada baris dengan rasio positif terkecil ini menjadi berharga 1 dan berharga 0 pada baris-baris yang lainnya. 6. Kembali ke langkah 3. Catatan : Bila ditemukan lebih dari satu baris yang mempunyai rasio positif terkecil, maka pilihlah sembarang karena tidak akan mempengaruhi hasil perhitungan. Berikut ini algoritma simpleks untuk kasus minimasi. 1. Ubahlah fungsi objektif dari fungsi minimasi menjadi fungsi maksimasi. 2. Modifikasi langkah ke-3 pada kasus maksimasi di atas menjadi : Jika seluruh variabel non basis pada baris fungsi objektif mempunyai koefisien


18

yang berharga non positif maka solusi basis fisibel sudah optimal. Jika baris pada fungsi objektif masih terdapat variabel dengan koefisien positif, pilihlah salah satu variabel yang berharga paling positif (paling besar) pada baris fungsi objektif untuk menjadi EV. Metode simpleks ini memungkinkan dilakukannya analisis sensitivitas pada masalah program linier. Analisis sensitivitas dilakukan untuk mengetahui seberapa sensitif solusi optimal untuk berubah apabila terdapat oerubahan pada nilai input untuk masalah program linier yang akan diselesaikan. Tinjau kembali masalah program linier pada halaman 36. A, x, dan cT dapat dipartisi menjadi : A=[B,N] x=(xB ,xN ), cT =(cTB ,cTN ) B menyatakan matriks basis dan N menyatakan matriks non basis. Masalah ini dapat dituliskan dalam bentuk tableau di bawah ini. xB

xN

B

N

b

cTB

cTN

0

Dengan operasi baris elementer (OBE) diperoleh : xB

xN

I

B −1 N

B −1 b

0

cTN − cTB B −1 N

−cTB B −1 b

Solusi basis xB kan merupakan solusi optimal jika vektor reduced cost cTN − cTB B −1 N semua elemennya lebih besar atau sama dengan nol. Analisis sensitivitas bermanfaat untuk menghindari perhitungan ulang apabila terjadi perubahan nilai pada input masalah program linier. Untuk mengetahui apakah solusi awal (sebelum ada perubahan) masih optimal atau tidak, cukup melihat


19

apakah vektor reduced cost cTN − cTB B −1 N semua elemennya masih lebih besar atau sama dengan nol atau tidak.

2.3.4

Pengambilan Keputusan Markov dengan Pendekatan Program Linier

Masalah program linier pada pengambilan keputusan Markov adalah meminimumkan biaya rata-rata jangka panjang per satuan waktu (g(R)) terhadap kendala-kendala yang ada (yaitu sifat-sifat dari distribusi peluang stasioner yang dituliskan pada persamaan (2.3.3)). Dengan demikian, fungsi objektif dari program liniernya adalah biaya rata-rata jangka panjang per satuan waktu (g(R)), sedangkan kendalanya adalah sifat-sifat dari distribusi peluang stasioner yang dituliskan pada persamaan (2.3.3). Masalah program linier ini dapat dituliskan sebagai berikut. min

g(R) =

X

cj (Rj )πj (R)

j∈I

terhadap

πj (R) = X

X

pkj (Rk )πk (R)

k∈I

πj (R) = 1.

j∈I

Algoritma pengambilan keputusan Markov dengan pendekatan program linier adalah sebagai berikut. 1. Menyelesaikan masalah program linier dengan metode simpleks. 2. Pilih I0 := {i |

X

πi∗ (a) > 0}.

a∈A(i)

Untuk suatu i ∈ I0 , Ri∗ := a dengan πi∗ (a) > 0. 3. Jika I0 = I maka Ri = Ri∗ . 4. Jika I0 6= I, pilih i bukan ∈ I0 dan suatu action a ∈ A(i) dengan pij (a) > 0 untuk suatu j ∈ I0 . Selanjutnya, Ri∗ := a dan I0 := I0 ∪ {i}. Ulangi langkah 3.

Bab 2 LANDASAN TEORI. 2.1 Pengantar Proses Stokastik

Recommend Documents