BAB 2 PROGRAM STOKASTIK

BAB 2 PROGRAM STOKASTIK

2.1 Pengertian Program Stokastik Banyak persoalan keputusan yang dapat dimodelkan dengan menggunakan program stokastik dengan tujuan menentukan nilai maksimum atau minimum. Tujuan dan kendala dari sebuah program stokastik adalah fungsi dari variabel, dan persoalan data yang berasal dari permasalahan yang sebenarnya. Sebagai contoh dari persoalan data termasuk biaya perunit, rata-rata produksi, penjualan atau kapasitas, investasi aset. Andaikan keputusan dinyatakan oleh variabel (x1, x2 , . . . , xn ). Sebagai contoh xi menyatakan produksi ke-i dari n produk. Bentuk umum program matematika adalah : Min f (x1, x2 , x3, . . . , xn ) Kendala g1 (x1 , x2, x3, . . . , xn ) ≤ 0 g1 (x1 , x2, x3, . . . , xn ) ≤ 0 .. .

(2.1)

g2 (x1 , x2, x3, . . . , xn ) ≤ 0 (x1 , x2, x3, . . . , xn ) ∈ X dimana X adalah himpunan bilangan real non negatif serta g1 , g2, . . . gn adalah kendala yang dihadapi dalam program stokastik. Program Stokastik adalah sebuah nama yang menyatakan program matematika yang dapat berupa linear, cacah, cacah campuran, non linear tetapi dengan menampilkan elemen stokastik pada data. Oleh karena itu dapat dinyatakan bahwa :

a. Pada program stokastik deterministik, data (koefisien) adalah bilangan-bilangan yang diketahui (tertentu). 5 Universitas Sumatera Utara

6 b. Pada program stokastik, data (koefisien) merupakan bilangan yang tidak diketahui (tidak pasti) yang disajikan sebagai distribusi peluang.

Program stokastik merupakan program matematika dengan situasi (yang mengandung) ketidakpastian. Program stokastik adalah merupakan program matematika, dimana beberapa data yang termuat pada tujuan atau kendala mengandung ketidakpastian, ketidakpastian biasanya dicirikan oleh distribusi peluang pada parameter. Walaupun ketidakpastian didefinisikan dengan tepat tetapi pada prakteknya diberikan beberapa skenario (hasil yang mungkin dari data) yang spesifik dan distribusi peluang gabungan yang cepat. Hasil-hasil secara umum digambarkan pada elemen w ∈ W . Ketika beberapa data acak, maka penyelesaian dan nilai tujuan optimal untuk masalah optimisasi juga acak. Ada dua tipe permasalahan program stokastik, yaitu :

1. Recourse Models (Model Rekursif) 2. Probabilistically Constrained Models (model Kendala Berpeluang)

Suatu cara logis yang diperlukan dalam persoalan adalah membuat sebuah keputusan sekarang dan meminimumkan biaya rata-rata harapan (yang digunakan) sebagai konsekwensi dari keputusan. Paradigma ini dikenal sebagai model Recourse. Andaikan x adalah vektor keputusan yang diambil, dan y(w) adalah sebuah vektor keputusan yang menyatakan aksi terbaru atau konsekwensi dari x. Himpunan berbeda yang berisi y akan dipilih dari tiap-tiap hasil yang mungkin dari w. Formulasi dua tahapnya adalah min f1 (x)+ nilai harapan [f2(y(w), w)] kendala g1 (x) ≤ 0, . . . , gm (x) ≤ 0 h1 (x, y(w)) ≤ 0, untuk setiap w ∈ W .. .

.. .

(2.2)

hk (x, y(w)) ≤ 0 untuk setiap w ∈ W

Universitas Sumatera Utara

7 x ∈ X, y(w) ∈ Y Himpunan kendala h1 , h2, . . . , hk , menggambarkan hubungan antara keputusan tahap pertama x dan keputusan tahap kedua y(w). Di catat bahwa dipersyaratkan (diharuskan) tiap-tiap kendala dipenuhi dengan peluang 1, atau untuk setiap w ∈ W yang mungkin. Fungsi f2 merupakan penyelesaian yang sering muncul dari persoalan matematika. Tidak dibutuhkan untuk membuat korelasi yang berubah-ubah (recourse) untuk keputusan tahap pertama, perlu untuk dibuat korelasi yang terbaik. Model Recourse dapat diperluas dengan banyak cara. Untuk persoalan tahap ganda, pengaruh keputusan sekarang akan ditunggu untuk beberapa ketidakpastian yang diselesaikan kembali (direalisasikan), sehingga pembuatan keputusan yang lain didasarkan pada apa yang terjadi. Tujuannya adalah untuk meminimumkan biaya yang diharapkan dari semua keputusan yang diambil. Pada beberapa kasus, dapat digunakan suatu metode yang lebih tepat untuk mencoba menentukan sebuah keputusan, yang mana keputusan tersebut dijamin oleh himpunan kendala yang akan dipenuhi oleh sebuah peluang tertentu. Model umum dengan kendala berpeluang disebut sebagai probabilistically constrained models yang dirumuskan sebagai berikut : min f (x1 , x2 , x3, . . . , xn ) kendala P r[g1 (x1, x2 , x3, . . . , xn ) ≤ 0 . . . gm (x1, x2, x3, . . . , xn ) ≤ 0] ≥ α h1 (x1, x2 , x3, . . . , xn ) ≤ 0

(2.3)

h2 (x1, x2, x3, . . . , xn ) ≤ 0] (x1, x2 , x3, . . . , xn ) ∈ X 2.2 Program Stokastik Dua Tahap Banyak persoalan perencanaan dan manajemen yang mengandung resiko dan ketidakpastian dibahas dan diselesaikan dengan program stokastik dua tahap. Persoalan stokastik dengan kompensasi dari divergensi pada sistem dengan kendala mem-

Universitas Sumatera Utara

8 punyai aplikasi yang lebih banyak dari pada model program yang lain. Penyelesaian persoalan program stokastik dua tahap berisi vektor acak dan vektor deterministik. Pada tahap pertama, penyelesaian persoalan rencana awal deterministik akan dibuat. Pembentukan rencana awal deterministik dilakukan sebelum kondisi acak dari persoalan ditentukan. Sebuah vektor acak pada penyelesaian persoalan yang sesuai digunakan untuk merencanakan kompensasi divergensi, spesifikasi parameter dari persoalan akan muncul pada tahap kedua. Tujuan dari manager pada persoalan di atas adalah meminimum nilai rata-rata biaya, yang mana tidak hanya termasuk pengeluaran pada tahap perencanaan pendahuluan tetapi juga pada tahap kedua yang diperlukan untuk mengkompensasi pada divergensi di dalam sistem kendala persoalan. Jika persoalan program stokastik dengan model dua tahap dapat diselesaikan maka pemilihan dari rencana awal deterministik akan menjamin keberadaan (eksistensi) vektor acak di dalam kompensasi untuk sistem yang divergen. Andaikan terdapat persoalan berikut:

Min(C, X)

(2.4)

A0 X = B 0

(2.5)

AX = B

(2.6)

X ≥0

(2.7)

dimana C = {cj }, j = 1, 2, . . . , m B = (bi ), i = 1, 2, . . . , m B0 = (b0k ), k = 1, 2, . . . , m A0 =|| a0kj ||, k = 1, 2, . . . , m : j = 1, 2, . . . , n

Universitas Sumatera Utara

9 A =|| aij ||, i = 1, 2, . . . , m : j = 1, 2, . . . , n Andaikan elemen dari matriks A = A(ω), vektor B = B(ω) dan C = C(ω) bernilai acak. Maka untuk proses penyelesaian dari persoalan (2.4 - 2.7) akan dibagi menjadi dua tahapan, sebelum pengamatan dari parameter acak pada kondisi dari tahap pertama dipilih rencana non-negatif deterministik X 0 yang memenuhi kondisi (2.5). pada tahap kedua ditentukan spesifikasi ω 0 dari setiap kejadian acak yang bersamaan (sesuai) dengan nilai A(ω 0) dan B(ω 0). Hitung divergensi B(ω 0 ) − A(ω 0)X 0 yang muncul pada kondisi (2.6) setelah realisasi ω 0 ∈ Ω. Definisikan vektor kompensasi divergensi Y ≥ 0 yang sesuai dengan hubungan berikut

D(ω 0 )Y (ω 0 ) = B(ω 0) − A(ω 0)X 0

(2.8)

dimana D =|| dil , i = 1, 2 . . . , m; l = 1, 2 . . . , n adalah sebuah matriks kompensasi yang berisi elemen acak. Sehingga diasumsikan bahwa realisasi acak ω yang diamati pada tahap kedua tidak bergantung pada pemilihan rencana pendahuluan X 0. Perhatikan persoalan program matematika berikut : Tentukan vektor X berdimensi n dan vektor Y (ω) berdimensi n1 , ω ∈ Ω. Yang menghasilkan

min X Eω {(C(ω), X)

+min Y (H, Y (ω))}

(2.9)

dengan kendala

A0 X = B 0

(2.10)

A(ω)X + D(ω)Y (ω) = B(ω) = B(ω), ω ∈ Ω

(2.11)

X ≥), Y (ω) ≥ 0

(2.12)

Universitas Sumatera Utara

10 H adalah vektor penalty yang bergantung pada nilai kompoinen dari vektor Y (ω) yang mana merupakan kompensasi divergensi. E adalah notasi ekspekstasi matematika setelah ditentukan rencana awal X 0 , kita pilih komponen vektor Y (ω) dengan cara menjamin penalty minimum untuk kompensasi divergensi pada kondisi dari persoalan. Dengan kata lain, setelah ditentukan vektor X 0 , perlu menyelesaikan persoalan

min(H, Y (ω)) | D(ω)Y (ω) = B(ω) − A(ω)X 0Y (ω) ≥ 0} Y

(2.13)

Kebergantungan (keadaan) pada bermacam-macam proses aktual yang dapat dimodelkan, menyebabkan persoalan dinamik akan memiliki salah satu bentuk berikut yaitu : tidak dapat dikondisikan, kondisi probabilistik atau kendala statistik. Untuk persoalan dinamik dengan kendala tidak dapat dikondisikan, karakteristik keputusan adalah membuat pada basis informasi mengenai distribusi yang dikombinasikan oleh parameter acak dari kondisi pada semua tahapan. Pada persoalan dinamik dengan kondisi dua kasus kendala dapat dibedakan menjadi : (a) jika oleh momen pembuatan keputusan hanya realisasi dari parameter acak pada tahap sebelumnya yang diperkirakan diketahui dan (b) jika oleh momen pembuatan keputusan melengkapi informasi yang tersedia mengenai realisasi parameter acak (termasuk kondisi) yang dinyatakan tahapan, tetapi nilai dari parameter acak pada tahapan berurutan tidak diketahui. Terdapat relasi tertentu antara persoalan tahap ganda dengan yang tidak dapat dikondisikan dan kondisi kendala. Penyelesaian optimal untuk persoalan program stokastik dinamik dapat diperoleh dengan strategi murni atau campuran. Pada komponen kasus akhir pada penyelesaian atau karakteristik statistik dari distribusi yang memberikan penyelesaian akan bergantung pada nilai parameter acak di dalam kondisi persoalan, yang direalisasikan oleh momen pembuatan keputusan. Konstruksi model probabilistik dinamik dan melaksanakan metode untuk realisasi yang ditampilkan akan sangat sulit. Pada bagian ini akan diberikan beberapa persoalan yang berisi model matematika untuk persoalan tahap ganda dan prosedur untuk mengkonstruksi penyelesaiannya.

Universitas Sumatera Utara

11 Untuk mengoperasikan model program stokastik diuraikan dengan metode sebagai berikut:

a. Bootstrap Data Historis b. Pemodelan statistika dengan pendekatan ”value at risk” c. Model vektor Autoregressi

a. Bootstrap Data Historis Pendekatan paling sederhana untuk membangun skenario hanya memakai data yang ada tanpa pemodelan matematika. Setiap skenario merupakan sampel dari perolehan aset yang diperoleh dengan mensampling perolehan yang diamati di masa lalu. Waktu dari catatan historis yang tersedia dipilih secara acak dan untuk setiap waktu dalam sampel dibawa perolehan dari semua kelas tersebut. Ini merupakan skenario perolehan bulanan. Jika ingin dibangun skenario perolehan untuk horizon waktu panjang misalnya 1 tahun, disampel perolehan 12 bulan dari titik waktu yang berbeda. Susunan perolehan dari deretan yang disampel merupakan perolehan 1 tahun. Dengan pendekatan ini korelasi diantara kelas aset dipertahankan. b. Model Statistika dari Konsep Value-at-Risk Analisis deret waktu dari data historis dapat dipakai untuk mengestimasi perubahan dari matriks korelasi antara kelas aset. Matriks korelasi ini dipakai untuk mengukur resiko dengan metode Value-at-Risk (VaR). Nyatakan peubah acak dengan vektor acak k-dimensi w. Dimensi w sama dengan jumlah faktor resiko yang ingin dimodelkan. Dengan mengandaikan bahwa peubah acak secara gabungan bersebaran normal dapat didefinisikan fungsi kepadatan peluang dari w sebagai 0

f (w) = (2π)−p02 | Q |−102 exp [− 12 (w − w) ¯ Q−1 (w − w)] ¯ disini w adalah ekspektasi dari w dan Y matriks kovarian dan dapat dihitung dari data historis.

Universitas Sumatera Utara

12 Setelah parameter dari sebaran normal multivarian diestimasi dapat memakainya dalam simulasi Monte Carlo dengan menggunakan pendekatan faktorisasi Cholesky atau prosedur pembentukan skenario yang didasarkan pada analisis komponen utama yang diajukan oleh Jamshidian dan Zhu (1997). Simulasi dapat diterapkan secara berulang pada status berbeda dari pohon kejadian. Segitupun, mungkin saja ingin dipersyaratkan nilai acak yang dibangun pada nilai-nilai yang diperoleh oleh beberapa peubah acak. Sampling bersyarat dari peubah normal multivariat dilakukan seperti berikut. Peubah w dipartisi menjadi 2 subvektor w1 dan w2 dengan w1 vektor dimensi K, dari peubah acak untuk nama beberapa informasi tambahan tersedia dan w2 adalah vektor dimensi K2 − K − K1 dari peubah sisa. Vektor nilai ekspektasi dan matriks kovarian dipartisi secara analog sebagai

w ¯=

"

w ¯1

#

dan

Q=

w ¯2

"

Q11 Q12

#

Q21 Q22

Fungsi kepadatan peluang marginal dari w2 dengan diketahui w1 = w1∗ diberikan oleh 0

f (w | w1 = w1∗ ) = (2π)−p2 02 | Q22.1 |−102 exp [− 12 (w2 − w ¯2.1) Q−1 ¯2.1)] 22.1(w1 − w dimana nilai ekspektasi bersyarat dan matriks kovarian diberikan oleh −1 ∗ w ¯2.1(w1∗ = (w ¯2 − Q21Q−1 11 µ1 ) + Q21 Q11 w1

dan Q22.1 = Q22 − Q21Q111Q12 Skenario w2 untuk periode t dipersyaratkan pada nilai w1 diberikan oleh w1t dapat dibangun dari peubah normal multivariat melalui pernyataan √ t 0 w2i = w2i exp [σi tw2i ] t dengan w2i nilai hari ini dan σi adalah perubahan periode tunggal dari komponen ke

i peubah acak w2 .

Universitas Sumatera Utara

13 c. Pembentukan Skenario Menggunakan Model Vektor Autoregressi Model vektor Autoregressi dapat dipakai untuk membentuk skenario. Dalam hal ini diambil ilustrasi etnang sistem simulasi Asset Liahlity Management (ALM) untuk dana pensiun. Karena cakupan dari sistem ini selalu dibatasi pada keputusan strategis jangka panjang model investasi hanya mempraktekkan kumpulan kecil dari kelas aset yang besar yaitu deposito, bond, real estate dan saham. Terpisah dari perolehan atas aset-aset ini, setiap skenario harus mengandung informasi tentang pertumbuhan gaji masa datang untuk menghitung nilai masa datang pensiun. Model vektor autoregresi untuk membentuk skenario perolehan aset dan pertumbuhan gaji adalah Rt = c + V ht−1 + εt εt
Universitas Sumatera Utara