METODE PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL UNTUK MENYELESAIKAN PERMASALAHAN OPTIMISASI PROGRAM STOKASTIK DISKRIT TESIS. Oleh

METODE PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL UNTUK MENYELESAIKAN PERMASALAHAN OPTIMISASI PROGRAM STOKASTIK DISKRIT

TESIS

Oleh

UMMI HABIBAH 077021011/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

METODE PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL UNTUK MENYELESAIKAN PERMASALAHAN OPTIMISASI PROGRAM STOKASTIK DISKRIT

TESIS

Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

UMMI HABIBAH 077021011/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

Nama Mahasiswa Nomor Pokok Program Studi

: METODE PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL UNTUK MENYELESAIKAN PERMASALAHAN OPTIMISASI PROGRAM STOKASTIK DISKRIT : Ummi Habibah : 077021011 : Matematika

Menyetujui Komisi Pembimbing

(Dr. Sutarman, M.Sc) Ketua

Ketua Program Studi

(Prof.Dr.Herman Mawengkang)

(Dr. Saib Suwilo, M.Sc) Anggota

Direktur

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

Tanggal lulus : 2 Juni 2009


Telah diuji pada Tanggal : 2 Juni 2009

PANITIA PENGUJI TESIS Ketua Anggota

: :

Dr. Sutarman, M.Sc 1. Dr. Saib Suwilo, M.Sc 2. Prof. Dr. Opim Salim S., M.Sc 3. Drs. Open Darnius, M.Sc


ABSTRAK Penelitian ini mengemukakan atau menjelaskan suatu strategi penyelesaian untuk menyelesaikan permasalahan optimisasi program stokastik diskrit. Metode yang diajukan didasarkan pada pendekatan program stokastik melalui pengambilan sampel dan menyelesaikan persoalan pendekatan tersebut dengan memakai algoritma optimisasi. Teknik yang diajukan ini dapat menghasilkan suatu penyelesaian optimal terhadap persoalan awal dengan probabilitas mendekati satu dengan kecepatan proses eksponensial apabila ukuran sampel ditingkatkan. Kata Kunci : Program Stokastik, Optimal, Pendekatan Rata-rata Sampel, Optimisasi Diskrit.

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata SampeliUntuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

ABSTRACT This thesis addresses a solution strategy for solving stochastic discrete optimization programming problem. The proposed methodology relies on approximation the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. The proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially fast as the sample size increased. Keywords : Stochastic Program, Optimal, Sample Average Approximation, Discrete Optimization.

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata SampeliiUntuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

KATA PENGANTAR

Syukur Alhamdulillah kehadirat Allah SWT. Penulis panjatkan atas limpahan Rahmat dan Karunia-Nya karena terselesaikannya penulisan tesis ini yang berjudul Metode Pengembangan Pendekatan Rata-rata Sampel untuk Menyelesaikan Permasalahan Optimisasi Program Stokastik Diskrit. Pada kesempatan ini penulis menyampaikan ucapan terima kasih yang sebesarbesarnya kepada: Bapak Prof. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk menempuh pendidikan di Universitas Sumatera Utara. Ibu Prof. Dr. Ir. T. Chairun Nisa, B., M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang sudah memberikan kesempatan kepada penulis untuk mengikuti perkuliahan di Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan bimbingan kepada penulis sehingga tesis ini dapat diselesaikan. Bapak Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara dan selaku anggota komisi pembimbing yang telah memberikan saran dan bimbingan kepada penulis.

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampeliii Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

Seluruh staf pengajar pada program studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang yang sudah membimbing dan membantu selama penulis mengenyam pendidikan. Teruntuk Keluarga semuanya, Suami: Muhammad, ST,M.Sc dan anakanak : Zikri Alzuhayli dan Alya Muhammad. Orang tua, Abu: H Mukhtaruddin Ali dan Mak : Hj Fatimah Nusan, Kakak dan Adik-adik. Juga Mertua Abdul latief dan Mi: Hamidah dan adik-adik. Terima kasih kepada semuanya yang senantiasa mendukung dan mendoakan untuk keberhasilan penulis dalam menyelesaikan pendidikan ini. Kepada Teman-teman serta semua pihak yang tidak dapat penulis sebutkan satu persatu di sini, penulis ucapkan banyak terima kasih atas bantuan dan dorongan yang telah di berikan sehingga penulis dapat menyelesaikan pendidikan tepat waktu. Kepada Ibu Rosimanidar dan Keluarga yang telah banyak membantu penulis dalam menghadapi banyak kesulitan selama menyelesaikan pendidikan ini. Penulis menyadari tesis ini masih mempunyai kekurangan, namun demikian harapan penulis semoga tesis ini dapat bermanfaat bagi yang membutuhkannya.

Medan, Juni 2009 Penulis, (Ummi Habibah)

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampeliv Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

RIWAYAT HIDUP

Penulis dilahirkan di Punteut pada tanggal 1 Ramadhan 1396 H atau bertepatan dengan tanggal 26 Agustus 1976, sebagai anak kedua dari delapan bersaudara dari orang tua, H. Mukhtaruddin Ali dan Hj. Fatimah Nusan. Penulis menamatkan Sekolah Dasar (SD), SD Negeri Punteut pada tahun 1988. Sekolah menengah Pertama (SMP), SMP Negeri Bayu pada tahun 1991. Sekolah Menengah Atas (SMA), SMA Negeri 1 Lhokseumawe pada tahun 1994. Pada tahun 1994 penulis melanjutkan pendidikan sarjana di Universitas Syiah Kuala pada Fakultas Matematika dan Ilmu Pengetahuan Alam jurusan matematika dan lulus pada tahun 1999. Dari tahun 2001 hingga sekarang penulis dipercaya sebagai salah seorang staf pengajar pada Politeknik Negeri Lhokseumawe. Tahun 2007 penulis berkesempatan untuk melanjutkan program master pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara Medan.

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata SampelvUntuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

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

i

ABSTRACT

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

ii

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

iii

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

v

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

vi

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

1

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

1

1.2 Perumusan Permasalahan . . . . . . . . . . . . . . . . . . . .

3

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

3

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

4

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

4

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

5

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

9

3.1 Pengertian Program Stokastik

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

9

3.2 Permasalahan Optimisasi . . . . . . . . . . . . . . . . . . . .

10

3.3 Hasil-hasil Konvergen . . . . . . . . . . . . . . . . . . . . . .

11

3.3.1 Nilai Objektif dan Penyelesaian Konvergen

. . . . . . . .

11

3.3.2 Tingkat kekonvergenan . . . . . . . . . . . . . . . . . .

13

3.3.3 Nilai Objektif Sampel Asymptotic . . . . . . . . . . . . .

19

BAB 4 PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL 4.1 Penetapan Ukuran Sampel

. . . .

23

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

23

Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampelvi Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

4.2 Replikasi . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.3 Batas Capaian

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

26

4.4 Postprocessing, Penyaringan, dan Pemilihan . . . . . . . . . . .

28

4.5 Menyelesaikan permasalahan PRS . . . . . . . . . . . . . . . .

29

BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . . . .

32

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

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

33

vii Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Program stokastik tergolong suatu program matematika, dimana ianya merupakan metode dasar untuk menyelesaikan permasalahan optimisasi dibawah fungsi ketidakpastian. Bentuk permasalahan optimisasi memuat beberapa data pada fungsi tujuan dan kendala mengandung ketidakpastian dicirikan pada distribusi peluang dan parameter. Dalam permasalahan program stokastik akan dibuat suatu keputusan dengan mengoptimalkan nilai fungsi harapan (objektif) sebagai konsekuensi dari keputusan, pernyataan ini lebih dikenal dengan model recourse. Permasalahan program stokastik diskrit merupakan cabang program stokastik dengan bilangan diskrit yang menjadi peubah keputusan. Permasalahan optimisasi program stokastik diskrit telah banyak dikembangkan orang, dimana algoritma - algoritma stokastik yang dapat digunakan untuk menyelesaikan permasalahan program optimisasi diskrit antara lain menggunakan algoritma genetik, algoritma simulated annealing, algoritma tabu search. Diantara penelitian tersebut, Kleyweght (2001) menggunaan metode pendekatan rata-rata sampel atau the sample average approximation method (PRS) dalam menyelesaikan permasalahan optimisasi program stokastik diskrit yang diutamakan pada permasalahan stokastik knapsac. Selanjutnya Li (2006) melalukan penelitian tentang metode logaritma langsung untuk simulasi program stokastik diskrit pada sistim reaksi kimia.


1

2

Penelitian lain oleh Jeff (2006) mendapatkan pendekatan simulasi kejadian diskrit dengan variabel keputusan bilangan bulat menggunakan COMPASS (Convergent Optimization via Most-Promising-Area Stochastic Search). Kemudian Chang (2007) juga telah mempresentasikan suatu algoritma dasar-sampling permasalahan optimisasi program stokastik diskrit melalui pendekatan nonstochastic multi-armed bandit. Borndorfer (2008) menuliskan tentang permasalahan optimisasi diskrit dalam transportasi publik. Selanjutnya Shi (2008) telah mengembangkan suatu algoritma baru untuk menyelesaikan permasalahan optimisasi program stokastik diskrit pengalokasian sumber yang dicontohkan pada permasalahan pengalokasian buffer dalam jaringan telekomunikasi dan pengalokasian sumber dalam sistim perpabrikan. Algoritma baru tersebut merupakan hasil kombinasi dari metode Nested Partitions, Teknik Ordinal Optimization, dan suatu teknik Efficient Simulation Control. Hasil numerik perpaduan algoritma tersebut efektif digunakan dalam skala besar pada permasalahan optimisasi program stokastik diskrit. Dan masih banyak penelitian-penelitian lain. Penggunaan metode PRS untuk menyelesaikan permasalahan optimisasi program stokastik juga telah banyak digunakan oleh peneliti-peneliti sebelumnya. Diantaranya, Ahmed (2002) menggunakan metode PRS untuk menyelesaikan permasalahan program stokastik dengan Integer Recourse. Kemudian Greenwald (2008) menggunakan metode PRS untuk menyelesaikan permasalahan optimisasi program stokastik yang diterapkan pada agen perdagangan. Selanjutnya Rossi (2008) menggunakan metode PRS untuk menyelesaikan permasalahan program Even-Driven Probabilistic Constrain. Masih banyak lagi yang belum disebutkan di sini. Adapun alasan penelitian ini menggunakan metode pengembangan PRS untuk menyelesaikan permasalahan optimisasi program stokastik diskrit disebabkan karena


3

probabilitas replikasi dari penggunaan metode PRS akan menghasilkan suatu penyelesaian optimal yang akan meningkatkan tingkat eksponensial dalam ukuran sampel N. Hal ini ditunjukkan oleh tingkat kekonvergenan yang bergantung pada kondisi sesuai dari permasalahan tersebut, diikuti dengan kecendrungan menurun dengan bertambahnya variabel keputusan. Ukuran sampel diperlukan di sini untuk peningkatan ketelitian yang sebanding dengan logaritma banyaknya penyelesaian yang mungkin. Perkiraan gap optimalitas dipertimbangkan pada kasus yang terlalu lemah untuk menunjukkan bahwa suatu penyelesaian yang sebenarnya akan diperoleh. Metode PRS mempunyai kelebihan untuk dikombinasikan dengan teknik yang ada dalam memecahkan permasalahan optimisasi deterministik. Metode yang diusulkan melibatkan pemecahan beberapa replikasi pendekatan rata-rata sampel untuk permasalahan optimisasi, dan mungkin terjadi peningkatkan ukuran sampel beberapa kali. Prilaku perhitungan yang kompleksitas dari metode PRS untuk memecahkan permasalahan optimisasi adalah sebagai suatu fungsi dari ukuran sampel. 1.2 Perumusan Permasalahan Untuk mendapatkan penyelesaian optimal (maksimun atau minimum) dalam permasalahan optimisasi program stokastik diskrit sukar dilakukan sehingga perlu pendekatan pada fungsi nilai yang diharapkan dengan memakai metode PRS. 1.3 Tujuan Penelitian Penelitian ini bertujuan untuk mendapatkan suatu metode pengembangan PRS dalam memperoleh nilai fungsi optimal dari permasalahan optimisasi program stokastik diskrit.


4

1.4 Kontribusi Penelitian Penelitian ini diharapkan dapat memberikan kontribusi pada memperolehnya metode pengembangan PRS untuk menyelesaikan permasalahan keputusan pada perencanaan yang mengandung ketidakpastian. 1.5 Metodologi Penelitian Penelitian ini membahas metode pengembangan PRS untuk menyelesaikan permasalahan optimisasi program stokastik diskrit. Sebagai langkah awal pada BAB 2 akan dibicarakan tentang permasalahan optimisasi program stokastik diskrit. Kemudian pada BAB 3 akan dibicarakan tentang permasalahan program stokastik. Selanjutnya pada BAB 4 akan dibahas tentang metode pengembangan PRS yang akan digunakan untuk mendapatkan penyelesaian optimal dari permasalahan optimisasi program stikastik diskrit. Dan pada BAB 5 menyimpulkan kesimpulan dan saransaran.


BAB 2 TINJAUAN PUSTAKA

Permasalahan optimisasi program stokastik untuk model ketidakpastian di dalam data masukan, yang mana ketidakpastian tersebut diperagakan oleh suatu distribusi peluang. Paradigma kesulitan stokastik dapat dipelajari melalui model, masukan yang direalisir diungkapkan melalui suatu rangkaian langkah-langkah dan seseorang dapat mengambil keputusan dari setiap langkah sebagai jawaban atas informasi yang baru dipelajari. Dalam model perencanaan, menurut Shi (2008) ada kalanya kendala yang akan membatasi suatu permasalahan dapat dinyatakan oleh peubah bilangan diskrit, sebagai contoh terapan pada permasalahan pengalokasian sumber seperti perencanaan fasilitas, penjadwalan pekerjaan, pengalokasian buffer, pengontrolan populasi, dan manajemen portofolio tergolong dalam permasalahan optimisasi program stokastik diskrit. Program stokastik diskrit merupakan salah satu kajian permasalahan optimisasi yang sukar untuk dipecahkan. Dimana untuk permasalahan program stokastik diskrit ini fungsi nilai yang diharapkan atau fungsi objektif g(x) memiliki bentuk sangat rumit dan sukar untuk menghitung kejadian yang akan diperkirakan. Karenanya permasalahan program stokastik diskrit ini merupakan salah satu permasalahan yang sulit sehingga sedikit kemajuan dalam perkembangan pemecahannya sebagaimana dikemukakan oleh Keyweght (2001). Algoritma-algoritma program stokastik yang dapat digunakan untuk menyelesaikan permasalahan optimisasi program stokastik diskrit diantaranya algoritma genetik (AG), algoritma simulated annealing (SA), dan algoritma tabu search (TS). Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

5

6

Algoritma-algoritma ini merupakan metoda probabilitas dalam fungsi optimisasi yang berfungsi untuk menjadikan penyelesaian menjadi optimal (maksimum atau minimum), mungkin dengan penambahan suatu masukkan untuk mencegah infeasibel. Permasalahan optimisasi program stokastik diskrit telah banyak dikembangkan orang, diantaranya penelitian oleh Shi (2008) yang telah mengembangkan suatu algoritma baru untuk menyelesaikan permasalahan optimisasi program stokastik diskrit pengalokasian sumber. Algoritma baru tersebut merupakan hasil kombinasi dari metode Nested Partitions, Teknik Ordinal Optimization, dan suatu teknik Efficient Simulation Control. Hasil kombinasi tersebut sesuai dengan perspektif global didasari oleh metode Nested Partitions dan bersifat konvergen yang cepat, didasari oleh teknik Ordinal Optimization. Hasil numerik perpaduan algoritma tersebut efektif digunakan dalam skala besar pada permasalahan optimisasi program stokastik diskrit. Kemudian penelitian oleh Chang (2007) dimana canya telah mempresentasikan suatu algoritma dasar-sampling untuk memecahkan dasar permasalahan optimisasi program stokastik diskrit melalui pendekatan nonstochastic multi-armed bandit. Dimana algoritma tersebut memecahkan permasalahan PRS yang sebenarnya dengan memperbaharui iteratif dan sampling dari suatu distribusi peluang ruang pencarian. Selanjutnya penelitian oleh Kleyweght (2001) yang menggunaan metode PRS dalam permasalahan optimisasi program stokastik diskrit yang diutamakan pada permasalahan stokastik knapsac. Metode ini menggunakan pendekatan dasar simulasi Monte Carlo untuk permasalahan optimisasi program stokastik diskrit. Dimana ide dasar dari metode ini adalah membangkitkan suatu sampel acak dan kemudian fungsi nilai yang diharapkan didekati dengan fungsi rata-rata sampel yang sesuai.


7

Penelitian lain oleh Jeff (2006) juga telah mendapatkan suatu pemecahan permasalahan optimisasi program stokastik diskrit dengan simulasi SCOMPASS (Convergent Optimization via Most-Promising-Area Stochastic Search). Dimana metode ini menggunakan pendekatan simulasi dengan proses stokastik yang disebut simulasi kejadian diskrit dan variabel keputusannya adalah bilangan bulat. Kemudian penelitian oleh Li (2006) menghasilkan metode logaritma langsung untuk simulasi stokastik diskrit pada sistem reaksi kimia. Penelitian ini menghasilkan suatu simulasi lebih akurat dengan penggunaan teori proses Markov, khususnya algoritma simulasi stokastik. Selanjutnya penelitian oleh Alrefaei (1999) menggunakan algoritma simulated annealing dengan konstanta temperatur untuk permasalahan optimisasi stokastik diskrit. Dimana ianya mempresentasikan suatu metode untuk mendapatkan penyelesaian optimal global pada permasalahan optimisasi program stokastik diskrit. Metode tersebut dibuat serupa dengan metode simulated annealing untuk optimisasi deterministik diskrit. Ada banyak literatur yang membahas pendekatan-pendekatan lain untuk menyelesaikan permasalahan program stokastik diskrit ini dimana banyaknya penyelesaiannya cukup kecil yang memenuhi syarat penilaian g(x) untuk masing-masing nilai x . Secara fakta bahwa nilai fungsi objektif tidak diketahui secara pasti. Dalam tulisan ini dipilih metode PRS untuk permasalahan program stokastik diskrit, dimana ide dasar dari pendekatan ini adalah membangkitkan suatu sampel acak W dengan harapan bahwa fungsi nilai yang diharapkan didekati oleh fungsi rata-rata sampel yang bersesuaian sebagaimana dibahas oleh Kleywegt (2001). Kemudian permasalahan optimisasi rata-rata sampel yang diperoleh dipecahkan, dan procedurnya diulangi beberapa kali hingga batas berhenti di penuhi. Disini akan diUmmi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

8

tunjukkan bahwa peluang mendekati satu bersifat eksponensial dengan peningkatan ukuran sampel, dimana suatu penyelesaian optimal dari permasalahan pendekatan rata-rata sampel tersebut merupakan suatu penyelesaian yang sebenarnya dari permasalahan optimisasi.


BAB 3 PROGRAM STOKASTIK

3.1 Pengertian Program Stokastik Program stokastik berkembang sangat cepat karena pemakaiannya pada perencanaan dalam pengambilan keputusan yang mengandung ketidakpastian. Proses pengambilan keputusan dapat dimodelkan menggunakan program matematika dengan tujuan mendapatkan penyelesaian optimal, maksimum maupun minimum. Penyelesaian optimal sebagai keputusan yang dipilih bergantung pada kendala yang membatasi permasalahan, seperti persyaratan minimum pada sumber dana, waktu, tenaga, dan fasilitas-fasilitas lain. Tujuan dan kendala adalah berupa fungsi dari variabel dan persoalan data. Sebagai contoh dari persoalan data termasuk biaya perunit, rata-rata produksi, penjualan, dan kapasitas. Andaikan keputusan yang dipilih dinyatakan dengan peubah x1, x2 , x3, · · · , xn . Sebagai contoh xi menyatakan pengalokasian sumber ke i dari n total sumber, maka bentuk umum persamaan matematika dapat ditulis sebagai berikut: Fungsi objektif : maxZ = f (x) Kendala : fi (x) ≥ bi , i = 1, 2, 3, · · · , n x ≥ 0, x ∈ X

(3.1)

dimana X adalah himpunan bilangan riil nonnegatif . Program stokastik dapat dimodelkan menggunakan program matematika, dimana ianya memiliki peubah berupa: linier, cacah, cacah campuran, nonlinier, maupun diskrit dengan menampilkan elemen-elemen stokastik dalam data. Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

9

10

Program stokastik sebagai model dari program matematika dapat dibedakan menjadi dua model berikut:

1. Program matematika deterministik dengan data adalah bilangan yang diketahui. 2. Program stokastik dengan data bilangan yang tidak diketahui (ketidakpastian) yang ditampilkan dalam distribusi peluang.

3.2 Permasalahan Optimisasi Bentuk umum permasalahan optimisasi ditulis : min {g(x) := Ep G(x, W )}

(3.2)

x∈S

dimana W merupakan suatu vektor acak dengan distribusi peluang P, S suatu himpunan berhingga (S merupakan suatu subset Rn berhingga dengan koordinat bilangan bulat), G(x, w) merupakan suatu fungsi bernilai riil dari dua (vektor) variabel x dan R w, dan Ep G(x, W ) = G(x, w)P (dw) sebagai fungsi objektif atau nilai yang diharapkan. Fungsi g(x) sebagai nilai yang diharapkan, diasumsikan terdifinisi dengan baik. Untuk setiap x ∈ S fungsi G(x, .) terukur dan EP {|G(x, W )|} < ∞.Terdapat beberapa karakteristik utama dalam permasalahan optimisasi diantaranya:

1. Fungsi nilai yang diharapkan g(x) = EP G(x, W ) tidak dapat ditulis dalam suatu bentuk tertutup atau nilainya tidak dapat dihitung dengan mudah. 2. Fungsi G(x, w) dapat dihitung dengan mudah bila diberikan nilai variabel x dan w. 3. Himpunan S untuk penyelesaian feasibel walaupun berhingga, merupakan himpunan sangat besar. Himpunan tersebut tumbuh secara eksponensial dengan variabel yang banyak. Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

11

Pada bagian ini akan dibicarakan sifat-sifat konvergensi dari estimator PRS, terutama yang diterapkan pada permasalahan optimisasi program stokastik diskrit. Untuk pemakaian hasil klasik, seperti Hukum Bilangan Besar, perlu diandaikan bahwa sampel yang dibentuk bersebaran bebas identik (bbi). Namun perlu diperhatikan bahwa sifat-sifat konvergensi dapat diturunkan terhadap kondisi lebih luas. 3.3 Hasil-hasil Konvergen Misalkan W 1, · · · , , W N merupakan sampel acak bbi untuk N realisasi vektor N P G (x, W j ) maka acak W . Fungsi rata-rata sampelnya ditulis sebagai gˆN (x) = N1 j=1

permasalahan optimisasi menjadi: (3.3)

min gˆN (x) x∈S

Dengan mengacu pada persamaan (3.2) dan (3.3) sebagai persamaan untuk mengharapkan nilai optimal dari permasalahan PRS. Ekspektasi fungsi nilai E [ˆ gN (x)] = g (x). Himpunan feasibel S berhingga, maka permasalahan (3.2) dan (3.3) mempunyai penyelesaian optimal, ditandai dengan S ∗ dan SˆN . Misalkan v ∗ dan vˆN menandakan nilai-nilai optimal, dengan nilai v ∗ = min g (x) dan vˆN = min gˆN (x) x∈S

x∈S

Di sini juga dipertimbangkan himpunan penyelesaian ε-optimal. Untuk ε ≥ 0 dikatakan bahwa x ¯ sebagai suatu penyelesaian ε-optimal persamaan (3.2) jika x ¯∈S dan g (¯ x) ≤ v ∗ + ε. Himpunan semua penyelesaian ε-optimal persamaan (3.2) dan ε . Jelasnya untuk ε = 0 himpunan S ε bersamaan dengan (3.3) ditandai oleh S ε dan SˆN ε bersamaan dengan SˆN . S ∗ , dan SˆN

3.3.1 Nilai Objektif dan Penyelesaian Konvergen Teorema berikut menetapkan konvergen dengan peluang satu (dp1) pada estimator statistik di atas. Suatu peristiwa terjadi dp1 untuk N cukup besar artinya Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

12

untuk P-hampir tiap-tiap realisasi ω = {W 1 , W 2, · · · } sebagai barisan acak, di sana ada suatu bilangan bulat N (ω). Peristiwa yang dipertimbangkan terjadi untuk semua sampel {W 1, · · · , W n } dari ω dengan n ≥ N (ω). Pernyataan tersebut menyatakan yang demikian merupakan bilangan bulat N(ω) bergantung pada barisan realisasi ω adalah acak. Teorema 1: Berikut ini merupakan dua sifat pegangan:

i. vˆN → v ∗ merupakan dp1 ketika N → ∞, dan ε ⊂ S ε } terjadi dp1 untuk N cukup besar. ii. untuk ε ≥ 0 manapun peristiwa {SˆN

Bukti: Mengikuti Hukum Bilangan Besar untuk x ∈ S manapun, gˆN (x) konvergen ke g(x) merupakan dp1 ketika N → ∞. Himpunan S berhingga dan gabungan suatu jumlah berhingga menetapkan masing-masing himpunan terukur nol juga mempunyai ukuran nol. Mengikuti dp1, gˆN (x) konvergen ke g(x) yang bersifat unif orm dalam x ∈ S. Pernyataan itu adalah, gN (x) − g(x)| → 0 merupakan dp1 ketika N → ∞ δN = max |ˆ

(3.4)

x∈s

Karena |ˆ vN − v ∗| ≤ δN , mengikuti dp1 vˆN → v ∗ ketika N → ∞. Untuk ε ≥ 0 pertimbangkan bilangan, ρ (ε) = min ε g (x) − v ∗ − ε

(3.5)

x∈S\S

Untuk x ∈ S\S ε manapun memberikan g(x) > v ∗ + ε dan himpunan S berhingga, menyebabkan ρ(ε) > 0. Misalkan N sebagai bilangan cukup besar seperti δN <

ρ(ε) . 2

Kemudian vˆN <

dan untuk x ∈ S\S ε manapun memberikan gˆN (x) > v ∗+ε+ ρ(x) . Menyebabkan v ∗ + ρ(ε) 2 2


13

ε jika x ∈ S\S ε , maka gˆN (x) > vˆN + ε dan karenanya x bukan anggota himpunan SˆN . ε ⊂ S ε . Terbukti. Menyebabkan SˆN δ ε ⊂ SˆN . Mengikuti Jika δ suatu bilangan 0 ≤ δ ≤ ε, kemudian S δ ⊂ S ε dan SˆN δ ⊂ S ε terjadi dp1 untuk Teorema 1 di atas untuk δ ∈ [0, ε] manapun, peristiwa SˆN ε = {x∗ } dp1 N cukup besar. Menyebabkan jika S ε = {x∗} suatu singleton, maka SˆN

untuk N cukup besar. Khususnya, jika permasalahan (3.2) sebenarnya mempunyai suatu penyelesaian optimal unik x∗, kemudian dp1 untuk memperkirakan N yang ˆN = x∗. besar, permasalahan (3.3) mempunyai penyelesaian optimal unik x ˆN dan x Misalkan himpunan A = {g(x) − v ∗ : x ∈ S} merupakan suatu subset dari himpunan R+ dengan bilangan nonnegatif dan |A| ≤ |S|, karenanya A berhingga. δ = S ε} Mengikuti analisa di atas untuk ε ∈ R+ \A manapun adalah suatu peristiwa {SˆN

terjadi dp1 untuk N cukup besar. 3.3.2

Tingkat kekonvergenan Hasil di atas tidak menunjukkan segalanya tentang tingkat kekonvergenan vˆN

δ dan SˆN kepada mitra yang sebenarnya. Dengan penggunaan teori Deviasi Besar (DB), δ ⊂ S ε } mendekati 1 bersifat menunjukkan bahwa, pada δ ∈ [0, ε] peluang peristiwa {SˆN

exponensial yang cepat ketika N → ∞. δ Anggaplah ε ≥ 0, δ ∈ [0, ε], dan peristiwa {SˆN = S ε }. Pernyataan berikut

menyatakan bahwa: o n [ \ δ ε ˆ {ˆ gN (x) ≤ gˆN (y) + δ} SN 6⊂ S =

(3.6)

x∈S\S ε y∈S

Karenanya: n

o

δ P SˆN 6⊂ S ε ≤

X x∈S\S ε

P

\

!

{ˆ gN (x) ≤ gˆN (y) + δ}

(3.7)

y∈S

Anggaplah suatu pemetaan u : S\S ε . Pernyataan berikut mengikuti dari persamaan Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

14

(3.7) bahwa: n o X δ P SˆN 6⊂ S ε ≤ P (ˆ gN (x) − gˆN (u (x)) ≤ δ)

(3.8)

x∈S\S ε

Kita berasumsi bahwa pemetaan u(x) dipilih sedemikian sehingga untuk beberapa ε∗ > ε, menyebabkan g (u (x)) ≤ g (x) − ε∗ untuk semua x ∈ S\S ε

(3.9)

Jika u(.) adalah suatu pemetaan dari S\S ε ke himpunan S ∗ , dimana u(x) ∈ S ∗ untuk semua x ∈ S\S ε , maka persamaan (3.9) menyatakan bahwa: ε∗ = min ε g (x) − v ∗ x∈S\S

(3.10)

dan ε∗ > ε karena himpunan S berhingga. Oleh karena itu suatu pemetaan u(.) sesuai dengan kondisi persamaan (3.9) yang selalu ada. Karena masing-masing x ∈ S\S ε , misalkan H(x, w) = G(u(x), w) − G(x, w), maka ekspektasi E|H(x, W )| = G(u(x)) − G(x), maka ekspektasi E|H(x, W )| ≤ −ε∗ . Misalkan W1 , · · · , WN sampel acak bbi untuk N realisasi vektor acak W, anggaplah N ˆ N (x) = 1 P H (x, W j ) = gˆN (u (x)) − gˆN (x). fungsi rata-rata sampel sebagai: h N j=1

Pernyataan berikut mengikuti dari persamaan (3.8) yaitu: o n X δ ε ˆ ˆ P hN (x) > −δ P SN 6⊂ S <

(3.11)

x∈S\S ε

Misalkan Ix(.) menandakan fungsi tingkat DB . Ketidaksamaan (3.11) menyiratkan bahwa: o X δ ε ˆ e−N Ix (−δ) P SN 6⊂ S < n

(3.12)

x∈S\S ε

Adalah penting untuk catatan bahwa ketidaksamaan (3.12) di atas tidaklah asymptotic dan valid untuk sampel acak dengan ukuran N manapun. Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

15

Asumsi ( A): Untuk tiap-tiap x ∈ S menyebabkan fungsi pembangkit moment dari variabel acak H(x, W ) berhingga dalam suatu neighborhood 0. Asumsi ( A) di atas menyatakan bahwa, jika H(x, W ) suatu variabel acak yang dibatasi, atau jika H(x, .) tumbuh secara linier dan W mempunyai himpunan distribusi bersifat exponensial. Teorema 2: Misalkan ε dan δ bilangan nonnegatif seperti δ ≤ ε , maka o n δ 6⊂ S ε ≤ |S\S ε | e−Nγ(δ,ε) P SˆN

(3.13)

γ (δ, ε) = min ε Ix (−δ)

(3.14)

di mana

x∈S\S

Lebih dari itu, jika Asumsi ( A) sebagai pegangan, maka γ (δ, ε) > 0 Bukti: Ketidaksamaan (3.13) adalah suatu konsekwensi utama dari ketidaksamaan (3.12). Pernyataan tersebut menyatakan bahwa −δ > −ε∗ ≥ E[H(x, W )], dan karenanya mengikuti Asumsi ( A) bahwa Ix(−δ) > 0 untuk tiap-tiap x ∈ S\S ε . Ini menyiratkan bahwa γ(δ, ε) > 0. Terbukti. Hasil asymptotic berikut adalah suatu konsekwensi utama ketidaksamaan (3.13) yaitu: 1 δ ε ˆ lim sup log[1 − P SN ⊂ S ] ≤ −γ (δ, ε) N →∞ N

(3.15)

δ ⊂ S ε) Mengikuti ketidaksamaan (3.15) menyebabkan peluang peristiwa (SˆN

mendekati 1 secara exponensial yang cepat ketika N → ∞. Sampling Monte Carlo yang dikombinasikan dengan suatu metoda efisien untuk memecahkan permasalahan Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

16

PRS yang deterministik, dengan ketentuan bahwa konstanta γ(δ, ε) bukanlah terlalu kecil. Konstanta γ(δ, ε) dalam persamaan (3.14) dapat didekati oleh: γ (δ, ε) ≈ min ε x∈S\S

(ε∗ − δ)2 (ε − δ)2 (−δ − E |H (x, W )|)2 ≥ > 2 2 2σx2 2σmax 2σmax

(3.16)

di mana, 2 = maxε V ar (G (u (x) , W ) − G (x, W )) σmax x∈S\S

(3.17)

Fungsi tingkat DB variabel acak G(x, W ) yang digunakan, mengakibatkan perkiraan bersifat konstanta exponensial serupa kepada menaksir persamaan (3.16) tetapi dengan σx2 yang digantikan oleh varians G(x, W ). Dalam kaitan dengan suatu hal korelasi positif antara G(x, W ) dan G(u(x), W ), varians G(x, W ) − G(u(x), W ) cenderung menjadi lebih kecil dibanding varians G(x,W), dengan demikian batas atasnya o n δ 6⊂ S ε , terutama ketika u(x) dipilih untuk memperkecil lebih kecil dari pada P SˆN var[G(x, W ) − G(u(x), W )] [g(x) − g(u(x))]2 Untuk menggambarkan implikasi beberapa batas persamaan (3.13) karena isu kompleksitas memecahkan permasalahan stokastik, ditentukan suatu tingkat signifikan δ ⊂ α ∈ (0, 1), dan penaksiran ukuran sampel N yang diperlukan untuk peluang P {SˆN

S ε } menjadi sedikitnya 1 − α. Dengan ruas kanan persamaan (3.13) menjadi kecil dari atau sama dengan α, diperoleh: 1 log N≥ γ (δ, ε)

|S\S ε | α

Lebih dari itu persamaan (3.14) menjadikan γ(δ, ε) ≥

(3.18) (ε−δ)2 2 3σmax

untuk semua ε ≥ 0

yang kecil. Oleh karena itu untuk semua ε ≥ 0 yang cukup kecil dan δ ∈ (0, ε), suatu kondisi cukup untuk persamaan (3.18) adalah: 2 3σmax log N≥ (ε − δ)2

|S| α

(3.19)


17

Batas persamaan (3.19) mungkin terlalu konservatif untuk perkiraan praktis ukuran sampel yang diperlukan. Bagaimanapun, perkiraan persamaan (3.19) mempunyai konsekwensi menarik untuk isu kompleksitas. Suatu karakteristik kunci persamaan (3.19) adalah N hanya bergantung kedua-duanya secara logaritma pada himpunan feasibel S dan peluang toleransi α. Anggaplah:

i. ukuran himpunan feasibel S tumbuh paling banyak secara exponensial, 2 tumbuh secara polinomial, ii. varians σmax

iii. kompleksitas menghasilkan suatu penyelesaian δ-optimal untuk persamaan (3.3) tumbuh secara polinomial pada ukuran sampel N.

Kemudian penyelesaian yang tumbuh secara polinomial, dengan peluang sedikitnya 1 − α, disebut penyelesaian ε-optimal untuk persamaan (3.2). Sekarang anggaplah suatu moment permasalahan yang sebenarnya mempunyai penyelesaian optimal unik x∗ , yaitu S ∗ = {x∗} adalah suatu singleton, dan pertimbangkan peristiwa permasalahan PRS persamaan (3.3) mempunyai penyelesaian optiˆN = x∗ . Peristiwa itu ditandai oleh {ˆ xN = x∗ }. Lagipula, anggaplah mal unik x ˆN dan x pemetaan u : S\S ε → {x∗ }, yaitu u(x) = x∗ , dan konstan bersesuaian γ ∗ = γ(0, 0). Pernyataan berikutnya adalah: γ∗ =

min Ix(0)

x∈S\{x∗ }

(3.20)

dengan Ix(.) menjadi fungsi tingkat DB yaitu G(x∗, W ) − G(x, W ). Maka ekspektasi nilai E|G(x∗ , W )−G(x, W )| = g(x∗)−g(x) dan karenanya E|G(x∗ , W )−G(x, W )| < 0 untuk tiap-tiap x ∈ S\{x∗}. Oleh karena itu, jika Asumsi (A) sebagai pegangan, fungsi pembangkit moment G(x∗, W )−G(x, W ) bernilai berhingga dalam suatu neighborhood 0, kemudian γ ∗ > 0. Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

18

Teorema 3: Anggaplah permasalahan sebenarnya mempunyai penyelesaian optimal unik x∗ dan fungsi pembangkit moment dari tiap-tiap variabel acak G(x∗ , W ) − G(x, W ), x ∈ S\{x∗ }, adalah bernilai berhingga pada R. Kemudian 1 log [1 − P (ˆ xN = x∗)] = −γ ∗ N →∞ N lim

(3.21)

Bukti: Mengikuti persamaan (3.15), lim sup N →∞

1 log[1 − P (ˆ xN = x∗ )] ≤ −γ ∗ N

(3.22)

xN 6= x∗}. PeriAnggaplah komplemen peristiwa {ˆ xN = x∗}, ditandai dengan {ˆ gN (x) ≤ gˆN (x∗)}, x ∈ S\{x∗}. stiwa {ˆ xN 6= x∗} sama dengan gabungan peristiwa {ˆ xN 6= x∗ ≥ P (ˆ gN (x) ≤ (ˆ gN (x∗)). DeOleh karena itu, untuk x ∈ S\{x∗} manapun, P (ˆ ngan penggunaan batas bawah teorema DB Cramers, pernyataan tersebut mengikuti ketidaksamaan berikut: lim inf N →∞

1 log[1 − P (ˆ xN = x∗)] ≥ −Ix (0) N

(3.23)

Sebagai pegangan untuk tiap-tiap x ∈ S\{x∗}. Ketidaksamaan (3.22) dan (3.23) menyiratkan persamaan (3.21). Terbukti. Anggaplah S ∗ = {x∗} dan bilangan, κ = max∗ x∈S\{x

V ar [G (x, W ) − G (x∗, W )] 2 } [g (x) − g (x∗ )]

Dengan mengikuti persamaan (3.21), bahwa κ ≈

1 .κ (2γ)2

(3.24)

dipandang sebagai suatu

bilangan berkondisi permasalahan sebenarnya. Ukuran sampel peristiwa {ˆ xN = x ∗ } diperlukan untuk terjadi dengan peluang ditentukan secara kasar sebanding dengan κ.


19

Permasalahan dengan suatu himpunan feasibel besar S, bilangan

min g (x)−

x∈S\{x∗ }

g (x∗) walaupun positif jika S ∗ = {x∗ } cenderung menjadi kecil. Oleh karena itu ukuran sampel diperlukan untuk mengkalkulasikan penyelesaian optimal {x∗} yang tepat. Karena permasalahan dalam keadaan kurang baik, dicari pendekatan penyelesaian (ε-optimal) dari permasalahan sebenarnya. Batas persamaan (3.13) jadilah lebih informatif karena konstanta bersesuaian γ(δ, ε) dijamin untuk menjadi order sedikit (ε−δ)2 . 2 2σmax

Pernyataan di atas juga insightful untuk mencatat suatu perilaku kondisi bilangk P an κ permasalahan optimisasi diskrit dengan fungsi objektif linier G (x, W ) = W i xi i=1 k

dan himpunan feasibel S memberikan vertex dari hypercube unit R , yaitu S = {0, 1}k . Di dalam kasus tersebut permasalahan optimisasi sebenarnya adalah bersesuaian de k P g (x) = $i xi dimana $i = E [Wi ] Umpamakan bahwa $i > 0 ngan min x∈{0,1}k

i=1

untuk semua i ∈ {1, · · · , k}, adalah penyelesaian optimal unik dari permasalahan sebenarnya, yaitu S ∗ = {0}. Diberikan ϑ2i = ρij = √

Cov[Wi ,Wj ]

√

V ar[Wi ]

V ar[Wj ]

V ar[Wi ] (E[Wi ])2

menandakan koefisien variasi kuadrat Wi , dan misalkan

menandakan koefisien korelasi antara Wi dan Wj . Pernyataan

tersebut untuk x ∈ {0, 1}k \{0} manapun, mengikuti: max ϑ2i . Seperti itu, κ =

i∈{1,...,k}

P V ar[ ki=1 Wi xi ] Pk 2 x∈{0,1}k \{0} [ i=1 $i xi ]

max

P V ar [ ki=1 Wi xi ] Pk 2 [ i=1 $i xi ]

=

Pk

i=1

Pk

ρij ϑi $i xi ϑj $j xj Pk i=1 j=1 $i xi $j xj

Pk

j=1

= max ϑ2i i∈{1,...,k}

Persamaan yang terakhir mengikuti sebab yang maksimum dicapai dengan pengaturan xi = 1 untuk index i di mana W i mempunyai koefisien maksimum variasi kuadrat ϑ2i , dan menentukan xj = 0 untuk variabel sisa. 3.3.3 Nilai Objektif Sampel Asymptotic Subset S dari S mengikuti ketidaksamaan vˆN ≤ minx∈S 0 gˆN (x). Khususnya, dengan S = S ∗, pernyataan tersebut mengikuti vˆN ≤ minx∈S ∗ gˆN (x), dan karenanya


≤

20

vN ] ≤ E merupakan estimator vˆN yang bias negatif, ekspektasi nilai E [ˆ

min gˆN (x)

x∈S ∗

≤

gN (x)] = v ∗ min E [ˆ

x∈S ∗

Pernyataan tersebut mengikuti Teorema 2 dp1 untuk N cukup besar, dimana himpunan SˆN penyelesaian optimal permasalahan PRS tercakup di dalam S ∗. Di dalam kasus tersebut menyatakan bahwa, vˆN = min gˆN (x) ≥ min∗ gˆN (x). Karena x∈S

x∈δˆN

ketidaksamaan kebalikan sebagai pegangan, pernyataan tersebut mengikuti dp1, dimana vˆN − min∗ gˆN (x) = 0 untuk N cukup besar. Kemudian kalikan kedua ruas x∈S √ √ vN − min∗ gˆN (x)] = 0 untuk persamaan ini oleh N yang mengikuti dp1, menjadi N [ˆ x∈S

N cukup besar, dan karenanya lim

N →∞

√ N [ˆ vN − min∗ gˆN (x)] = 0 x∈S

dp1

(3.25)

Karena dp1 konvergen menyiratkan konvergen di dalam peluang, pernyataan tersebut √ vN − min∗ gˆN (x)] konvergen dalam peluang mengikuti persamaan (3.25) bahwa N [ˆ x∈S −1 kepada nol, yaitu vˆN = min∗ gˆN (x) + oP N 2 . Lagipula, karena v ∗ = g(x) untuk x∈S

∗

x ∈ S manapun, pernyataaan tersebut berubah menjadi: n√ o √ √ ∗ ∗ N[min∗ gˆN (x) − v ] = N min∗[ˆ gN (x) − v ] = min∗ N [ˆ gN (x) − g (x)] x∈S

x∈S

x∈S

Anggaplah bahwa untuk tiap-tiap x ∈ S varians dapat ditulis menjadi: τ 2(x) = var(G(x, W ))

(3.26)

ada. Kemudian mengikuti teorema limit pusat (TLP) bahwa, untuk x ∈ S o n√ N [ˆ gN (x) − g (x)] konvergen dalam distribusi kepada suatu variabel manapun, yang didistribusikan secara normal Z(x) dengan rata-rata nol dan varians σ 2(x). Lebih dari itu, mengikuti TLP, variabel acak Z(x0 ) mempunyai fungsi kovarians yang sama sebagai G(x0 , W ), yaitu: kovarians antara Z(x) danZ(x ) sama dengan kovarians antara G(x, W ) dan G(x, W ) untuk x, x0 ∈ S manapun . Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

21

Anggaplah varians σ 2(x) yang digambarkan dalam persamaan (3.26), ada untuk tiap-tiap x ∈ S ∗ kemudian √ N (ˆ vN − v ∗) ⇒ min∗ Z (x)

(3.27)

x∈S

dimana Z(x) suatu variabel acak berdistribusi secara normal dengan rata-rata nol dan fungsi kovarians yang bersesuaian G(x, W ). Jika S ∗ = (x∗ ) adalah suatu singleton, kemudian √

N (ˆ vN − v ∗) ⇒ N 0, σ 2 (x∗ )

(3.28)

Walaupun untuk x manapun sebagai nilai rata-rata yang diharapkan dari Z(x) adalah nol, yang diharapkan nilai minimum Z(x) di atas suatu subset S 0 dari S dapat negatif dan cenderung menjadi lebih kecil untuk suatu himpunan lebih besar S 0 . Oleh karena itu, mengikuti persamaan (3.28) untuk permasalahan dalam kondisi yang kurang baik, dimana himpunan dari penyelesaian atau hampir optimal adalah besar, perkiraan vˆN dari v ∗ cenderung menjadi dibiaskan. Di bawah kondisi tambahan √ vN ) − v ∗) → E[minx∈S ∗ Z (x)]. mengikuti persamaan (3.28) bahwa N (E(ˆ Hal penting yang perlu diperhatikan adalah sebagai berikut:

ˆN konvergen terhadap mitranya v ∗ dan x∗ apabila ukuran 1. Apakah vˆN dan x sampel N dinaikkan. 2. Jika ya, dapat dianalisis lagi konvergensi, dan karena itu diestimasikan ukuran sampel yang diperlukan memperoleh optimal sebenarnya 3. Adalah pendekatan optimisasi yang efisien untuk menyelesaikan masalah PRS dengan ukuran sampel yang diinginkan.


22

4. Perhatikan bahwa untuk N yang diketahui penyelesaian x ˆN adalah layak dan merupakan calon untuk penyelesaian optimal terhadap permasalahan awal. Apakah dapat diberikan informasi tentang kualitas dari calon penyelesaian itu.

Pertanyaan-pertanyaan diatas telah dijawab untuk program stokastik diskrit. Telah dibuktikan bahwa untuk program stokastik linier dengan sebaran diskrit, suatu penyelesaian optimal dari PRS memberikan penyelesaian optimal eksak dari permasalahan awal dengan peluang mendekati 1 secara eksponensial apabila N bertambah sebagaimana dikemukakan oleh (Shapiro, 2001). Syarat-syarat optimalitasnya menurut (Ahmed, 2002) telah diajukan. Lebih lanjut lagi, teknik sampling ini telah diintegrasikan untuk menyelesaikan program linier stokastik dari berbagai ukuran dengan hasil yang cukup akurat. Kemudian konvergensi dari pendekatan PRS telah juga diperluas untuk program stokastik dengan himpunan keputusan diskrit dan berhingga oleh Kleywegt (2001).


BAB 4 PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL

Metode PRS merupakan suatu metode layak dapat digunakan untuk menyelesaikan permasalahan optimisasi program stokastik diskrit. Menurut Kleywegt (2001) metode PRS memiliki rata-rata yang bersifat numerik dari pendekatan sebuah penyelesaian oleh simulasi Monte Carlo. Dalam bagian yang sebelumnya ditetapkan sejumlah hasil konvergen untuk metode PRS. Hasil tersebut menguraikan bagaimana nilai optimal vˆN dan himpunan ε penyelesaian ε-optimal program PRS konvergen kepada mitranya v ∗ dan S ε , ketiSˆN

ka meningkatkan ukuran sampel N . Hasil ini menyediakan beberapa pertimbangan teoritis untuk metode yang diusulkan. 4.1 Penetapan Ukuran Sampel Dalam suatu algoritma, suatu ukuran sampel N berhingga atau suatu barisan ukuran sampel berhingga harus dipilih, dan algoritma harus berhenti setelah sejumlah waktu berhingga. Perkiraan persamaan (3.19) memberikan suatu batas pada ukuran sampel yang diperlukan untuk mendapatkan suatu penyelesaian ε-optimal dengan peluang sedikitnya 1 − α. Perkiraan ini mempunyai dua kekurangan untuk perhitungan tujuan. Pertama, karena banyaknya permasalahan bukanlah mudah untuk 2 dalam beberapa permasalahan mungkin susah unmenghitung perkiraan, sebab σmax

tuk dihitung. Ke dua, batasnya mungkin terlalu konservatif untuk memperoleh suatu perkiraan praktis tentang ukuran sampel yang diperlukan.


23

24

Untuk memilih ukuran sampel N, beberapa cara harus diambil sebagai pilihan. Dengan N lebih besar, fungsi objektif dari permasalahan PRS cendrung menjadi perkiraan akurat dari fungsi objektif sebenarnya, suatu penyelesaian optimal permasalahan PRS cendrung menjadi penyelesaian lebih baik, dan bersesuaian pada batas gap optimalitas. Bagaimanapun, tergantung pada permasalahan PRS (3.3) dan metode yang digunakan untuk memecahkan permasalahan PRS. Perhitungan kompleksitas memecahkan permasalahan PRS meningkat secara linier dan sering bersifat eksponensial, dalam ukuran sampel N. Karenanya penetapan ukuran sampel N , merupakan suatu cara untuk mendapatkan penyelesaian optimal permasalahan PRS, gap batas pada optimalitas pada satu bagian lain, dan usaha perhitungan pada bagian yang berikutnya, harus menjadi pilihan. Penetapan ukuran sampel N yang mungkin disesuaikan dengan dinamis, tergantung pada hasil dari perhitungan persiapan. Secara khusus, menaksir nilai objektif g(x) suatu penyelesaian feasibel x ∈ S oleh rata-rata sampel gˆN (x) memerlukan sedikit usaha perhitungan dibandingkan memecahkan permasalahan PRS (untuk ukuran sampel N yang sama). Seperti itu, walaupun pertimbangan kompleksitas perhitungan satu motivasi untuk memilih suatu ukuran sampel N yang kecil untuk permasalahan PRS. Pertimbangan itu dapat menjadi suatu gagasan untuk memilih ukuran sampel N 0 yang lebih besar untuk memxN ) tentang nilai objektif gˆ(xN ) dari suatu peroleh suatu perkiraan yang akurat gˆN 0 (ˆ penyelesaian optimal x ˆN permasalahan PRS. xN ) tentang g(ˆ xN ) diUkuran ketelitian suatu perkiraan rata-rata sampel gˆN 0 (ˆ berikan oleh varians sampel yang bersesuaian

2 (ˆ SN 0 xN ) , N0

yang mana dapat dihitung dari

ukuran sampel yang sama N. Lagi pula pilihan N 0 melibatkan suatu cara antara usaha xN ) S 2 0 (ˆ perhitungan dan ketelitian, yang terukur oleh N 0 . N


25

4.2 Replikasi Jika kompleksitas perhitungan memecahkan permasalahan PRS meningkat cepat secara linier dalam ukuran sampel N, mungkin saja lebih efisien untuk memilih suatu ukuran sampel N yang lebih kecil untuk menghasilkan pemecahan permasalahan PRS dengan sampel bbi, disebut pembangkit replikasi dalam memecahkan permasalahan PRS. Dengan pendekatan seperti itu, beberapa isu harus ditujukan. Adakah suatu jaminan suatu penyelesaian optimal (atau ε-optimal) untuk permasalahan yang sebenarnya akan dihasilkan jika suatu jumlah cukup permasalahan PRS, berdasar pada ukuran sampel N independents, dipecahkan. Procedur pemecahan itu dapat dipandang seperti percobaan Bernaulli dengan peluang sukses p = p(N ). Sukses di sini berarti bahwa suatu penyelesaian optimal x ˆN yang dihitung dari permasalahan PRS adalah suatu penyelesaian optimal dari permasalahan yang sebenarnya. Pernyataan tersebut mengikuti teorema 2, peluang p cendrung kepada 1 ketika N → ∞, lebih dari itu teorema 2 cendrung kepada 1 secara eksponensial yang cepat berpegang pada Asumsi (A). Bagaimanapun, untuk suatu N yang berhingga peluang p kecil atau bahkan nol. Peluang untuk menghasilkan suatu penyelesaian optimal permasalahan sebenarnya sedikitnya sekali dalam M percobaan adalah 1 − (1 − p)M , dan peluang ini cendrung kepada suatu ketika M → ∞, p adalah positif. Isu lain yang harus ditujukan adalah bagaimana pemilihan bilangan M replikasi. Suatu cara yang serupa kepada pemilihan ukuran sampel N, bilangan M replikasi mungkin terpilih dengan dinamis. Untuk simplikasi presentasi, umpamakan bahwa masing-masing PRS replikasi menghasilkan suatu calon penyelesaian, yang bisa merupakan suatu penyelesaian optimal (ε-optimal) permasalahan PRS. Diberikan x ˆm N menandakan calon penyelesaian itu yang dihasilkan ke-m PRS replikasi (percobaan).


26

∗ Gap Optimalitas g(ˆ xm N ) − v dapat diperkirakan. Jika suatu ukuran tempat berhenti

berdasar pada perkiraan gap optimalitas itu dicukupi, kemudian tidak ada lagi replikasi dilakukan. Cara lainnya, tambahan replikasi PRS dengan ukuran sampel yang sama N dilakukan, atau ukuran sampel N ditingkatkan. Argumentasi yang berikut menyediakan suatu petunjuk sederhana seperti pada suatu tambahan PRS replikasi dengan ukuran sampel yang sama N mungkin untuk menghasilkan suatu penyelesaian yang lebih baik. Dengan konstruksi, variabel acak g(ˆ xm N ), m = 1, 2, · · · adalah bbi, dan distribusi peluang yang umum mempunyai suatu sokongan berhingga sebab himpunan S berhingga. Anggaplah M replikasi dengan ukuran sampel N telah dilakukan. Jika distribusi peluang G(ˆ xN ) terus dilakukan, kemudian peluang yang ke-(M+1) PRS replikasi dengan ukuran sampel yang sama menghasilkan suatu penyelesaian lebih baik dan akan bersifat sama ke 1/(M+ 1). Karena distribusi g(xN ) adalah diskrit, peluang ini harus kurang dari atau sama dengan 1/(M+ 1). Diharapkan 1/(M+ 1) menjadi cukup kecil, tambahan PRS replikasi dengan ukuran sampel yang sama tidaklah akan berharga, bagaimanapun ukuran sampel N harus ditingkatkan atau prosedur seharusnya yang dihentikan. 4.3 Batas Capaian Untuk menghentikan keputusan, seperti halnya untuk evaluasi capaian dimaksud, lebih disukai menghitung gap optimalitas g(ˆ x) − v ∗ untuk penyelesaian yang PN 0 x) = N1 j=1 G(ˆ x, W j ) adalah suatu estimator ditentukan pada x ∈ S. Yaitu: gˆN 0 (ˆ x) diperkirakan oleh g(ˆ x), dan varians gˆN 0 (ˆ

2 (ˆ SN 0 x) , N0

2 dimana SN (ˆ x) adalah perbedaan

sampel G(ˆ x, W j ), yang didasarkan pada ukuran sampel N 0 . m = Suatu estimator v* diberikan: v¯N

1 M

PM

m−1

m m vˆN . Dimana vˆN menandakan

M ] = E[ˆ vN ], dan karenanya nilai objektif optimal ke-m PRS replikasi. ekspektasi E[¯ vN


27

M estimator v¯N mempunyai bias negatif yang sama sebagai v¯N .

Dari persamaan (3.27) & (3.28) menunjukkan bahwa pembiasan ini cenderung menjadikan penyelesaian lebih besar satuan optimal pada permasalahan dalam keadaan kurang baik, atau hampir optimal. Pertimbangkan estimator yang bersesuaM x) − v¯N sebagai optimalitas gap g(ˆ x) − v ∗, di titik x ˆ. Karena, ian itu adalah: gˆN 0 (ˆ

M E gˆN 1 (ˆ x) − v¯N x) − v ∗ = g (ˆ x) − E [ˆ vN ] ≥ g (ˆ

(4.1)

mengikuti pada rata-rata di atas estimator menaksir optimalitas gap g(ˆ x) − v ∗ terlalu vN ] monoton turun tinggi. Itu adalah mungkin untuk menunjukkan bahwa bias v ∗ − E[ˆ M diperkirakan oleh: dalam ukuran sampel N. Varians v¯N M 2 X 1 SM m M 2 = vˆN − v¯N M M (M − 1) m=1

(4.2)

Jika sampel M dengan ukuran N, dan sampel evaluasi dengan ukuran N 0 adalah indeM x) − v¯N dapat diperkirakan pendent, kemudian varians estimator gap optimalitas gˆN 0 (ˆ

oleh

2 (ˆ SN 0 x) N0

+

2 SM M

.

Suatu estimator gap optimalitas g(ˆ x)−v ∗ dengan varians yang lebih kecil adalah 1 M M M M m σ (ˆ x) − v¯N , dimana g¯N (ˆ x) = gˆM (ˆ x) dan gˆN (ˆ x) adalah nilai objektif ratag¯N M m=1 N P m (ˆ x) = N1 N x, W mj ). Varians rata sampel pada x ˆ sampel ke-m PRS ukuran N, gˆN j=1 G(ˆ PM S¯2 M M m m M M 2 (ˆ x) − v¯N diperkirakan oleh MM = M (M1 −1) m=1 [(ˆ gN (ˆ x) − vˆN ) − (¯ gN (ˆ x) − v¯N )] . g¯N Estimator gap optimalitas yang mana mempunyai varians paling kecil tergantung pam m (ˆ x) dan vˆN , seperti halnya pada ukuran sampel N, N 0 dan M. da korelasi antara gˆN m (ˆ x) untuk m = 1 · · · , M perlu Computational usaha tambahan untuk menghitung gˆN

juga diperhitungkan ketika mengevaluasi seperti reduksi varians. Yang manapun jalan M M M x) − v¯N dan g¯N (ˆ x) − v¯N , TLP dapat diberlakukan bagi estimator gap optimalitas gˆN 0 (ˆ

sedemikian sehingga ketelitian dari suatu estimator gap optimalitas dapat diperhitungkan oleh penambahan estimasi simpangan baku 2α kepada estimator tersebut. Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

28

Di sini zα = Φ−1 (1 − α), dimana Φ (z) adalah fungsi distribusi kumulatif standard normal. Sebagai contoh, jika x ∈ S menandakan calon penyelesaian itu dengan x) yang terbaik ditemukan setelah replikasi M, kemudian suatu estimator nilai gˆN 0 (ˆ 2 2 S (ˆ x) S2 M x) − v¯N + Zα NN0 0 + MM atau gap optimalitas mempertimbangkan ketelitian gˆN 0 (ˆ ¯

M M g¯N (ˆ x) − v¯N + zα √SM . M

Karena algoritma kontrol berguna bagi memisahkan suatu estimator gap opti 2 2 S (ˆ x) S2 M x) − v¯N + zα NN0 0 + MM malitas ke dalam komponennya. Sebagai contoh, gˆN 0 (ˆ ∗

∗

= (ˆ gN 0 (ˆ x) − g (ˆ x)) + (g (ˆ x) − v ) + v −

M v¯N

+ zα

2 2 x) SM SN 0 (ˆ + N0 M

12

(4.3)

Di dalam empat terminologi pada sisi kanan peryataan di atas, istilah yang pertama mempunyai nilai yang diharapkan nol; istilah yang kedua adalah gap optimalitas benar; istilah yang ketiga adalah bias, yang mempunyai hal positif mengharapkan penurunan nilai dalam ukuran sampel N; dan istilah yang keempat adalah ketelitian, yang mana penurunan jumlah M replikasi ukuran sampel N. Dengan begitu suatu kekurangan dari estimator gap optimalitas adalah bahwa estimator tersebut mungkin ˆ adalah suatu penyelesaian optimal, besar jika M, N, atau N 0 adalah kecil, sekalipun x yaitu g(ˆ x) − v ∗ = 0. 4.4 Postprocessing, Penyaringan, dan Pemilihan Anggaplah suatu keputusan telah dibuat untuk proses pemberhentian, sebagai contoh ketika estimator gap optimalitas cukup kecil. Pada langkah ini calon penyex) dapat terpilih ketika penyelesaian itu lesaian x ∈ S dengan nilai yang terbaik gˆN 0 (ˆ dipilih. Bagaimanapun, mungkin saja bermanfaat untuk melaksanakan suatu evaluasi lebih terperinci menghasilkan calon penyelesaian sepanjang replikasi. Ada beberapa metode pemilihan dan penyaringan statistik untuk memilih subset penyelesaian atau penyelesaian tunggal, antara berhingga himpunan penyelesaian, penggunaan sampel Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

29

penyelesaian nilai objektif. Sepanjang langkah yang pertama prosedur dikombinasikan, suatu subset S 00 tenx1N , · · · , x ˆM tang calon penyelesaian S 0 = {ˆ N } dipilih disebut penyaringan untuk evaluasi xm lebih lanjut, berdasar pada nilai rata-rata sampel gˆN 0 (ˆ N ). Sepanjang langkah yang kedua, ukuran sampel N 00 ≥ N 0 ditentukan untuk evaluasi lebih terperinci, berdasar 2 00 0 xm pada varians sampel SN 0 (ˆ N ). Kemudian N − N pengamatan tambahan yang di-

x) terpilih hasilkan, dan calon penyelesaian xˆ ∈ S 00 dengan nilai yang terbaik gˆN 00 (ˆ ketika yang dipilih penyelesaian. Prosedur yang dikombinasikan menjamin bahwa penyelesaian yang di pilih mempunyai nilai objektif g(ˆ x) di dalam suatu toleransi diteg (ˆ xm tapkan δ dengan nilai yang terbaik min xˆm N ) di atas semua calon penyelesaian N ∈S x ˆm N dengan peluang sedikitnya sama dengan tingkat kepercayaan spesifik 1 − α. 4.5 Menyelesaikan permasalahan PRS Secara prinsip teknik enumerasi kleyweght (2001) dapat dipakai untuk menyelesaikan permasalahan PRS (3.3). Pertama, perkiraan persamaan (3.19) memberikan suatu batas pada ukuran sampel yang diperlukan untuk mendapatkan suatu penyelesaian δ-optimal dengan peluang sedikitnya 1 − α. Pemilihan ukuran sampel N lebih besar, menyebabkan fungsi objektif dari permasalahan PRS cendrung untuk menjadi perkiraan yang akurat dari fungsi objektif sebenarnya. Mengakibatkan penyelesaian optimal permasalahan PRS cendrung untuk menjadi penyelesaian yang lebih baik, dan bersesuaian pada batas gap optimalitas. Bagaimanapun, tergantung pada permasalahan PRS dan metode yang digunakan, perhitungan kompleksitas untuk memecahkan permasalahan PRS meningkat secara linier dan bersifat eksponensial, dalam ukuran sampel N. Kedua, kompleksitas perhitungan memecahkan permasalahan PRS, mungkin lebih efisien untuk memilih ukuran sampel N yang lebih kecil dengan sampel bbi, Ummi Habibah : Metode Pengembangan Pendekatan Rata-Rata Sampel Untuk Menyelesaikan Permasalahan Optimasi Program Stokastik Diskrit, 2009 USU Repository © 2008

30

disebut pembangkit replikasi. Anggaplah M replikasi dengan ukuran sampel N telah dilakukan. Distribusi peluang g(ˆ xN ) menyebabkan peluang yang ke-(M+1) PRS replikasi dengan ukuran sampel yang sama menghasilkan suatu penyelesaian lebih baik dan bersifat sama ke 1/(M+ 1). Karena distribusi diskrit, peluang ini harus kurang dari atau sama dengan 1/(M+ 1). Diharapkan 1/(M+ 1) menjadi cukup kecil, tambahan PRS replikasi dengan ukuran sampel yang sama tidaklah akan berharga, bagaimanapun ukuran sampel N harus ditingkatkan atau prosedur seharusnya yang dihentikan. Ketiga, untuk menghentikan keputusan atau evaluasi capaian, lebih disukai menghitung gap optimalitas g(ˆ x)−v ∗ penyelesaian yang ditentukan pada x ∈ S. Suatu M M estimator gap optimalitas g(ˆ x) −v ∗dengan varians yang lebih kecil adalah g¯N (ˆ x) − v¯N , m (ˆ x) adalah nilai objektif rata-rata sampel pada sampel ke-m PRS ukuran N. dan gˆN

Estimator gap optimalitas yang mana mempunyai varians paling kecil tergantung pada m m (ˆ x) dan vˆN , seperti halnya pada ukuran sampel N, N 0 dan M. korelasi antara gˆN

Keempat, Anggaplah suatu keputusan telah dibuat untuk proses pemberhentian, sebagai contoh ketika estimator gap optimalitas cukup kecil. Selanjutnya calon x) dapat terpilih ketika penyelesaipenyelesaian x ∈ S dengan nilai yang terbaik gˆN 0 (ˆ an itu dipilih. Digunakan metode pemilihan dan penyaringan statistik untuk memilih subset penyelesaian antara berhingga himpunan penyelesaian. Pertama prosedur x1n , · · · , x ˆM dikombinasikan, suatu subset S 00 tentang calon penyelesaian S 0 = {ˆ N } dipilxm ih untuk evaluasi lebih lanjut, berdasar pada nilai rata-rata sampel gˆN 0 (ˆ N ). Kedua, ukuran sampel N 00 ≥ N 0 ditentukan untuk evaluasi lebih terperinci, berdasar pada 2 00 0 xm varians sampel SN 0 (ˆ N ). Kemudian N − N pengamatan tambahan yang dihasilkan,

x) terpilih ketika yang dan calon penyelesaian x ˆ ∈ S” dengan nilai yang terbaik gˆN ”(ˆ dipilih penyelesaian.


31

Berikut ini algoritma PRS untuk permasalahan optimisasi program stokastik diskrit yang dikemukana oleh Kleywegt (2001) berbunyi:

1. Pilih ukuran sampel awal N dan N 0 , dimana suatu kaidah keputusan untuk menentukan jumlah M dari replikasi PRS (mungkin meliputi suatu jumlah maksimum M 0 dari PRS replikasi dengan ukuran sampel yang sama, seperti

1 M 0 +1

yang cukup kecil), suatu kaidah pengambilan keputusan untuk meningkat ukuran sampel N dan N’ jika dibutuhkan, dan toleransi ε. 2. Untuk m = 1, 2, · · · , M, lakukan langkah 2.1 hingga 2.3. Bangkitkan sebuah sampel berukuran N, dan pecahkan permasalahan PRS (3.2), dengan nilai obm dan ε-penyelesaian optimal x ˆm jektif vˆN N . Estimasikan atau perkirakan gap ∗ optimalitas g(ˆ xm N ) − v , dan varians dari gap estimator. Jika gap optimalitas

dan varians dari gap estimator adalah cukup kecil, lanjutkan ke langkah 4. 3. Jika gap optimalitas atau varians dari gap estimator adalah terlalu besar, naikkan ukuran sampel N atau N 0 , dan kembali ke langkah 2. 4. Pilih penyelesaian terbaik x ˆ diantara semua calon penyelesaian x ˆm N yang ada, dengan menggunakan sebuah penyaringan dan prosedur seleksi. Berhenti.


BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan Ada beberapa kesimpulan yang dapat ditarik, diantaranya:

1. Pemilihan ukuran sampel N yang lebih besar menyebabkan fungsi objektif dari permasalahan PRS cendrung untuk menjadi perkiraan yang akurat dari fungsi objektif sebenarnya, dimana suatu penyelesaian optimal permasalahan PRS cendrung untuk menjadi penyelesaian yang lebih baik, dan bersesuaian pada batas gap optimalitas. 2. Batas capaian yang dimaksud jika gap optimalitas dan varians dari gap estimator adalah cukup kecil 3. Proses pemilihan dan penyaringan statistik yaitu: Pertama semua prosedur subxN 0 · · · , x ˆM set S 0 dikombinasikan, dimana calon penyelesaian S = {ˆ N } dipilih, 00 0 xm berdasar pada nilai rata-rata sampel gˆN 0 (ˆ N ). Kedua, ukuran sampel N ≥ N 2 ditentukan berdasarkan pada varians sampel SN xm 0 (ˆ N ).

5.2 Saran Penelitian ini menggunaan metode pendekatan rata-rata sampel untuk mendapatkan penyelesaian optimal dalam permasalahan program optimisasi stokastik diskrit. Penelitian selanjutnya disarankan dapat menggunakan median sebagai ganti rata-rata pada sampel, disebabkan kerena median lebih tahan terhadap outlier.


32

DAFTAR PUSTAKA

Alrefaei, Mahmoud H., Sigrun Andradottir, 1999, A Simulated Annealing Algorithms with Constant Temperature for Discrete Stochastic Optimization, Management Science/Vol. 45, No. 5, May 1999. Borndorfer, Ralf, 2008, Discrete Optimization in Public Transportation, paper presented at the 1st Indo-US Symposium on Advances in Mass Transit and Travel Behaviour Research February 12-15, 2008, IIT Guwahati, Assam, India. Chang H. S., Jiaqiqo H., Michael C. F., and Steven I. M., 2007, Nonstochastic Multi-Armed Bandit Approach to Stochastic Discrete Optimization, http://www.isr.umd.edu./ Marcus/docs/adv.pdf , tanggal akses 15 desember 2008. Greenwald, A., Bryan Gullemette, Viktor Naraditskiy, dan T. Schantz, 2008, Scaling Up the Sample Average Approximation Method for Stochastic Optimization wih Applications to Trading Agent, http://www.sics.se/tada05/greenwald.pdf, tanggal akses 15 desember 2008. Jeff, Hong, L., 2006, Discrete Optimization via Simulation Using COMPASS, OPERATION RESEARCH, Vol 54, No. 1, pp. 115-129. Hill, Stacy D., 2005, Discrete Stochastic Approximation with Application to Resource Allocation, Johns Hopkins APL Technical Digest, Vol. 26, No. 1, 2005 Kleywegt, A. J., A. Shapiro, and T. Homem-De-Mello, 2001. The sample average approximation method for stochastic discrete optimization. SIAM Journal of Optimization, 12:479-502. Rossi, R., S. Armagan Tarim, Brahim Hnich, and Steven Prestwich, 2008, A Sample Average Approximation Approach for Even-Driven Probabilistic constrain Programming,http://4c.ucc.ie/4cite/TR-02-2008.pdf, tanggal akses 15 desember 2008. Shapiro, A., and Homem de Mello, T., 2001, On Rate of Convergence of Monte Carlo Approximations of Stochastic Program, SIAM Journal on Optimization, 11:70-86. Shi, L., Chun-Hung C., 2008, A New Algorithm for Stochastic Discrete Resource Allocation Optimization, http://www.jhvalp.edu/SPSA/PDF-SPSA/Hill-Techg05.pdf, tanggal akses 15 desember 2008.


33

METODE PENGEMBANGAN PENDEKATAN RATA-RATA SAMPEL UNTUK MENYELESAIKAN PERMASALAHAN OPTIMISASI PROGRAM STOKASTIK DISKRIT TESIS. Oleh

Recommend Documents