BAB 2 PEMROGRAMAN STOKASTIK
2.1 Program Stokastik Sebagai Suatu Ketidakpastian Program stokastik adalah program matematika dimana semua data yang tergabung kedalam tujuan atau batasan berbentuk ketidakpastian [Holmes,.1990]. Ketidakpastian ini biasanya dicarikan dengan distribusi probability pada parameter. Walaupun ketidakpastian terdefenisi secara tepat, namun dalam praktek harus disusun secara terperinci dengan beberapa skenario sebagai akibat yang mungkin dari data, dalam spesifikasi dan ketepatan distribusi gabungan peluang. Ketidakpastian dapat ditandai dengan distribusi peluang untuk kejadian acak. Pada umumnya, perkiraan batasan diskrit distribusi peluang diberlakukan untuk masalah tractable. Tiap-tiap kejadian acak atau kombinasi beberapa kejadian acak yang tercakup dalam pembuatan model suatu skenario, dinotasikan w.
Dimana
masing-masing skenario yang mempunyai suatu kemungkinan tertentu untuk terjadi, dinotaasikan pw. karena hanya salah satu dari skenario yang terjadi, maka peluang skenario harus menuju. Untuk mengambil tiap-tiap skenario ke dalam pertimbangan maka masalah linier stokastik perlu dirumuskan. Pada program stokastik, ide recourse dapat tercakup pada sasaran dengan meminimumkan biaya untuk keputusan yang pertama dan konsekwensi biaya ekspektasi untuk keputusan dengan skenario berbeda. Dengan vektor x untuk pembuatan keputusan pertama dan y pembuat perlakuan untuk skenario tertentu,maka masalah [Holmes, 2005] untuk hal demekian dinyatakan dengan : Min cx + ew h(x, w) Kendala Ax = b, x ≥ 0 Dimana (x,w) = min g w y KendalaT W y = Dw + f W
(2.1)
5 Universitas Sumatera Utara
6 Dari masalah stokasitik yang dinyatakan di atas dapat diperinci sebagai berikut. Program linier meminimumkan biaya keputusan pertama, cx, dan biaya ekspetasi untuk konsekwensi, biaya recourse h(x, w). biaya recourse tergantung pada keputusan x dan bervariasi untuk masing-masing skenario. Kemudian program linier determinitk biaya recourse dengan temuan suatu tindakan optimal y untuk bereaksi terhadap hasil kejadian acak tertentu. Untuk seperti itu,ada suatu tindakan yang berbeda untuk bereaksi terhadap hasil kejadian acak tertentu. Untuk seperti itu,ada suatu tindakan yang berbeda y untuk masing-masing skenario. Perumusan untuk masalah yang mempunyai keputusan x menjadi tidak terikat pada hasil kejadian acak. Ini menunjukkan arti bahwa keputusan tidaklah didasarkan pada keadaan yang akan datang, dengan implementasi keputusan yang riil. Ini disebut property nonanticipativas. Jika skenario suatu masalah berkembang ke dalam skenario berbeda didalam periode waktu berurutan, maka batasan yang lebih rumit mungkin diperlukan untuk model yang bercabang. Namun untuk hal ini percabangan tidaklah dimanfaatkan dalam memecahkan permasalahan, dan nonanticipativas dijamin tanpa batasan tambahan. Masalah skokastik dapat dimodelkan dalam suatu bentuk format deterministik lebih tradisional. Nilai yang diharapkan dapat dihitung dari peluang pw dan suatu variable berbeda yw dapat diperkenalkan dengan tegas untuk masing-masing skenario. Perumusanya [Holmes, 2005] dinyatakan dengan: Min cx + Σpw g w y w Kendala Ax = b T W Y W = DW X, Y W ≤ 0
(2.2)
Beberapa aplikasi program stokastik antara lain perencanaan produksi, skedulling, pembuatan rute, pengalokasian, ekspansi kapasitas, investasi energi, control dan manajemen lingkungan, management air, pertamina, financial dan lain -lain [Sahanidis, 2004].
Universitas Sumatera Utara
7 2.2 Model Stokastik Dua Tahap Dan Penyelesaianya Model stokastik yang diuraikan pada bagian ini adalah model recourse, yaitu penggabungan antara model antisifatif dan model adaptif [Mawengkang,H.et.al,2006]. Persoalan stokastik dua tahap dengan rekursif dapat ditulis sebagai Min f (x) + E[Q(X, W )] Kendala Ax = b X ∈ RM 0
(2.3)
X adalah keputusan antisipatif tahap pertama yang diambil sebelum peubah acak teramati dan Q(x,w) merupakan nilai optimalnya, untuk sembarang Ω,dari program tak linier : Min ε(y, w) Kendala W (w)y = h(w) − T (w)x X ∈ RM 1
(2.4)
Dengan y keputusan adafitif tahap kedua yang tergantung pada realisasi vector acak tahap pertama ε(y, w)n merupakan fungsi biaya tahap kedua dan {T (w), W (w), h(w) | wεΩ} adalah parameter model dengan dimensi tertentu. Parameter - parameter ini merupakan fungsi dari vektor acak w dank arena itu merupakan parameter acak. T adalah materiks teknologi yang mengandung koefisien teknologi yang mengubah keputusan tahap pertama x menjadi sumber daya untuk persoalan tahap kedua. W adalah matriks recourse dan h vektor sumber daya tahap kedua. Secara umum model recourse dua tahap dapat diformulasikan sebagai. Dari bentuk program stokastik perlu dibentuk model deterministik yang ekivalen sehingga mudah diselesaikan.
Universitas Sumatera Utara
8 2.3 Formulasi Deterministik Ekivalen Pandang model program stokastik linier berikut Min g0 (x, ξ) Kendala gi (x, ξ) ≤ 0, i = 1, . . . , m, xXcRn
(2.5)
dengan ξ˜ vektor acak yang bervariasi pada himpunan Ξ ⊂ Rk . Lebih tepat lagi, diandaikan bahwa keluarga (family) F dari ”kejadian”, yaitu himpunan bagian dari Ξ , dan sebaran peluang P pada F diketahui. Jadi untuk setiap himpunan bagian A ⊂ Ξ yang merupakan kejadian-kejadian, yaitu A ∈ F , peluang P (A) diketahui. Selanjutnya, diandaikan bahwa fungsi gi (xi ) : Ξ → R ∀x, i merupakan peubah acak dan sebaran peluang P adalah bebas. Namun, problema diatas tidak ”well defined” karena pengertian ”min” dan juga kendala tidak jelas, jika yang diperhitungkan adalah nilai keputusan x sebelum menge˜ Karena itu revisi terhadap proses pemodelan perlu dilakukan, tahui realisasi dari ξ. yang akan menghasilkan model deterministik ekivalen untuk model diatas 2.4 Proses Formulasi Pembentukan model analogi terhadap program stokastik linier dengan recourse, untuk problema (2.5) dilakukan dengan cara berikut. Ambil
gi+ (x, ξ) =
0
g (x, ξ) i
jika qi(x, ξ) ≤ 0,
(2.6)
selainnya,
kendala ke i dari (2.5) dilanggar jika dan hanya jika gi+ (x, ξ) > 0 untuk suatu keputusan x dan realisasi ξ dari ξ˜ . Di sini dapat diberikan untuk setiap kendala suatu recourse atau aktivitas tahap-kedua yi (ξ) ,setelah mengamati realisasi ξ , dipilih sehingga mengantisipasi pelanggaran kendala - jika ada - dengan memenuhi gi (x, ξ) − yi (ξ) ≤ o . Usaha tambahan ini diandaikan mengakibatkan penambahan biaya atau
Universitas Sumatera Utara
9 penalti qi per unit, jadi biaya tambahan ini (disebut fungsi recourse) berjumlah ( m ) X Q(x, ξ) =min qi yi(ξ) | yi(ξ) ≥ gi+ (x, ξ), = 1, . . . , m (2.7) x i=1
Yang menghasilkan biaya total - tahap pertama dan biaya recourse
f0 (x, ξ) = g0 (x, ξ) + Q(x, ξ)
(2.8)
selain (2.7), dapat dipikirkan suatu program linier recourse yang lebih umum dengan suatu recourse vektor y(ξ) ∈ Y ⊂ Ψn , (Y himpunan polyhedral, seperti {y | y ≥ 0}), suatu sembarang fixed m × n ¯ matriks W ( matriks recourse ) dan vektor unit biaya q ∈ Ψn , menghasilkan untuk (2.6) fungsi recourse.
Universitas Sumatera Utara
