SIMULASI PENGEPAKAN BOLA MENGGUNAKAN METODE KEPLER CONJECTURE Ngarap Im Manik1; Marcellos Setiadi2 1, 2
Jurusan Matematika, Fakultas Sains dan Teknologi, Universitas Bina Nusantara, Jln. K.H. Syahdan No. 9, Palmerah, Jakarta Barat 11480 email:
[email protected]
ABSTRACT Packing the ball is important in everyday life, particularly those related to the packing of goods. Implementation of packing balls in real life too, are often less efficient, since most of the existing ball packing random. To optimize the packing balls in a limited space method proposed by Kepler Conjecture. This method was chosen because it has a relatively low density or larger and can fill a box-shaped container more efficiently and orderly. To solve the above problem was done by a simulation program. The results simulation program has been providing the output of packaging in the form of 3D models that can be manipulated to determine the optimal size of the container in a packaging. Keywords: simulation, packing the ball, Kepler Conjecture
ABSTRAK Pengepakan bola merupakan hal penting dalam kehidupan sehari-hari, khususnya yang berkaitan dengan pengepakan barang. Implementasi dari pengepakan bola dalam kehidupan nyata juga seringkali kurang efisien, mengingat kebanyakan pengepakan bola yang ada dilakukan secara acak. Untuk mengoptimalkan pengepakan bola pada ruang terbatas, diusulkan dengan metoda Kepler Conjecture. Metode ini dipilih karena memiliki tingkat kepadatan yang relatif lebih besar dan dapat mengisi wadah berbentuk kotak secara lebih efisien dan teratur. Untuk penyelesaian masalah di atas dilakukan dengan sebuah program simulasi. Hasil program simulasi telah memberikan keluaran berupa model pengepakan dalam bentuk 3D, yang dapat dimanipulasi untuk menentukan besarnya ukuran wadah yang optimal dalam suatu pengepakan. Kata kunci: simulasi, pengepakan bola, Kepler Conjecture
Simulasi Pengepakan Bola …... (Ngarap Im Manik; Marcellos Setiadi)
45
PENDAHULUAN Optimasasi peletakan suatu benda atau barang 3 dimensi merupakan salah satu masalah dasar dalam bidang geometri. Berdasarkan jumlah dan tipe objek yang digunakan, tiap-tiap susunan akan memberikan tingkat efisiensi yang berbeda-beda. Benda dengan bentuk bulat sempurna (bola) merupakan objek yang memiliki kombinasi peletakan paling besar daripada bidang 3 dimensi dasar lainnya. Hal ini dikarenakan bentuk bola secara virtual memiliki bidang sentuh paling kecil terhadap sesamanya. Sehubungan dengan hal di atas, untuk pengepakan bola pada saat ini jarang diteliti; kecuali pada masa lampau, ada beberapa penelitian seperti bentuk cannonball packing (dinamakan demikian karena merupakan cara menyusun tumpukan peluru meriam pada dek kapal) merupakan susunan yang dianggap paling optimal dalam pengepakan bola. Pada tahun 1611, bentuk ini disempurnakan oleh Kepler menjadi model yang dapat digunakan dalam berbagai bentuk wadah teratur, yang kemudian model ini dikenal dengan istilah Kepler Conjecture. Makalah ini membahas tentang optimisasi pengepakan bola menggunakan metode Kepler Conjecture melalui perancangan sebuah program simulasi, yang mudah digunakan untuk mensimulasikan pengepakan bola secara optimal sehingga hasil dari simulasi ini dapat menentukan besarnya ukuran wadah yang optimal dalam suatu pengepakan. Program dibuat dengan menggunakan pemrograman MATLAB 7.1, dengan Platform Windows XP Professional Edition.
SPHERE PACKING Ada beberapa model penempatan bola homogen dalam ruang 3 dimensi. Semua model penempatan, pada akhirnya akan memiliki pola periodik berupa kubus, piramida bipolar, dan hexagonal (Steinhauss, 1999). Bentuk pengepakan bola juga akan memberikan ruang celah kosong terbanyak, dibandingkan benda 3 dimensi teratur lainnya (Eppstein, 2006). Model-model pengepakan bola yang pernah diajukan antara lain (1) Tetrahedral Lattice. Susunan bola akan membentuk tetrahedral, di mana tiap-tiap bola akan bersentuhan dengan 4 bola lainnya. Bentuk ini terjadi pada susunan atom Carbon(C) yang membentuk berlian. Implementasinya, pada bentuk real tidak banyak ditemukan karena bentuk ini merupakan salah satu model yang paling tidak efisien, baik pada penggunaan ruang maupun tingkat kerapatannya; (2) Cubic Lattice. Pola penyusunan dengan cara ini akan menghasilkan bentuk 3 dimensi berupa balok/kubus, bentuk yang paling umum digunakan sebagai wadah penampung. Dengan metode ini, tingkat kerapatan masingmasing bola akan sama dengan perbandingan antara volume satu bola dengan volume kubus terkecil yang dapat menampung satu bola tersebut. Tingkat kerapatan dengan metode ini lebih kecil daripada metode Keppler’s Conjecture; dan (3) Random Packing. Sesuai namanya, peletakan bola dilakukan secara acak. Model pengepakan bola seperti ini banyak ditemui dalam wadah berupa keranjang/jala. Bentuk yang dibahas dalam makalah ini adalah bentuk Kepler’s Conjecture (Conway J.H., 1993).
Kepler Conjecture Kepler Conjecture pertama kali dipublikasikan sebagai model dengan tingkat kepadatan terbesar dalam pengepakan bola oleh Kepler pada tahun 1611. Bentuk ini merupakan perluasan dari cannonball packing. Jika dilihat dari sudut pandang vertikal, setiap lapisan pada model ini merupakan bentuk beehive packing/hexagonal packing, yang merupakan model paling optimal dalam peletakan lingkaran dalam ruang planar 2 dimensi (Baragar, 2001: 324).
46
Jurnal Mat Stat, Vol. 10 No. 1 Januari 2010: 45-52
Gambar 1 Beehive packing
Dalam perhitungannya, Kepler menggunakan asumsi bahwa tumpukan-tumpukan bola akan membentuk suatu bangunan yang menyerupai susunan tetrahedral.
Gambar 2 Susunan Kepler Conjecture membentuk Tetrahedral
Dapat dilihat dari gambar di atas bahwa jumlah bola dari tiap barisan berkurang satu buah untuk setiap tumpukan di atasnya. Jika jari-jari tiap bola adalah 1 satuan dan jumlah bola pada barisan di pinggir tumpukan pertama adalah n, maka (Weisstein, E.W., 2005) Panjang sisi tetrahedral (s):
s = 2n + 3
2 − 2
Volume tetrahedral dengan sisi s (V): V =
s3 6 2
Jumlah bola pada lapisan dasar:
n + (n − 1) + ... + 1 =
(1)
n(n + 1) 2
(2)
Jumlah bola total (x):
k 2 + k n 3 + 3n 2 + 2n x=∑ = 2 6 k =1 n
(3)
Tingkat kerapatan tumpukan dapat didefinisikan sebagai rasio antara total volume bola dengan volume tetrahedral yang terbentuk sehingga:
Simulasi Pengepakan Bola …... (Ngarap Im Manik; Marcellos Setiadi)
47
Kerapataan (δ): δ=
(
)
x 43 πr 3 n 3 + 3n 2 + 2n 4π 6 2 = × 3 V 18 2n + 3 2 − 2
(
)
(4)
Jika n mendekati m takk hingga, makka tingkat keerapatan di attas akan mennjadi:
(
)
⎤ 24π 2 π 2 ⎡ n 3 + 3n 2 + 2n 4π 6 2 = × ⎥= 3 n −>∞ 18 13 36 6 ⎢⎣ 2n + 3 2 − 2 ⎦⎥
δ = Lim ⎢
(
)
T Tingkat keraapatan ini meerupakan yanng terbesar sampai saat inni, dan belum m berhasil diibuktikan bahwa cara c penyussunan ini merupakan m y yang terbaik k. Jika diim mplementasikkan pada ru uang tak berhinggga, maka metode ini akann membuat setiap s bola bersentuhan dengan d 12 boola lain di seekitarnya, membenntuk suatu susunan s Cubboctahedron.. Bentuk peenyusunan secara s Cubicc Close Latttice atau Hexagonnal Close Lattice tidak mempengaruh m hi tingkat kerrapatan modeel Kepler Coonjecture. P Perbedaan d kedua model dari m penyusunan hanya sebatas kom mbinasi layerr pada tumpu ukan bola yang dissusun. Implem mentasi untuuk model Keepler Conjecture bentuk Close Cubicc Lattice dap pat dilihat pada benntuk susunann buah-buahaan di kios terrdekat, umum mnya pada buah apel dann jeruk. Untu uk bentuk Hexagonnal Close Laatticedan, conntoh implem mentasinya daapat dilihat pada p penyussunan bola meriam m di dek kapaal pada masaa abad pertenngahan dan penyusunan p bola b bilyar daan Snooker ((Hales T, 200 05).
Simulaasi Simulasi meerupakan prooses trial annd error seh hingga penyeelesaian massalah dengan n metode simulasi tidak selam manya memberikan solusi yang optim mal untuk suuatu masalah yang dihadaapi. Oleh karena ittu, bentuk siimulasi sebaaiknya hanyaa digunakan jika j pemecaahan masalahh secara anallitis tidak dapat dillakukan (Karrlsson dan Saamuelsson, 2000). 2 Beriku ut ini adalah diagram darri proses peraancangan program m simulasi.
Gambar 3 Diagram Prroses Perancan ngan Program m Simulasi (Sumber: Jagstam, De Vin, V 2007)
48
Jurrnal Mat Stat, Vol. V 10 No. 1 Januari 201 10: 45-52
State Transition Diagram State Transition Diagram adalah salah satu cara menggambarkan jalannya proses. Di dalamnya dapat dilihat input/kondisi, state proses, output/aksi yang terjadi dan perubahan state. Komponen dasar state transition diagram dapat dilihat pada Gambar 4.
State X
Input
State sekarang
Output State Y
State selanjutnya
Gambar 4 Komponen Dasar State Transition Diagram
State menunjukkan satu atau lebih kegiatan atau keadaan atau atribut yang menjelaskan bagian tertentu dari proses anak panah berarah, menunjukkan perubahan state yang disebabkan oleh input tertentu (state X ke state Y). Input/kondisi X merupakan suatu kejadian pada lingkungan eksternal yang dapat dideteksi oleh sistem, misalnya sinyal, interupsi atau data. Hal ini menyebabkan perubahan dari satu state ke state lainnya atau dari satu aktivitas ke aktivitas lainnya. Output/aksi Y merupakan hal yang dilakukan oleh sistem jika terjadi perubahan state atau merupakan reaksi terhadap kondisi. Aksi dapat menghasilkan output, tampilan pesan pada layar, dan kalkulasi.
Pseudocode Pseudocode adalah suatu bahasa umum yang menggunakan kosa kata dari satu bahasa (misalnya bahasa Inggris) dan perintah (syntax) dari bahasa yang lain (misalnya bahasa pemrograman terstruktur) (Pressman, 2004: 411). Pseudocode adalah suatu bahasa pemrograman yang informal dan sangat fleksibel, yang tidak dimaksudkan untuk dieksekusi pada mesin, tetapi hanya digunakan untuk mengorganisir cara berpikir pemrogram sebelum melakukan coding. Pseudocode dapat menjadi alternatif dalam perancangan perangkat lunak di samping alat bantu berupa diagram. Tidak ada standarisasi dalam hal penulisan pseudocode. Pemrogram dapat menulisnya dalam bahasa apa saja yang mereka sukai dan dipadukan dengan bahasa pemrograman tertentu. Pemrogram juga bebas menggunakan teknik dan aturannnya sendiri.
PROGRAM SIMULASI Program simulasi ini terdiri dari 3 buah modul fungsi pada MATLAB, yang masing-masing akan memberikan gambar sebuah hasil simulasi untuk tiap metode yang digunakan, sesuai dengan ukuran wadah yang ditentukan dalam input. Modul yang telah dibuat ini dapat diintegrasikan ke dalam program aplikasi yang membutuhkan, selama program tersebut dapat berinteraksi dengan MATLAB. Program ini tidak memiliki interface khusus karena semua fungsi dipanggil melalui layar command prompt pada MATLAB untuk memaksimalkan hasil simulasi. Secara umum, program simulasi yang telah dirancang dapat dilihat pada state transition diagram berikut ini.
Simulasi Pengepakan Bola …... (Ngarap Im Manik; Marcellos Setiadi)
49
Gambar 5 State Transition Diagram program
Sedangkan salah satu modul progam yang telah dibuat dapat dilihat pada pseudocode program berikut ini. KepplerSphere1.m function [jumlah] = KepplerSphere1(pkotak,lkotak,tkotak) refresh; {bersihkan layar} [x,y,z] = sphere (20); { inisialisasi } x = x+1; y = y+1; z = z+1; xtengah = 1; ytengah = 1; ztengah = 1; jumlah = 0; hold on; bolax = 1; bolay = 1; bolaz = 1; xgambar = x; ygambar = y; zgambar = z; while (tkotak >= ztengah + 1) {setting posisi dan gambar bola } if mod(bolaz,2) == 1 ytengah = 1; ygambar = y; else ytengah = 1.57735; ygambar = y + 0.57735; end while (lkotak >= ytengah + 1) if mod(bolaz,2) == 1 if mod(bolay,2) == 1 xtengah = 1; xgambar = x; else xtengah = 2; xgambar = x + 1; end else if mod(bolay,2) == 1 xtengah = 2; xgambar = x + 1;
50
Jurnal Mat Stat, Vol. 10 No. 1 Januari 2010: 45-52
eelse xtengah = 1; xgambar = x; e end endd whiile (pkotak >= > xtengah +1) + s (xgambaar,ygambar,zgambar); jum surf mlah = jumlaah + 1; bolaxx = bolax + 11; x xtengah = xteengah + 2; xggambar = xggambar + 2; endd bolaay = bolay + 1; bolax = 1; 1 ytenngah = ytenggah + 1.732005; ygambarr = ygambar + 1.73205; end bolaz = bolaz + 1; bolay = 1; ztengaah = ztengahh + 1.63300; zgambar = zgambar z + 1.63300; end
H HASIL DA AN PEMB BAHASAN N Hasil U Untuk menjaalankan proggram simulaasi ini, dibutu uhkan spesiffikasi hardw ware Processo orr AMD Athlon 1,7 1 GHz; Meemory 512 MB; M Hard Dissk 200 GB; Input I Keybooard dan mouuse dengan Monitor: 17’, resoolusi 1024 x 768. Program m dibuat denngan menggu unakan bahassa pemrogram man Matlab 7.1. pada sistem operasi o Winddows XP Proo dengan haasil keluaran seperti beriikut. Program m secara kesseluruhan dijalankaan di dalam m lingkungaan MATLAB B command d window. Proses P simuulasi dapat langsung dilakukaan dengan memberikan m p perintah padaa MATLAB B untuk mem manggil fungsi dari progrram yang telah dippersiapkan beerikut input ukuran u ruangg yang diing ginkan. Hasil simulasi jugga dapat dim manipulasi lebih lannjut melalui toolset yangg telah disediiakan oleh MATLAB, M unntuk mendappatkan sudut pandang yang lebbih baik. Coontoh hasil simulasi dapaat dilihat paada gambar berikut b ini ddengan masu ukan data input ukuuran ruang 6,6,6 6 diperoleeh:
Gambar 6 Hasil H Simulasi Hexagonal Close Lattiice dengan Inpput (6,6,6)
Gambar 7 Hasil Simulaasi Cubic Lattice d dengan Input (6,6,6)
Simulasii Pengepaka an Bola …... (Ngarap ( Im Manik; M Marce cellos Setiadi))
51
Pembahasan Setelah dilakukan evaluasi terhadap keseluruhan program ini, didapatkan hasil sebagai berikut. Program telah memberikan output yang diharapkan, yaitu menggambarkan model peletakan bola pada ruang tiga dimensi sesuai metode yang diinginkan. Metode yang digunakan pada proses simulasi ini dapat dikembangkan lebih lanjut untuk mendapatkan hasil penempatan yang lebih optimal, untuk berbagai bentuk dan ukuran wadah. Program simulasi ini mudah untuk digunakan karena dipandu dengan menu-menu program.
PENUTUP Dari uraian di atas, dapat disimpulkan bahwa metode Keppler Conjecture dapat mengefisienkan pengepakan bola pada ruang terbatas. Untuk memudahkan prosesnya, dilakukan dengan merancang sebuah program simulasi, yang dari hasil program telah memberikan keluaran model pengepakan dalam bentuk 3 dimensi yang dapat dimanipulasi sehingga dapat ditentukan besarnya ukuran wadah yang optimal dalam pengepakan bola tersebut.
DAFTAR PUSTAKA Baragar, A. (2001). A survey of classical and modern geometries with computer activities, New Jersey. Conway, J. H., and Sloane, N.J. (1993). A sphere packing, lattices, and groups, 2nd ed., New York: Springer-Verlag. Eppstein, D. Sphere packing and kissing numbers. Retrieved in 2008 from http://www.ics.uci.edu/~eppstein/junkyard/spherepack.html. Ferguson, S.P. (2001). Sphere packing. V. Retrieved in 2008 from http://arxiv.org/abs/math.MG/9811077/. Hales, T.C. (2005). A proof of the Kepler Conjecture. Retrieved in 2009 from http://www.math.princeton.edu/~annals/issues/2005/Nov2005/Hales.pdf. Jagstam, M., and De Vin, L.J. Why we need to offer modeling and simulation engineering curriculum. Retrieved in 2009 from http://www.informs-sim.org/wsc01papers/219.PDF. Karlsson. J., and Samuelsson. F. (2000). Simulation techniques in industrial environment, Swedia. Oscarsson, J., and Urenda, M.M. Documentation of discrete event simulation models for manufacturing system life cycle simulation. Retrieved from http://www.informs-sim.org/wsc02papers/144.pdf. Pressman, R.S. (2004). Software engineering: A practitioner’s approach, 5th ed., Singapore: McGrawHill Companies, Inc. Weisstein, E.W. (2005). Kepler Conjecture. From MathWorld--A Wolfram Web Resource. Retrieved in 2009 from http://mathworld.wolfram.com/KeplerConjecture.html.
52
Jurnal Mat Stat, Vol. 10 No. 1 Januari 2010: 45-52