ALGORITMA EKSAK UNTUK MENYELESAIKAN PERSOALAN BIN COVERING
TESIS
Oleh ERI SAPUTRA 097021080/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universitas Sumatera Utara
ALGORITMA EKSAK UNTUK MENYELESAIKAN PERSOALAN BIN COVERING 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 ERI SAPUTRA 097021080/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universitas Sumatera Utara
Judul Tesis
: ALGORITMA EKSAK UNTUK MENYELESAIKAN PERSOALAN BIN COVERING Nama Mahasiswa : Eri Saputra Nomor Pokok : 097021080 Program Studi : Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Opim Salim S, M.Sc) Ketua
Ketua Program Studi
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Herman Mawengkang) Anggota
Dekan
(Dr. Sutarman, M.Sc)
Tanggal lulus : 19 Januari 2012
Universitas Sumatera Utara
Telah diuji pada Tanggal 19 Januari 2012
PANITIA PENGUJI TESIS Ketua
: Prof. Dr. Opim Salim S, M.Sc
Anggota : 1. Prof. Dr. Herman Mawengkang 2. Prof. Dr. Tulus, M.Si 3. Drs. Sawaluddin, M.IT
Universitas Sumatera Utara
ABSTRAK Tesis ini menjelaskan tentang algoritma eksak untuk menyelesaikan permasalahan bin covering. Penyelesaiannya dengan menggunakan prosedur branch and bound dan teknik generasi kolom. Dalam permasalahan integer programming, generasi kolom digunakan untuk menyelesaikan linear programming relaksasi. Branch and bound dapat digunakan untuk banyak kelas pada masalah skala besar seperti sebuah prosedur yang dapat menjadi penghalang berat dalam hal total waktu komputasi. Setelah diambil pendekatan untuk menguji pengurangan masalah dimana sebagian besar variabel integer tetap konstan dan hanya sebagian kecil diperbolehkan untuk bervariasi dalam langkah-langkah diskrit. Hal ini dapat di implementasikan dalam struktur dari sebuah program dengan memperhatikan semua variabel integer pada batas solusi yang selanjutnya sebagai non basic dan penyelesaian masalah berkurang dengan mempertahankan non basic. Kata kunci
: Generasi kolom, Branch and bound, Program linear relaksasi, Integer programming, Bin covering
i Universitas Sumatera Utara
ABSTRACT
This tesis present an exact algorithm for solving the problems of bin covering. Using the branch and bound procedures and the technique of column generation. In the problem of integer programming, column generation is used to solve the relaxation of linear programming. While a straightforward branch and bound approach could be adopted, for many classes of large scale problems such a procedure would be prohibitively expensive in terms of total computing time. After have adopted the approach of examining a reduced problem in which most of the integer variables are held constant and only a small subset allowed to vary in discrete steps. This may be implemented within the structure of a program by examining all integer variables at their bounds at the continuous solution as nonbasic and solving the reduced problem with these maintained nonbasic
Keyword
: Column generation, Branch and bound, Linear programming relaxation, Integer programming, Bin covering
ii Universitas Sumatera Utara
KATA PENGANTAR
Syukur Alhamdulillah kehadirat ALLAH SWT, penulis panjatkan atas limpahan Rahmat dan KaruniaNya yang telah diberikan sehingga penulis dapat menyelesaikan tesis dengan judul : ”Algoritma Eksak Untuk Menyelesaikan Permasalahan Bin Covering”. Selawat dan salam kepada junjungan Nabi Muhammad SAW beserta keluarga dan sahabat sekalian. Tesis ini merupakan salah satu persyaratan penyelesaian studi pada Program Studi Magister Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. Pada kesempatan ini penulis menyampaikan terima kasih dan penghargaan yang sebesar-besarnya kepada: Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di FMIPA Universitas Sumatera Utara Prof. Dr. Herman Mawengkang selaku ketua Program Studi Magister Matematika FMIPA Universitas Sumatera Utara dan juga sebagai pembimbing pada penulisan tesis ini yang berkat dorongan dan bantuan beliau sehingga penulisan tesis ini dapat diselesaikan. Prof. Dr. Opim Salim S, M.Sc juga sebagai pembimbing dalam penulisan tesis ini atas saran dan bantuan sehingga penulisan ini dapat diselesaikan. Prof. Dr. Tulus, M.Si selaku pembanding atas saran dan bantuannya untuk kesempurnaan penulisan tesis ini serta bimbingan selama perkuliahan berlangsung. Drs. Sawaluddin, M.IT selaku pembanding atas saran dan bantuannya untuk kesempurnaan penulisan tesis ini. iii Universitas Sumatera Utara
Seluruh Staf Pengajar pada Program Studi Magister Matematika FMIPA Universitas Sumatera Utara yang telah banyak memberikan ilmu pengetahuan selama masa perkuliahan. Ibu Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika FMIPA Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis selama mengikuti perkuliahan. Seluruh sahabat serta rekan - rekan seperjuangan mahasiswa angkatan 2009 genap atas kebersamaan dan bantuan dalam mengatasi masalah selama perkuliahan berlangsung. Ucapan terima kasih yang tak terhingga dan penghargaan setinggi tingginya penulis ucapkan kepada ayahanda H. Abubakar Yunus, SP dan Ibunda Hj. Nurmiati, S.Pd yang telah mencurahkan kasih sayang dan dukungan kepada penulis. Terima kasih juga kepada adik - adik penulis (Emira Laura Putri, Evira Agustina Putri, Esar Alkautsar) dan buat seluruh keluarga yang telah membantu, memberikan semangat dan dorongan kepada penulis hingga penulisan tesis ini selesai. Terima kasih juga kepada sahabat dan rekan - rekan lainnya yang tidak dapat disebutkan satu persatu, yang telah membantu dan memberikan semangat untuk penulis hingga tesis ini selesai. Akhir kata penulis menyadari bahwa tesis ini masih jauh dari sempurna. Untuk itu penulis mengharapkan kritik dan saran untuk penyempurnaan tesis ini. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihak pihak lainnya yang memerlukannya.
Medan, Januari 2012 Penulis,
Eri Saputra iv Universitas Sumatera Utara
RIWAYAT HIDUP
Penulis di lahirkan di Simpang Mulieng Kabupaten Aceh Utara pada tanggal 08 Oktober 1986 dan merupakan anak pertama dari empat bersaudara. Dari ayah H.Abubakar Yunus dan ibu Hj. Nurmiati. Penulis menamatkan Sekolah Dasar (SD), SD Negeri Simpang Mulieng, Lulus tahun 1999. Sekolah Lanjutan Tingkat Pertama (SLTP), SLTP Negeri 1 Syamtalira Aron, Lulus tahun 2002. Sekolah Menengah Atas (SMA), SMA Negeri 1 Syamtalira Aron, Lulus tahun 2005. Pada tahun 2005 penulis melanjutkan pendidikan sarjana di Universitas Islam Sumatera Utara Pada Fakultas Keguruan dan Ilmu Pendidikan Jurusan Pendidikan Matematika dan Lulus pada tahun 2009. Tahun 2009, penulis berkesempatan untuk melanjutkan Program Master pada Program Studi Magister Matematika Universitas Sumatera Utara Medan.
v Universitas Sumatera Utara
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 Masalah
3
1.3 Tujuan Penelitian
3
1.4 Manfaat Penelitian
3
1.5 Metode Penelitian
3
BAB 2 TINJAUAN PUSTAKA
5
BAB 3 LANDASAN TEORI
10
3.1 Program Linear Integer
10
3.2 Algoritma Eksak
11
3.3 Pemodelan Matematika
11
BAB 4 HASIL DAN PEMBAHASAN
16
4.1 Algoritma Branch and Bound
16
4.2 Generasi Kolom
19
4.3 Algoritma Bin Covering Flow Exact
23
vi Universitas Sumatera Utara
4.4 Heuristik Pencarian Sekitar Layak
24
BAB 5 KESIMPULAN
27
DAFTAR PUSTAKA
28
vii Universitas Sumatera Utara
