1 SKRIPSI SRI RAHAYU

PENDEKATAN ALGORITMA PEMROGRAMAN DINAMIK DALAM MENYELESAIKAN PERSOALAN KNAPSACK 0/1

SKRIPSI

SRI RAHAYU 060823001

PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains


PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010


PERSETUJUAN

Judul

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas

: PENDEKATAN ALGORITMA PEMROGRAMAN DINAMIK DALAM MENYELESAIKAN PERSOALAN KNAPSACK 0/1 : SKRIPSI : SRI RAHAYU : 060823001 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (MIPA) UNIVERSITAS SUMATERA UTARA

Diluluskan di Medan, Juli 2010 Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Drs. Marwan Harahap, M.Eng NIP. 19461225 197403 1 001,-

Drs. Bambang Irawan, M.Sc NIP. 19470421 197603 1 001,-

Diketahui / Disetujui Oleh: Departemen Matematika FMIPA USU Ketua,

Dr. Saib Suwilo, M.Sc NIP.19640109 198803 1 004,-


PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan,

Juli 2010



PENGHARGAAN

Puji dan syukur penulis panjatkan kepada Allah SWT, dengan limpahan dan karunia-Nya kertas kajian ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Ucapan terima kasih penulis sampaikan kepada Drs. Bambang Irawan, M.Sc dan Drs. Marwan Harahap, M.Eng selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada penulis untuk menyempurnakan kajian ini. Panduan ringkas, padat dan professional telah diberikan kepada penulis agar dapat menyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Matematika FMIPA USU Dr. Saib Suwilo, M.Sc dan Drs. Henry Rani Sitepu, M.Si, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU, dan rekan-rekan kuliah. Akhirnya, tidak terlupakan kepada kedua orang tua dan semua ahli keluarga dan rekan terdekat penulis selama ini yang telah memberikan bantuan dan dorongan yang diperlukan. Semoga Allah SWT memberikan balasan yang layak.


ABSTRAK

Pemrograman Dinamik adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian hingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Dalam tulisan ini membahas tentang penggunaan algoritma Pemrograman Dinamik untuk mencari solusi optimal pada Masalah Knapsack 0/1. Masalah Knapsack 0/1 dapat didefinisikan dalam menentukan lintasan terpendek dari titik sumber ke tujuan yang memenuhi kendala biaya dan waktu pada suatu graph. Lintasan yang terpilih bernilai 1 dan yang tidak terpilih bernilai 0 kemudian diimplementasikan kedalam suatu program dengan menggunakan Visual Basic 6.0.


ABSTRACT

Dynamic Programming is a method of solving problems by way of describing a solution to a set of steps or stages such that the solution of the problem can be viewed from a series of interrelated decisions. In this paper discusses the use of Dynamic Programming algorithm to find optimal solutions to the Knapsack Problem 0 / 1. Knapsack Problems 0 / 1 is defined to determine the shortest path from point source to the destination that meets the cost and time constraints on a graph. Chosen path is value 1 and not selected path is 0 then implemented into a program with using Visual Basic 6.0.


DAFTAR ISI

Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

ii iii iv v vi vii viii ix

Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tinjauan Pustaka 1.5 Tujuan Penelitian 1.6 Kontribusi Penelitian 1.7 Metode Penelitian

1 1 4 4 4 6 6 7

Bab 2 Landasan Teori 2.1 Konsep Dasar Graph 2.2 Graph Berlabel 2.3 Lintasan Minimum 2.4 Lintasan Terpendek 2.5 Pemrograman Linier (Linear Programming) 2.6 Pemrograman Bilangan Bulat (Integer Programming) 2.7 Knapsack 2.8 Pemrograman Dinamik (Dynamic Programming) 2.8.1 Konsep Dasar Dalam Pemrograman Dinamik 2.8.2 Analisa Algoritma Pemrograman Dinamik 2.8.3 Dua Pendekatan Algoritma Pemrograman Dinamik 2.8.4 Algoritma Pemrograman Dinamik 2.9 Visual Basic 6.0

8 8 11 14 15 16 17 19 21 21 25 26 26 27

Bab 3 Pembahasan 3.1 Lintasan Terpendek 3.2 Analisis Knapsack 3.3 Analisis Pemrograman Dinamik 3.4 Flowchart Pemrograman Dinamik 3.5 Rancangan Antar Muka Program

29 29 29 36 43 44


Bab 4 Kesimpulan dan Saran 4.1 Kesimpulan 4.2 Saran

47 47 48

Daftar Pustaka Lampiran


DAFTAR TABEL

Halaman Tabel 2.1 Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5

Biaya Pemasangan Jaringan Listrik Enumerasi Lengkap Penentuan Nilai Minimum untuk Tahap-1 pada x1 Penentuan Nilai Minimum untuk Tahap-2 pada x2 Penentuan Nilai Minimum untuk Tahap-2 pada x3 Penentuan Nilai Minimum untuk Tahap-2 pada x4

12 34 40 40 41 41


DAFTAR GAMBAR

Halaman Gambar 2.1. Gambar 2.2. Gambar 2.3. Gambar 3.4. Gambar 2.5. Gambar 2.6. Gambar 2.7. Gambar 2.8. Gambar 3.1. Gambar 3.2. Gambar 3.3 Gambar.3.4 Gambar 3.5. Gambar 3.6. Gambar 3.7. Gambar 3.8. Gambar 3.9.

Graph 5 titik dan 6 sisi Graph dengan 6 titik dan 10 sisi Digraph G Graph Berlabel Jaringan Listrik 8 Kota Lintasan Terpendek / Shortest Path (garis tebal) Tahapan fungsi transisi Tahapan baku Return dan Transition Function Representasi graph dalam penyaluran air bersih Lintasan Terpendek dengan nilai biaya dan waktu Lintasan Terpendek dengan Nilai Biaya dan Waktu Ilustrasi Lintasan Pencarian Lintasan Terpendek Flowchart Algoritma Dynamic Programming Form Menu Utama Form Entri Data Graph Form Hasil dari Hitung Cari Lintasan Terpendek Form Hasil Graph Lintasan Terpendek

9 9 11 13 15 22 23 24 31 38 39 42 43 44 45 45 46


1 SKRIPSI SRI RAHAYU

Recommend Documents