METODE BRANCH AND BOUND UNTUK MENYELESAIKAN PROGRAM STOKASTIK INTEGER DENGAN ADANYA RESIKO
TESIS
Oleh
ADIL H. PANGARIBUAN 087021052/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
METODE BRANCH AND BOUND UNTUK MENYELESAIKAN PROGRAM STOKASTIK INTEGER DENGAN ADANYA RESIKO
TESIS
Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh
ADIL H. PANGARIBUAN 087021052/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
Judul Tesis
: METODE BRANCH AND BOUND UNTUK MENYELESAIKAN PROGRAM STOKASTIK INTEGER DENGAN ADANYA RESIKO Nama Mahasiswa : Adil H. Pangaribuan Nomor Pokok : 087021052 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Herman Mawengkang) Ketua
(Dr. Saib Suwilo, MSc) Anggota
Ketua Program Studi,
Dekan,
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Eddy Marlianto, M.Sc)
Tanggal lulus: 18 Mei 2010
Universitas Sumatera Utara
Telah diuji pada Tanggal 18 Mei 2010
PANITIA PENGUJI TESIS
Ketua : Anggota :
Prof. Dr. Herman Mawengkang 1. Dr. Saib Suwilo, MSc 2. Dr. Sutarman, M.Sc. 3. Dra. Mardiningsih, M.Si.
Universitas Sumatera Utara
ABSTRAK Tesis ini bertujuan melakukan pengembangan pada metode branch-and-bound, yaitu dalam rangka menyelesaikan permasalahan multistage stochastic integer programs with risk dalam hubungannya dengan permasalahan wait-and-see yang dapat dipisahkan kedalam kasus seperti resiko netral. Model-model yang termasuk dalam kelas ini penyelesaiannya akan disajikan sebagai suatu kombinasi dari algoritma branchand-bound dengan relaksasi non-anticipativity dan kendala percabang (constraint branching) sepanjang subspaces non-anticipativity. Kata kunci : Pemograman Stokastik Bilangan Bulat, Model Multi-Tahap, Model Mean-Risk, Optimasi Program Cacah Campuran.
Universitas Sumatera Utara
i
ABSTRACT This thesis is addressed to develop branch-and-bound methods, that is to solve multistage stochastic integer programs with risk objectives which is related to wait-and-see problems which could be separated like risk neutral. All model classified to this is overcome by presenting a combination between branch-and-bound algorithm and relaxation of non-anticipativity and constraint branching along non-anticipativity subspaces. Keywords : Stochastic Integer Programming, Multistage Models, Mean-Risk Models, Mixed-Integer Optimization
Universitas Sumatera Utara
ii
KATA PENGANTAR
Puji Tuhan dan syukur kehadirat-Nya penulis panjatkan, karena berkat dan kasih karunia-Nya sehingga saya dapat menyelesaikan perkuliahan tepat waktu dan menyelesaikan tugas akhir ini, yang berupa tesis dengan judul ”METODE BRANCH AND BOUND UNTUK MENYELESAIKAN PROGRAM STOKASTIK INTEGER DENGAN ADANYA RESIKO”. Pada kesempatan ini, penulis menyampaikan ucapan terima kasih dan penghargaan yang sebesar-besarnya kepada: Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara. Bapak Prof. Dr. Eddy Marlianto, M.Sc selaku Dekan FMIPA Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti perkuliahan pada Program Studi Magister Matematika. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika pada Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Sumatera Utara dan juga selaku Ketua Komisi pembimbing tesis ini, yang telah dengan penuh kesabaran memotivasi dan membimbing penulis hingga selesainya tesis ini dengan baik. Bapak Dr. Saib Suwilo, MSc selaku Sekretaris Program Studi Magister Matematika pada Fakultas Matematika Dan Ilmu Pengetahuan Alam Universitas Sumatera Utara dan juga selaku anggota pembimbing tesis, yang telah banyak memberikan saran dan masukan, juga motivasi belajar selama masa perkuliahan. Bapak Dr. Sutarman, M.Sc dan Ibu Dra. Mardiningsih, M.Si selaku pembanding dan penguji atas segala saran dan petunjuk yang diberikan. Gubernur Sumatera Utara yang telah memberi bantuan Beasiswa pendidikan kepada penulis melalui BAPEDASU. Bapak Prof. Dr. Drs. Iryanto, M.si ; Prof. Dr. Opim Salim, MIkom. PhD ; Drs. Marwan Harahap, M.Eng; Dr. Tulus, M.Si ; Drs. Open Darnius, M.Sc ; Drs. Marihat Situmorang,M.Kom ; Drs. S.Arriswoyo,M.Sc ; Drs. Sawaluddin,M.IT sebagai staf pengajar yang telah memberikan ilmunya kepada penulis selama perkuliahan. Rekan mahasiswa angkatan 2007-2008 atas kerjasama dan kebersamaan yang indah selama perkuliahan dan rekan guru SMA Negeri 4 Medan yang turut memberi motivasi. Juga kepada adinda tercinta Sri Wahyuni Sirait.SE yang banyak memberi semangat dan inspirasi kepada penulis sebelum dan semasa perkuliahan. Universitas Sumatera Utara
iii
Secara khusus penulis menyampaikan terimakasih dan sayang yang mendalam kepada orang tua penulis Ayahanda Drs. JT. Pangaribuan dan Ibunda T. br Napitupulu (alm), abang, adik-adik, ipar dan semua keponakan saya yang senantiasa memberikan dukungan dan mendoakan keberhasilan penulis dalam menyelesaikan pendidikan ini. Kepada seluruh pihak yang tidak dapat penulis sebutkan satu persatu, penulis berterimakasih atas semua bantuan yang diberikan, semoga Tuhan Yang Maha Kuasa membalaskan segala kebaikan yang telah diberikan, Amin. Penulis menyadari tesis ini masih jauh dari sempurna, namunpun demikian penulis berharapan semoga tesis ini bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya. Sekian dan terimakasih.
Medan, 18 Mei 2010 Penulis,
Adil H. Pangaribuan
Universitas Sumatera Utara
iv
RIWAYAT HIDUP
A. DATA PRIBADI Nama
: Adil H. Pangaribuan
Tempat/tanggal lahir : Jakarta/10 Pebruari 1967 Jenis kelamin
: Laki-laki
Agama
: Kristen Protestan
Alamat Rumah
: Jl. Helvetia Raya No.65 Medan 20124
Nama Orang Tua
: Drs.JT.Pangaribuan (Ayah) : (Alm) T. br. Napitupulu (Ibu)
B. Riwayat Pendidikan 1973-1979
: SD Bethel Jakarta
1979-1982
: SMP Bethel Jakarta, SMP Nasrani Medan
1982-1985
: SMA Negeri 11 Medan
1985-1988
: FMIPA Program D-3 Matematika USU Medan
1993-1996
: FPMIPA Program Pendidikan Matematika IKIP Medan
2008-2010
: Program Pascasarjana Magister Matematika USU Medan
C. Pengalaman Kerja 1989-1991
: Guru PNS pada SMU Negeri Ranai Kab. Kep.RIAU
1991-Sekarang
: Guru PNS pada SMU Negeri 4 Medan
Universitas Sumatera Utara
v
DAFTAR SIMBOL Scenario tree representation τ G G
t
Z
=
number of stages
=
set of scenario groups.
=
set of scenario groups in stage t, for t = 1, . . . , τ
=
Benefit at end of period H
The Algorithm L i
=
Daftar subproblem
=
Nomor iterasi; also used to indicate the subproblem selected
i
=
Subset corresponding to iteration i
αi
=
Batas atas yang diperoleh pada iterasi ke i
βi
=
Batas bawah pada subproblem ke i
=
Penyelesaian layak untuk nilai subproblem ke i
U
=
Batas atas pada nilai optimal global
L
=
Batas bawah pada nilai optimal global
X∗
=
Kandidat optimum global
P
X
i
Probabilitas dan Ukurannya Ω
= ruang kejadian
ω
=
elemen dari Ω, kejadian
P
=
ukuran probabilitas pada Ω
(Ω, ω, P)
=
ruang probabilitas
ξ
=
variabel acak pada (Ω, ω, P) dengan realisasi didalam R
E
=
nilai ekspektasi
R
=
ukuran resiko umum
Fungsi Biaya Acak x
=
variabel keputusan dalam Rn
ξ
=
parameter acak dalam Rl
QE
=
fungsi nilai ekspektasi yang dipetakan dari dari Rn ke R
QR
=
fungsi resiko umum yang dipetakan dari Rn ke R
(ξt )Tt=1
=
proses stokastik data diskrit
Universitas Sumatera Utara
vi
DAFTAR ISI Halaman ABSTRAK
i
ABSTRACT
ii
KATA PENGANTAR
iii
RIWAYAT HIDUP
v
DAFTAR SIMBOL
vi
DAFTAR ISI
vii
DAFTAR TABEL
ix
DAFTAR GAMBAR
x
BAB 1 PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Perumusan Masalah
3
1.3 Tujuan Penelitian
3
1.4 Kontribusi Penelitian
3
1.5 Metode Penelitian
3
BAB 2 TINJAUAN PUSTAKA
5
BAB 3 LANDASAN TEORI
7
3.1 Program Stokastik
7
3.2 Program Stokastik Dua-Tahap (two-stage models)
8
3.2.1 Program Stokastik Cacah Campuran
9
3.3 Program Stokastik Multi Tahap (Multistage Stochastic Program)
10
3.3.1 Model Ekspektasi
10
3.3.2 Pemahaman Resiko dan Ukuran Resiko (Risk Measures)
11
3.4 Separable Wait-And-See Problems BAB 4 PEMBAHASAN
15 19
4.1 Metode Branch And Bound
19 Universitas Sumatera Utara
vii
4.2 Pengembangan Metode Branch And Bound
21
4.2.1 Algoritma
21
4.2.2 Pengembangan Algoritma
23
4.3 Komputasi
26
BAB 5 KESIMPULAN DAN SARAN
28
5.1 Kesimpulan
28
5.2 Saran
28
DAFTAR PUSTAKA
29
LAMPIRAN 1
30
LAMPIRAN 2
31
LAMPIRAN 3
34
Universitas Sumatera Utara
viii
DAFTAR TABEL
Nomor 5.1
Judul
Halaman
Computational results for multiknapsack problems
30
Universitas Sumatera Utara
ix
DAFTAR GAMBAR
Nomor
Judul
Halaman
4.1
Scenario tree ; multistage
20
4.2
The enumeration tree
20
4.3
Tree of subproblems and results of LP relaxations
21
Universitas Sumatera Utara
x
