ii
UNIVERSI TAS BINA NUSANTARA Program Ganda Teknik Informatika - M atematika Skripsi Sarjana Program Ganda Semester Ganjil 2006/2007
PERANCANGAN PROGRAM SIMULASI DAN PERBANDINGAN MODEL PENGEPAKAN BOLA DENGAN METODE KEPLER CONJECTURE DAN CUBIC LATTICE M arcellos Setiadi NIM : 0500589602 Abstrak
M asalah dalam pengepakan benda padat telah banyak diminati sejak lampau. Hingga kini, belum ada suatu algoritma pasti yang dapat menyelesaikan semua bentuk dan model yang paling efisien untuk masalah pengepakan. Pengepakan benda bola memiliki peranan penting dibandingkan bentuk lainnya karena berhubungan dengan teknologi informasi yang terus berkembang hingga kini. Implementasi dari pengepakan bola dalam kehidupan nyata juga seringkali kurang efisien, mengingat kebanyakan pengepakan bola jaman sekarang kebanyakan dilakukan secara acak/random. Karena hal ini, penulis merasa perlu ada suatu program yang dapat mensimulasikan dan membandingkan beberapa model pengepakan bola untuk meningkatkan efisiensi dan menentukan metode terbaik untuk melakukan pengepakan bola pada ruang terbatas.. M etode yang digunakan untuk mensimulasikan pengepakan adalah metode Kepler Conjecture dan Cubic Lattice. Kedua metode ini dipilih karena masing2 memiliki tingkat kepadatan yang relatif lebih besar dan dapat mengisi wadah berbentuk kotak secara lebih efisien dan teratur daripada metode lainnya. Perancangan program simulasi ini telah memberikan output berupa model pengepakan dalam bentuk 3D yang dapat dimanipulasi. Dengan hasil ini, diharapkan program dapat membantu menentukan besarnya ukuran wadah serta model pengepakan yang lebih efisien untuk wadah tersebut. Kata Kunci: Simulasi, pengepakan bola, permodelan, Kepler Conjecture, Cubic Lattice
iii
Kata Pengantar
Puji syukur dan terima kasih kepada Tuhan Yang M aha Esa yang telah memberkati dan membantu proses penyelesaian Skripsi ini. Walaupun tugas membuat Skripsi ini dirasa berat dan melelahkan, namun berkat bimbingan dari para dosen, dukungan teman-teman, serta jerih payah beberapa bulan terakhir ini, akhirnya Skripsi ini dapat diselesaikan walaupun masih jauh dari kesempurnaan. Skripsi ini disusun berdasarkan penjelasan dari para dosen, buku-buku pedoman dan teori, serta artikel2 online yang berhubungan dengan Simulasi, permodelan, dan metode2 pengepakan yang digunakan. Tentunya masih banyak kekurangan di dalam Skripsi ini, sehingga bantuan berupa kritik dan saran dari saudara sekalian sangat diharapkan. Akhir kata, saya ucapkan banyak terima kasih kepada para pembimbing serta teman2 sekalian yang telah meluangkan waktu dan tenaganya untuk memberikan petunjuk-petunjuk dalam mewujudkan Skripsi ini serta memberikan dukungan moral yang tak kalah perannya. Terutama sekali kepada Pak Ngarap dan Pak Sangadji selaku dosen pembimbing. Jakarta, 24 Januari 2007
M arcellos Setiadi 0500589602
iv
Daftar Isi Halaman Abstrak...................................................................................................................... ii Kata Pengantar .......................................................................................................... iii Daftar Isi.................................................................................................................... iv Daftar Gambar........................................................................................................... vi BAB 1. PENDAHULUAN....................................................................................... 1 1.1. Latar Belakang .................................................................................... 1 1.2. Identifikasi M asalah ............................................................................ 2 1.3. Ruang Lingkup .................................................................................... 3 1.4. Rumusan Rancangan ........................................................................... 3 1.5. Spesifikasi Rancangan......................................................................... 4 1.6. Tujuan dan M anfaat............................................................................. 4 1.6.1. Tujuan Penulisan ........................................................................ 4 1.6.2. M anfaat Penulisan...................................................................... 4 1.7. M etodologi .......................................................................................... 5 BAB 2. LANDASAN TEORI.................................................................................. 6 2.1. Sphere Packing.................................................................................... 6 2.1.1. Kepler Conjecture ...................................................................... 7 2.1.2. Cubic Lattice .............................................................................. 10 2.2. Perancangan Program Simulasi........................................................... 11 2.2.1. State Transition Diagram ........................................................... 13 2.2.2. Pseudocode................................................................................. 14 BAB 3. PERANCANGAN PROGRAM SIM ULASI.............................................. 16 3.1. Perancangan......................................................................................... 16 3.1.1. Perancangan Interface ................................................................ 16 3.1.2. State Transition Diagram ........................................................... 16 3.2. Pseudocode.......................................................................................... 17 BAB 4. IM PLEM ENTASI DAN EVALUASI ........................................................ 29 4.1. Spesifikasi Komputer yang digunakan................................................ 29 4.1.1. Spesifikasi Hardware.................................................................. 29
v 4.1.2. Spesifikasi Software ................................................................... 29 4.2. Analisis dan Cara Pengoperasian Program ......................................... 30 4.3. Evaluasi Program ................................................................................ 33 BAB 5. KESIM PULAN DAN SARAN................................................................... 34 5.1. Kesimpulan.......................................................................................... 34 5.2. Saran .................................................................................................... 35 Daftar Pustaka ........................................................................................................... 36 Riwayat Hidup........................................................................................................... 38 Lampiran Source Code Program ............................................................................... 39
vi
Daftar gambar
Gambar 1.1.
2 M odel Kepler Conjecture ............................................................... 2
Gambar 2.1.
Beehive Packing................................................................................ 8
Gambar 2.2.
Susunan Kepler Conjecture membentuk Tetrahedral ....................... 8
Gambar 2.3.
Diagram proses perancangan program simulasi................................ 12
Gambar 2.4.
Komponen dasar perancangan State Transition Diagram ................ 13
Gambar 3.1.
State Transition Diagram Program simulasi..................................... 16
Gambar 4.1.
Hasil Simulasi Hexagonal Close Lattice dengan input (6,6,6)......... 31
Gambar 4.2.
Hasil Simulasi Cubic Close Lattice dengan input (6,6,6)................. 32
