PEMBENTUKAN POHON SKENARIO UNTUK PROBLEMA KEPUTUSAN TAHAP GANDA

PEMBENTUKAN POHON SKENARIO UNTUK PROBLEMA KEPUTUSAN TAHAP GANDA

TESIS

Oleh

SAWALUDDIN 067021028/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

PEMBENTUKAN POHON SKENARIO UNTUK PROBLEMA KEPUTUSAN TAHAP GANDA

TESIS

Untuk Memperoleh Gelar Magister Sains Dalam Program Studi Magister Matematika Pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

SAWALUDDIN 067021028/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: PEMBENTUKAN POHON SKENARIO UNTUK PROBLEMA KEPUTUSAN TAHAP GANDA : Sawaluddin : 067021028 : Magister Matematika

Menyetujui, Komisi Pembimbing

(Dr. Sutarman, M.Sc) Ketua

(Prof. Dr. Herman Mawengkang) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 4 Juni 2008


Telah diuji pada Tanggal 4 Juni 2008

PANITIA PENGUJI TESIS

Ketua

:

Dr. Sutarman, M.Sc

Anggota

:

Prof. Dr. Herman Mawengkang Drs. Opim Salim S, M.Ikom Ph.D Drs. Marwan Harahap, M.Eng


ABSTRAK Dalam banyak aplikasi, sebaran peubah acak yang tidak diketahui atau yang diketahui, terlalu banyak waktu dan biaya untuk memperhatikan sebaran diskrit dengan banyak hasil yang mungkin atau menangani sebaran kontinu dengan integrasi numerik. Merupakan hal yang umum untuk memilih himpunan hasil representatif yang relatif kecil yang disebut skenario untuk menyajikan kejadian acak. Skenario dapat merupakan kuartil dari sebaran yang diketahui atau data historis, prediksi dan beberapa pohon atau dibangun dengan simulasi. Setiap skenario diberikan nilai probabilitas untuk merefleksikan kemungkinan kejadiannya. Untuk model tahap ganda, informasi skenario dapat diorganisasikan kedalam struktur pohon. Dalam model program stokastik, yang merupakan model sesuai untuk persoalan keputusan dengan ketidakpastian, selalu dihadapkan pada persoalan bagaimana menyajikan ketidakpastian. Apabila berhubungan dengan sebaran dimensi-ganda, persoalan membangun skenario sulit. Dalam tesis ini diajukan suatu algoritma untuk membangun pohon keputusan yang efisien untuk persoalan program stokastik tahap ganda. Kata Kunci : Stokastik, Stokastik Tahap Ganda, Pohon Skenario

i Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

ABSTRACT In most applications, the probability distribution of random variables is unknown or if it is given, it would be too much time and cost to consider the discrete distribution with a huge possible realizations or to handle the continuous distribution with numerical integration. It is common to choose a set of representative realizations with relatively small in number called scenario to present random events. Scenario can be a quartile of a known distribution or historical data, prediction of several trees or constructed using simulation. Each scenario is assigned to a probability value to reflect the likelihood of the occurrence of a random event. For multi-stage model the information of scenario can be organized is a tree structure. In this thesis we purpose an algorithm for generating efficiently tree decision of multi-stage stochastic programming problem. Keyword : Stochastic, Multistage of Stochastic, Scenario Tree

ii Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

KATA PENGANTAR Alhamdulillah puji syukur kehadirat Allah SWT atas berkat dan ridhoNya penulis dapat menyelesaikan penulisan tesis ini, yang berjudul ”Pembentukan Pohon Skenario dalam Pengambilan Keputusan Tahap Ganda”. Tesis ini merupakan tugas akhir pada Sekolah Pascasarjana Program Studi Magister Matematika, Universitas Sumatera Utara. Pada kesempatan ini, penulis juga menyempaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada : Kepala Bappeda Propinsi Sumatera Utara beserta stafnya yang telah memberikan beasiswa kepada penulis, Kepala Dinas Pendidikan Kota Medan yang telah memberi izin mengikuti perkuliahan Program Pascasarjana di Universitas Sumatera Utara. Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.Ak selaku Rektor Universitas Sumatera Utara dan Prof. Dr. Ir. T. Chairun Nisa B, M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara beserta Stafnya yang telah memberi kesempatan kepada penulis untuk mengikuti perkuliahan pada Angkatan ke II Program Educator Tahun 2006. Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Matematika SPs USU dan juga sebagai anggota komisi pembimbing pada penulisan tesis ini yang berkat dorongan dan bantuan beliau sehingga penulisan tesis ini dapat dirampungkan. Dr. Saib Suwilo, M.Sc, selaku Sekretaris Program Studi Matematika SPs USU, yang banyak memberikan kritik dan saran kepada penulis, serta bantuan dan motivasinya selama perkuliahan sehingga penulis dapat menyelesaikan perkuliahan.

iii Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

Dr. Sutarman M.Sc, selaku ketua komisi pembimbing berkat saran dan bantuannya kepada penulis sehingga perkuliahan dan penulisan tesis ini dapat diselesaikan. Drs. Opim Salim S, M.Ikom Ph.D dan Drs. Marwan Harahap M.Eng selaku pembanding atas saran dan bantuannya untuk kesempurnaan penulisan tesis ini serta bimbingan selama perkuliahan berlangsung. Dr. Iryanto M.Si, Dr. Tulus M.Si, Drs. Sawaluddin MIT, Drs. Open Darnius Sembiring M.Sc, Dra. Mardiningsih M.Si, Drs. Suwarno Arriswoyo M.Si, sebagai staf pengajar pada SPs Program Studi Matematika atas bimbingan dan bantuannya selama perkuliahan. Seluruh Staf Administrasi SPs USU, Ibu Misiani, S.Si, dan Sdri. Sri Rayani Tanjung, S.Si yang telah memberikan pelayanan yang baik pada penulis. Juandi Sidabutar, Fauziah Hasibuan dan Farawiati Adrianti selaku ketua kelas, bendahara dan sekretaris serta rekan-rekan seperjuangan, mahasiswa angkatan kedua (Tahun 2006) Program Educator, atas kebersamaan dan bantuan dalam mengatasi masalah selama perkuliahan berlangsung. Kepada orang tua penulis Rohali Hasibuan (Alm) dan Aslan Nasution atas dorongan dan doanya, semoga Allah SWT meridhoiNya, Istri tercinta Neti Purnama Siregar atas dorongan yang penuh kesabaran dan anak-anak tercinta Akmal Hafiz Hasibuan, Fariz Abdullah Hasibuan dan Ainun Mardiah Hasibuan semoga lebih berprestasi dari orang tua. Pada kesempatan ini penulis menyampaikan terima kasih kepada seluruh Keluarga Besar SMA Negeri 21 Medan yang terus mendoakan dan memotivasi iv Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

serta membantu penulis selama mengikuti pendidikan di SPs Program Studi Magister Matematika Universitas Sumatera Utara, Medan. Serta semua pihak yang telah turut membantu perkuliahan dan penulisan tesis ini hingga selesai. Kiranya tesis ini bermanfaat, semoga.

Medan, 20 Juni 2008 Penulis,

Sawaluddin

v Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

RIWAYAT HIDUP Sawaluddin dilahirkan di Mompangjulu kecamatan Panyabungan Kabupaten Tapanuli Selatan (sekarang Kabupaten Mandailing Natal setelah pemekaran) pada tanggal 5 Oktober 1960. Merupakan anak kedua dari enam bersaudara anak dari Rohali Hasibuan (Alm) dan Aslan Nasution. Masuk sekolah dasar di SD Negeri Mompangjulu tahun 1966 dan tamat tahun 1972, melanjutkan ke SMP negeri Panyabungan tamat tahun 1975 kemudian melanjutkan ke SMA Negeri Panyabungan selama tiga setengah tahun, karena ada pertambahan satu semester dan tamat tahun 1979. Pada tahun 1979 masuk FPMIPA IKIP Medan program ikatan dinas D.III tamat tahun 1982. Tahun 1984 diangkat jadi guru PNS di SMP Negeri Airbatu Asahan. Tahun 1990 pindah tugas ke SMP Bina Bersaudara sebagai guru PNS Dpk. Dan pada tahun yang sama melanjutkan kuliah di FPMIPA IKIP AlWashliyah Medan selesai tahun 1992, mempeoleh gelar Sarjana Pendidikan (S.1). Pada tahun 1996 penulis menikah dengan Neti Purnama Siregar sampai saaat ini dikaruniai tiga orang putra putri tercinta Akmal Hafiz Hasibuan, Fariz Abdullah Hasibuan dan Ainun Mardiah Hasibuan. Pada tahun 1997 mengikuti pelatihan IMTAQ dan IPTEK di Jakarta kemudian diangkat menjadi Instruktur Guru IMTAQ dan IPTEK Tingkat SMA Sumatera Utara. Pada tahun 1998 pindah tugas ke SMA Negeri 2 Medan. Pada tahun 1999 mengikuti Pelatihan Calon Kepala Sekolah Regional I (Aceh, Sumatera Utara, Riau dan Sumatera Barat). Pada tahun 2000 mengikuti Pelatihan Guru Inti di PPPG Yogyakarta, kemudian jadi Guru Inti Tingkat SMA Sumatera Utara. Selanjutnya pada tahun 2004 diangkat menjadi Kepala Sekolah pada SMA Negeri 21 Medan sampai sekarang. vi Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

Pengalaman berorganisasi : Tahun 2004/2007 menjadi Sekretaris JBMI (Jamiyah Batak Muslim Indonesia), dan pada tahun 2007/2010 dipercayakan menjadi Pembina Assosiasi Guru Matematika SMA/MA Sumatera Utara. Pada tahun 2006 diperkenankan mengikuti pendidikan Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara dengan program beasiswa dari Bappeda Propinsi Sumatera Utara.

vii Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

x

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

5

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

6

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .

6

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .

6

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

8

BAB 3 PROGRAM STOKASTIK . . . . . . . . . . . . . . . . . . .

15

3.1 Pengertian Program Stokastik . . . . . . . . . . . . . . .

15

3.2 Program Stokastik Dua Tahap . . . . . . . . . . . . . . .

18

3.3 Analisis Persoalan Program Stokastik Dua Tahap

. . . . .

22

. . . . . . . . . . . . .

30

3.4 Program Stokastik Tahap Ganda

viii Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

3.5 Pengertian Pembentukan Pohon Skenario . . . . . . . . .

39

BAB 4 ALGORITMA PEMBENTUKAN SKENARIO UNTUK PROGRAM STOKASTIK LINIER TAHAP GANDA . . . . . . . . . . . . 45 4.1 Pengantar

. . . . . . . . . . . . . . . . . . . . . . . .

45

4.2 Persiapan . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.3 Pohon Skenario dan Filtrasi . . . . . . . . . . . . . . . .

50

4.4 Algoritma Pembentukan Skenario . . . . . . . . . . . . .

56

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

60

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

62

ix Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

DAFTAR GAMBAR

Nomor

Judul

Halaman

3.1

Pohon Skenario . . . . . . . . . . . . . . . . . . . . . . .

40

4.1

Pohon Degenerate . . . . . . . . . . . . . . . . . . . . . .

54

4.2

Partisi Pertama . . . . . . . . . . . . . . . . . . . . . . .

54

x Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Optimisasi pengambilan keputusan dengan adanya ketidakpastian pada waktu ke waktu adakalanya dapat diselesaikan dengan program stokastik. Secara esensial model ini diajukan untuk menggantikan model deterministik, dimana koefisien atau parameter yang tidak diketahui adalah acak. Perkembangan dalam metode komputasi yang semakin maju menyebabkan persoalan berskala besar dapat terselesaikan secara efesien dan terpercaya. Program stokastik memberikan kerangka dasar pemodelan yang mampu melibatkan fitur dunia nyata, seperti kendala pengalihan, biaya transaksi, menghindari resiko, batasan pada kumpulan aset dan pertimbangan lainnya. Akan tetapi model optimisasi ini menjadi rumit jika terdapat sejumlah besar peubah, terutama untuk persoalan tahap ganda. Program stokastik tahap ganda kerapkali digunakan untuk memodelkan proses keputusan dalam keuangan, produksi, energi dan logistik. Input program stokastik tahap ganda adalah proses stokastik multivariate {ξ}Tt=1 yang didefinisikan sebagai ruang peluang (Ω, F , P) dimana Ω adalah himpunan ruang sampel, F adalah σ-field dan P adalah peluang dengan ξt pada Rd . Keputusan xt di t anggota Rmt diasumsikan nonantisipatif , yaitu hanya tergantung pada (ξ1 , . . . , ξt ). Sifat ini ekuivalen dengan ukuran xt atas σ-field Ft ⊆ F yang dibangun oleh ξ t := (ξ1 , . . . , ξt ). Yang jelas diperoleh Ft ⊆ Ft+1 untuk t = 1, . . . , T − 1. Karena

1 Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

2 pada waktu t = 1 input diketahui, diasumsikan bahwa F1 = {∅, Ω} dan tanpa kehilangan sifat-sifatnya bahwa FT = F. Proses stokastik tahap ganda dibentuk sebagai berikut:       xt ∈ Xt     " #   T   X hb1 , (ξt ), xti xt adalah Ft − terukur , t = 1, . . . , T min E     t=1        A t,0xt + At,1(ξt )xt−1 = ht (ξt ), t = 2, . . . , T 

(1.1)

dimana himpunan Xt ⊆ Rmt adalah tidak kosong dan polyhedral, koefisien biaya bt(ξt ) termasuk pada Rmt , sebelah kanan ht (ξt ) pada Rnt , At,0 adalah matriks (nt , mt ) dan At,1(ξt ) adalah matriks (nt , mt−1 ). Diasumsikan bahwa bt(·), ht (·) dan At,1(·) tergantung secara linier pada ξt sehingga beberapa komponen dari bt dan ht serta At,1 adalah acak. Walaupun kelompok batasan pertama dan ketiga dalam (1.1) harus dipenuhi titik per titik dengan peluang 1, kelompok kedua, batasan keterukuran atau batasan informasi, bersifat fungsional dan bukan titik per titik paling tidak jika T > 2 dan F1 ⊂ Ft ⊂ FT untuk 1 < t < T . Keberadaan batasan-batasan yang 6=

6=

berbeda secara kualitatif sedemikian merupakan sumber dari tantangan teoritis dan perhitungan model tahap ganda. Pendekatan perhitungan yang utama pada program stokastik tahap ganda tercapai pada approksimasi dari proses stokastik ξ = {ξ}Tt=1 yang mempunyai banyak skenario yang terbatas dan menunjukkan struktur pohon serta dimulai pada elemen tetap ξ1 pada Rd . Ini menunjukkan model program linier yang skalanya sangat luas pada banyak kasus dan diselesaikan dengan metode dekomposisi yang mengeksploitasi struktur khusus model.


3 Model antisipatif dan adaptif merupakan kasus khusus dari program stokastik. Kombinasi keduanya menghasilkan model rekursif yang menjadi fokus dalam penelitian ini. Model ini juga disebut sebagai model statis, dalam mana keputusan tidak tergantung pada pengamatan masa datang. Perancanaan yang baik harus memperhitungkan semua realisasi masa datang yang mungkin karena tidak akan ada kesempatan untuk memperbaharui keputusan nantinya. Dalam model adaptif, informasi yang dikaitkan dengan ketidakpastian muncul secara parsial sebelum pengambilan keputusan, jadi optimisasi terjadi dalam lingkungan pembelajaran. Model rekursif menggabungkan dua model yang diutarakan terdahulu, yang ingin menentukan kebijakan yang tidak hanya mengantisipasi pengamatan masa datang tapi juga memperhitungkan informasi yang ada untuk membuat keputusan rekursif. Misalnya, manajer portofolio memperhatikan gerak masa datang agar saham (antisipasi) tetapi juga menyeimbangkan posisi portofolio ketika harga berubah (adaptasi). Persoalan program stokastik dua tahap dengan rekursif dapat ditulis sebagai min

f (x) + E[Q(x, w)]

kendala Ax = b

(1.2)

0 x ∈ RM +

x adalah keputusan antisipatif tahap pertama yang diambil sebelum peubah acak teramati dan merupakan nilai optimalnya, untuk sembarang Ω, dari program tak linier: min

ξ(y, w)

kendala

W (w)y = h(w) − T (w)x 1 y ∈ RM +


(1.3)

4 dengan y keputusan adaptif tahap kedua yang tergantung pada realisasi vektor acak tahap pertama, ξ(y, w) merupakan fungsi biaya tahap kedua, dan persamaan {T (w), W (w), h(w)|w ∈ Ω} adalah parameter model dengan dimensi tertentu. Parameter-parameter ini merupakan fungsi dari vektor acak w dan karena itu merupakan parameter acak. T adalah matriks teknologi yang mengandung koefisien teknologi yang mengubah keputusan tahap pertama x menjadi sumber daya untuk persoalan tahap kedua. W adalah matriks rekursif dan h vector sumber daya tahap kedua. Secara umum model rekursif dua tahap dapat di formulasikan sebagai

min

f (x) + E

"

min {ξ(y, w)|T (w)x + W (w)y = h(w)}

#

M

y∈R+ 1

kendala

Ax = b

(1.4)

0 x ∈ RM +

Persoalan rekursif tidak dibatasi pada formulasi dua-tahap. Mungkin saja pengamatan dibuat pada T tahap berbeda dan terungkap dalam kumpulan informasi T At |t=1 dengan A1 ⊂ A2 ⊂ · · · ⊂ AT . Tahap berhubungan dengan waktu ketika beberapa informasi terungkap dan suatu keputusan dapat diambil (Perhatikan bahwa T adalah indeks waktu, sedangkan T (w) matriks)


5 Program tahap ganda yang memperluas model dua-tahap , diformulasikan sebagai persoalan optimasi terkelompok berikut " " min

f (y0 ) ∗ E

min ξ(y1 , w1) + · · · + E M

y1 ∈R+ 1

kendala

#

min ξ(yT , wT ) · · ·

#

M

yT ∈R+ T

T1(w1 )y0 + W1 (w1 )y1 = h1 (w1) .. .

(1.5)

TT (wT )YT −1 + WT (wT )yT = hk (wT ) 0 y0 ∈ RM +

Terdapat beberapa pendekatan untuk menghasilkan pohon skenario untuk program stokastik tahap ganda. Pendekatan tersebut didasarkan pada beberapa prinsip yang berbeda-beda yaitu :

a. Konstruksi berdasarkan bound b. Skema Monte Carlo atau Metode Quasi Monte Carlo c. Sampling (berdasarkan EVPI) dalam skema dekomposisi d. Prinsip moment-matching e. Approksimasi berdasarkan metric peluang

Terlihat bahwa untuk menyelesaikan model program stokastik, pembentukan skenario dan pohon kejadian sangatlah penting.

1.2 Perumusan Masalah Mentransformasikan model Program Stokastik Cacah Campuran (PSCC) menjadi model Program Bilangan Cacah-Campuran Linier adalah merupakan


6 ide kunci dalam penelitian ini. Hal ini dimungkinkan karena ketidakpastian dan waktu dapat dimodelkan sebagai sejumlah skenario yang berhingga. Dengan kata lain peneliti tidak memakai fungsi sebaran peluang untuk merepresentasikan ketidakpastian, karena adanya fungsi sebaran dapat mengakibatkan terjadinya diskontinuitas dan tak konveks. Begitupun, ukuran model ekivalen akan tumbuh sangat cepat sebagai konsekuensi dari jumlah skenario dan jumlah horizon waktu. Oleh karena itu penelitian ini juga akan mengajukan suatu metode untuk membentuk jumlah skenario yang efisien. Kerangka dasar dari metode ini akan dikembangkan untuk menyelesaikan transformasi PSCC ini.

1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah menyediakan alat untuk mendukung proses pengambilan keputusan yang mengandung ketidakpastian, misalnya : dalam bidang manajemen resiko.

1.4 Kontribusi Penelitian Kontribusi penelitian adalah diperolehnya suatu metode untuk menyelesaikan problem keputusan dan perencanaan yang mengandung ketidakpastian yang sering muncul dalam bidang energi, financial, pertanian, ekonomi dan logistik sertamanajemen portfolio listrik dalam skala yang luas.

1.5 Metodologi Penelitian Penelitian ini membahas pembentukan skenario terhadap persoalan keputusan dengan ketidakpastian tahap ganda. Sebagai langkah awal dibicarakan konsep dasar program stokastik dan program stokastik dua tahap. Selanjutnya dibahas


7 analisis persoalan program stokastik dua tahap yang bertujuan untuk mengeneralisasi program stokastik tahap ganda. Program stokastik tahap ganda yang dikaji bertujuan untuk membentuk pohon skenario. Setiap skenario diberikan nilai probabilitas untuk merefleksikan kemungkinan kejadiannya. Untuk model tahap ganda, informasi skenario dapat diorganisasikan kedalam struktur pohon. Pada bagian akhir dibahas mengenai pohon skenario dan filtrasi, prosedur pemutahiran pohon dan algoritma pembentukan skenario. Algoritma yang diperoleh dapat membangun barisan skenario yang mana tidak hanya menyediakan konvergensi asimptot, tetapi juga menyediakan ukuran optimalitas pada keputusan tahap pertama.


BAB 2 TINJAUAN PUSTAKA

Banyak konsep program stokastik tahap ganda telah dikembangkan. Filosofi dasar dari metode pembentukan skenario diajukan oleh Hoyland dan Wallace (2001). Para pengguna menyatakan bahwa penjualan yang diharapkan dalam distribusi marginal pada tiap-tiap kelas asset akan berkorelasi antara perbedaan kelas asset dan sifat-sifat statistik yang lain. Idenya adalah meminimumkan jarak antara sifat-sifat statistik dari hasil yang sudah dibangun dan sifat-sifat statistik tertentu. Masalah pembentukan pohon skenario untuk program matematika sudah banyak dibahas oleh peneliti. Biasanya persoalan pembentukan pohon skenario muncul pada program stokastik dua tahap dan tahap ganda. Dalam tulisan ini diuraikan secara singkat beberapa metode yang pernah diajukan. Robert et al. (1991) mengajukan reduksi skenario pada program stokastik. Masalah reduksi skenario optimal mereka adalah menentukan sebuah sub himpunan skenario dari kardinal yang ditentukan dan ukuran peluang yang didasarkan pada himpunan yang paling dekat dengan distribusi awal dengan menggunakan metriks peluang (berbentuk kerucut). Argument dari analisa stabilitas menyatakan bahwa Fortet-Mourier tipe metriks peluang dapat menjalankan metriks berbentuk kerucut. Algoritma yang sesuai dikembangkan untuk menentukan ukuran reduksi yang optimal. Hasil secara numerik digunakan mereduksi pohon skenario yang bermuatan listrik untuk manajemen power dengan ketidakpastian. 8 Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

9 Heitsch dan Rõmisch (2003) mengajukan algoritma untuk mereduksi skenario dalam program stokastik. Mereka memperhatikan program stokastik konveks dengan sebuah pendekatan distribusi peluang awal P yang mempunyai skenario dengan jumlah berhingga. Program stokasik yang dimaksud akan stabil terhadap gangguan dari P yang terukur pada Fortet-Mourier probability metriks. Persoalan reduksi skenario optimal akan berada pada penentuan ukuran peluang yang dibantu oleh sebuah subset pada P dari penentuan kardinalitas dan yang paling dekat terhadap p pada sebuah metriks peluang. Dua versi baru algoritma tipe forward dan backward diberikan untuk menghitung sehingga ukuran peluang yang direduksi optimal. Bandingkan dengan versi lama, pelaksanaan perhitungan (akurasi, waktu menjalankan) dari algoritma yang baru telah diperbaiki (lebih baik). Hasil secara numerik yang telah dilaporkan digunakan untuk kejadian berbeda dari pohon skenario dengan perhitungan optimal pada batas terkecil. Contoh-contoh pengujian juga termasuk pohon skenario ternary menyatakan proses bermuatan listrik mingguan dalam model manajemen power. Sedangkan Hoyland et al. (2003) mengajukan metode heuristik untuk membangun pohon skenario pada masalah keputusan tahap ganda. Mereka menampilkan sebuah algoritma untuk membangun pohon skenario dari masalah tahap tunggal dan tahap ganda. Algoritma yang diberikan untuk membangun sebaran diskrit tertentu oleh empat momen marginal pertama dan korelasi. Pohon skenario dikonstruksikan oleh dekomposisi masalah multivariate menjadi univariate, dan menggunakan prosedur iterative dengan kombinasi simulasi. Dekomposisi Cholesky dan bermacam-macam transformasi untuk mendapatkan korelasi yang tepat. Pengujian mereka menunjukkan bahwa algoritma yang baru secara substansial lebih cepat daripada algoritma Benchmark. Kecepatan akan


10 meningkat sebanding dengan jumlah pohon dan lebih besar dari 100 kali pada kasus 20 variabel acak dan 1000 skenario. Kaut dan Wallace (2003) mengajukan evaluasi dari metode pembangun skenario untuk program stokastik. Mereka mendiskusikan kualitas/keserasian (kecocokan) dari metode pembangun skenario untuk model program stokastik yang diberikan. Mereka memformulasi persyaratan minimal yang akan ditetapkan (ditentukan) pada metode pembangun skenario sebelum digunakan untuk menyelesaikan model program stokastik. Mereka juga menunjukkan bagaimana persyaratan dapat diuji. Prosedur pengujian metode pembangun skenario diilustrasikan pada kasus manajemen portofolio. Sebagai tambahan, mereka juga memberikan ulasan singkat metode pembangun skenario. Hochreiter dan Pflug (2004) mengajukan metode membangun pohon skenario sebagai masalah penempatan fasilitas multidimensi. Menurut mereka kualitas model optimisasi stokastik multiperioda yang muncul dalam perencanaan energi, aset dan manajemen pertanggungjawaban, perancanaan transportasi dan lain-lain. Kebanyakan bergantung pada kualitas model skenario, penggambaran pengaruh proses ketidakpastian fungsi keuntungan/biaya, seperti proses permintaan energi, besar aset dan pertanggungjawaban, permintaan untuk transportasi dan lain-lain. Cara yang biasa untuk membangun model skenario didasarkan pada perkiraan peluang yang tidak diketahui dan kesesuaian momen mereka dengan momen dari model skenario diskrit. Tujuan mereka adalah mendemonstrasikan masalah penentuan perkiraan skenario terbaik yang digambarkan sebagai masalah penempatan fasilitas multidimensi. Mereka juga mendiskusikan algoritma penyelesaian untuk masalah ini dan mendemonstrasikan kualias dari penyelesaian con-


11 toh numerik pada optimisasi finansial. Higle et al. (2002) mengajukan Stochastic Scenario Decomposition untuk program stokastik tahap ganda. Mereka memberikan algoritma Stochastic Scenario Decomposition (SSD) yang secara statistik dimotivasi oleh algoritma cutting plane untuk menyelesaikan program stokastik tahap ganda.

Metode ini

didasarkan pada penyelesaian masalah dual, dimana variabel berkaitan dengan penalti sesuai dengan kendala nonantisipasi dari masalah primal. Hasil analitik mereka dibuktikan dengan kondisi yang memperkenalkan SSD sebagai sebuah penyelesaian optimal yang berupa garis asimtot. Mereka juga menanggulangi beberapa hambatan perhitungan yang disebabkan oleh pertambahan ukuran kolom dari masalah master SSD. Mereka juga mengusulkan skema penyatuan variabel untuk menyelesaikan program master yang lebih kecil tanpa mengorbankan kualitas penyelesaian. Hasil perhitungan mereka juga mendemonstrasikan keefektifan dari skema penyatuan dalam menyelesaikan program master SSD. Casey dan Sen (2005) mengajukan algoritma pembentukan skenario untuk program linier stokastik tahap ganda.

Program linier stokastik tahap ganda

adalah rangkaian model optimisasi stokastik dimana fungsi dan kendalanya linier. Ketika variabel acak digunakan pada program linier stokastik tahap ganda adalah variabel kontinu. Masalah tersebut adalah dimensi tak terbatas, sehingga perhitungannya harus ditukar ke dalam bentuk dimensi terbatas. Berikut ini akan diberikan ulasan singkat mengenai metode pembentukan skenario. Metode dibahas meliputi Pure Scenario-generation methods dan Related methods.


12 Pure Scenario-generation methods meliputi : a. Conditional sampling b. Sampling dari korelasi dan marginal tertentu c. Moment matching d. Path-based methods e. Optimal discretization Sedangkan Related methods meliputi reduksi skenario dan internal sampling methods. Conditional sampling Metode traditional sampling dapat mengambil sampel hanya dari variabel univariate random. Ketika kita perlu mengambil sampel vektor acak, kita perlu untuk setiap sampel marginal untuk dipisahkan (menjadi komponen univeriate). biasanya sampel dikombinasi oleh semua univariate, yang menghasilkan vektor variabel acak independen. Persoalannya adalah ukuran dari pertambahan pohon berkembang secara eksponensial dengan dimensi vektor acak. Jika diambil s skenario dengan k marginal, maka akhir diproleh sk skenario. Persoalan lain adalah bagaimana untuk mendapatkan vektor acak yang dikorelasi,penentuan komponen prinsip (yang indenpenden oleh definisi) dan sampel tersebut, sebagai ganti dari variabel acak mula-mula. Pendekatan ini berguna untuk mereduksi dimensi dan mereduksi banyaknya skenario. Terdapat banyak cara memperbaiki sampling algoritma. Sebagai ganti dari Pure sampling, kita dapat menggunakan integration quadratures atas low discrepancy sequences seperti yang diajukan oleh Pennanen dan Koivu (2005).


13

Sampling dari marginal tertentu dan korelasi Seperti yang sudah dibahas sebelumnya, metode traditional sampling mempunyai masalah membangun vektor multivariate, khususnya jika mereka berkorelasi. Walaupun demikian, terdapat sampling-based methods untuk menyelesaikan masalah ini dengan menggunakan bermacam-macam transformasi. Moment matching Metode sebelumnya dapat dipakai (digunakan) jika kita mengetahui distribusi fungsi marginalnya. Jika distribusi fungsi marginalnya tidak diketahui, kita dapat menggambarkan marginal oleh momen mereka (rataan, variansi, kurtosis dan lain-lain) sebagai gantinya. Path-based methods Metode ini diawali oleh membangun path lengkap yaitu skenario, oleh pengembangan proses stokastik {ξt }. Hasil dari tahap ini bukanlah pohon skenario, tetapi kumpulan path yang dikenal sebagai fan. Untuk mentransformasi fan menjadi pohon skenario, skenario yang diperoleh dikelompokkan bersama (dibatasi), semuanya tetapi tidak periode sebelumnya. Proses ini dikenal sebagai pengelompokan, metode ini dapat ditemukan pada Dupacova et al. (2000) Optimal discretization Pflug (2001) mengajukan metode untuk menentukan pendekatan dari proses stokastik (pohon skenario) yang meminimumkan kesalahan pada fungsi objektif dari model optimisasi. Ketidak sesuaian metode sebelumnya menyebabkan pohon


14 skenario periode berganda dikonstruksikan kembali. Metode optimal discretization hanya mengerjakan proses univariate. Reduksi skenario Ini adalah metode untuk penurunan ukuran pohon yang diberikan. Metode ini bertujuan untuk menentukan subset skenario dari kardinal yang ditentukan, dan pengukuran peluang yang didasarkan pada himpunan yang paling dekat dengan distribusi awal dengan menggunakan matriks peluang. Metode ini digambarkan dalam Dupacova et al. (2003). Internal sampling methods Sebagai ganti dari penggunaan pohon skenario sebelum dibentuk, beberapa metode untuk menyelesaikan masalah proram stokastik diambil skenario selama prosedur penyelesaian. Metode yang paling penting dari tipe ini adalah metode stochastic quasi gradient dalam Eemoliev (1976). Sebagai tambahan terdapat metode dengan proses iteratif, yang diselesaikan dengan aliran pohon skenario, penambahan atau pengeluaran beberapa skenario dan menyelesaikan masalah lain. Metode ini berbeda dalam penambahan/ pengurangan skenario Casey and Sen (2005) menggunakan variabel aliran penyelesaian.


BAB 3 PROGRAM STOKASTIK

3.1 Pengertian Program Stokastik Banyak persoalan pengambilan keputusan dapat dimodelkan dengan menggunakan program matematika yang tujuannya untuk mendapatkan hasil yang maksimal atau minimal. Keputusan yang dihasilkan akan bergantung kepada kendala yang dibatasi oleh sumber dana, persyaratan minimum dan lain-lain. Keputusan dinyatakan oleh variabel dapat berupa bilangan cacah atau nonnegatif. Tujuan dan kendala adalah fungsi dari variabel, dan persoalan data. Sebagai contoh dari persoalan data termasuklah biaya perunit, rata-rata produksi, penjualan atau kapasitas. Andaikan keputusan dinyatakan oleh variabel (x1 , x2, · · · , xn ). Sebagai contoh x1 menyatakan produksi ke-i dari n produk. Bentuk umum program matematikanya adalah : min

f (x1, x2 , x3, · · · , xn )

kendala g1 (x1, x2, x3 , · · · , xn ) ≤ 0 g2 (x1, x2, x3 , · · · , xn ) ≤ 0 .. .

(3.1)

gm (x1 , x2, x3, · · · , xn ) ≤ 0 x1, x2, x3 , · · · , xn ∈ X dimana X adalah himpunan bilangan real non negatif.


16 Stokastik programming adalah 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 matematika deterministik, data (koefisien) adalah bilanganbilangan yang diketahui (tertentu). 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. Model rekursif 2. Model kendala berpeluang

Suatu cara logis yang diperlukan dalam persoalan adalah membuat sebuah keputusan sekarang dan meminimumkan biaya rata-rata harapan (yang digunakan)


17 sebagai konsekuensi dari keputusan. Paradigma ini dikenal sebagai Model Rekursif. Andaikan x adalah vektor keputusan yang diambil, dan y(w) adalah sebuah vektor keputusan yang menyatakan aksi terbaru atau konsekuensi dari x. Himpunan berbeda yang berisi y akan dipilih dari tiap-tiap hasil yang mungkin dari w. Formulasi dua tahapnya adalah minf1 (x) + nilai harapan [f2 (y(w), w)] kendala g1 (x) ≤ 0, · · · , gm (x) ≤ 0 h1 (x, y(w)) ≤ 0, untuk setiap w ∈ W .. .

(3.2)

hk (x, y(w)) ≤ 0, untuk setiap w ∈ W 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 berubahubah (recourse) untuk keputusan tahap pertama, perlu untuk dibuat korelasi yang terbaik. Model Rekursif 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.


18 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 kendala berpeluang dirumuskan sebagai berikut : min f (x1 , x2, x3, · · · , xn ) kendala P r[g1 (x1, x2 , x3, . . . , xn ) ≤ 0 gm (x1 , x2, x3, . . . , xn ) ≤ 0 ≤ α (3.3) h1 (x1, x2, x3 , . . . , xn ) ≤ 0 h2 (x1, x2, x3 , . . . , xn ) ≤ 0 x1, x2 , x3, . . . , xn ∈ X

3.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 mempunyai 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 meminimumkan nilai rata-rata biaya, yang mana tidak hanya termasuk pengeluaran pada tahap perencanaan pendahuluan tetapi juga


19 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)

(3.4)

A0 X = B 0

(3.5)

AX = B

(3.6)

X ≥0

(3.7)

dimana C = {cj }, j = 1, 2, · · · , m B = (bi ), i = 1, 2, · · · , m B 0 = (b0k ), k = 1, 2, · · · , m A0 = ka0kj k, k = 1, 2, · · · , m; j = 1, 2, · · · , n A = kaij k, 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 (3.4 − 3.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 (3.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 (3.6) setelah realisasi ω 0 ∈ Ω. Defini-


20 sikan vektor kompensasi divergensi Y ≥ 0 yang sesuai dengan hubungan berikut D(ω 0 )Y (ω 0 ) = B(ω 0) − A(ω 0)X 0

(3.8)

dimana D = kdil k, 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 Eω {(C(ω), X) + min(H, Y (ω))}

(3.9)

A0 X = B 0

(3.10)

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

(3.11)

X ≥ 0, Y (ω ≥ 0

(3.12)

X

Y

dengan kendala

H adalah vektor penalti yang bergantung pada nilai komponen 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 diselesaikan persoalan n

o

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

(3.13)

Persoalan (1.13) akan mempunyai banyak rencana, vektor Y (ω) tidak dapat ditentukan pada tiap ω ∈ Ω yang menjamin pemenuhan kondisi (3.11). persoalan


21 (3.9) - (3.12) dikenal sebagai persoalan program stokastik dua tahap dan persoalan (3.13) adalah persoalan tahap kedua. Model dan pendekatan dari penyelesaian persoalan program stokastik (dinamik) dua tahap dapat digunakan untuk perspektif perencanaan dan operasional manajemen, karena selalu terdapat keacakan yang mempengaruhi yang sudah direncanakan dan sistem manajemen (pelaksanaan). Model dua tahap juga kurang sensitif terhadap perubahan pada parameter dari kondisi persoalan, yang menyebabkan lebih stabil. Akibatnya vektor dapat diterima untuk rencana tahap pertama yang diperlukan untuk setiap ω ∈ Ω, terdapat vektor Y ≥ 0 sedemikian hingga D(ω)Y (ω) = B(ω) − A(ω)X

(3.14)

Andaikan kendala tambahan yang disebutkan secara implisit pada (3.14) muncul pada tahap kedua dari persoalan yang dihasilkan; dan andaikan kondisi yang ditentukan pada vektor non-negatif X dari persamaan (3.10) sudah ditentukan. Andaikan himpunan K1 = {X : A0 = B 0 , X ≥ 0} didefinisikan oleh kendala yang sudah ditentukan tetapi K2 = {X : ∀ω ∈ Ω, ∃Y ≥ 0, A(ω)X = B(ω)D(ω)Y (ω)} didefinisikan oleh kendala yang dihasilkan. Maka himpunan K = K1 ∩ K2 adalah himpunan vektor X yang layak/memenuhi persoalan (3.9)(3.12). Jika X ∈ K, maka vektor X memenuhi kendala yang sudah ditentukan A0 X = B, X ≥ 0 dan disamping itu, persoalan tahap kedua (3.6) akan memiliki banyak rencana.


22 Teorema 3.1. Himpunan K dengan vektor X pada persoalan program stokastik dua tahap adalah konveks. Bukti : K = K1 ∩ K2 tetapi K1 = {X : A0 = B 0, X ≥ 0} adalah konveks. Definisikan untuk ω ∈ Ω tertentu (yang ditentukan) himpunan K2ω = {X|∃Y (ω) ≥ 0} sedemikian hingga A(ω)X = B(ω) − D(ω)Y (ω) adalah konveks. Hal ini menyatakan bahwa K2 = ∩ω∈Ω K2ω dan K = K1 ∩ K2 adalah himpunan konveks sebagi pertolongan himpunan konveks.

3.3 Analisis Persoalan Program Stokastik Dua Tahap Himpunan K dari rencana pendahuluan untuk persoalan program stokastik dua tahap secara implisit telah ditentukan. Pada kasus generalisasi tidak diketahui bagaimana untuk mengkonstruksi himpunan K2 . Untuk beberapa kasus parsial, dimana sangat penting untuk banyak aplikasi, himpunan K2 mirip dengan Rn Diasumsikan bahwa rank dari matriks D adalah sama dengan m, kecuali (3.11) dapat disubstitusikan untuk relasi ekivalen pada p baris, sehingga : OY = BAX, dimana O adalah vektor berisi nol berdimensi m dan P adalah banyaknya baris bergantung pada D. Asumsikan bahwa rank dari matrik D yang berdimensi m × n adalah sama dengan m dan m kolom pertama adalah linier independen. Andaikan bahwa untuk tiap v ∈ Rn terdapat Y ≥ 0 sedemikian hingga : DY = v

(3.15)

Lemma 3.1. [Kall, 1966] Jika asumsi di atas dipenuhi, maka D mempunyai paling sedikit (m + 1) kolom, yaitu : n ≥ (m + 1).


23 Teorema 3.2. [Kall, 1966] Karena sistem persamaan DY = v mempunyai penyelesaian non-negatif untuk setiap v ∈ Rn , maka hal ini cukup menunjukkan bahwa terdapat penyelesaian non-negatif untuk sistem homogen dari persamaan linier : Dπ = 0

(3.16)

π lebih besar dari pada 0 untuk j = 1, 2, · · · , m Bukti : Sistem persamaan DY = v selalu mempunyai penyelesaian. Mulamula, andaikan Yˆj 6= 0 untuk j = 1, 2, · · · , m tetapi yang lainnya sama dengan nol. Selanjutnya hubungan α(Dπ) + DYˆ = v akan dipenuhi untuk sembarang α, jika diambil α yang cukup besar akan diperoleh penyelesaian non-negatif pada persamaan (3.15). kondisi (3.16) sulit dibuktikan dengan ekspektasi beberapa kasus parsial. Andaikan n menjadi sama dengan m = 1, maka kondisi cukup akan menjadi :Σm+1 j=1 πj Dj = 0, karena jika πm+1 = 0 akan diperoleh dependen linier dari m kolom pertama Dj , yang mana akan kontradiksi dengan fakta bahwa matriks D mempunyai rank m. Konsekwensinya adalah πm+1 > 0, sehingga diperoleh : −Dm+1 =

m X j=1

πj Dj , πj =

π ˆj π ˆm+1

(3.17)

Sistem di atas adalah persamaan linier yang hanya mempunyai satu penyelesaian. Jika positif maka K2 = Rn . Kondisi teorema 3.2 tidak cukup tetapi perlu, sedemikian hingga DY = v mempunyai penyelesaian cukup untuk keperluan pemecahan non-negatif dari DY = v tidak untuk setiap v ∈ Rm tetapi hanya untuk v = BAX dengan setiap X ∈ K1 dan setiap ω ∈ Ω sehingga v jauh dari memenuhi untuk semua Rm .


24 Persoalan (3.4)-(3.7) dapat diinterpretasi sebagai perencanaan produksi, dimana A adalah matriks untuk metode teknologi dasar dan D adalah matriks untuk metode teknologi kebetulan pada penentuan varian yang mungkin untuk kompensasi pada divergensi di dalam sistem yang dikondisikan. Pada kasus kondisi dari teorema 3.2 dapat diinterpretasikan dengan cara berikut. Sehingga untuk sembarang divergensi v ∈ Rm , kompensasi Y dapat diterima temuannya, yang dicukupkan oleh metode teknologi kebetulan menyatakan sebuah sistem tertutup, karena itu terdapat intensitas π tidak nol, yang mana semua hasilnya dieksploitasikan oleh metode produksi tertentu dapat dikonsumsi oleh yang lainnya. Sebagai contoh : penjualan dan pembelian dipisahkan dengan baik.

Teorema 3.3. Karena persoalan (3.13) mempunyai penyelesaian yang berhingga, maka hal ini perlu dan cukup menunjukkan bahwa sistem pertidaksamaan ZD ≤ H

(3.18)

mempunyai penyelesaian Pembuktian teorema di atas dapat dilihat dengan jelas pada teorema dualitas program linier yang diajukan oleh Dantzig (1956). Jika persoalan (3.13) dapat diselesaikan dan mempunyai penyelesaian optimal maka dualnya juga dapat diselesaikan dan begitu juga sebaliknya. Kendala dari persoalan dual untuk (3.13) adalah kondisi (3.17) Kondisi dari teorema 3.3 memiliki kegunaan secara ekonomi. Sehingga biaya pada eksploitasi pada metode teknologi kebetulan dilikuidasi dari divergensi yang berhingga, karena itu cukup dan perlu terdapat sistem estimasi Z untuk menghasilkan metode teknologi kebetulan. Biaya produksi yang disebabkan oleh esti-


25 masi output pada metode teknologi yang ke-i tidak lebih tinggi pada eksploitasi dengan singular intensity dari pada pengeluaran pada eksploitasi dengan singular intensity. Teorema 3.4. Judin (1974) Andaikan matriks D mempunyai m + 1 kolom dan m P πj Dj , πj > 0, j = 1, 2, · · · , m memenuhi kondisi teorema 3.2 yaitu :−Dm+1 = j=1

maka untuk pemenuhan kondisi teorema 3.3 adalah syarat perlu dan cukup bahwa digantikan relasi (hubungan) berikut m X

πj hj + hm+1 ≥ 0, πj > 0, j = 1, 2, · · · , m

(3.19)

j=1

Bukti : Syarat perlu. Andaikan persoalan tahap kedua (3.13) dapat diselesaikan, maka kumpulan rencana dari masalah dual menjadi tidak kosong. Andaikan vektor Z0 memenuhi kondisi (3.17) persoalan dual yaitu : Z0 Dj ≤ hj , j = 1, 2, · · · , m + 1

(3.20)

karena itu, dengan πj > 0 m X

πj Z0 Dj ≤

j=1

m X

πj hj : Z0 Dm+1 = −

j=1

m X

Z0 πj Dj

(3.21)

j=1

disamping itu, kita dapatkan Z0 Dm+1 = −

m X

Z0 πj Dj ≤ hm+1

(3.22)

j=1

Dari kondisi (3.20) dan (3.21) diperoleh hasil (3.18) syarat cukup. Andaikan (3.18) digantikan oleh fungsi tujuan pada persoalan tahap kedua (3.13) yang tidak berkendala pada himpunan rencana, maka himpunan rencana persoalan dual untuk persoalan tahap kedua adalah kosong. {Z|ZD ≤ H} = ∅


(3.23)

26 Dari linear independen vektor-vektor D1 , D2 , · · · , Dm jika mengikuti sistem ZDj = hj , j = 1, 2, · · · , m

(3.24)

hanya mempunyai penyelesaian Z0 , karena persamaan (3.22) diperoleh Z0 Dm+1 > hm+1

(3.25)

Dari kondisi teorema dan persamaan (3.23), (3.24) diperoleh Z0 Dm+1 = −

m P j=1

Z0 πj Dj = −

m P

πj hj > hm+1

j=1

yang mana kontradiksi dengan kondisi (3.18) sehingga teorema dipenuhi. Kondisi (3.18) menguntungkan secara ekonomi pada persoalan penjadwalan. Andaikan metode teknologi berbentuk sistem tertutup, maka biaya dari exploitasi metode accindetal output yang bertujuan kompensasi divergensi akan berhingga, jika tidak mungkin mendapatkan keuntungan dari rezim yang tidak jalan dari pekerjaan (jika persamaan (3.16) dapat dipenuhi). Dalam pekerjaan yang diajukan oleh Kall (1966) ditunjukkan bahwa kondisi analog yang hilang dari keuntungan juga tergantikan dalam kasus ketika n > m + 1, tetapi kondisi ini hanya syarat perlu. Perhatikan sebuah deterministik ekivalen untuk persoalan program stokastik dua tahap pada (3.9)-(3.12) dan tunjukkan bahwa persoalan (3.9)-(3.12) adalah persoalan program konveks. Dual untuk persoalan tahap kedua (3.13) adalah (Z, BAX) → Max

(3.26)

ZD ≤ H

(3.27)

Andaikan penyelesaian persoalan (3.13) ada dan berhingga, maka terdapat penyelesaian berhingga untuk persoalan (3.24)-(3.25) dan nilai optimal untuk keduanya


27 telah dikerjakan oleh Dantzig (1956). Definisikan nilai fungsi sebagai ∅. Dapat diperoleh bahwa ∅(X, A, B) menjadi titik maksimum (3.24) yang dicapai dengan kondisi (3.25) untuk X, A, B yang ditetapkan. Sehingga untuk sembarang X1 dan X2 nilai ekstrimum fungsi tujuan (3.24) adalah berhingga, diperoleh Z(αX1 + (1 − α)X2 , A, B)(B − A(αX1 + (1 − α)X2 ) = Z(αX1 + (1 − α)X2 , A, B)[α(B − AX1 ) + (1 − α)(B − AX2)] ≤ αZ(X1 , A, B)(B − AX1 ) + (1 − α)Z(X2 , A, B)(B − AX2 ) Andaikan ∅ adalah fungsi tujuan dari persoalan deterministik ekivalen, maka ∅ adalah fungsi konveks, karena kombinasi non-negatif fungsi konveks adalah fungsi konveks. Dari konveksitas fungsi tujuan ∅ mengikuti kontinuitas pada setiap titik dalam dari himpunan konveks K. Oleh karena itu dibuktikan oleh pernyataan berikut. Teorema 3.5. Deterministik ekivalen untuk persoalan program stokastik duatahap (3.9)-(3.12) adalah persoalan program konveks. Pernyataan selanjutnya memberikan dasar teori untuk mengkonstruksi pendekatan numerik pada penyelesaian persoalan dua-tahap. Perhatikan metode untuk menyelesaikan persoalan dua tahap diperlukan penggunaan hubungan (persamaan) fungsi dasar untuk ∅(X) dan menyediakan kondisi differensiabel ∅(X). Pada bagian ini akan digunakan fungsi dasar untuk fungsi konveks F (µ) pada titik µ0 ∈ M, untuk fungsi linear L, jika F (µ) − F (µ0) ≥ (L, µ − µ0 ) untuk setiap µ ∈ M. Hal ini dapat dilihat pada Judin (1974) dan Kall (1966). Teorema 3.6. Fungsi ∗

E{C − Z (A, B, X0)A} =

Z

{C(ω) − Z ∗[A(ω), B(ω), X0]A(ω)}dp Ω


28 adalah dasar untuk fungsi tujuan dari persoalan deterministik ekivalen pada titik X0 ∈ K. Di dalam pembahasan yang dikerjakan oleh Kall (1966) telah didemonstrasikan bahwa jika ukuran peluang pada ruang A, B kontinu absolut relatif terhadap ukuran lebesque pada ruang A, B dan kondisi tertentu dipenuhi maka fungsi tujuan ∅(X) yang merupakan persoalan deterministik ekivalen adalah kontinu differensiabel setiap tempat pada himpunan K Untuk investigasi kondisi optimalitas rencana X pada persoalan tahap pertama, dibutuhkan vektor CX = E[CZ ∗(A, B, X)A] dan bentuk linear Lx = (Cx1 , X) = E[CZ ∗(A, B, X)A]. Judin (1974) mengajukan formulasi kondisi perlu untuk optimalitas pada rencana X di dalam persoalan program stokastik dua tahap. Teorema 3.7. Jika X ∗ adalah rencana deterministik untuk persoalan dua tahap maka untuk sembarang X ∈ K, Lx (X ∗ ≤ Lx (X)

(3.28)

Bukti. Andaikan X ∗ adalah rencana optimal tetapi X rencana yang diterima untuk persoalan dua tahap. Dapat diperoleh : ∅(X ∗ ) ≤ ∅(X) E(CX ∗ + Z ∗(A, B, X ∗)(B − AX ∗ )) ≤ E(CX + Z ∗ (A, B, X)(B − AX)) (3.29) E(Z ∗ (A, B, X ∗)(B − AX ∗ )) ≥ E(Z ∗ (A, B, X)(B − AX))

(3.30)

Kurangkan (3.28) dari (3.27), dana diambil Z ∗ (A, B, X ∗) sebagai rencana optimal untuk masalah dual dan diperoleh hasil (3.26) Melalui pekerjaan yang diajukan oleh Efimov (1970) dan Judin (1974) diperoleh bahwa kemungkinan untuk membuat kegunaan secara ekonomi pada kondisi


29 (3.26). Vektor Z ∗ (A, B, X) adalah penyelesaian masalah dual untuk persoalan dua tahap dan merupakan vektor estimasi untuk produk jarang (kurang) atau berlebihan pada intensitas X dari metode teknologi setelah matriks teknologi A dan vektor permintaan B yang direalisasikan. Estimasi ini mendefinisikan pengaruh dari nilai divergensi pada pengeluaran untuk likuidasi ekonomi dari divergensi. Nilai m X

aij Zi∗ (A, B, X)Cj

i=1

menunjukkan keuntungan dari eksploitasi pada metode teknologi dengan intensitas singular, dengan perkiraan parameter persoalan direalisasikan sebagai elemen matriks A dan komponen vektor B dan C, tetapi estimasi produk dihitung untuk kasus di dalam eksploitasi metode teknologi yang dikerjakan dengan intensitas X. Jika vektor X ∗ mendefinisikan rencana awal optimal untuk persoalan program dua tahap, rekaptulasi keuntungan rata-rata pada intensitas X ∗ selama penggunaan metode produksi teknologi dihitung pada optimasi optimal yang tidak lebih kecil dari rekapitulasi keuntungan rata-rata yang dihitung pada estimasi optimal untuk sembarang rencana lain X yang dibolehkan. Akan diformulasi tanpa pembuktian teorema pada kondisi cukup dan perlu dari optimalitas untuk rencana persoalan program stokastik dua tahap. Teorema 3.8. Andaikan X ∗ titik internal (dalam) dari himpunan K, tetapi sebuah fungsi objektif ∅(X) pada persoalan deterministik ekivalen terhadap persoalan dua tahap yang diferensiabel di dalam neighbourhood dari titik X ∗ . Maka persoalan dual Z ∗ (A, B, X ∗) sedemikian hingga CX ∗ = E[C − Z ∗(A, B, X ∗)A] = 0

(3.31)

Jika dan hanya jika X ∗ adalah penyelesaian persoalan dua tahap (Judin, 1974).


30 3.4 Program Stokastik Tahap Ganda Persoalan program stokastik dinamik digeneralisasi oleh kasus dua tahap. Banyak persoalan praktis yang berupa perencanaan, perancangan dan manajemen tidak dapat digambarkan dengan bantuan model statis. Perencanaan dengan periode waktu yang panjang berkembang pada sistem ekonomi, kontrol operasional pada peralatan militer, regulasi pada proses teknologi dan persoalan lain yang termasuk pada parameter acak dan mengharuskan deskripsi untuk penggunaan model probabilistik dinamik. Untuk model bertujuan, metode program stokastik tahap ganda seringkali digunakan. Model program stokastik tahap ganda dan metode untuk realisasi secukupnya bergantung pada informasi mengenai nilai parameter di dalam kondisi persoalan, yang mana memiliki waktu untuk membuat keputusan selanjutnya. Terdapat persoalan dinamik yang mana tiap-tiap tahap berurutan disyaratkan untuk melengkapi kompensasi divergensi yang dikondisikan oleh kondisi realisasi persoalan dan oleh pembuatan keputusan tercepat (tahap sebelumnya). Pada masalah yang lain disyaratkan bahwa tiap-tiap tahap peluang yang memenuhi kendala tidak melebihi nilai tertentu yang diberikan sebelumnya atas ekspektasi matematika pada fungsi dari divergensi di dalam kondisi yang dibatasi oleh bilangan yang diberikan atau nilai dari fungsi pada parameter acak yang direalisasikan pada tahap sebelumnya. 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


31 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 keputuan 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. Untuk perhitungan selanjutnya dan analisis persoalan program stokastik tahap ganda, didefinisikan konsep yang diberikan berikut ini. Andaikan terdapat tahap ke-i yaitu Ωi , i = 0, 1, · · · , n untuk beberapa ruang kejadian elementer ωi , dimana Ω0 berisi satu elemen ω0 . Andaikan Ωk adalah descartian product Ωi , i = 1, 2, · · · , k; ω k = (ω1 , · · · , ωk ), Ωn = Ω dan andaikan pada Ω diberikan ukuran probabilistik p yang didefinisikan dengan cara : jika A ⊂ Ωk maka pk (A) =


32 p(A × Ωk+1 × · · · × Ωn ). Diperkenalkan ruang probabilistik (Ω, Σ, P ) dengan Σ berkaitan dengan σ-algebra, definisikan Pk sebagai kondisi ukuran probabilistik pada Ωk . Pk (A|ω k−1 ∈ B) =

Pk (A × B) Pk (Ωk × B)

Untuk sembarang A ⊂ Ωk , B ⊂ Ωk−1 . X k dinyatakan sebagai descartian product Xi , i = 1, 2, · · · , k; X k = (x1, · · · , xk ) ∈ X k , X n ≡ X dimana X0 , X1, · · · , Xn adalah barisan himpunan dari struktur sembarang X k ∈ X k , k = 0, 1, · · · , n dan himpunan X termasuk satu titik X0 . Andaikan mk diberikan sebagai fungsi vektor pada ϕk (ω k , X k ) berdimensi untuk setiap ω k ∈ Ωk , X k ∈ X k , k = 1, · · · , n dan juga untuk setiap ω ∈ Ω pada himpunan X fungsi ϕ0 (ω n , X n ). Masukkan himpunan acak G0k = G0k (ω k ) dan bk (ω k−1 )mk fungsi vektor. Bk berdimensi acak dari ω k−1 (dibatasi dan terukur) dinyatakan sebagai ruang Banach yang termasuk pada fungsi vektor berdimensi k P bk (ω k−1 ) m1. Akhirnya, Eωk (U (ω k )|ω k−1 ) menyatakan kondisi ekspektasi mai=1

tematika U (ω k ) dibawah perkiraan realisasi ω k−1 yang diketahui. Andaikan dibahas model berbeda pada persoalan program stokastik tahap ganda dengan menggunakan notasi yang diperkenalkan di atas. Andaikan terdapat persoalan program stokastik tahap ganda : Eϕ0 = (ω n , X n ) → inf

(3.32)

Eϕk = (ω k , X k ) ≥ bk

(3.33)

X k ∈ Gk , k = 1, 2, · · · , n

(3.34)


33 Untuk memformulasi persoalan secara lengkap, diperlukan titik luar apakah kendala yang tidak dapat dikondisikan atau kondisional, apakah penyelesaian persoalan ditentukan dengan strategi murni atau strategi campuran, dan di dalam kelas fungsi yang terukur atau distribusi yang akan mendapatkan penyelesaian. Persoalan praktisnya akan bergantung pada makna isi, penyelesaian pada tiaptiap tahap dapat dihitung sebagai vektor deterministik atau sebagai rule-function pada penyelesaian dari realisasi dan parameter acak yang diobservasi dari kondisi, atau sebagai distribusi menentukan distribusi kontinu Xk dengan perkiraan informasi yang diperlukan mengenai nilai yang direalisasikan data initial acak yang diperoleh model konkrit untuk persoalan dan struktur informasinya ditentukan oleh keputusan selanjutnya. Di dalam syarat-syarat yang diajukan oleh Ermolyev (1970), hasil-hasil persoalan stokastik tahap ganda dari rangkaian tipe - pengamatan - keputusan - pengamatan - · · · - keputusan Keputusan - pengamatan - keputusan - · · · - keputusan Andaikan dibahas bermacam-macam model persoalan program stokastik tahap ganda yang menggunakan klasifikasi yang diberikan oleh Judin (1972). Persoalan stokastik tahap ganda dengan kendala yang tidak dapat dikondisikan adalah

Z

ϕ0(ω n , X n )dFωn ,X n → inf

(3.35)

ϕk (ω k , X k )dFωk ,X k

(3.36)

X k ∈ Gk , k = 1, 2, · · · , n

(3.37)

Ωn ×X n

Z

Ωk ×X k

Pemilihan beberapa kelas yang paling menarik untuk aplikasi dari sejumlah struktur informasi yang merupakan persyaratan persoalan program tahap ganda


34 dengan kendala kondisional. Model kongkrit dari (3.30) − (3.32) pada kasus persoalan dengan kendala kondisional, diselesaikan dengan strategi campuran adalah: Z

ϕ0(ϕn , X n )dFωn ,X n → inf

(3.38)

ϕk (ω k , X k )dFωk |ω dFωk |ωk−1 ≥ bk (ω k−1 )

(3.39)

Ωn ×X n

Z Ωk ×X k

X k ∈ Gk (ω k ), k = 1, 2, · · · , n

(3.40)

Penyelesaian persoalan akan menjadi himpunan fungsi distribusi FX k |ωk . Biasanya untuk mengatakan persoalan diselesaikan dengan distribusi yang ditentukan kemudian jika FX k |ωk didefinisikan setelah realisasi dan pengamatan parameter acak ω k , distribusi yang ditentukan kemudian bergantung pada X k−1 dan ω k . Dikatakan bahwa persoalan yang diselesaikan dengan distribusi yang ditentukan sebelumnya, jika FX k |ωk didefinisikan setelah realisasi dan pengamatan ω k−1 tetapi sebelum pengamatan ω k , distribusi yang ditentukan sebelumnya bergantung pada X k−1 dan ω k−1 . Jika persoalan tahap ganda dengan kendala kondisional diselesaikan dengan strategi murni, model konkrit (3.30) (3.32) akan menjadi : Z

ϕ0 (ω n , X n )dFωn → inf

(3.41)

ϕk (ω k , X k )dFωk |ωk−1 ≥ bk (ω k−1 )

(3.42)

Ωn ×X n

Z Ωk ×X k

X k ∈ Gk (ω k ), k = 1, 2, · · · , n

(3.43)

Fungsi Xk dari parameter acak yang direalisasikan dan diamati pada kondisi dari persoalan merupakan penyelesaian. Persoalan diselesaikan dengan aturan yang ditentukan kemudian jika keputusan dibuat setelah realisasi dan pengamatan


35 ω k ; aturan-aturan yang ditentukan kemudian untuk penyelesaian sedemikian hingga X k = X k (ω k ). Dikatakan bahwa persoalan diselesaikan dengan aturan yang ditentukan sebelumnya jika keputusan dibuat setelah realisasi dan pengamatan ω k−1 , tetapi sebelum pengamatan ω k . Pada kasus aturan sebelumnya : X k = X k (ω k−1 )

Biasanya, persoalan (3.36) (3.38) atau (3.39) (3.41) dikenal sebagai persoalan stokastik tahap ganda dengan rigid model, jika kondisi (3.37) atau (3.40) tidak disertakan, keputusan tiap-tiap tahap dibuat setelah observasi kondisi dan keputusan pada tahap sebelumnya. Relasi tertentu yang dimiliki antara determinasi domain untuk persoalan dengan kendala yang tidak dapat dikondisikan dan kendala yang dapat dikondisikan. Pernyataan berikut akan menggeneralisasi hasil yang diperoleh, yang telah dikerjakan oleh Eismer, et al. (1971) untuk persoalan stokastik tahap ganda parsial linear. Pernyataan yang berikut diambil dari Judin (1974). Andaikan U adalah himpunan penyelesaian yang layak untuk persoalan stokastik tahap ganda dengan kendala yang tidak dapat dikondisikan U = {X k ∈ G1 × · · · × Gn |Eϕk (ω k , X k ) ≥ bk , k = 1, 2, · · · , n Dan V [bn (ω n−1 ] adalah himpunan penyelesaian (aturan penyelesaian, distribusi sebelum atau sesudah penyelesaian) pada persoalan dengan kendala kondisional. Teorema 3.9. Himpunan U dan V adalah terhubung oleh relasi U = {X n ∈ V [˜bn (ω n−1 )]|E˜bk (ω k−1 ) = bk , k = 1, 2, · · · , n}


36 Bukti : V˜ = {X n ∈ V [˜bn(ω n−1 )]|E˜bk (ω k−1 ) = bk , k = 1, 2, · · · , n}. Andaikan X n ∈ V˜ . Yang menyatakan bahwa

Eωk ϕk (ω k , X k ) =Eωk−1 {Eωk ϕk (ω k , X k )|ω k−1 ≥ Eωk−1˜bk (ω k−1 ) = bk ; k = 1, 2, · · · , n

karena X n ∈ U . Andaikan X n ∈ U , definisikan

˜bk (ω k−1 ) = Eωk {ωk (ω k , X k )|ω k−1 + {bk − Eωk ϕk (ω k , X k )} ≤ Eωk {ϕk (ω k , X k )|ω k−1 }, k = 1, 2, · · · , n Dengan definisi ˜bk (ω n−1 ) didapatkan Eωk−1 ˜bk (ω k−1 ) = bk . Sehingga X n ∈ V˜ . Akibat. Dengan fungsi sama ϕk (ω k , X k ) dan himpunan Gk , k = 1, 2, · · · , n domain penyelesaian layak dari persoalan (3.33) (3.35) dan (3.36) (3.38) atau (3.39) (3.41) bergantung pada persoalan yang diselesaikan dengan strategi campuran atau strategi murni bersamaan bentuknya jika dan hanya jika Ebk (ω k−1 ) = bk . Pernyataan di atas menyebabkan kemungkinan untuk memformulasi ulang hasil kualitatif dan seringkali juga menghitung metode yang dikerjakan untuk persoalan dengan kelas tertentu dan untuk investigasi konstruktif pada persoalan kelas lain. Relasi antara distribusi penyelesaian dan aturan penyelesaian sangat menarik. Jika fungsi ϕ0 adalah konveks dan komponen fungsi vektor ϕk adalah konkaf pada X dengan tiap-tiap ω, maka nilai optimal dari fungsi objektif yang dicapai pada distribusi penyelesaian dapat dicapai juga dengan aturan penyelesaian. Konveksitas dari ϕ0 dan −ϕk tidak menghabiskan kondisi dengan strategi optimal murni


37 dan strategi campuran yang didefinisikan menyatu dan nilai sama dari fungsi tujuan. Nilai fungsi tujuan untuk aturan optimal sebelumnya pada persoalan stokastik tahap ganda di dalam rigid model dengan nilai fungsi tujuan didistribusi penyelesaian optimal sebelumnya. Pernyataan lebih tegas untuk aturan penyelesaian sesudahnya dan distribusi penyelesaian diberikan berikut. Teorema 3.10. (a) Andaikan ukuran probabilistik Fω di dalam Ω = Ωn adalah kontinu (b) andaikan terdapat fungsi positif g0 (ω) dan gk (ω k ) berkendala atas menurut module ϕ0 (ω n , X n ) dan semua komponen ϕk (ω k , X k ). Maka penyelesaian aturan optimal sesudahnya untuk persoalan stokastik tahap ganda didefinisikan oleh nilai yang sama pada fungsi tujuan sebagai distribusi penyelesaian optimal sesudahnya. Bukti teorema 3.10 untuk persoalan stokastik satu tahap diberikan oleh Judin (1972). Persoalan program stokastik tahap ganda dengan kendala kondisional dapat disubstitusikan untuk sistem persamaan yang memenuhi pemisahan tahapan. Andaikan akan dibahas persoalan (3.39) (3.41) yang diselesaikan dengan strategi murni (dengan penyelesaian sebelum aturan penyelesaian sesudahnya).


38 Untuk definisi domain pada persoalan tahap ke-i berkaitan dengan himpunan : Ki = {Xi ∈ G0 |∃{yi+1 ∈ G0i+1 , · · · , yn ∈ G0n }; Eωi [ϕi (ω i , X i )|ω i−1 ] ≥ bi(ω i−1 ,

(3.44)

Eωi+s [ϕi (ω i+s , xi, yi+1 , · · · , yi+s )|ω i+s−1 ] ≥ bi+s (ω i+s−1 ) Jika {∀ωi+s−1 , · · · , ω n−1 , s = 1, 2, · · · , n − 1} G0i menyatakan proyeksi Gi terhadap hyper-plane dari koordinat yang didefinisikan oleh komponen vektor Xi . Persyaratan keberadaan dari vektor yi+s , s = 1, 2, · · · , n−i yang memenuhi kondisi (3.42) adalah ekivalen terhadap keberadaan kendala di dalam persoalan dua tahap. Kondisi cukup dan perlu untuk menyelesaikan persoalan (3.39) (3.41) adalah kondisi K1 6= ∅ (fungsi objektif (3.39) dengan asumsi berkendala). Jika disamping K1 6= ∅, Ki 6= ∅, i = 2, 3, · · · , n. Fungsi tujuan dari persoalan Qi(Xi ) pada tahap ke i mengatakan kondisional ekspektasi matematika ϕ0 (ω n , X n ) pada asumsi semua tahapan sebelum tahap ke i, himpunan ω i−1 merupakan parameter yang direalisasikan dengan kondisi persoalan dan komponen keputusan himpunan X i−1 , dan sesudah tahapan ke ∗ , · · · , Xn∗ . i keputusan optimal berikutnya :Xi+1

Qi (Xi ) = Eωn |ωi−1 (ω n , X i−1 , Xi , Xi+1 , · · · , Xn∗ )

(3.45)

Sejauh ini, definisi penyelesaian aturan optimal pada tahap ke i dari persoalan stokastik tahap ganda direduksi untuk menyelesaikan persoalan program matematika berikut inf Qi(Xi )

Xi ∈Xi


(3.46)

39 Aturan sesudahnya untuk penyelesaian adalah : Xi = Xi (ω i ), yi+s = yi+s (ω i+s ); s = 1, 2, · · · , n − i dan aturan sebelumnya untuk penyelesaian adalah : Xi = Xi (ω i−1 ); yi+s = yi+s (ω i+s−1 ); s = 1, 2, · · · , n − i . Jika fungsi tujuan dapat dipisahkan, yaitu ϕ0 (ω n , X n ) =

n P

ϕ0j (ω j , X j ) kita

j=1

mempunyai Qi(Xi ) = Eωi |ωi−1 {ϕ0 (ω i , X i ) + Q∗i+1 (ω i , X i )} . dimana Q∗i (ω i−1 , X i−1 ) = inf Eωi |ωi−1 {ϕ0(ω i , X i ) + Q∗i+1 (ω i , X i )}, i = 1, 2, · · · , n − 1 Xi ∈Ki

dengan i = n Q∗n (ω n−1 , X n−1 ) = inf Eωi |ωi−1 ϕ0n (ω n , X n ) Xi ∈Ki

. Analog dengan persoalan pemisahan tahapan untuk persoalan stokastik tahap ganda dengan strategi campuran yang dikonstruksikan.

3.5 Pengertian Pembentukan Pohon Skenario Dalam banyak aplikasi, sebaran peubah acak tidak diketahui atau walaupun diketahui, terlalu mahal untuk memperhatikan sebaran diskrit dengan banyak hasil yang mungkin atau menangani sebaran kontinu dengan integrasi numerik. Merupakan hal yang umum untuk memilih himpunan hasil representatif yang relatif kecil yang disebut skenario untuk menyajikan kejadian acak. Skenario dapat merupakan kuartil dari sebaran yang diketahui atau data historis, prediksi dan beberapa pohon atau dibangun dengan simulasi. Setiap skenario diberikan nilai probabialitas untuk merefleksikan kemungkinan kejadiannya. Untuk model


40 tahap ganda, informasi skenario dapat diorganisasikan ke dalam struktur pohon. Gambar 3.1, memberikan contoh pohon skenario untuk persoalan 4 tahap.

Gambar 3.1 : Pohon Skenario

Buhul akar menyatakan waktu sekarang atau bagian dari data yang diketahui. Pada tahap 2, terdapat 4 kemungkinan berbeda dan setiap dari padanya mempunyai berbagai hasil berbeda yang mungkin di tahap 3 dan seterusnya. Suatu skenario terdiri dari lintasan lengkap dari buhul akar ke satu buhul daun. Ambil jumlah tahap T dan jumlah hasil yang mungkin dalam setiap tahap dapat dilabel secara berurutan oleh Kt , untuk t = 1, · · · T . Buhul di setiap tahap dapat dilabel secara berurutan dengan kt = 1, · · · , Kt untuk semua t. Dt(k) menyatakan turunan langsung dalam waktu t dari buhul k. Misalnya dalam pohon skenario di Gambar 3.1. D3(1) memperlihatkan turunan langsung dari buhul 1 yang merupakan dua buhul paling kiri dalam waktu 3. Untuk setiap buhul daun k dalam tahap T , andaikan Ptk merupakan probabilitas terkait dari keterjadian skenario. Untuk t =T −1 , − − − − − − −1, pkt diberikan oleh pkt+1 = Σ1∈Dt+1 . . . p1t+1 dengan p1 = 1


41 Pohon keputusan memberikan kelenturan kepada pemodel untuk memilih skenario yang diperlukan untuk diperhatikan dan kepentingannya. Begitupun tidaklah praktis untuk memperhatikan terlalu banyak skenario. Ini terutama terjadi untuk persoalan dimana banyak mengandung faktor acak. Untuk mengoperasikan model program stokastik, pembentukan skenario dan pohon kejadian sangatlah penting. Dibawah ini diuraikan secara singkat metode pembentukan tersebut.

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 dimasa 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.


42 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 1 ¯ t Q−1 (w − w)] ¯ f (w) = (2φ)−p/2|Q|−1/2exp [− (w − w) 2 disini w adalah ekspektasi dari w dan Y matriks kovarian dan dapat dihitung dari data historis. Setelah parameter dari sebaran normal multivariat diestimasi kita 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. Begitupun, 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


43 ekspektasi dan matriks kovarian dipartisi secara analog sebagai     ¯1  Q11 Q12 w w ¯ =   dan Q =   w ¯2 Q21 Q22 Fungsi kepadatan peluang marginal dari w2 dengan diketahui w1 = w1∗ diberikan oleh 1 f (w|w1 = w1∗ ) = (2φ)−p2 /2|Q22.1|−1/2exp [− (w2 − w ¯2.1)t Q−1 ¯2.1)] 22.1 (w2 − w 2 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 − Q21Q−1 11 Q12 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. c. Pembentukan skenario menggunakan model vektor autoregressi Model vektor Autoregressi dapat dipakai untuk membentuk skenario. Dalam hal ini diambil ilustrasi tentang sistem simulasi Asset Liablity 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


44 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 ∼ N (o, Q), t = 1, 2. . . . , T Rit = ln(1 + πit ), i = 1, 2, . . . , m, t = 1, 2, . . . , T Dengan m jumlah deret waktu aset, φit laju perubahan diskrit dari peubah i ditahun t, Rt vektor dimensi-m dari laju majemuk, c vektor koefisien berdimensi m, V adalah matriks koefisien m × m, εt vektor dimensi m dari pencilan dan Q matriks kovariansi m × m Spesifikasi model vektor autoregressi harus dipilih secara hati-hati, walaupun beberapa hubungan inter-temporal diantara perolehan mungkin signifikan lemah yang didasarkan pada data historis, tidak berakibat bahwa hubungan ini juga bermanfaat untuk membentuk skenario.


BAB 4 ALGORITMA PEMBENTUKAN SKENARIO UNTUK PROGRAM STOKASTIK LINIER TAHAP GANDA

4.1 Pengantar Problem keputusan sekuensial tahap ganda muncul dalam berbagai pemakaian, yaitu keuangan (Carino et.al, 1998), sitem produksi (Boskma et.al, 1977), pembangkit daya (Nowak dan Romisch, 2000). Ketidak pastian dari data (misalnya, harga,harga permintaan, ketersediaan), bersama-sama dengan perubahan sekuensial data terhadap waktu, mengarah pada model optimisasi dengan ketidakpastian sekuensial. Model demikian dapat mengambil salah satu dari berikut: i) program stokastik tahap ganda (PSTG), atau ii) program dinamik stokastik (misalnya proses keputusan Markov). Sementara program dinamik stokastik (PDS) dapat merupakan pendekatan sesuai untuk situasi tertentu, kebanyakan aplikasi realistik menghendaki sejumlah besar peubah status yang mana sulit diakumulasi secara efisien oleh PDS. Untuk aplikasi realistik berskala besar dengan banyak peubah status dan kendala, PSTG memberikan alat pemodelan yang cocok. Namun, perkembangan yang ada saat ini untuk PSTG adalah keterbatasan komputasinya. Salah satu prasyarat untuk model PSTG adalah diskritisasi dari proses stokastik yang menyajikan perubahan data acak. Walaupun peubah acak yang membentuk proses ini kontinu, PSTG harus terselesaikan secara numerik dan ini menghendaki peubah acak diskrit (nyatanya, peubah ini harus hanyak mempunyai sejumlah hasil yang berhingga); proses diskrit ini dapat disajikan oleh pohon skenario dan ia biasanya suatu diskritisasi dari proses kontinu atau agregasi dari proses diskrit. 45 Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

46 Terdapat pendekatan sains dan seni terhadap diskritisasi/agregasi dari proses evolusi data. Sains muncul dalam pendekatan proses evolusi data; seni timbul dari realisasi bahwa diskritisasi rinci mengakibatkan persoalan yang tak mungkin secara numerik, sedangkan diskritisasi kasar mengakibatkan model yang dapat dipertanyakan dengan memperhatikan kejadian penting.

Keseimbangan yang

tepat tidaklah mudah. Untuk pendekatan sains terhadap pembentukan skenario, dapat diidentifikasi dua pendekatan terkait. Salah satunya didasarkan pada aproksimasi statistik (misalnya penyesuaian moment/target seperti dalam Hoyland dan Wallace, 2001), dan yang lainnya pada teori aproksimasi (seperti dalam Pflug (2001) dan Growe-Kuska et.al (2000)). Seperti untuk seni pembentukan skenario, timbul cerita dalam komunitas program stokastik, bahwa pohon skenario perlu memperhitungkan kejadian peluang kecil, biaya tinggi (yang kadang-kadang diacu sebagai katastropik). Sayangnya petunjuk kualitatif sulit untuk dikuantifikasi dan diimplementasikan. Dalam praktek, PSTG (misalnya P ) mungkin terlalu besar walaupun diselesaikan dengan memakai algoritma terbaik pada komputer tercepat jadi pendekatan yang diambil dalam literatur program stokastik menggantikan problem P oleh problema lainnya Pˆ , yang diformulasikan dengan menggantikan proses stokastik sebenarnya yang mendasari P dengan pendekatan kasar. Pandangan yang diambil dalam tulisan ini didasarkan pada pendekatan PSTG (yang lebih halus), dinyatakan dengan P oleh barisan aproksimasi Pk , problem keputusan didekati bukan difokuskan secara eksklusif pada pendekatan proses stokastik yang mendasari problema keputusan. Pandangan ini telah dilakukan untuk program stokastik linier (PSL) dua-tahap (misal Fauendorfer dan Kall (1988) serta Edirisinghe dan Ziemba (1996), dan lain-lain). Namun perluasan dari ide ini untuk PSLTG


47 belum begitu berhasil. Sementara pendekatan ini membawa pada aproksimasi yang konvergen secara asimptotik, batas atas menghendaki penyelesaian PSLTG dalam tiap iterasi, jadi mengakibatkan komputasi yang cukup ekstensif ditiap iterasi. Dalam tulisan ini, dikaji suatu algoritma untuk menyelesaikan PSLTG yang menggunakan beberapa alat sama seperti dalam PSL dua-tahap, jadi setiap mempertahankan kemampuan komputasi. Pada waktu bersamaan pendekatan ini juga memberikan optimalitas asimptotik. Kontribusi lainnya ialah algoritma yang diajukan memberikan realisasi operasional dari pengertian tentang prolongation yang pertama kali diajukan oleh Olsen (1976). Pemakaian prolongation Olsen dimotivasi oleh matematika dari hasil konvergensinya. Dalam tulisan ini, prolongation tidak hanya memberikan basis untuk hasil konvergensi, tapi juga memberikan kebijakan operasi untuk memperluas penyelesaian primal dari aproksimasi penyelesaian problem awal. Sementara prolongation demikian tidak dapat menghasilkan penyelesaian layak untuk semua skenario yang mungkin, metode ini memberikan kemungkinan pemenuhan kelayakan. Ini merupakan langkah penting untuk mengimplementasikan penyelesaian PSLTG yang diperoleh dari aproksimasi problem awal P .

4.2 Persiapan PSL merupakan paradigma ampuh untuk penjumlahan keputusan dengan adanya ketidakpastian.

Secara matematika, andaikan terdapat indeks waktu

t ∈ {1, · · · , T } dan horizon waktu yang terdiri dari T tahapan. Ketidakpas T tian dimodelkan oleh ruang peluang yang difilter Ξ, S, {F}t=1 , P . Ruang


48 sampel Ξ didefinisikan sebagai Ξ := Ξ1 × · · · × ΞT , dengan ΞT ⊂ Rrt , rt bilangan bulat positif. Hasilnya adalah ξ := (ξ1 , · · · , ξT ∈ Ξ dan ξ~ = (ξ1 , · · · , ξt ). σ-aljabar S merupakan himpunan kejadian yang diberikan nilai peluang oleh ukuran peluang P dan {F}Tt=1 adalah saringan pada S. Keputusan (recourse) pada tahap t merupakan peubah acak xt : Ξ → Rnt , dimana nt bilangan bulat positip. Biaya keputusan diwaktu t merupakan peubah acak ct : Ξ → Rnt . Untuk semua t ∈ {1, · · · , T } dan semua r ∈ {1, · · · , T }, bt : Ξ → Rmt dan Atr adalah matriks berharga riel mt × nt . Model matematika dari PSLTG dapat ditulis sebagai :

min cT1 x1 + E

x1 ,··· ,xT

T P

cTt (ξ~t )xt(ξ~t )

t=2

kedala A11x1 = b1 t P At1x1 + Atr xr (ξ~t ) = bt (ξ~t ) r=2

x1 > 0, xt(ξ~t ) ≥ 0 xt ∈ L2 (Ξ1 × · · · × ΞT , Rny )a.s.t = 2, · · · , T

Dalam formulasi ini, hendak berlaku hampiran pasti apabila dikatakan bahwa suatu kebijakan x = (x1, · · · , xT diambil terhadap filtrasi F = {Ft}Tt=1 , diperlihatkan dengan x ∈ F, berarti bahwa setiap xj terhadap σ-aljabar Ft terkait, yaitu xt ∈ Ft . Kebijakan demikian juga dikatakan nonantisipatif karena xt merupakan fungsi dari (ξ1 , · · · , ξt ) tapi bukan dari vektor acak (ξt+1 , · · · , ξT ). PSLTG dapat direformulasi dalam cara demikian sehingga peran yang dimainkan oleh {F}Tt=1


49 dimasukkan dalam model min

E

T P

cTt |Ft xt

t=1

 t P   E Atr xt |Ft = E[bt|Ft ]a.s for t = 1, · · · , T    r=1     xt ≥ 0 kedala    x = (x1 , · · · , xT ) ∈ F       xt ∈ L2 (Ξ, Rnt )

(4.1)

Seperti dalam Wright (1994), problem ini dinyatakan sebagai P (F d , F c ). Problem P (F d , F c ) memakai 2 filtrasi : argumen pertama (F d ) mengatakan filtrasi terhadap mana keputusan diambil sedangkan argumen kedua (F c ) mengatakan filtrasi terhadap kendala persamaan dipakai. Keputusan x diadaptasi terhadap t P Atr xt = bt dapat dipaksa untuk diadapF d jika x ∈ F d . Kendala persamaan r=1 c

tasi pada filtrasi F dengan menggantikan kedua sisi persamaan dengan ekspetasi t P c c Atr xt|Ft = E [bt |Ftc]. Dikatakan bahwa filbersyarat terhadap Ft yaitu E r=1

trasi G =

{Gt}Tt=1

lebih kasar dari pada filtrasi F = {F}Tt=1 jika Gt ⊂ Ft untuk

setiap t ∈ {1, · · · , T }. Andaikan Fˆ lebih kasar dari pada F. Problem keputusan P (Fˆ , F ) adalah min

E

T P

i h E cTt |Fˆt xi

t=1

 t P   E Atr xt |Ft = E[bt |Ft] a.s untuk t = 1, · · · , T    r=1     xt ≥ 0 kendala   ˆ    x = (x1, · · · , xT ) ∈ F     xt ∈ L2 (Ξ, Rnt )


50 ˆ F): juga dapat dibentuk problem kendala terpadu P (F,    xt > 0    kendala x = (x1, . . . , xT ) ∈ F      xt ∈ L2 (Ξ, Rnt ) Problem terpada penuh P (Fˆ , Fˆ ) adalah    xt > 0 kendala   xt ∈ L2 (Ξ, Rnt ) Jika F 1 dan F 2 dua filtrasi dengan F 1 lebih besar dari pada F 2 , maka kendala dalam P (F , F 2) lebih terbatas dari pada yang dalam P (F, F 1 ). Jadi, dengan memperhatikan nilai P (F , F 1) dan P (F, F 2) oleh v(P (F, F 1)) dan v(P (F, F 2)), berturut-turut terdapat v(P (F , F 1)) ≤ v(P (F, F 2))

(4.2)

Sekarang pandang suatu PSLTG dimana hanya bt acak, yaitu program stokastik hanya mempunyai ruas kanan acak, data lainnya deterministik. Maka ˆ Fˆ ) bernilai sama seperti nilai problem nilai dari problema terpadu lengkap P (F, kendala terpadu P (F , Fˆ ) (Wright, 1994). Ini mengakibatkan bahwa jika diperhatikan mengoptimalkan PSLTG layak dengan ruas kanan acak pada barisan filk+1 k untuk semua t ∈ (1, · · · , T ) dan andaikan nilai trasi {F k }∞ k=1 dengan Ft ⊆ Ft

optimal dari P (F k , F k ) yang dinyatakan dengan v k , maka v k adalah barisan naik monoton dari bilangan riel yang terbatas keatas oleh v(P (F, F)).

4.3 Pohon Skenario dan Filtrasi Apabila semua peubah acak memiliki dukungan berhingga ketidakpastian yang ada dalam model tahap ganda dapat disajikan oleh pohon skenario. Karena


51 algoritma bekerja dengan diskritisi, dalam bagian ini dikaitkan antara pohon skenario (yang dikrit) dan filtrasi, yang berlaku untuk peubah acak kontinu dan juga diskrit. Pembicaraan di bawah ini dari Rockafellar (1999). Suatu pohon skenario T = (N , A) merupakan pohon berakar dimana semua daun dengan kedalaman T . Himpunan buhul pada kedalaman t dinyatakan oleh S N t , jadi himpunan buhul adalah N = t N t . Himpunan acak buhul n dinyatakan oleh Cnt . Setiap besaran (n, m) memiliki sebaran bersyarat terkait qmn dari transisi P qnm = 1. ke n dengan diketahui bahwa n tercapai. Jadi m∈Cn

Secara alternatif pohon skenario dapat dideskripsikan dengan memakai filtrasi dimana σ-aljabar menyajikan informasi tersedia untuk pengambil keputusan. Dengan mengandaikan ξ~t mempunyai dukungan berhingga, σ-aljabar Ft = σ(ξ~t ) yang dibentuk oleh ξ~ berhingga dan juga filtrasi {F1 , · · · , FT }. Karena Ft berhingga ia dibentuk oleh partisi berhingga Bjt dari Ξ: Ξ=

kt [

Bit

dengan

Bjt ∩ Blt = ∅ untuk j 6= l

(4.3)

i=1

Hal yang sama benar untuk Fi+1 : kt+1

Ξ=

[

Bit+1

dengan Bjt+1 ∩ Blt+1 = ∅ untuk j 6= l

(4.4)

i=1

Sifat filtrasi mengakibatkan hubungan antara 2 partisi Bjt dan Bjt+1: ∀i, 1 ≤ i ≤ kt , ∃Jit+1 ⊆ {1, · · · , kt+1 } dengan

Bit =

[

Bkt+1

(4.5)

k∈Jit+1

~ t = 1, · · · , T } Perhatikan bahwa apabila dikatakan suatu kebijakan x = {xt(ξ), diambil terhadap filtrasi {Ft}Tt=1 , dimaksud bahwa setiap xt terukur terhadap σ-aljabar Ft terkait. Ini mengakibatkan :


52 ~ = konstan ∀ξ~ ∈ B t, ∀i, t x is F-adaptasi ⇔ xt (ξ) i

Hubungan antara filtrasi F dan pohon skenario dapat dibuat eksplasit dengan mengedentifikasi komponen Bit dari partisi dengan buhul terkait dari pohon skenario. Notasi :

a T = (N , A), pohon skenario merupakan pohon berakar dimana setiap buhul n termasuk dalam tahap tn , yaitu n ∈ N tn . Terdapat : 1 n = 1 dengan tl = 1 merupakan satu-satunya akar 2 buhul {n|tn = T } daun, dan 3 lintasan unit dari akar n = 1 kesembarang daun n dengan tn = T adalah suatu skenario. b S adalah komponen skenario (lintasan akar ke pohon); c s peluang skenario s ∈ S ; d Sn himpunan skenario yang melalui buhul n; e P¯n =

P

Ps peluang mencapai buhul n;

s∈Sn

f Hn ⊆ N buhul sebelum atau historis dari buhul n; g Hn pendahulu langsung atau buhul orang tua dari buhul n ∈ N , n ≥ 2; h Fn,s ⊆ N buhul penerus atau masa datang dari n pada skenario s; i Fn = ∪s∈S Fn,s buhul penerus dari n atau masa datang dari n ∈ N ;


53 j Cn ⊆ N buhul penerus langsung dari n atas anak dari n; k Qn,m peluang bersyarat mencapai buhul n diketahui bahwa buhul n telah dicapai; ¯n ⊆ Ξ himpunan skenario yang disajikan oleh buhul n; l B m cn ≡ ctn (ξ) dan Anm ≡ Atntm (ξ). Andaikan Fˆ filtrasi yang berkaitan dengan pohon T . PSLTG terhadap pohon skenario T adalah problem terpadu penuh P (Fˆ , Fˆ ). Problem terpadu penuh ini merupakan program linier dan dapat ditulis sehingga : P

min P

p¯n cTn xn

n∈N :¯ pn>0

: p¯n > 0Anm xm + Ann xn = bn

(4.6)

m∈Hn

xn ≥ 0∀n : p¯n > 0 Dual dari pohon ini P

max

bTn un

n∈N :¯ pn>0

(4.7)

P

ATnn un +

ATmn un ≤ p¯n cn

∀n : p¯n > 0

m=inFn :¯ pn >0

Dengan menggantikan peubah dual un dengan p¯n un dan membagi kendala ke n dengan p¯n diperoleh problem dual berikut : P

max

p¯n bTn πn

n∈N :¯ pn >0

ATnn πn

+

P

(4.8) qn,m ATmn πn ≤ cn

∀n : p¯n > 0

m∈Fn :¯ pn >0

ˆn . Versi berskala dari dual Penyelesaian optimal dinyatakan sebagai x ˆn dan π memiliki interprestasi probabilistik. Dalam bentuk ini, vektor dual π ˆn menyajikan


54 nilai marjinal bersyarat dari sumber daya (dipersyaratkan pada saat dibuhul n). Kendala kelayakan dual menyerupai kondisi optimalitas program dinamis yang menghendaki bahwa nilai marjinal dari sumber daya dibuhul n ditambah nilai lebih untuk masa datang tidak melampaui cn , harga dibuhul n. Degenerate subfiltrasi Terdapat korespondensi 1-1 antara filtrasi berhingga dan pohon skenario. Degenerate subfiltrasi Fˆ didefenisikan hanya menyatakan bahwa Fˆt = {Ξ, Ø}. Pohon skenario terkait disekitar pohon degenerate; ia hanya terdiri dari satu skenario (Gambar (4.1))

Gambar 4.1 : Pohon Degenerate

Jika dipartisi Ξt tertentu menjadi dua himpunan bagian Ξt1 dan Ξt2, maka pohon baru diperoleh seperti dalam Gambar (4.2). Kedua buhul dalam tahap t

Gambar 4.2 : Partisi Pertama ˆˆ menyajikan dua himpunan bagian. Filtrasi baru dinyatakan dengan F. Filtrasi


55 ˆ ini adalah sedemikian hingga Fˆt = Fˆ untuk τ < t dan ˆ Fˆt = σ Ξ1 × · · · × Ξt1 × · · · × ΞT , Ξ1 × · · · × Ξt2 × · · · × ΞT , Ø untuk s ≥ t. Prosedur pemutahiran pohon Prosedur pemutahiran pohon disini merupakan suatu metode sistematis untuk membentuk barisan subfiltrasi yang setiap tahapnya lebih mulus dari pada sebelumnya. Diketahui suatu pohon T , metode ini akan memberikan suatu pohon skenario baru T + . Prosedur mengandaikan bahwa suatu buhul n telah teridentifikasi dari lintasan sampel yang diberikan pada buhul ini akan dipartisi menjadi dua himpunan bagian untuk menghasilkan diskritisasi lebih mulus. Prosedur :

Langkah 1. Andaikan m ∈ N sehingga m 6∈ N . Andaikan bahwa m buhul baru; Langkah 2. Andaikan Tn = (An , Nn ) subpohon berakar dari T dengan buhul akar n; Langkah 3. Andaikan Tm = (Am , Nm ) menyatakan suatu pohon yang isomorphis dengan subpohon Tn ; mempunyai sifat graph sama seperti pohon Tn . Andaikan buhul akar dari Tn adalah m. Langkah 4. Andaikan T + = (A+ , N + ) dengan N + = N ∪ Nm dan A+ = A ∪ Am ∪ {(hn , m)} Untuk setiap n ∈ N + , hitung p¯n .


56 4.4 Algoritma Pembentukan Skenario ~ acak, data lainnya deterministik. Juga, Pada PSLTG dengan ruas kanan b(ξ) ~ Pohon awal mungkin degenerate atau dipersyaratkan bt fungsi affine dari ξ. pendekatan lainnya. Penyelesaian terhadap problema terpadu penuh ini menghasilkan pada tiap buhul n; (i) keputusan primal x ¯n dan (ii) vektor pengali dual x ¯n . Andaikan ξ~n suatu skenario yang berkaitan dengan buhul n. diketahui keputusan primal dan pengali dual untuk tiap buhul n, andaikan Bn suatu barisan optimal untuk buhul PL berikut :  P   min(cn − E[(ATrtn π ¯τ )|](ξ~n ))T xn   τ =t +1  n  P Atn tn xn = bn − Atntm x ¯m   m∈Hn :¯ pn >0     x ≥0 n PL ini mempunyai suatu penyelesaian karena penyelesaian dual π ¯n yang diperoleh dari problem terpadu penuh adalah layak untuk PL ini dan PL ini layak penuh xn }n∈N dan {Bn }n∈N untuk menghasilkan oleh pembentukan. Dapat dipakai x ¯1 , {¯ suatu kebijakan terhadap problem awal. Ini diperoleh dengan memakai persamaan berikut : ~ = B −1(b2 (ξ~2 ) − A21x ˆ1) x2,B (ξ) 2

(4.9)

~ =0 x2,N (ξ)

(4.10)

~ = B −1(btn (ξ~tn ) − xtn ,B (ξ) n

tX n −1

Atrn xr (ξ~r ))

(4.11)

r=1

~ =0 xtn,N (ξ)

(4.12)

Kebijakan ini akan disebut sebagai baris prolongasi optimal dan merupakan estimasi dari penyelesaian optimal terhadap problem awal. Untuk setiap x ¯1 tahap ~ dapat dihitung secara rekursif. ~ keputusan xt (ξ) pertama dan setiap skenario ξ,


57 Kebijakan demikian mungkin tak layak yaitu mungkin ada himpunan dari ukuran positif pada kebijakan tidak memenuhi kendala nonnegativitas. Pandang buhul n dan perhatikan buhul Hn dan Fn masa datang buhul ini. Bilamana skenario ξ~ teridentifikasi secara eksplisit untuk buhul n dan andaikan ~ m∈Hn dan secara eksplisit mengenal xn menyatakan kebijakan terkait {xtm , (ξ)} ketergantungannya pada skenario. Penyelesaian dual yang terkait dengan semua ¯ n definisikan nilai fungsi buhul masa datang dalam Fn akan dinyatakan dengan π kelebihan gn pada buhul n sebagai  X  ~ ¯ g  ( ξ; X ; Π ) := min(c − E[(ATrtn π ¯τ )|](ξ~n ))T xn n n n n    τ =tn +1    X ~ Atntn xn = bn (ξ~tn ) − Atntm x(ξ)    m∈Hn:¯ pn >0      xn > 0 gn dikatakan sebagai nilai fungsi kelebihan pada buhul n, karena koefisien hanya dari PL tadi dapat diartikan sebagai perunit harga yang mengakomodasi estimasi nilai kelebihan yang didasarkan pada pengali dual terkait dengan buhul n berikutnya. Penting untuk diperhatikan bahwa fungsi nilai kelebihan juga merupakan fungsi dari keseluruhan kebijakan yang menuju ke buhul n. Jadi, ξ~ berubah ¯n , skenario yang disajikan oleh buhul n. terhadap B Asumsi batas atas dan bawah Andaikan Un menyatakan batas atas dan Ln batas bawah untuk ekspek~ Xn ; Π ¯ n )|B ¯ n ]. Diandaikan baku bilamana fungsi nilai kelebitasi bersyarat E[gn (ξ; ¯ n , batas atas dan batas bawah sama dengan ekspektasi han adalah affine pada B bersyarat ini. Batas atas baku yang dipakai dalam program stokastik (misalnya batas Edmundson-Madansk) memenuhi asumsi ini sekarang didefinisikan parame-


58 ter kesenjangan yang diperlihatkan dengan δn : δn = Un Ln

(4.13)

~ =π ¯m . Peubah acak π ¯n : Ξ → Rmt didefinisikan sebagai π ¯ n (ξ) ¯m bilamana ξ~ ∈ B Dievaluasi kebijakan saat ini untuk tiap buhul dengan mengevaluasi parameter kesenjangan δn dan juga indeks ketaklayakan. Ketaklayakan akan didasarkan pada ukuran himpunan ξ dimana kebijakan melanggar batas nonnegativitas. definisikan : ~ ≥ 0) η¯n := 1 − P (ξ~ ∈ Ξ|xtn,B (ξ)

(4.14)

η¯n tidak mudah ditentukan, namun batas atasnya lebih mudah diselesaikan. Per~ suatu hitungan dari peluang ini juga difasilitasi oleh kenyataan bahwa xtn,B (ξ) fungsi affine, seperti dapat terlihat dari struktur baris prolongasi optimal. Dalam setiap kejadian, andaikan ηn ≥ ηˆn menyatakan indeks kelayakan untuk buhul n. Sekarang algoritma pembentukan skenario dapat dituliskan sebagai berikut:

Langkah 0. Pilih parameter toleransi positif ε1 , ε2 dan εs , dan dipilih ε3 > εs buat k = 1. Langkah 1. Andaikan F 1 = {F}Tt=1 filtrasi degenerate, dengan Ft = {Ξt , Ø}. Definisikan pohon degenerate sebagai : a T 1 = (N 1 , A1) terdiri dari lintasan tunggal b S 1 skenario tunggal, p1s = 1 c p¯n1 = 1 apabila n ∈ N 1 d qnm = 1 apabila n ∈ {1, · · · , T − 1}, m ∈ Fn (a) bn1 := E[btn ]


59 Langkah 2. (selesaikan persoalan lengkap). Selesaikan PSLTG yang terkait dengan pohon T k . PSLTG merupakan problem terpadu lengkap. Penyelesaian dari k : j, m ∈ \k } dan problem ini menghasilkan kebijakan primal-dual {xkj , πm

nilai optimal v k . Langkah 3. Hitung δn dan ηn untuk tiap buhul n ∈ N k dengan p¯n > ε3 (jika buhul n adalah p¯n ≤ ε3, maka buhul ini diabaikan). Langkah 4. (aturan penghentian) Jika δn < ε1, ηn < ε2∀n ∈ N k dan ε3 ≤ ε2, stop; kebijakan yang dibentuk oleh basis prolongasi optimal sesuai untuk problem awal. Langkah 5. (reduksi ε3) Jika p¯n < ε3 ∀n ∈ N k maka buat ε3 ← ε3 /2 dan kembali kelangkah 3. pn > ε3 Langkah 6. (pemisahan) Andaikan L = n ∈ N k |¯ ¯ sedemikian a Jika terdapat suatu n ∈ L, sehingga δn > ε1 maka ambil n hingga δn = maxn∈L {δn }. Gunakan prosedur pemutahiran pohon di buhul n ¯ . Hasil ini dalam pohon skenario baru T k+1 . Buat k ← k + 1 dan kembali kelangkah 2. b Jika untuk semua buhul n ∈ L, δn < ε1 , namun ada buhul m ∈ L, ¯ buhul dalam L dengan ηn terbesar. sehingga ηm ≥ ε2 , maka andaikan n Pakai prosedur pemutahiran pohon pada buhul n ¯ . Hasil ini dalam pohon skenario baru T k+1 . Buat k ← k + 1 dan kembali kelangkah 2.


BAB 5 KESIMPULAN

Beberapa persoalan optimisasi yang berskala besar dapat diselesaikan dengan menggunakan model program stokastik. Ukuran dari persoalan akan berpengaruh secara langsung terhadap banyaknya skenario yang digunakan untuk model dengan ketidakpastian. Untuk menyelesaikan aproksimasi yang dibangun oleh diskritisasi, maka model peluang dinyatakan dengan ketidakpastian. Kejadian di dalam contoh pada masalah asal digambarkan oleh pohon skenario diskrit, banyak skenario dapat bertambah besar karena algoritma terdahulu memerlukan penggabungan (skenario), sehingga persoalan optimisasi dapat diselesaikan dengan tepat waktu. Namun pendekatan program stokastik standar belum tersedia sarana untuk bagaimana menetapkannya, sehingga gabungan pohon skenario dapat dibangun (dikembangkan). Prosedur pemutahiran pohon disini merupakan suatu metode sistematis untuk membentuk barisan subfiltrasi yang setiap tahapnya lebih mulus dari pada sebelumnya. Pada bagian akhir pembahasan, digambarkan suatu algoritma yang membangun barisan pohon skenario yang mana tidak hanya menyediakan konvergensi asimptot, tetapi juga menyediakan ukuran optimalitas (menggunakan (Σn pn σn )) pada keputusan tahap pertama. Lebih jauh, algoritma ini menyediakan barisan kebijakan (prolongations), yang dapat digunakan untuk menyesuaikan kepada realisasi aktual pada setiap tahapan.


61 Dalam tulisan ini, prolongation tidak hanya memberikan basis untuk hasil konvergensi, tapi juga memberikan kebijakan operasi untuk memperluas penyelesaian primal dari aproksimasi penyelesaian problem awal. Sementara prolongation demikian tidak dapat menghasilkan penyelesaian layak untuk semua skenario yang mungkin, metode ini memberikan kemungkinan pemenuhan kelayakan. Ini merupakan langkah penting untuk mengimplementasikan penyelesaian PSLTG yang diperoleh dari aproksimasi problem awal P . Sehingga diperoleh alat untuk mendukung proses pengambilan keputusan yang mengandung ketidakpastian, dan diperoleh juga satu metode untuk membentuk jumlah skenario yang efesien.


DAFTAR PUSTAKA Birge, J. R., and F. V. Louveaux. 1997. Introduction to Stochastic Programming. Springer Series in Operations Research, Springer-Verlag, New York. Boskma, K., R. J. Peters, and H. A. E. Kuper. 1977. Stochastic programming in production planning: a case with nonsimple recourse. Stastistica Neerlandica 31, 113-126. Carino, D. R., D. H. Myers, and W. T. Ziemba. 1998. Concepts, technical issues and uses of the Russell-Yasuda-Kasai financial planning model. Oper. Res. 46(4) 450-462. Casey, M.; Sen, S. 2005. The Scenario generation algorithm for multistage stochastic linear programming, Mathematics of Operations Research 30, 615-631. Dantzig, G. B. 1956. Recent Advances in Linear Programming, Management Sci. 2, 131 144 Dupaˇcová, J.; Consigli, G.; Wallace, S. W. 2000. Scenarios for multistage stochastic programs, Annals of Operations Research. 100. 25-53. Dupaˇcová, J.; Gröwe-Kuska, N.; Römisch, W. 2003. Scenario reduction in stochastic programming: An approach using probability metrics, Mathematical Programming Ser. A 95, 493-511. Edirisinghe, N. 1999. Bounds-based approximations in multistage stochastic programming. Ann. Oper. Res. 85 103-127. Edirisinghe, N., and W. Ziemba. 1996. Implementing bounds-based approximations in convex-concave two stage stochastic programming. Math. Programming 78(2) 314-340. Efimov, V. M. 1970. Optimal Estimations under Uncertainty, Econ. Math. Methods, 6, No. 3. Eismer, M. J., Kaplan, R. S., dan Soden, J. V. 1971. Admissible Rules for the E-Model of Chance-Constrained Programming, Management Sci., No. 17. Ermolyev, J. M. 1970. Stochastic Quasi-Gradient Methods and Applications, Ph.D. in the Institute of Cybernetics Ukrainian S.S.R. Academy of Sciences, Kiec. Fauendorfer, K. 1996. Barycantric sceanario trees in convex multistage stochastic programming. Math. Programming B 75, 277-293. Fauendorfer, K., and P. Kall. 1988. A solution method for SLP recourse problems with arbitrary multivariate distributions-the independent case. Problems Control Inform. Theory 17, 177-205. Growe-Kuska, N., J. Dupacova, and W. Römisch. 2000. Scenario reduction in stochastic programming: an approach using probability metrics. Preprint, Institut fur Mathematik, Humboldt-Universitat zu Berlin, Berlin, Germany. 62 Sawaluddin : Pembentukan Pohon Skenario Untuk Problema Keputusan Tahap Ganda, 2008 USU e-Repository © 2008

63 Heitsch, H. ; Römisch, W. 2003. Scenario reduction algorithms in stochastic programming, Computational Optimization and Applications. 24, 187-206. Higle, J. L. ; Rayco, B. And Sen, S. 2002. Stochastic Scenario Decomposition for Multi-Stage Stochastic Programs. NSF grant DMI-9978780. Hochreiter, R., and G.Ch.Pflug, 2004. Scenario Tree Generation as a Multidimensional Facility Location Problem, Working Paper, University of Vienna Hoyland, K., and Wallace, S. W. 2001. Generating scenario trees for multi-stage decisions problems. Management Sci. 47, 295-307. Hoyland, K. ; Kaut, M. ; and Wallace, S. W. 2003. A Heuristic for momentmatching scenario generation, Computational Optimization and Applications 24, 169-185. Jamshidian, F, and Y. Zhu. 1997. Scenario Simulation: Theory and Methodology, Finance and Stochastics,pp. 43-67. Judin, D. B. 1972. Multi-Stage Planning Problems under Risk and Uncertainty, Technologi Cybernetics. No. 6. Judin, D. B. 1974. Mathematical Methods of Management under Uncertainty, Moscow, Soviet Radio. Kall, P. 1966. Qualitative Aussagen zu einigen Problemen der stochastischen Programmierung, Z. Wahrscheinlichkeitstheorie und verw. Gebiete. 6, 246 272. Kaut, M. ; Wallace, S. W. 2003. Evaluation of scenario-generation methods for stochastic programming, Stochastic Programming E-Print Series 14, (speps.org). Nowak, K., and Römisch, S. W. 2000. Stochastic Lagrangian relaxation applied to power scheduling in a hydrothermal system under uncertainty. Ann. Oper. Res.100, 251-272. Olsen, P. 1976. Discretizations of multistage stochastic programming. Math. Programming Stud. 6, 111-124. Pennanen, T. ; Koivu, M. 2005. Epi-convergent discretizations of stochastic program via integration quadratures, Numerische Mathematik 100, 141-163. Pflug, G. Ch. 2001. Scenario tree generation for multiperiod financial optimization by optimal discretization, Mathematical Programming 89, 251-271. Robert, Kusta-Gröwe and Rmisch. 1991. Scenario Reduction in Stochastic Programming. An Approach using Probability Metrics. Math. Programming, 15 31 Rockafellar, R. T. 1999. Duality and optimality in multistage stochastic programming. Ann. Oper. Res. 85, 1-19. Wright, S. E. 1994. Primal-dual aggregation and disaggregation for stochastic linear programs. Math. Oper. Res. 19, 893-908.


PEMBENTUKAN POHON SKENARIO UNTUK PROBLEMA KEPUTUSAN TAHAP GANDA

Recommend Documents