MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS

MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS

TESIS

Oleh

FAJRIANA 067021002/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008

Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS

TESIS

Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

FAJRIANA 067021002/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008


Judul Tesis

: MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS Nama Mahasiswa : Fajriana Nomor Pokok : 067021002 Program Studi : 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: 16 Juli 2008


Telah diuji pada Tanggal 16 Juli 2008

PANITIA PENGUJI TESIS Ketua Anggota

: Dr. Sutarman, M.Sc : 1. Prof. Dr. Herman Mawengkang 2. Dr. Tulus, M.Si 3. Drs. Open Darnius, M.Sc


ABSTRAK Perogram Stokastik berhubungan dengan suatu problem pengambilan keputusan yang optimal dalam keadaan ketidakpastian. Standar pendekatan untuk memformulasikan program stokastik didasarkan pada asumsi proses stokastik tidak bergantung pada keputusan-keputusan optimisasi. Penelitian ini menjelaskan suatu kelas problem keputusan optimisasi mempengaruhi waktu penemuan informasi untuk subset dari parameter-parameter ketidakpastian. Penelitian ini memperluas pendekatan standar pemodelan dengan mempresentasikan formulasi pemograman disjunctive yang mengakomodasikan program-program stokastik untuk problem pada kelas ini. Suatu sifat set secara teori untuk reduksi ukuran dari model yang teridentifikasi. Kata Kunci : Program stokastik, ketidakpastian, optimisasi.

i Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

ABSTRACT Stochastic programming deals with the problem of making optimal decisions in the presence of uncertainty. The standard approach to formulating stochastic programs is based on the assumption that the stochastic process is independent of the optimization decisions. We address a class of roblems where the optimization decisions influence the time of information discovery for a ubset of the uncertain parameters. We extend the standard modeling approach by presenting disjunctive programming formulation that accommodates stochastic programs for this class of problems. A set of theoretical properties that lead to reduction in the size of the model is identified. Keywords : Stochastic programming, uncertainty, optimization.

ii Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

KATA PENGANTAR Pertama penulis panjatkan syukur kehadirat Allah yang Maha Pengasih Lagi Penyayang atas segala Rahmat dan karunia-Nya yang telah diberikan kepada penulis, sehingga penulis dapat menyelesaikan tesis ini tepat pada waktunya. Tesis ini berjudul ”Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas”. Tesis ini merupakan persyaratan tugas akhir pada Program Studi Matematika SPs Universitas Sumatera Utara. Pada kesempatan yang baik ini, penulis menyampaikan ucapan terimakasih dan penghargaan yang sebesarbesarnya kepada: Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.Ak selaku Rektor Universitas Sumatera Utara Prof. Dr. Ir. T. Chairun Nisa B, M.Sc selaku Direktur Sekolah Pascasarjana yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara Medan. Prof. Dr. Herman Mawengkang selaku ketua Program Studi Magister Matematika SPs Universitas Sumatera Utara, dan juga sebagai anggota komisi pembimbing yang telah banyak membantu dalam penulisan tesis ini. Dr. Saib Suwilo, M.Sc selaku sekretaris Program Studi Magister Matematika SPs Universitas Sumatera Utara. Dr. Sutarman, M.Sc selaku ketua komisi pembimbing yang telah banyak membantu dalam penulisan tesis ini.

iii Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

Seluruh Staf Pengajar pada Program Studi Magister Matematika SPs Universitas Sumatera Utara, yang telah memberikan ilmunya selama masa perkuliahan; Misiani, S.Si selaku staf Administrasi program studi Magister Matematika SPs Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis. Seluruh rekan-rekan mahasiswa angkatan ke-lima tahun 2006/2007 Program Studi Magister Matematika SPs Universitas Sumatera Utara atas kerjasama dan kebersamaan dalam mengatasi berbagai masalah yang dihadapi selama perkuliahan, sehingga tugas-tugas bersama dapat diselesaikan dengan baik. Secara khusus penulis menyampaikan rasa terima kasih kepada suami tercinta Ibrahim Chalid, anak tersayang Rifa Maghfirah Chalid, dan bunda yang telah melahirkan Ati Roswar, serta seluruh keluarga berkat dorongan dan perhatiannya yang disertai dengan doanya, penulis dapat menyelesaikan pendidikan ini. Semoga tesis ini dapat bermanfaat bagi pembaca, dan pihak-pihak lain yang memerlukannya. Tentunya sebagai manusia tidak pernah luput dari kekurangan sehingga tulisan ini jauh dari sempurna.

Medan, Penulis,

Fajriana

iv Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

Juli 2008

RIWAYAT HIDUP Penulis dilahirkan di Lhokseumawe pada tanggal 20 Juli 1976 dari seorang ayah bernama M. Yusuf Tom (Alm) dan Ibu bernama Hj. Ati Roswar, A.Ma. Penulis merupakan putri tunggal. Jenjang pendidikan dasar mulai dari SD ditamatkan di daerah kelahiran penulis, yaitu di SD Muhammadiyah Lhokseumawe pada tahun 1989 dan lulus MTs Bustanul Ulum Langsa Aceh Timur pada tahun 1993. Pada tahun 1995 penulis lulus dari SMA Muhammadiyah Lhokseumawe Nanggro Aceh Darussalam (NAD) dan pada tahun yang sama juga lulus seleksi UMPTN masuk Universitas Syiah Kuala Banda Aceh. Penulis memilih Program Studi Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) UNSYIAH dan menamatkannya pada tahun 2001. Pada tahun 2006 penulis diterima di Sekolah Pascasarjana Universitas Sumatera Utara (USU) pada Program Studi Matematika FMIPA dengan beasiswa PEMDA NAD melalui Universitas Malikussaleh. Saat ini penulis bekerja sebagai tenaga pengajar pada Fakultas Teknik Universitas Malikussaleh Lhokseumawe Nanggro Aceh Darussalam (NAD)

v Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

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

i

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

ii

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

iii

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

v

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

vi

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

viii

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

1

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

1

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

2

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

2

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

2

1.5 Metode Penelitian . . . . . . . . . . . . . . . . . . . . .

3

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

4

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .

9

3.1 Standar Program Stokastik . . . . . . . . . . . . . . . .

13

3.2 Tipe-Tipe Ketidakpastian . . . . . . . . . . . . . . . . .

14

3.2.1 Ketidakpastian Exogenous . . . . . . . . . . . . . .

15

3.2.2 Ketidakpastian Endogenous . . . . . . . . . . . . .

16

BAB 4 MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS . . . . . . . . . . . . . 20 4.1 Uraian Masalah . . . . . . . . . . . . . . . . . . . . . . vi Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

20

4.2 Contoh-contoh Problem . . . . . . . . . . . . . . . . . . 4.2.1 Pengembangan Kapasitas pada Proses Jaringan

22

. . .

22

4.2.2 Problem Ukuran-ukuran . . . . . . . . . . . . . . .

23

4.3 Notasi dan Definisi . . . . . . . . . . . . . . . . . . . .

25

4.4 Model

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

27

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

32

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

34

vii Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

DAFTAR GAMBAR

Nomor

Judul

Halaman

3.1

Pohon Skenario dengan parameter-parameter tidak pasti ξ1 , ξ2

11

3.2

Penyajian alternatif untuk pohon skenario pada gambar 3.1; variabel-variabel xst . . . . . . . . . . . . . . . . . . . . .

13

3.3

Keputusan bergantung pohon-pohon skenario untuk problem ladang gas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1

Penyajian menurut bagan problem proses jaringan . . . . . .

viii Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

21

BAB 1 PENDAHULUAN

1.1 Latar Belakang Program stokastik berhubungan dengan problem pengambilan keputusan yang optimal dalam keadaan ketidakpastian. Ketidakpastian yang disajikan oleh distribusi probabilitas. Interaksi antara stokastik dan proses pengambilan keputusan dimodelkan sedemikian sehingga pengambil keputusan mempunyai pilihan yang sesuai berdasarkan bagaimana ketidakpastian itu berkembang. Dari perspektif pemodelan, terdapat banyak kajian dalam literatur program stokastik yang berkaitan dengan problem ketidakpastian exogenous (Jonsbraten (1998)). Yaitu keputusan optimal yang tidak dapat mempengaruhi proses stokastik. Pflug (1990) yang pertama mengajukan kasus tentang ketidakpastian endogenous, yaitu proses stokastik tergantung pada keputusan yang optimal. Penelitian sebelumnya pada kelas ketidakpastian ini terbatas pada beberapa makalah saja. Penelitian ini berkaitan dengan ketidakpastian endogenous. Jadi hanya mengkaji ulang penelitian sebelumnya dalam literatur program stokastik untuk ketidakpastian jenis ini. Literatur review terhadap problem ketidak-pastian exogenous dapat ditemukan di dalam Sahinidis (2004), Schultz (2003) dan Birge (1997). Secara umum, rancangan keputusan dapat mempengaruhi proses stokastik dalam dua cara. Pada satu sisi, pengambil keputusan dapat menyebabkan perubahan distribusi probabilitas dengan membuat satu keputusan kemungkinan.

1 Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

2 Pada sisi lain, pengambil keputusan tidak dapat secara langsung mempengaruhi distribusi probabilitas, tetapi dapat untuk mendapatkan informasi yang lebih akurat dengan menyelesaikan ketidakpastian (secara parsial). Perbedaannya adalah bahwa ketika kasus pertama pengambil keputusan dapat memaksa satu keputusan yang mungkin untuk menjadi yang lebih mungkin, kasus kedua pengambil keputusan hanya dapat menjadi lebih yakin mana keputusan yang dapat terjadi pada masa depan.

1.2 Perumusan Masalah Model program stokastik yang diperhatikan dalam penelitian ini memiliki karakteristik tertentu. Karakteristik ini memiliki adanya ketergantungan antara peubah. Sehingga metode penyelesaian yang harus digunakan untuk program stokastik ini tidak dapat mengunakan program stokastik yang umum. Disini akan dikembangkan model program stokastik dan metode penyelesaiannya.

1.3 Tujuan Penelitian Adapun tujuan dalam penelitian ini adalah untuk memperoleh suatu model keputusan dengan parameter tidak pasti dan teknik penyelesaiannya.

1.4 Kontribusi Penelitian Kontribusi penelitian ini adalah mengembangkan suatu model program stokastik untuk dapat menyelesaikan problem keputusan tidak pasti.


3

1.5 Metode Penelitian Penelitian ini bersifat literature dan dilakukan dengan mengumpulkan informasi dari jurnal- jurnal. Adapun langkah-langkah yang dilakukan adalah sebagai berikut:

1. Menguraikan program stokastik 2. Memodelkan peubah keputusan dengan parameter tidak pasti 3. Teknik penyelesaian dengan parameter tidak pasti


BAB 2 TINJAUAN PUSTAKA

Viswanath et al. (2004) menyajikan suatu contoh tipe pertama ketidakpastian endogenous di mana keputusan-keputusan optimisasi dapat mempengaruhi distribusi probabilitas. Mereka menganggap bahwa problem suatu jaringan traversal two stage pada masing-masing busur (arc) dihubungkan dengan suatu probabilitas yang menunjukkan probabilitas pada busur yang ada ke traversal setelah suatu kejadian acak. Seluruh tujuannya adalah untuk meminimumkan panjang lintasan terpendek yang diharapkan dari sumber ke tujuan setelah suatu kejadian acak yang akan membawa sebagian dari busur di dalam jaringan yang tidak tersedia ke traversal. Pada stage pertama, investasi-investasi dibuat pada beberapa busur dengan meningkatkan probabilitas-probabilitas busur ini akan ada ke traversal setelah kejadian acak. Ini diikuti oleh kejadian acak. Di dalam stage kedua, suatu alur (path) dari sumber ke tujuan itu harus dilewati dengan menggunakan busur-busur yang tersedia. Problem ini muncul di dalam merencanakan pembebasan bencana antara kota-kota dengan possibilitas bahwa beberapa ruterute saling berhubungan yang tidak dapat dipakai sebagaimana mestinya karena suatu bencana (kejadian acak). Problem perencanaan pembangunan ladang gas ( Goel & Grossmann (2004)) merupakan suatu contoh dunia nyata dari tipe kedua ketidakpastian endogenous, dimana keputusan-keputusan yang optimal mengontrol resolusi ketidakpastian. Pada problem ini, suatu set ladang (reservoir-reservoir gas) yang tersedia untuk produksi. Ukuran dan kualitas cadangan dari ladang ini adalah tidak 4 Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

5 pasti. Ketidakpastian di dalam suatu ladang terselesaikan hanya ketika suatu fasilitas dipasangkan di ladang tersebut. Jadi, keputusan-keputusan investasi mengontrol waktu kapan ketidakpastian akan diselesaikan. Oleh karena itu, terlepas dari pertimbangan pengeluaran modal yang besar dan pendapatan yang dihubungkan dengan investasi pada suatu ladang, itu juga penting untuk menentukan potensi memperoleh informasi berharga sebagai hasil investasi. Informasi ini dapat berperan penting untuk keputusan-keputusan yang baik pada masa mendatang. Jonsbraten et al. (1998) pertama mengajukan problem dengan ketidakpastian endogenous dimana keputusan-keputusan optimisasi menentukan waktu kapan beberapa ketidakpastian akan diselesaikan. Pengarang-pengarang memperkenalkan suatu versi ”problem ukuran-ukuran” (Jorjani et al., 1999), suatu pabrik yang berhubungan dengan problem dimana permintaan untuk suatu produk harus dicukupi dalam berbagai ukuran-ukuran sepanjang suatu time-span yang diberikan. Komponen variabel dari biaya produksi untuk masing-masing ukuran merupakan tidak-pasti dan ketidakpastian yang dihubungkan dengan suatu ukuran diselesaikan hanya setelah ukuran itu dihasilkan untuk pertama kali. Dengan demikian, keputusan-keputusan produksi membantu pengambil keputusan mengendalikan waktu ketika ketidakpastian-ketidakpastian di dalam biaya produksi untuk berbagai ukuran-ukuran akan diselesaikan. Pengarang-pengarang menyajikan suatu enumerasi algoritma implisit untuk problem-problem dengan limitasi yang ada hanya dua keputusan stage. Held dan Woodruff (2003) menyajikan metode-metode solusi heuristik untuk problem interdiksi jaringan multistage. Contoh lain tentang menentukan


6 waktu kapan keputusan-keputusan ketidakpastian-ketidakpastian yang optimal dalam berbagai parameter-parameter akan diselesaikan. Problem ini melibatkan dua pemain bersaing: operator dan interdiktor. Masing-masing stage di dalam problem ini, sasaran operator untuk melewati jaringan sepanjang alur terpendek yang tersedia. Sementara interdiktor menginginkan untuk memperpanjang alur yang diambil oleh operator sedapat mungkin dengan penghapusan sebagian dari gambar node di dalam jaringan. Struktur jaringan yang tepat diketahui untuk operator tetapi bukan untuk interdiktor. Berbagai struktur jaringan yang mungkin didalilkan untuk interdiktor dalam bentuk suatu set skenario. Selama masing-masing stage, interdiktor mengeliminasikan beberapa node dari jaringan didasarkan pada skenario yang didalilkan. Operator kemudian melewati jaringan sepanjang alur yang terpendek yang ada menggunakan sisa node-node di dalam jaringan. Karena interdiktor itu dapat mengamati operator melewati jaringan, bagian dari ketidakpastian di dalam struktur dari jaringan itu diselesaikan selama masing-masing stage. Diberikan alur terpendek di dalam jaringan secara implisit yang ditentukan oleh keputusan-keputusan yang interdiksi, tujuan dari interdiktor adalah untuk menginterdiksikan node-node yang informasi diperoleh sangat berharga dan panjang yang diharapkan dari alur terpendek adalah dimaksimalkan. Problem ini dihadapi oleh pegawai pabean (interdiktor) berusaha untuk mencegah penyelundup-penyelundup (operator) dari barang-barang penyelundupan ke dalam negeri. Jonsbraten (1998b, hal. 149-174) mengajukan problem dari rangkaian secara optimal pengeboran sumur-sumur produksi dalam suatu reservoir minyak. Tidak hanya mengebor sumur minyak meningkatkan kapasitas produksi di reservoir, juga memberikan informasi yang lebih akurat tentang kualitas dari reservoir.


7 Dengan demikian, kontribusi keputusan-keputusan investasi untuk resolusi ketidakpastian. Pengarang beranggapan bahwa algoritma enumerasi implisit resolusi ketidakpastian di modelkan mengunakan pendekatan Bayes. Ahmed (2000) menyajikan problem dimana distribusi probabilitas bergantung pada keputusan-keputusan yang optimal didasarkan pada aksioma pilihan Luce (Luce, 1977), yang menyebutkan bahwa state probabilitas dengan individual memilih item x dari suatu pilihan set R yang diberikan oleh PrR =

PU (x) 0 , U (x )

x0 ∈R

di mana U (x) adalah utiliti dari item x kepada setiap individu. Di dalam problem lokasi fasilitas yang diperkenalkan di dalam pekerjaan ini, fasilitas-fasilitas harus menset p ke luar dari tempat-tempat yang potensi n yang bahwa biaya keseluruhan yang diharapkan seperti melayani pelanggan-pelanggan pada lokasilokasi m diperkecil dan permintaan-permintaan pada semua lokasi-lokasi pelanggan dipenuhi. Variabel optimisasi xj ∈ {0, 1} mewakili apakah suatu fasilitas akan menset pada lokasi j, pengarang menggunakan aksioma pilihan Luce untuk menyimpulkan bahwa probabilitas suatu pelanggan akan memilih untuk mendapatkan pelayanan pada lokasi j adalah yang diberikan oleh pi,j =

u x P i,j j , ui,k xk k∈Ni

dimana parameter ui,j adalah utiliti yang dilihat oleh pelanggan-pelanggan pada lokasi i di dalam melayani pada lokasi j dan Ni adalah himpunan dari fasilitasfasilitas menempatkan di sekitar lokasi pelanggan i. Sasaran dari problem itu adalah untuk mengoptimalkan keputusan-keputusan xj yang biaya pelayanan diharapkan semua pelanggan adalah diminimumkan. Pengarang menyajikan banyak contoh-contoh berkenaan dengan pemilihan mendesain jaringan dan server dimana pengambil keputusan itu dapat mempengaruhi distribusi probabilitas. Pengarang menyajikan suatu perumusan pemrograman hiperbolik 0-1 dan solusi algoritma eksak untuk versi-versi single stage pada problem ini.


8 Dicatat bahwa Jonsbraten et al. (1998), Held dan Woodruff (2003) dan Jonsbraten (1998b) telah mengajukan problem perencanaan dengan ketidakpastianketidakpastian endogenous bahwa keputusan-keputusan optimal seperti menentukan waktu kapan ketidakpastian-ketidakpastian akan diselesaikan. Pengarangpengarang ini hanya memperkenalkan algoritma-algoritma penyelesaian hampiran untuk versi-versi yang disederhanakan pada problem yang sesuai. Model optimisasi rigorous belum diperkenalkan oleh pengarang-pengarang yang manapun.


BAB 3 LANDASAN TEORI

Beberapa tahun terakhir, isu ketidakpastian dalam mendesain dan perencanaan sistem proses telah memberikan perhatian penting pada masyarakat rancang bangun kimia. Tiga tipe pendekatan utama yang telah digunakan untuk menunjuk isu ini. Didasarkan pendekatan fleksibilitas (Swaney dan Grossmann, 1985; Pistikopoulos, 1995; Banerjee dan Lerapetritou, 2002) telah dikembangkan untuk menyajikan problem dimana perhatian utama adalah untuk memastikan operasi yang feasibel atas suatu nilai cakupan yang diberikan pada proses parameterparameter. Sebaliknya program stokastik didasarkan pada pendekatan-pendekatan, kebanyakan dalam bentuk model-model two-stage (Clay dan Grossmann, 1997; Liu dan Sahinidis, 1996) atau aproksimasi rencana-rencana (Subramanian et al., 2000), telah dikembangkan untuk menunjukkan problem dimana tujuannya adalah untuk memperoleh keputusan-keputusan perencanaan atau mendesain keputusankeputusan yang mengoptimalkan kinerja ekonomi. Sementara banyak model-model telah dipertimbangkan harapan-harapan yang mengoptimalkan kinerja metriks, telah pula beberapa pekerjaan (Ahmed dan Sahinidis, 1998; Bok et al., 1998) untuk menunjuk resiko atau variabilitas di dalam kinerja. Ketiga tipe pendekatan didasarkan pada porograman parametrik (Hene et al., 2002). Tujuan ini untuk mengkarakteristikkan secara sistematis ruang dari proses parameter-parameter dalam bentuk daerah-daerah yang optimal. Pendekatan ini secara khusus digunakan untuk problem dimana banyaknya parameter-parameter yang tidak pasti relatif kecil. Pendekatan lain yang digu9 Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

10 nakan untuk menunjuk isu dari ketidakpastian termasuk pemrograman matematika fuzzy (Balasubramanian dan Grossmann, 2003) dan proses-proses keputusan Markov (Cheng et al., 2003). Program stokastik (Birge dan Louveaux, 1997; Kail dan Wallace, 1994) menawarkan suatu kerangka yang sistematis untuk problem-problem keputusankeputusan yang harus dibuat secara optimal atas suatu time-span yang diberikan, selama nilai-nilai dari beberapa parameter optimisasi bersifat tidak pasti dan ketidakpastian itu dapat diwakili oleh distribusi probabilitas. Pendekatan model dalam program stokastik didasarkan pada asumsi time-span yang menyeluruh merupakan diskret ke dalam periode-periode waktu keputusan tersebut harus dibuat setiap kali periode waktu, sedangkan ketidakpastian menyelesaikan antara periodeperiode waktu. Keputusan-keputusan di dalam banyak periode waktu dapat saja disesuaikan didasarkan pada realisasi- realisasi untuk parameter-parameter ketidakpastian yang telah diselesaikan pada waktu lalu. Fleksibilitas ini dikenal sebagai recourse dan merupakan salah satu dari fitur yang paling menarik pada program stokastik. Sasaran dari program stokastik merupakan untuk membatasi keputusan-keputusan atas seluruh time-span secara simultan sehingga secara keseluruhan performan yang diharapkan adalah optimal, di mana ekspektasi dihitung didasarkan pada distribusi probabilitas yang diberikan. Kita akan membatasi penelitian ini untuk problem yang distribusi probilitas diskrit. Proses stokastik dapat diwakili oleh suatu pohon skenario (seperti pada gambar 3.1). Masing-masing node untuk periode waktu t dalam pohon skenario mewakili suatu informasi state yang mungkin untuk waktu periode. Masingmasing busur mewakili suatu transisi yang mungkin dari suatu state informasi da-


11 lam periode waktu t ke satu dalam periode waktu t + 1 dan dihubungkan dengan suatu transisi probabilitas. Multiple busur-busur yang berasal dari suatu node untuk periode waktu t mewakili kemungkinan multiple untuk transisi. Karenanya ketidakpastian dalam beberapa parameter akan diselesaikan pada akhir periode waktu t. Suatu alur (path) dari akar daun (root node) ke suatu simpul daun (leaf node), yang dikenal sebagai skenario. Skenario mewakili suatu kombinasi yang mungkin dari nilai-nilai parameter-parameter yang tidak pasti. Probabilitas dari skenario merupakan probabilitas mencapai simpul daun dari akar daun. Himpunan dari periode-periode waktu dengan tingkat informasi yang sama (atau ketidakpastian) terdiri dari stage. Problem-problem lebih dari two stage dikenal sebagai problem multistage. Dicatat bahwa penyelesaian suatu problem program stokastik multistage secara siknifikan lebih sulit dibanding menyelesaikan problem program stokastik two stage. Jadi dengan demikian, menggunakan model two stage lebih umum dibanding menggunakan model multistage.

Gambar 3.1 : Pohon Skenario dengan parameter-parameter tidak pasti ξ1 , ξ2


12 Gambar 3.1 memberi penyajian standar suatu pohon skenario untuk suatu problem dengan parameter-parameter yang tidak pasti ξ1 , ξ2 dan realisasi-realisasi tiga periode waktu yang mungkin termasuk nilai-nilai untuk kedua parameterparameter H (”Ketinggian”) dan L (”Rendah”) dengan realisasi kedua-duanya memiliki kemungkinan yang sama. Secara berurutan ketidakpastian-ketidakpastian di dalam ξ1 dan ξ2 diselesaikan pada akhir periode-periode waktu pertama dan kedua. Pohon skenario memiliki empat kemungkinan skenario yang sama dan tiga stage, dengan stage pertama, kedua dan ketiga yang sesuai dengan periode waktu t = 1, t = 2 dan t = 3, secara berurutan. Dalam gambar 3.1, angka-angka pada simpul daun mewakili indeks untuk skenario yang sesuai. Gambar 3.2 memberi penyajian alternatif (Ruszczynski, 1997) untuk pohon skenario yang telah diperlihatkan dalam gambar 3.1. Dalam penyajian ini, masing-masing skenario diwakili oleh suatu himpunan node yang unik. Node-node skenario-skenario s, s0 pada periode waktu t dihubungkan oleh garis horizontal jika mereka berpasangan dengan state informasi yang sama. Pada kasus tersebut, skenario s, s0 disebut indistinguishable dalam periode waktu t. Secara umum skenario s, s0 disebut indistinguishable pada beberapa waktu jika mereka bersifat identik dalam merealisasikan untuk semua parameter yang tidak pasti dimana ketidakpastian telah diselesaikan pada masa lalu. Konsep dari indistinguishability adalah central ke nonanticipativitas didasarkan pendekatan untuk merumuskan programprogram stokastik.


13

Gambar 3.2 : Penyajian alternatif untuk pohon skenario pada gambar 3.1; variabel-variabel xst

3.1 Standar Program Stokastik SSP adalah ”standar” program stokastik (Jonsbraten et al., 1998) untuk suatu problem linier dengan periode-periode waktu T dan pohon skenario S.

s.t

X

Asτ,t

X

(3.1a)

s

t

ast

∀ (t, s)

(3.1b)

xst ∈ χst

∀ (t, s)

(3.1c)

∀ (s, s0 , t) ∈ NSe

(3.1d)

xsτ

≤

ps

X

cst xst

(SSP ) min

τ ≤t

0

xst = xst

Pada (SSP), parameter ps mewakili probabilitas dari skenario s dengan variabel-variabel xst mewakili variabel keputusan untuk periode waktu t di dalam skenario s. (3.la) mewakili fungsi objektif meminimisasi harapan dari beberapa kriteria ekonomi. Konstrain (3.1b) mewakili periode tunggal dan periode pengait kendala untuk skenario tertentu yang karakteristik pada semua model multiperiod.


14 Konstrain (3.1c) mewakili pembatasan-pembatasan integralitas dan batas pada variabel-variabel xts. (3.1d) mewakili nonanticipativitas atau implementabilitas (Rockafellar dan Wets, 1991; Ruszczynski, 1997) konstrain-kontrain yang menjalankan pembatasan keputusan tersebut tidak dapat didasarkan pada informasi yang diungkapkan di masa datang. State konstrain-konstrain ini yang jika skenario s, s0 bersifat indistinguishable pada periode waktu t. Keputusan-keputusan untuk skenario s, s0 pada periode waktu t harus sama. NSe mewakili himpunan dari (s, s0 , t) skenario s dan s0 merupakan bersifat indistinguishable pada periode waktu t karena proses stokastik yang diwakili oleh pohon skenario S. Sebagai contoh, aturan nonanticipativitas untuk pohon skenario pada gambar 3.2 akan memberikan batasan-batasan x11 = x21 = x31 = x41 , x12 = x22 dan x32 = x42. Dicatat bahwa himpunan NSe dan konstrain nonanticipativitas pada (SSP) bergantung pada struktur dari pohon skenario.

3.2 Tipe-Tipe Ketidakpastian Suatu pohon skenario berisi semua informasi yang diperlukan untuk menggambarkan proses stokastik pada problem. Yakni, realisasi-realisasi yang mungkin untuk masing-masing parameter yang tidak-pasti, probabilitas-probabilitas yang sesuai untuk masing-masing realisasi, dan waktu kapan ketidakpastian akan diselesaikan di setiap parameter-parameter ini. Didasarkan pada ketergantungan dari proses stokastik pada keputusan-keputusan yang optimal, Jonsbraten (1998b) golongkan ketidakpastian dalam dua kategori.


15 3.2.1 Ketidakpastian Exogenous Hampir semua penelitian yang sebelumnya dalam literatur program stokastik berhubungan dengan problem proses stokastik ketidakpastian exogenous. Oleh karena itu pohon skenario, tidak terikat pada keputusan-keputusan optimisasi. Jadi dengan demikian, probabilitas skenario p(·) dan himpunan NSe merupakan suatu priori yang diketahui dan merupakan input ke (SSP). Pada pasar yang kompetitif, ketidakpastian di dalam harga pasar gas berasal dari sifat yang exogenous ketika yang ditujukan di dalam investasi dan perencanaan operasional untuk membangun ladang-ladang gas yang optimal. Ini karena pada pasar yang kompetitif keputusan-keputusan investasi dan operasi tidak dapat mempengaruhi harga gas pada masa depan maupun menentukan waktu kapan ketidakpastian di dalam harga gas akan diselesaikan. Karena (SSP) mereplikasikan masing-masing variabel keputusan dan masingmasing konstrain di suatu model deterministik untuk setiap skenario. Ukuran dari (SSP) tumbuh dengan cepat peningkatan di dalam banyaknya skenario. Hal ini mengharuskan pemakaian algoritma dekomposisi untuk solusi problem ukuran secara realistis, terutama ketika beberapa variabel-variabel keputusan bersifat diskrit. Sahinidis (2004), Schultz (2003) dan Birge (1997) menyajikan tinjauan ulang terbaru dari penelitian sebelumnya dalam komoditas program stokastik pada problem dengan ketidakpastian yang exogenous. Metode L-shaped (Vanslyke dan Wets, 1969; Laporte dan Louveaux, 1993), yang merupakan adaptasi dari metode dekomposisi Bender (Geoffrion, 1972), merupakan kemungkinan menggunakan algoritma paling umum untuk menyelesaikan program-program stokastik linier two-stage dengan variabel-variabel integer di dalam stage pertama.


16 Algoritma-algoritma lain untuk menyelesaikan program-program stokastik twostage termasuk algoritma membatasi nilai yang progresif oleh Rockafellar dan Wets (1991), dualitas Lagrangean didasarkan algoritma branch and bound oleh Caroe dan Schultz (1999) dan algoritma optimisasi global branch and bound oleh Ahmed et al. (2004). Dalam teori, algoritma membatasi nilai yang progresif dapat digunakan untuk menyelesaikan program-program stokastik multistage linier, dimana algoritma branch and bound yang diperkenalkan oleh Caroe dan Schultz (1999) dapat diaplikasikan untuk setiap program stokastik multistage. Bagaimanapun riset dalam algoritma-algoritma untuk menyelesaikan program-program stokastik multistage merupakan langkah-langkah yang perkembangan dalamnya. Satu pendekatan untuk menemukan solusi ”yang baik” pada program stokastik multistage merupakan untuk mengaproksimasikan pohon skenario multistage oleh suatu urutan dari pohon skenario two stage dan menggunakan solusi-solusi program-program stokastik two-stage yang sesuai untuk menetapkan keputusan-keputusan di dalam program stokastik multistage.

3.2.2 Ketidakpastian Endogenous Problem-problem proses stokastik bergantung pada keputusan-keputusan yang optimal dikatakan ketidakpastian endogenous. Secara umum, pengambil keputusan dapat mempengaruhi proses stokastik dengan pengendalian waktu ketika ketidakpastian-ketidakpastian dalam berbagai parameter-parameter akan diselesaikan, atau dengan menyebabkan perubahan di dalam probabilitas-probabilitas skenario. Perbedaan adalah bahwa di dalam kasus yang pertama, pengambil kepu-


17 tusan dapat mengetahui nilai yang benar suatu parameter sebelumnya dibanding kemudian, kasus yang kedua, pengambil keputusan dapat membuat suatu realisasi yang mungkin lebih baik. Dari beberapa literatur, beberapa problem dengan dua tipe dari ketidakpastian-ketidakpastian endogenous. Gagasan-gagasan untuk merumuskan (SSP) dapat digunakan untuk merumuskan program stokastik untuk problem ini. Sifat ketidakpastian endogenous memperkenalkan kesulitan-kesulitan yang sangat tinggi merintangi penggunaan langsung dari (SSP). Perencanaan optimal untuk pembentukan ladang-ladang gas di bawah ketidakpastian dalam kualitas cadangan merupakan suatu problem dunia nyata, dimana keputusan-keputusan optimal mempengaruhi waktu ketika ketidakpastianketidakpastian dalam berbagai parameter-parameter akan diselesaikan. Secara umum, banyak informasi penting tentang kualitas cadangan pada suatu ladang dapat diperoleh dengan penerapan suatu WP (Well Platform) di ladang. Asumsi bahwa ketidakpastian dalam persediaan dari suatu ladang gas dipecahkan dengan WP diinstallkan. Dengan demikian, keputusan-keputusan investasi memenuhi pengambil keputusan untuk mengendalikan waktu ketika ketidakpastian di suatu ladang gas akan diselesaikan. Gambar 3.3 memperlihatkan bahwa untuk suatu problem dengan dua ladang gas, A dan B, dan empat periode waktu. Struktur dari pohon skenario bergantung pada ketika investasi-investasi pada ladang-ladang ini akan selesai. Mengasumsikan bahwa ukuran-ukuran dari ladang-ladang A dan B bersifat tidak pasti dan kedua parameter-parameter dapat memberikan nilai-nilai High atau Low. Ukuran dari suatu ladang mewakili total volume gas yang dapat diperoleh dari ladang.


18 Pohon skenario di dalam gambar 3.3 (a) hasil oleh sautu kebijakan investasi dimana WP pada ladang A dipasangkan pada tahun pertama. WP pada ladang B dipasangkan di tahun ke 2 atau 3 tergantung pada ukuran dari ladang A (karena ukuran dari ladang A akan diketahui seperti ketika WP dipasangkan pada ladang itu). Pohon skenario di dalam gambar 3.3 (b) hasil oleh suatu kebijakan investasi di mana WP pada ladang A dipasangkan pada tahun ke 2 WP di ladang B dipasangkan di tahun ke 3 dengan tidak mengabaikankan ukuran dari ladang A.

Gambar 3.3 : Keputusan bergantung pohon-pohon skenario untuk problem ladang gas

Seperti yang digambarkan pada contoh tersebut, struktur dari pohon skenario tidak dapat diidentifikasikan suatu priori jika pengambil keputusan mengendalikan waktu ketika ketidakpastian-ketidakpastian dalam berbagai parameterparameter akan diselesaikan. Dengan demikian himpunan NSe tidak diketahui sebelumnya dan standar program stokastik (SSP) tidak bisa digunakan untuk problem seperti itu. Pada kasus dimana keputusan-keputusan yang optimal mempengaruhi distribusi probabilitas. Sebaliknya, probabilitas skenario p(·) tidak dapat diperlakukan sebagai parameter-parameter. Ini memperkenalkan ketaklinearanketaklinearan dan nonconvexitas di dalam (SSP). Karena kesulitan-kesulitan seba-


19 gai akibat dari ketergantungan dari NSe dan p(·) pada keputusan-keputusan yang optimal, penelitian sebelumnya dalam komoditas pemrograman stokastik pada problem dengan ketidak-pastian endogenous yang dibatasi pada beberapa paper saja.


BAB 4 MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS

Dalam bab ini, menyajikan tentang problem perencanaan dimana keputusankeputusan harus dioptimalkan dalam ketidakpastian. Keputusan-keputusan optimisasi menentukan waktu ketika ketidakpastian-ketidakpastian dalam beberapa parameter-parameter itu akan diselesaikan. Ketidakpastian-ketidakpastian di dalam parameter-parameter (exogenous) akan diselesaikan pada waktu yang ditentukan. Kita mulai dengan suatu uraian problem yang umum dari kelas dalam pembahasan. Pengembangan kapasitas proses jaringan dan problem ukuran-ukuran (Jorjani et al., 1999; Jonsbraten et al., 1998) diperkenalkan sebagai kejadiankejadian yang spesifik dari problem pada kelas ini. Ini diikuti oleh suatu uraian yang singkat notasi yang digunakan di dalam bab ini dan model pemrograman stokastik yang diusulkan.

4.1 Uraian Masalah Kita mempertimbangkan problem dengan suatu horizon waktu yang diskret, T = {1, 2, . . . , T }, dan suatu himpunan hingga dari ”sumber” dari ketidakpastian endogenous, X = {1, 2, . . . , I}. Keputusan-keputusan yang sesuai dengan variabel-variabel bi,t untuk semua i ∈ X , dan variabel-variabel yt dan xt harus dioptimalkan atas seluruh horizon waktu.


21

Gambar 4.1 : Penyajian menurut bagan problem proses jaringan Variabel bi,t menunjukkan keputusan-keputusan biner, variabel-variabel yt dan xt adalah vektor-vektor yang komponen-komponennya kontinu dan diskret. ξt menunjukkan parameter yang tidak pasti exogenous dihubungkan dengan periode waktu t ∈ T . θi adalah parameter endogenous yang tidak pasti yang dihubungkan dengan sumber i ∈ X . Ketidakpastian di dalam ξt akan diselesaikan secara otomatis pada periode waktu t resolusi ketidakpastian di θi bergantung pada keputusan-keputusan bi,t. Urutan kejadian pada setiap periode waktu adalah sebagai berikut. Keputusan-keputusan yt dan xt diterapkan pada awal periode waktu t. Ini diikuti oleh resolusi ketidakpastian di dalam parameter-parameter yang exogenous ξt dan di dalam parameter-parameter endogenous θi untuk sumber i seperti bahwa bi,t = 1 dan bi,τ = 0 untuk semua τ < t. Keputusan-Keputusan xt diterapkan pada akhir periode waktu. Kita mengasumsikan suatu himpunan diskret dari realisasi yang mungkin, Ξ, untuk vektor ξ = {ξ1 , ξ2 , . . . , ξT } suatu himpunan diskret dari realisasi yang mungkin, Θi , untuk θi . Kita berasumsi bahwa hanya ada satu parameter endoge-


22 nous yang tidak pasti yang dihubungkan dengan sumber i untuk semua i ∈ X . Jadi; Dengan demikian, θi adalah suatu skalar untuk semua i ∈ X .

4.2 Contoh-contoh Problem 4.2.1 Pengembangan Kapasitas pada Proses Jaringan Problem pengembangan kapasitas dalam proses jaringan adalah suatu contoh yang spesifik dari problem dari kelas dalam pembahasan. Gambar 4.1 menunjukkan suatu proses jaringan dapat digunakan untuk menghasilkan bahan kimia A. Bahan kimia A dihasilkan dalam unit 3 dari bahan kimia B, yang sedang dibeli dari pasar. Bagaimanapun, teknologi baru kini tersedia dalam bentuk unit-unit 1 dan 2 yang dapat menghasilkan B dari bahan baku C dan D, berturut-turut. Bahan kimia C dan D dapat dibeli dari pasar. Jika diperlukan, bahan kimia A juga dapat dibeli dari pasar. Juga, inventori dari bahan kimia A dapat dipertahankan. Permintaan untuk bahan kimia A harus dipenuhi pada setiap periode waktu t atas suatu waktu yang diberikan pada suatu horizon waktu T . Keputusankeputusan dibuat dalam periode waktu t termasuk menentukan apakah unitunit yang spesifik harus dioperasikan pada periode waktu t atau tidak (variabelvariabel bi,t ∈ {0, 1} untuk i = 1, 2, 3). Apakah unit-unit yang spesifik harus exp ∈ {0, 1} untuk i = 1, 2, 3), perdipasangkan atau diperluas (variabel-variabel yi,t QE untuk i = 1, 2, 3), luasan di dalam kapasitas dari unit-unit (variabel-variabel yi,t rate untuk j = 1, 2, 3), dan jual beli untuk laju alur penilaian (variabel-variabel yj,t

dan xsales ). memenuhi permintaan dari A (variabel-variabel xpurch t t


23 Hasil-hasil (ton dari produk per ton dari bahan baku) dari unit-unit 1 dan 2, yang diwakili oleh θ(·), bersifat tidak pasti. Juga, permintaan mendatang untuk bahan kimia A, yang diwakili oleh ξt untuk t ∈ T , bersifat tidak pasti. Ketidakpastian dalam hasil dari suatu unit akan diselesaikan hanya setelah unit itu sudah dipasangkan dan dioperasi untuk satu periode waktu. Ketidakpastian permintaan di suatu periode waktu yang spesifik diselesaikan secara otomatis pada periode waktu tersebut. Urutan dari kejadian pada setiap periode waktu adalah sebagai berikut. Keputusan-keputusan mengenai unit-unit untuk menginstal atau memperluas, perluasan-perluasan di dalam kapasitas unit-unit ini, yang unit-unit untuk beroperasi dan laju alir penilaian diputuskan pada awal periode waktu. Konfigurasi hasil jaringan yang kemudian dioperasikan pada laju alir yang diputuskan untuk periode waktu. Ketidakpastian-ketidakpastian di dalam permintaan-permintaan untuk periode waktu yang spesifik dan di dalam hasil-hasil dari unit-unit 1 dan 2, bila ada unit-unit ini telah dioperasikan di dalam periode waktu untuk pertama kali, yang kemudian diselesaikan. Didasarkan pada pengamatan untuk permintaan dan hasil-hasil, keputusan-keputusan penjualan dan pembelian untuk periode waktu dilakukan pada akhir periode waktu.

4.2.2 Problem Ukuran-ukuran Problem ukuran-ukuran (Jorjani et al., 1999; Jonsbraten et al., 1998) adalah contoh spesifik yang lain dari problem dalam pembahasan. Di dalam problem ini, suatu lini produksi harus mengimbangi permintaan untuk suatu produk di dalam satu set ukuran-ukuran yang berbeda, X = {1, 2, . . . , I}, pada setiap periode


24 waktu ∈ T . Jika permintaan untuk ukuran tertentu tidak dapat dijumpai di suatu periode waktu yang spesifik, defisit itu dapat diisi oleh penyerahan dari suatu ukuran yang lebih besar. Bagaimanapun, hal ini melibatkan suatu biaya yang disubtitusikan. Biaya-biaya lain termasuk biaya produksi yang ditetapkan untuk menset peralatan untuk masing-masing ukuran yang dihasilkan pada setiap periode waktu, variabel biaya inventori dan variabel biaya produksi untuk masingmasing unit yang dihasilkan. Permintaan-permintaan, yang diwakili oleh ξt selama periode waktu ∈ T , bersifat tidak pasti. Variabel biaya produksi, yang diwakili oleh θi untuk ukuran i ∈ X , tinggal konstant atas horizon waktu adalah juga tidak pasti. Permintaan pada periode waktu t akan diamati secara otomatis di periode waktu tersebut. Sebaliknya, ketidakpastian di dalam variabel biaya produksi untuk ukuran i, θi, akan diselesaikan hanya ketika ukuran dihasilkan untuk pertama kali. Jadi dengan demikian, ketidakpastian permintaan adalah exogenous dan ketidakpastian di dalam variabel biaya produksi adalah endogenous. Keputusan-keputusan diperlukan dalam setiap kali periode waktu termasuk apakah untuk menghasilkan ukuran i atau tidak (variabel-variabel biner bi,t). Banyak unit-unit dari ukuran i untuk dihasilkan (variabel-variabel yi,t) dan banyak unit-unit dari ukuran i digunakan untuk memenuhi permintaan ukuran i0 (variabelvariabel xi,i0 ,t). Keputusan-keputusan produksi (bi,t, yt ) diterapkan pada awal periode waktu t. Ini diikuti oleh resolusi ketidakpastian pada permintaan-permintaan untuk periode waktu t dan di dalam variabel biaya produksi untuk ukuran-ukuran yang dihasilkan untuk pertama kali pada periode waktu t. Akhirnya, keputusan-


25 keputusan yang disubtitusikan (xi,i0,t ) untuk memenuhi permintaan-permintaan pada periode waktu t diterapkan pada akhir periode waktu itu.

4.3 Notasi dan Definisi Masing-masing skenario di dalam problem ini mewakili suatu realisasi yang mungkin untuk vektor (ξ1 , ξ2 , . . . , ξT , θ1, θ2, . . . , θI ). Kita berasumsi bahwa himpunan dari skenario yang diberikan oleh Ξ × (×i∈X Θi , yaitu, himpunan dari skenario terdiri dari semua kombinasi realisasi yang mungkin untuk vektor dari parameter-parameter yang exogenous, (ξ1 , ξ2 , . . . , ξT }, dengan vektor dari parameterparameter endogenous. Himpunan realisasi untuk vektor dari parameter-parameter endogenous adalah himpunan dari semua kombinasi untuk berbagai parameterparameter endogenous. Himpunan S = {1, 2, . . . , S} digunakan untuk indeks himpunan dari skenario-skenario yang individu bersifat indeks oleh s, di mana s ∈ S. θis dan ξts mewakili perwujudan-perwujudan dari θi dan ξt berturut-turut, di dalam skenario s. 0

Untuk skenario s, s0 ∈ S , himpunan D(s, s0 ) = {i|i ∈ X , θis 6= θis } menunjukkan himpunan sumber ketidakpastian endogenous yang skenario distinguish s dan s0 . Ekspresi |D(s, s0 )| menunjukkan kardinalitas dari himpunan ini. Secara umum, D(s, s0 ) memenuhi 0 ≤ |D(s, s0 )| ≤ I untuk semua s, s0 ∈ S, di mana I merupakan banyaknya sumber dari ketidakpastian endogenous. Menurut definisi, D(s, s0 ) = D(s0 , s). Untuk skenario, s, s0 ∈ S, t(s, s0 ) merupakan akhir periode waktu t yang merealisasikan semua parameter exogenous diselesaikan hingga dan termasuk periode


26 waktu t merupakan sama di dalam skenario s, s0 . Dengan kata lain, t(s, s0) kali yang terakhir periode waktu pada akhir skenario seperti, s, s0 bersifat indistinguish yang didasarkan pada resolusi ketidakpastian exogenous. Secara Matematika, 0

t(s, s0) = max{t|t ∈ T , ξτs = ξτs ∀τ ∈ T , τ ≤ t} t

0

Kita menggambarkan t(s, s0 ) = 0 jika {t|t ∈ T , ξτs = ξτs

∀τ ∈ T , τ ≤ t} = ∅.

Catat bahwa skenario tidak dapat terpisah s, s0 ∈ S seperti |D(s, s0 )| = 0 dan t(s, s0 ) = T . Ini adalah karena skenario s, s0 akan lengkap serupa jika mereka memenuhi kondisi-kondisi tersebut. Menurut definisi, t(s, s0 ) = t(s0 , s). L0 = {(s, s0 )|s, s0 ∈ S, s < s0 , |D(s, s0 )| = 0}, menunjukkan himpunan dari skenario yang memasangkan (s, s0) seperti bahwa skenario dan bersifat serupa di dalam perwujudan-perwujudan untuk semua parameter endogenous. Kondisi s < s0 mencegah salinan di dalam L0 untuk pasangan yang sama dari skenario s, s0 . L1+ = {(s, s0 )|s, s0 ∈ S, s < s0 , |D(s, s0 )| > 1} menunjukkan himpunan dari skenario yang memasangkan (s, s0 )|. s, s0 berbeda di dalam perwujudan-perwujudan θi untuk sedikitnya satu i ∈ X . Dengan cara yang sama, L1 = {(s, s0)|s, s0 ∈ S, s < s0, |D(s, s0 )| = 1}. L1T = {(s, s0)|s, s0 ∈ L1 , t(s, s0) = T } adalah himpunan dari skenario yang memasangkan (s, s0 ) skenario itu s, s0 seperti berbeda di dalam perwujudan persisnya satu parameter endogenous dan bersifat identik di dalam perwujudan-perwujudan untuk semua parameter yang exogenous.


27 4.4 Model Wujud dari program-program stokastik untuk problem ini digambarkan dalam bagian 4.1 (Grossmann, 2002), (P1). (P 1)

φ = min

X

ps

s∈S

X

s.t.

w

X

w s s ct wt

+x cst xst +y cst yts +

t∈T

b X

csi,t bsi,t

!

(4.1)

i∈I

Asτ,twτs +x Asτ,txsτ +y Asτ,tyτs +

τ ∈T ,τ ≤t

b X

Asi,τ,tbsi,τ

!

≤ ast (4.2)

i∈I

∀s ∈ S, t ∈ T 0

bsi,1 = bsi,1 ∀s, s0 ∈ S, s < s0 , i ∈ I 0

y1s = y1s ∀s, s0 ∈ S, s < s0

(4.3b)

xst = xst ∀(s, s0) ∈ L0 , t ∈ T , t ≤ t(s < s0 )

(4.3c)

bsi,t+1 = xsi,t+1 ∀(s, s0) ∈ L0 , t ∈ T , t ≤ t(s < s0 ), i ∈ I

(4.3d)

0

0

0

s s yi,t+1 = yt+1 ∀(s, s0) ∈ L0 , t ∈ T , t ≤ t(s < s0 )

0 Zts,s

^

⇔

i∈D(s,s0 ) s,s0

Zt

(4.3a)

^

⇔

i∈D(s,s0 )

"

t ^

#

∀(s, s0 ) ∈ L1+ , t ∈ T , t ≤ t(s < s0 )

(4.4)

∀(s, s0 ) ∈ L1+ , t ∈ T , t ≤ t(s < s0 )

(4.5)

 0 Zts,s 0   xst = xs,s  t  ∨ [¬Zts,s0 ] s0 bs  i,t+1 = bi,t+1 ∀i ∈ I if t ≤ T − 1 0 s s = yt+1 if t ≤ T − 1 yt+1 0 ∀(s, s ) ∈ L1+ , t ∈ T , t ≤ t(s < s0 )

(4.6)

"

(¬bsi,τ τ =1

(4.3e)

t ^

s0

(¬bi,τ

#

τ =1



wts ∈ Wts , xst ∈ Xts , yts ∈ Yts , bsi,t ∈ {0, 1} ∀s ∈ S, t ∈ T , i ∈ I 0

Zts,s ∈ {T rue, F alse} ∀(s, s0 ) ∈ L1+ , t ∈ T , t ≤ t(s < s0 )


28 Pada (PI), variabel-variabel bsi,t, xst dan yts menggambarkan keputusan keputusan yang diperlukan dalam periode waktu t dari skenario s. Vektor wts mewakili variabel-variabel lain yang diasosiasikan dengan periode t di dalam skenario s. Dalam proses kontrol bsi,t, xst dan yts adalah ”variabel kendali”, wts adalah ”variabel state (keadaan)”. bsi,t adalah variabel-variabel biner, xst dan yts adalah variabel vektor-vektor yang kedua-duanya komponen-komponen integer dan komponenkomponen kontinu. Seperti yang dijelaskan dalam bagian 4.1, keputusan yts dan bsI,t diimplimentasikan pada awal periode waktu t. Keputusan-keputusan xst diimplementasikan pada akhir periode waktu t setelah resolusi ketidakpastian pada periode waktu tersebut. Parameter b csi,t adalah perwujudan dalam scenario s, untuk koefisien biaya yang sesuai dengan variable keputusan bi,t. Dengan kata lain, b csi,t =b ci,t (ξ1s , ξ2s , . . . , ξTs , θ1s , θ2s , . . . , θIs ). Sama halnya, perwujudan-perwujudan untuk koefisien-koefisien bi(·)

(·)

(·)

aya yang sesuai dengan variabel-variabel xt , yt dan wt dalam skenario s diwakili oleh x cst ,y cst dan w cst , berturut-turut. Matriks (atau vektor-vektor) b Asi,τ,t,x Asτ,t,y Asτ,t dan w Asτ,t menggambarkan perwujudan-perwujudan untuk koefisien konstrain matriks (atau vektor-vektor) dari variabel-variabel ini di dalam skenario s. Persamaan (4.1) menunjukkan fungsi objektif dengan meminimumkan harapan dari kriteria ekonomi. Ketidaksamaan (4.2) menunjukkan konstrain, untuk skenario tertentu, yang menentukan keputusan-keputusan pada periode waktu t dan yang menghubungkan keputusan-keputusan ke seberang periode-periode waktu. Ini termasuk sistim yang bujur sangkar dari persamaan konstrain-konstrain yang dapat digunakan untuk mengeliminasikan ”state” variabel-variabel wts .


29 Keputusan-keputusan untuk skenario yang berbeda terhubung oleh batasanbatasan nonanticipativas, (4.3)-(4.7). Aturan nonanticipativitas memerlukan keputusan di dalam skenario s dan s0 harus sama pada suatu waktu yang diberikan, jika skenario s dan s0 bersifat indistinguishable pada waktu itu. Didasarkan pada urutan dari kejadian digambarkan dalam bagian 4.1, resolusi ketidakpastian pada periode waktu t berlangsung setelah keputusan-keputusan yts dan bsi,t telah dit(·)

(·)

(·)

erapkan. Dengan demikian, keputusan-keputusan xt , bi,t+1 dan yt+1 harus sama untuk scenario s, s0 jika skenario ini s, s0 bersifat indistinguishable setelah resolusi ketidakpastian pada periode waktu t. Catat bahwa, kita mengacu pada ”indistinguishability dari skenario s, s0 setelah resolusi ketidakpastian exogenous dan ketidakpastian endogenuous pada waktu periode t ”dengan hanya ” indistinguishability pada skenario ini dalam periode waktu t”. Didasarkan pada urutan dari kejadian pada setiap periode waktu, semua skenario satu sama lain indistinguishable sebelum keputusan-keputusan bsi,t dan yts diimplementasikan pada periode waktu pertama kali. Jadi dengan demikian, (·)

keputusan-keputusan b·i,1 dan y1 harus sama untuk semua skenario (konstrainkonstrain (4.3)). Catat bahwa kondisi s < s0 menentukan untuk menghindari penggandaan konstrain-konstrain (4.3) untuk pasang skenario yang sama s, s0 . Persamaan-persamaan (4.4) menunjukkan konstrain nonanticipativitas rangkaian skenario s, s0 itu seperti (s, s0 ) ∈ L0 ;yaitu., realisasi untuk semua parameter endogenous dalam skenario s dan s0 bersifat identik. Dalam hal ini, skenario s, s0 akan indistinguishable pada periode waktu t, jika dan hanya jika skenario ini bersifat identik di dalam realisasi semua parameter exogenous diamati hingga dan termasuk periode waktu t. Persamaan- persamaan (4.4) memakai batasan-batasan


30 (·)

(·)

(·)

nonanticipativas pada keputusan-keputusan xt , yt+1 dan bt+1 untuk skenario s, s0 hanya jika t memenuhi t ≤ t(s, s0). Kontrain-konstrain (4.5)-(4.7) adalah konstrain nonanticipativitas rangkaian skenario s, s0 itu seperti (s, s0) ∈ L1+ ; yaitu., skenario s dan s0 berbeda di dalam merealisasikan sedikitnya satu parameter endogenous. Dalam hal ini, indistinguishability skenario s, s0 bergantung pada kedua-duanya, ketidakpastian endogenous dan ketidakpastian exogenous diselesaikan pada masa lalu. Didasarkan pada ketidakpastian-ketidakpastian exogenous dan endogenous diselesaikan pada masa lalu, batasan-batasan (4.5)-(4.7) secara implisit mengidentifikasi apakah skenario s, s0 bersifat indistinguishable setelah keputusan-keputusan y(·) dan bi,(·) telah diimplementasikan pada periode waktu t, dan memakai konstrain-konstrain nonanticipativitas secara setimpal. Dengan jelas, untuk t > t(s, s0) skenario s, s0 dapat dibedakan hanya didasarkan pada realisasi parameter-parameter exogenous. Karenanya, konstrain-konstrain (4.5)-(4.7) digunakan hanya untuk t seperti t ≤ t(s, s0), di mana (s, s0 ) ∈ L1+ . 0

Pada (PI), variabel Boolean Zts,s adalah benar jika dan hanya jika skenario s dan s0 bersifat indistinguishable setelah resolusi ketidak-pastian pada periode waktu t. Menurut definisi t(s, s0) untuk t ≤ t(s, s0), indistinguishability skenario s, s0 pada periode waktu t tergantung semata-mata ketidakpastian endogenous diselesaikan melalui keputusan-keputusan. Konstrain-konstran logika (4.5) dan (4.6) menghubungkan indistinguishability skenario s, s0 pada periode waktu t de0

ngan keputusan-keputusan bsi,τ dan bsi,τ , berturut-turut. Skenario s, s0 berbeda di dalam perwujudan-perwujudan suatu himpunan hingga dari parameter-parameter 0

endogenous. Batasan status (4.5) bahwa Zts,s adalah benar jika dan hanya jika


31 ketidakpastian belum diselesaikan dalam parameter-parameter dan termasuk periode waktu t dari skenario s. Dengan cara yang sama, konstrain logika (4.6) 0

menghubungkan variabel Zts,s pada variabel keputusan yang sesuai untuk skenario s0 . Disjunction (4.7) menentukan konstrain-konstrain non anticipativas pada (·)

(·)

(·)

0

variabel-variabel xt , yt+1 dan bi,t+1 untuk skenario s, s0 hanya jika Zts,s adalah Benar. Catat bahwa untuk mempertanggungjawabkan offset di dalam indeks variabel-variabel ini, konstrain-konstrain nonanticipativas pada variabel-variabel (·)

(·)

bi,t+1 , yt+1 skenario s, s0 diterapkan hanya jika t ≤ T − 1. Meski mungkin kelihatannya bahwa suatu pembatasan yang serupa diperlukan di dalam konstrainkonstrain (4.4b)-(4.4c), bagaimanapun, sebelum dijelaskan di dalam bagian ini, kita tidak bisa memisahkan skenario; jelas s, s0 ∈ S seperti yang (s, s0 ) ∈ L0 dan t(s, s0 ) = T . Karenanya, di dalam konstrain-konstrain (4.4b)-(4.4c) kondisi bahwa t ≤ T − 1 adalah implisit dalam kondisi t ≤ t(s, s0). Wts , Xts dan Yts menunjukkan pembatasan-pembatasan dan integralitas pada variabel-variabel wts , xst dan yts berturut-turut, untuk ∈ T , s ∈ S.


BAB 5 KESIMPULAN

Dalam penelitian ini, menentukan tentang program stokastik dengan keputusan optimisasi menentukan waktu ketika ketidakpastian-ketidakpastian pada subset dari parameter-parameter yang akan diselesaikan. Kelas pada problem ini relevan pada aplikasi-aplikasi terutama dalam dunia nyata, dimana pengambil keputusan memiliki opsi informasi yang perolehan dari ahli yang aktif dengan membuat beberapa investasi. Penelitian ini telah memperluas kerangka modeling program stokastik dengan menggabungkan interaksi antara keputusan-keputusan optimisasi dan proses penemuan informasi melalui pemakaian program disjunctive. Ketika fleksibilitas sangat bernilai pada pengambil keputusan, menuju situasi dimana pohon skenario bergantung pada keputusan-keputusan yang optimal. Dan oleh karena itu, standar program stokastik yang umum tidak dapat digunakan. Penelitian ini mengusulkan suatu model optimisasi mixed-integer/ disjunctive dimana ketergantungan dari pohon skenario pada keputusan-keputusan optimal yang dimodelkan dengan mengaplikasikan konstrain-konstrain non anticipativitas dengan kondisi dalam bentuk disjunctive. Karena konstrain-konstrain non anticipativitas di dalam model yang diusulkan harus diaplikasikan pada masing-masing pasangan skenario, ukuran dari model dapat di explode dengan suatu peningkatan dari skenario. Kita menujukan bahwa isu ini dengan memberikan teoritis yang memenuhi oleh setiap penyelesaian layak model yang diusulkan. Ketika himpunan dari skenario berpasangan dengan 32 Fajriana : Model Program Stokastik Dengan Keputusan Ketidakpastian Yang Tak Bebas, 2009.

33 diskret Ξ × (×i ∈ χ Θi ), di mana Ξ mewakili himpunan diskret untuk vektor dari parameter-parameter yang exogenous. Dan θi adalah himpunan diskret untuk parameter endogenous berhubungan dengan sumber i. Konstrain-konstrain (2.5)(2.7) perlu untuk digunakan pada pasangan-pasangan (s, s0 ) hanya jika skenario s0 berbeda di dalam perwujudan parameter endogenous dan mereka bersifat identik di dalam perwujudan-perwujudan untuk semua parameter yang exogenous. Sifat ini digunakan untuk mengembangkan suatu model yang signifikan pada batasanbatasan lebih sedikit tetapi hanya pada ruang fesibel yang sama dengan model yang asli.


DAFTAR PUSTAKA

Ahmed, S., 2000. Strategic planning under uncertainty: Stochastic integer programming approaches. Ph.D. thesis, University of Illinois at Urbana- Champaign. Ahmed, S., Sahinidis, N. V., 1998. Robust process planning under uncertainty. Industrial and Engineering Chemistry Research 37(5), 1883-1892. Ahmed, S., Tawarmalani, M., Sahinidis, N. V., 2004. A finite branch-and-bond algorithm for two-stage stochastic integer programs. Mathematical programming 100 (2) 355-377. Balasubramanian, J., Grossmann, I. E., 2003. Scheduling optimization under uncertainty - an alternative approach. Computers and Chemical Engineering 27 (4), 469-490. Banerjee, I., Lerapetritou, M. G., 2002. Design optimization under parameter uncertainty for general black-box models. Industrial and Engineering Chemistry Research 41 (26), 6687-6697. Birge, J. R., 1997. Stochastic programming computation and applications. INFORMS J. Comput. 9, 111133. Birge, J. R., Louveaux, F. C., 1997. Introduction to stochastic programming. Springer-Verlag, New York. Bok, J. K., Lee, H., Park, s., 1998. Robust investment model for long-range capacity expansion of chemical processing network under uncertain demand forecast scenarios. Computers and Chemical Engineering 22(7-8), 1037-1049. Caroe, C. C, Schultz, R., 1999. Dual decomposition in stochastic integer programming. Oper. Res. Lett. 24, 37-45. Cheng, L., Subrahmanian, E., Westerberg, A. W., 2003. Design and planning under uncertainty: issues on problem formulation and solution. Computers and Chemical Engineering 27 (6), 781-801. Clay, R. L., Grossmann, I. E., 1997. A disaggregation algorithm for the optimization of stochastic planning models. Computers and Chemical Engineering 21 (7), 751-774. Geoffrion, A., 1972. Generalized benders’ decomposition. Journal of Optimization Theory and Applications 10 (4), 237. Goel, V., Grossmann, I. E., 2004. A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Computers and Chemical Engineering 28 (8), 14091429. Goel, V., Grossmann, I. E., 2005. Stochastic programming approaches for the optimal development of gas fields under uncertainty. A Dissertation. Cornegie Mellon University.


35 Held, H. Woodruff, D. L., 2003. Heuristics for multi-stage interdiction of stochastic net-works. Journal of Heuristics (Submitted for publication) Hene, T.S., Dua, V., Pistikopoulos, E. N., 2002. A hybrid parametric/stochastic programming approach for mixed-integer nonlinear problems under uncertainty. Industrial ang Engineering Chemistry Reseach 41(1), 67-77. Jonsbraten, T. W., 1998b. Optimization models for petroleum field exploitation. Ph.D. thesis, Norwegian School of Economics and Business Administration. Jonsbraten, T. W., Wets, R. J. B., Woodruff, D. L., 1998. A class of stochastic programs with decision dependent random elements. Annals of Operations Research 82, 83106. Jorjani, S., Scott, C. H., Woodruff, D. L., 1999. Selection of an optimal subset of sizez. International Journal of Production Research 37 (16), 3697-3710. Kall, P., Wallace, S., 1994. Stochastic Programming. Wiley, Chichester etc. Laporte, G., Louveaux, F. V., 1993. The integer 1-shaped method for stochastic integer programs with complete recourse. Operations Research Letters 13 (3), 133-142. Liu, M. L., Sahinidis, N. V., 1996. Optimization in process planning under uncertainty. Industrial and Engineering Chemistry Research 35 (11), 4154-4165. Luce, R. D., 1977. Choice axiom after 20 years. Journal of Mathematical Psychology 15 (3), 215-233. Pflug, G., 1990. On-line optimization of simulated markovian processes. Math. Oper. Res. 15, No.3, 381-395. Pistikopoulos, E. N., 1995. Uncertainty inprocess design and operations. Computers and Chemical Engineering 19, S553-S563, suppl. S. Rockafellar, R., Wets, R. J.-B., 1991. Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16, 119-147. Ruszczynski, A., 1997. Decomposition methods in stochastic programming. MathProgramming (Ser. B) 79, 333353. Sahinidis, N. V., 2004. Optimization under uncertainty: State-of-the-art and opportunities. Comput. Chem. Eng. 28 (6-7), 971983. Schultz, R., 2003. Stochastic programming with integer variables. Mathematical Programming 97 (1-2), 285309. Subramanian, D., Pekny, J. F., Reklaitis, G. V., 2000. A simulation-optimization frame work for addressing combinatorial and stochastic aspects of an r&d pipeline management problem. Computers and Chemical Engineering 24 (27), 10051011.


36 Swaney, R. E., Grossmann, I. E., 1985. An index for operational flexibility in chemical process design. I. formulation and theory. Aiche Journal 31 (4), 621- 630 Vanslyke, R. M., Wets, R., 1969. L-shaped linear programs with applications to optimal control and stochastic programming. Siam Journal on Applied Mathematics 17 (4). Viswanath, K., Peeta, S., Salman, S., 2004. Investing in the links of a stochastic network to minimize expected shortest path length (Working paper).


MODEL PROGRAM STOKASTIK DENGAN KEPUTUSAN KETIDAKPASTIAN YANG TAK BEBAS

Recommend Documents