METODE PENCARIAN LANGSUNG UNTUK MENYELESAIKAN PROBLEMA KNAPSACK
Oleh:
SKRIPSI
SRI WAHYUNI 050803028
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009
Universitas Sumatera Utara
i
PERSETUJUAN
Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: METODE PENCARIAN LANGSUNG UNTUK MENYELESAIKAN PROBLEMA KNAPSACK : SKRIPSI : SRI WAHYUNI : 050803028 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Medan, Oktober 2009
Komisi Pembimbing Pembimbing 2
:
Dra. Elly Rosmaini, M. Si NIP 196005201985032002
Pembimbing 1 Prof. Dr. Herman Mawengkang NIP : 194611281974031001
Diketahui/Disetujui oleh Departeman Matematika FMIPA USU Ketua.
Dr. Saib Suwilo, M.Sc NIP 196401091988031004
Universitas Sumatera Utara
ii
PERNYATAAN METODE PENCARIAN LANGSUNG UNTUK MENYELESAIKAN PROBLEMA KNAPSACK SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya. Medan, Oktober 2009 SRI WAHYUNI 050803028
Universitas Sumatera Utara
iii
PENGHARGAAN
Segala puji dan syukur penulis haturkan atas kehadirat Allah Subhanna Wa Ta’ala yang telah melimpahkan Nikmat dan karunia-Nya, sehingga penulis berhasil menyelesaikan skripsi ini dalam waktu yang telah ditetapkan. Dan tak lupa pula shalawat dan salam senantiasa tercurah kepada Nabi Allah, Muhammad Shalallahu ‘Alaihi Wassalam yang diutus sebagai rahmat untuk sekalian alam serta keluarga dan sahabat beliau serta orang-orang yang berpegang teguh dengan petunjuk Sunnah beliau hingga hari kiamat. Dalam kesempatan ini, penulis ingin mengucapkan jazakumullahu khairan katsiran kepada semua pihak yang telah membantu dan membimbing penulis dalam penyusunan skripsi ini, ucapan terima kasih saya sampaikan kepada : 1. Bapak Prof. Dr. Herman Mawengkang selaku pembimbing I dan Dra. Elly Rosmaini M. Si selaku pembimbing II yang telah memberikan bimbingan dan pengarahan kepada saya sehingga skripsi ini dapat saya selesaikan. 2. Bapak Drs. Suwarno Ariswoyo, M.Si. dan Drs. H. Haluddin Panjaitan selaku dosen penguji saya. 3. Bapak Dr. Saib Suwilo, M.Sc. dan Drs. Henry Rani Sitepu, M.Sc. selaku Ketua dan Sekretaris Departemen Matematika 4. Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumetera Utara. 5. Semua Dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU 6. Terkhusus kedua orangtua tercinta, Bapak Suharno dan Ibu Sari Armaini, dan kedua Adik saya serta semua keluarga besar Alm. Sopan yang selama ini memberikan bantuan dan dorongan yang diperlukan. 7. Seluruh teman-teman kuliah dan junior Matematika khususnya stambuk 2005 dan juga teman terdekat saya Rima, Nenna, Sundari, Febby, Chinta, Lia, Radhi, Santri dan Dika serta sahabat-sahabat saya di Pelajar Islam Indonesia (PII) yang telah memberikan semangat, dorongan dan saran dalam pengerjaan skripsi ini. Semoga segala bentuk bantuan yang telah diberikan kepada penulis mendapatkan balasan yang lebih baik dari Allah Subhanna Wa ta’ala.
Universitas Sumatera Utara
iv
ABSTRAK
Pencarian langsung yang dimaksud pada penelitian ini mempunyai karakteristik struktur oleh himpunan bagian dari variabel terbatas untuk asumsi nilai diskrit, linier dan dapat dipisahkan dari variabel kontinu. Strategi melepaskan variabel non-basis dari batasannya dikombinasikan dengan “kendala aktif” dan ide dari superbasis, telah menghasilkan beberapa syarat yang cocok, strategi ini digunakan untuk kekuatan variabel basis non – Integer yang cocok untuk mengerjakan lingkungan point integernya. Studi kriteria untuk memilih sebuah variabel non-basis untuk mengerjakan dengan strategi pembulatan juga telah dibuat. Implementasi sukses dari algoritma ini menyelesaikan bermacam-macam uji masalah. Hasilnya menunjukkan bahwa strategi pembulatan membuahkan sebuah harapan penyelesaian optimal dari problema Knapsack
Universitas Sumatera Utara
v
EXHAUSTIVE SEARCH METODH TO SOLVE KNAPSACK PROBLEMS ABSTRACT
Search approach which is addressed in this paper has structure characterized by a subset of variables restricted to assume discrete values, which are linier and seperable from the continuous variables. The strategy of releasing nonbasic variables from their bounds, combined with the “active constraint” method and the notion of superbasics, has ben developed for efficienty requirements, this strategy is used to force the appropriate non-integer basic variables to move to their neighbourhood integer points. A study of criteria for choosing a nonbasic variable to work with in the integerizing strategy has also been made. Succesful implementation of these algorithms was achieved on various test problems. The result show that the proposed integerizing strategy is promising in tackling certain classes of mixed integer programming problems.
Universitas Sumatera Utara
vi
DAFTAR ISI
Halaman ii iii iv v vi vii viii ix
PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR Bab 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Identifikasi Masalah 1.3 Tujuan Penelitian 1.4 Tinjauan Pustaka 1.5 Kontribusi Penelitian 1.6 Metode Penelitian
1 1 2 2 3 4 4
Bab 2 LANDASAN TEORI 2.1 Problema Knapsack dengan Algoritma Branch and Bound 2.1.1 Algoritma Branch and Bound 2.1.2 Pohon 2.1.3 Metode 2.2 Problema Knapsack dengan Algoritma Greedy 2.2.1 Greedy by Profit 2.2.2 Greedy by Weight 2.2.3 Greedy by Density 2.3 Problema Knapsack dengan Exhautives Search 2.4 Problema Knapsack dengan Algoritma Genetika 2.4.1 Algoritma Genetika 2.4.2 Penerapan Algoritma Genetika pada Problema Knapsack 2.4.3 Flowchart
5 5 5 6 6 11 12 13 14 16 18 18 19 22
Bab 3 PEMBAHASAN 3.1 Pendekatan Basis 3.2 Metode Derivatif 3.3 Hasil 3.4 Algoritma
23 23 24 26 29
Bab 4 KESIMPULAN DAN SARAN 4.1 Kesimpulan 4.2 Saran
32 32 32
DAFTAR PUSTAKA
34
Universitas Sumatera Utara
vii
DAFTAR TABEL
Tabel 2.1 Keterangan berat, Keuntungan dan P/W tiap Jenis Barang Tabel 2.2 Greedy by Profit Tabel 2.3 Greedy by Weight Tabel 2.4 Greedy by Density Tabel 2.5 Greedy by Density Tabel 2.6 Exhautive Search
Halaman 7 13 14 15 16 17
Universitas Sumatera Utara
viii
DAFTAR GAMBAR
Gambar 2.1 Akar Pohon Problema Knapsack dengan n-4 Gambar 2.2 Pohon Status Problema Knapsack Tahap Awal Gambar 2.3 Pohon Status Problema Knapsack Tahap Kedua Gambar 2.4 Pohon Status Problema Knapsack Tahap Ketiga Gambar 2.5 Pohon Status Problema Knapsack Gambar 2.6 Flowchart Algoritma Genetika
Halaman 7 9 9 10 10 24
Universitas Sumatera Utara
