PENYELESAIAN MULTI PERIOD DEGREE CONSTRAINED MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA MODIFIED PRIM DAN PEMOGRAMAN GNU OCTAVE
OLEH MAS DAFRI MAULANA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG BANDAR LAMPUNG 2017
SOLVING THE MULTI PERIODS DEGRE CONSTRAINED MINIMUM SPANNING TREE BY USING MODIFIED PRIM’S ALGORITHM AND GNU OCTAVE
by Mas Dafri Maulana ABSTRACT In graph theory, one of optimization problem is determining minimum spanning tree (MST) of a given graph G. If there is another restriction on the vertices of the MST, the problem emerges as the Degree Constrained Minimum Spanning Tree (DCMST). The application of the DCMST arises in daily life including the design of telecommunication network, transportation network, and so on. Usually, the DCMST represents the networks where the installation process only done at once, at one stage. However, due some limitations and constraints , especially fund , the installation process must be done in some steps., and this emerges as the Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST). To solve the MPDCMST, we developed three algorithms based on Modified Prim’s which are MPDCMST_awal, MPDCMST_akhir and MPDCMST_kick. The algorithm was implemented using GNU Octave and used 300 random table problems.The result showed that the value of solution for the MPDCMST_kick was the best among the three methods developed.
Key words : minimum spanning tree, multi period degree constrained, modified Prim’s algorithm.
PENYELESAIAN MULTI PERIOD DEGREE CONSTRAINED MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA MODIFIED PRIM DAN PEMOGRAMAN GNU OCTAVE
Oleh Mas Dafri Maulana ABSTRAK Dalam teori graf, salah satu masalah optimasi adalah penentuan pohon rentang minimum, atau dikenal dengan istilah Minimum Spanning Tree (MST), yaitu menentukan bobot yang minimum dari suatu graf yang terhubung. Jika pada suatu MST diberikan kendala degree (derajat) pada tiap titiknya maka MST tersebut menjadi masalah DCMST (Degree Constrained Minimum Spanning Tree). Contoh terapan dari DCMST adalah masalah proses instalasi suatu jaringan yang dapat dilakukan dalam satu tahap. Akan tetapi, karena ada kendala (umumnya kendala pendanaan) maka proses instalasi tersebut harus dilakukan dalam beberapa tahap. Masalah inilah yang disebut dengan instalasi jaringan multi tahap atau Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST). Untuk menyelesaikan MPDCMST dapat digunakan Algoritma Prim yang telah dimodifikasi atau disebut dengan Modified Prim. Penelitian ini bertujuan untuk mengimplementasikan Algoritma Prim untuk penentuan MST, DCMST, dan MPDCMST. Program DCMST dan MPDCMST dibuat dengan memberikan kendala batasan degree ≤ 3 dan membagi proses instalasi menjadi 3 tahap. Implementasi MPDCMST menggunakan beberapa algoritma yakni MPDCMST_awal, MPDCMST_akhir, dan MPDCMST_kick. Dilakukan pada 300 data dengan orde graf dari 10 sampai dengan 100. Setiap pengujian dalam satu permasalahan di kenakan 30 kali uji dan dicatat waktu yang diperlukan untuk menyelesaikan suatu permasalah tersebut. Hasil menunjukkan bahwa nilai DCMST merupakan lower bound untuk MDCMST dan berdasarkan solusi optimal MPDCMST_kick merupakan metode terbaik dari ketiga metode ini.
Kata Kunci : minimum spanning tree, multi period degree constrained, modified prim,algoritma.
PENYELESAIAN MULTI PERIOD DEGREE CONSTRAINED MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA MODIFIED PRIM DAN PEMOGRAMAN GNU OCTAVE OLEH
Skripsi Sebagai Salah Satu Syarat untuk Memperoleh Gelar SARJANA SAINS Pada Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS LAMPUNG BANDAR LAMPUNG 2017
: PENYELESAIAN MULTI PERIOD DEGREE
Judul Skripsi
CONSTRAINED MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA MODIFIED PRIM DAN PEMOGRAMAN GNU OCTAVE Nama Mahasiswa
: Mas Dafri Maulana
Nomor Pokok Mahasiswa
: 1317031051
Jurusan
: Matematika
Fakultas
: Matematika dan Ilmu Pengetahuan Alam
MENYETUJUI 1. Komisi Pembimbing
Ir. Warsono, M. S., Ph.D NIP. 19630216 1987031 003
Dra. Wamiliana, M. A., Ph. D NIP. 19631108 1989022 001
2. Ketua Jurusan Matematika
Drs. Tiryono Ruby, M.Sc.,Ph.D NIP. 19620704 198803 1 002
MENGESAHKAN
1. Tim Penguji Ketua
: Ir. Warsono, M. S., Ph.D
............................
Sekretaris
: Dra. Wamiliana, M. A., Ph. D
............................
Penguji Bukan Pembimbing
: Dian Kurniasari, S.Si., M. Sc.
............................
2. Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam
Prof. Warsito, S.Si., D.E.A., Ph.D. NIP. 19710212 199512 1 001
Tanggal Lulus Ujian Skripsi
: 29 Mei 2017
PERNYATAAN
Saya yang bertanda tangan dibawah ini, menyatakan bahwa skripsi saya berjudul “Penyelesaian Multi Period Degree Constrained Minimum Spanning Tree Menggunakan Algoritma Modified Prim dan Pemograman GNU Octave” adalah hasil pekerjaan saya sendiri, bukan hasil orang lain. Semua hasil tulisan yang tertuang dalam skripsi ini telah mengikuti kaidah penulisan karya ilmiah Universitas Lampung. Apabila kemudian hari terbukti bahwa skripsi ini merupakan hasil salinan atau dibuat oleh orang lain, maka saya bersedia menerima sanksi sesuai ketentuan akademik yang berlaku.
Bandar Lampung, Yang menyatakan
Mas Dafri Maulana NPM. 1317031051
Juni 2017
RIWAYAT HIDUP
Penulis dilahirkan di Pringsewu pada tanggal 13 November 1995, sebagai anak pertama dari dua bersaudara, dari Bapak Solihin dan Ibu Lilis Suryani.
Penulis menyeselesaikan pendidikan di TK Dharma Wanita Bumi Dipasena Makmur pada tahun 2002, Madrasah Ibtidaiyah Negeri Mukti Karya pada tahun 2008, Madrasah Tsanawiyah Negeri Model Talang Padang pada tahun 2011, dan Sekolah Menengah Atas Negeri 1 Gadingrejo pada tahun 2013.
Pada tahun 2013, penulis terdaftar sebagai mahasiswa Jurusan Matematika, FMIPA, Universitas Lampung melalui jalur SBMPTN. Selama menjadi mahasiswa, penulis aktif di organisasi HIMATIKA sebagai anggota Bidang Eksternal, UKMF Natural sebagai redaktur, dan Rohani Islam sebagai anggota Bidang Informasi dan Komunikasi periode 2014/2015. Kemudian pada periode 2015/2016 penulis aktif sebagai Kepala Departemen Komunikasi dan Informasi BEM FMIPA dan sebagai Pemimpin Umum UKMF Natural periode 2016. Pada tanggal 18 Januari – 14 Februari 2016 penulis melakukan Kerja Praktek di Badan Pusat Statistik (BPS) Kota Bandar Lampung dan pada 25 Juli – 25 Agustus 2016 penulis melaksanakan Kuliah Kerja Nyata di Desa Payung Makmur, Kecamatan Pubian, Kabupaten Lampung Tengah.
KATA INSPIRASI
“Allah meninggikan orang – orang yang beriman di antara kamu dan orang – orang yang diberi ilmu pengetahuan beberapa derajat” {QS. Al-Mujadillah : 11)
“Man jadda wajada” (Siapa bersungguh-sungguh , dia akan berhasil)"
“Sesuatu akan terlihat tidak mungkin sampai saat semuanya selesai.” (Nelson Mandela)
"Para petualang itu bebas. Mereka makan saat mereka mau, tidur saat mereka mau dan bergerak saat mereka mau. Tapi, jadi bebas itu butuh tanggung jawab." (Krusty)
Ayahanda Solihin & Ibunda Lilis Suryani
Adik Hadi Wijoyo
Kakek & Nenek
Almamaterku tercinta Universitas Lampung
SANWACANA
Puji syukur kehadirat Allah SWT yang telah melimpahkan berkah dan rahmatNya sehingga penulis dapat menyelesaikan skripsi yang berjudul “Penyelesaian Multi Period Degree Constrained Minimum Spanning Tree Menggunakan Algoritma Modified Prim dan Pemograman GNU Octave” ini. Penulisan skripsi ini merupakan salah satu syarat untuk memperoleh gelar Sarjana Sains di Universitas Lampung.
Dalam penyusunan skripsi ini penulis banyak mendapat bantuan berupa saran, bimbingan, maupun motivasi dari berbagai pihak. Oleh karena itu, penulis mengucapkan terima kasih kepada : 1. Ir. Warsono, M. S., Ph. D. selaku dosen pembimbing utama yang telah meluangkan waktu untuk membimbing, mengarahkan, memotivasi dan menyediakan waktu untuk penulis, sehingga skripsi ini dapat terselesaikan. 2. Dra. Wamiliana, M. A., Ph. D. selaku dosen pembimbing kedua yang memberikan bantuan, waktu, pemikiran dan saran dalam penyelesaian skripsi ini. 3. Dian Kurniasari, S. Si., M. Sc. selaku dosen pembahas atas waktu, evaluasi, dan saran yang membangun dalam penyusunan skripsi ini.
4. Bapak Drs. Suharsono S, M.S., M.Sc., Ph.D. selaku pembimbing akademik yang memberikan arahan dan saran selama proses perkuliahan. 5. Drs. Tiryono Ruby M.Sc., Ph.D. selaku Ketua Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam. 6. Bapak Prof. Warsito, S.Si., D.E.A., Ph.D., selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lampung. 7. Seluruh dosen Jurusan Matematika dan Ilmu Pengetahuan Alam. 8. Ayah, Ibu, Hadi dan keluarga yang selalu memberikan doa, dukungan, dan semangat sehingga penulis menyelesaikan skripsi ini. 9. Helin Meilinawati penyemangat dalam penyelesaian skripsi ini. 10. Ali A. J, A. Haris S., Muzahid A., Efrizal, Suyitno, Arif, Shela M., Faizatin, Yeyen, Afif, Aulia A., Wibi, Wika, Nandra, Adib, Ramadi, Fernando, Imam, Ferli, Iwan, Kominfo, mbak Lia, teman-teman satu bimbingan, teman – teman seperjuangan Matematika angkatan 2013 dan seluruh pihak yang telah membantu penulis yang tidak dapat disebutkan satu persatu. Penulis menyadari bahwa masih banyak kekurangan dalam skripsi ini. Oleh karena itu, kritik dan saran dari pembaca akan sangat bermanfaat bagi penulis. Semoga skripsi ini dapat bermanfaat bagi semua pihak yang membaca.
Bandar lampung, Penulis,
Mas Dafri Maulana
Juni 2017
DAFTAR ISI
Halaman DAFTAR TABEL .......................................................................................... iii DAFTAR GAMBAR ...................................................................................... iv I.
PENDAHULUAN 1.1. Latar Belakang .............................................................................. 1 1.2. Batasan Masalah ............................................................................ 4 1.3. Tujuan............................................................................................ 4 1.4. Manfaat Penelitian......................................................................... 4
II.
TINJAUAN PUSTAKA 2.1. Konsep Dasar Teori Graf .............................................................. 6 2.2. Tree (Pohon).................................................................................. 10 2.3. MST dan Beberapa Turunannya ................................................... 16 2.4. Konsep Dasar Matriks ................................................................... 18 2.5. Hubungan Graf dan Matriks.......................................................... 19 2.6. Model (Persamaan) Matematis...................................................... 23 2.7. GNU Octave .................................................................................. 26
III.
METODE PENELITIAN 3.1. Waktu dan Tempat Penelitian ....................................................... 27 3.2. Bahan dan Alat .............................................................................. 27 3.3. Alur Penelitian............................................................................... 28
IV.
PEMBAHASAN 4.1. Data yang Digunakan .................................................................... 38 4.2. Penentuan HVTk dan MaxVTk..................................................... 38 4.3. Implementasi ................................................................................. 39 4.4. Pengujian dan Hasil ....................................................................... 58
V. VI. VII.
KESIMPULAN DAFTAR PUSTAKA LAMPIRAN
DAFTAR TABEL
Tabel
Halaman
1. Penyelesaian MST dengan Algoritma Kruskal ................................. 13 2. Penyelesaian Algoritma Prim ............................................................... 15 3. Tabel banyak titik dan banyak sisi pada graf terhubung sederhana ..... 29 4. Elemen HVTk untuk setiap periode ..................................................... 38 5. Data pada file 18 folder 10-vertex........................................................ 40 6. Tabel graf terhubung dan bobotnya hasil Algoritma MPDCMST_awal................................................................................. 45 7. Tabel graf terhubung dan bobotnya hasil Algoritma MPDCMST_akhir ................................................................................ 51 8. Tabel graf terhubung dan bobotnya hasil Algoritma MPDCMST_kick ................................................................................. 57 9. Rata-rata bobot yang diperoleh dari dari Algoritma MST, DCMST, MPDCMST_awal, MPDCMST_akhir, dan MPDCMST_kick............ 58 10. Rata-rata waktu yang digunakan GNU Octave dalam proses Algoritma MST, DCMST, MPDCMST_awal, MPDCMST_akhir, dan MPDCMST_kick ........................................... 61 11. Rata-rata waktu yang digunakan GNU Octave dalam proses Algoritma MPDCMST_awal dan MPDCMST_akhir ............................................................................... 63
DAFTAR GAMBAR
Tabel
Halaman
1. Contoh graf dengan 3 titik dan 5 sisi ................................................... 6 2. Contoh walk dari graf di atas adalah 𝑣1 , 𝑒1 , 𝑣2 , 𝑒4 , 𝑣4 , 𝑒3 , 𝑣5 , 𝑒2 , 𝑣1 ..... 8 3. Graf berbobot ....................................................................................... 8 4. Derajat pada graf .................................................................................. 9 5. Subgraf merentang ............................................................................... 10 6. Tree ...................................................................................................... 10 7. Rooted tree ........................................................................................... 11 8. Hasil penerapan Algoritma Kruskal ..................................................... 13 9. Hasil penerapan Algoritma Prim .......................................................... 16 10. Contoh graf direpresentasikan ke dalam matriks. ................................ 19 11. Tampilan data folder 10-vertex file 1.dat di Octave ............................ 28 12. Hasil menggabungkan titik X dan Y dengan bobotnya ....................... 31 13. Bentuk matriks persegi dari data folder 10-vertex file 1.dat ................ 32 14. Matriks Tetangga data 1 pada folder 10-vertex ................................... 33 15. Hasil nilai T dan V Algoritma Prim ..................................................... 34 16. Graf Contoh graf dengan 10 titik ......................................................... 35 17. Graf hasil MPDCMST tahap 1 ............................................................. 36 18. Graf hasil MPDCMST tahap 2 ............................................................. 36 19. Graf hasil tahap 3 ................................................................................. 37 20. Visualisasi graf MPDCMST_awal pada periode-1 .............................. 42 21. Visualisasi graf MPDCMST_awal pada periode-2 .............................. 43 22. Visualisasi graf MPDCMST_awal hasil periode-3 .............................. 45 23. Visualisasi graf MPDCMST_akhir pada periode-1 ............................. 48 24. Visualisasi graf MPDCMST_akhir pada periode-2 ............................. 49 25. Visualisasi graf MPDCMST_akhir hasil periode-3 ............................. 51
26. Visualisasi MPDCMST_kick periode-1 .............................................. 54 27. Visualisasi MPDCMST_kick periode-1 setelah HVT1 masuk ............................................................................ 54 28. Visualisasi MPDCMST_kick periode-1 setelah titik 6 dihapus .......... 55 29. Visualisasi MPDCMST_kick periode-2 .............................................. 56 30. Visualisasi graf MPDCMST_kick periode-3 ....................................... 57 31. Grafik visualisasi Tabel 9..................................................................... 59 32. Grafik visualisasi Tabel 10................................................................... 61 33. Grafik visualisasi Tabel 11................................................................... 63
I.
PENDAHULUAN
1.1 Latar Belakang
Perkembangan ilmu pengetahuan dan teknologi yang sangat pesat tidak lepas dari peranan ilmu matematika. Matematika merupakan salah satu alat yang dapat membantu mempermudah pemecahan permasalahan kehidupan sehari-hari. Salah satu cabang matematika yang dapat membantu memecahkan permasalahan tersebut adalah teori graf. Teori graf adalah teori yang sudah ada sejak lebih dari dua ratus tahun silam. Jurnal pertama tentang teori graf muncul pada tahun 1736, oleh matematikawan terkenal dari Swiss bernama Euler.
Pada umumnya teori graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Kurang lebih seratus tahun setelah Euler memberikan solusi tentang jembatan Konigsberg, belum ada perkembangan yang signifikan dalam teori graf. Pada tahun 1847 G. R. Kirchoff berhasil mengembangkan teori pohon pada teori graf yang diterapkan dalam persoalan jaringan listrik.
Luasnya penerapan teori graf membuat begitu banyak cabang ilmu seperti, ilmu komputer, biologi, kimia, ekonomi, dan bahkan permainan pun tidak lepas dari teori graf. Salah satu penerapan teori graf adalah optimasi. Optimasi merupakan suatu
2
proses untuk mencapai hasil ideal atau optimal (nilai efektif yang dapat dicapai) berdasarkan kendala yang diberikan.
Dalam teori graf salah satu masalah optimasi adalah penentuan pohon rentang minimum, atau dikenal dengan istilah Minimum Spanning Tree (MST), dimana dapat diperoleh suatu bobot yang minimum dari suatu graf yang terhubung. Contoh penerapannya adalah desain jaringan telekomunikasi, jaringan transportasi, jaringan komunikasi, jaringan air minum, dan lain-lain. Untuk menentukan MST terdapat dua Algoritma yang umum digunakan yaitu Algoritma Prim dan Algoritma Kruskal.
Jika pada suatu MST diberikan kendala degree (derajat) pada tiap titiknya maka MST tersebut menjadi masalah DCMST (Degree Constrained Minimum Spanning Tree). Contoh terapan MST adalah masalah proses instalasi suatu jaringan yang dapat dilakukan dalam satu tahap. Akan tetapi, karena ada kendala (umumnya kendala pendanaan) maka proses instalasi tersebut harus dilakukan dalam beberapa tahap. Masalah inilah yang disebut dengan instalasi jaringan multi tahap atau Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST).
Untuk menyelesaikan MPDCMST dapat digunakan Algoritma Prim yang telah dimodifikasi atau disebut dengan Modified Prim. Solusi yang didapat merupakan solusi heuristic bukan solusi exact. Solusi heuristic adalah solusi yang ‘nearly optimal’. Heuristic digunakan karena jika menggunakan metode exact, akan sangat
3
“time consuming”. Beberapa metode exact yang dapat digunakan antara lain Metode Branch and Bound, Cutting Plane, Branch and cut, dan lain-lain.
Algoritma Modified Prim digunakan karena pada Modified Prim, jaringan tetap terhubung dan tidak mungkin terbentuk forest pada tiap-tiap tahap. Hal tersebut menjadi alasan mengapa pada penelitian ini digunakan Modified Prim, bukan Modified Kruskal karena pada Algoritma Modified Kruskal tidak ada jaminan bahwa jaringan tetap terhubung pada proses instalasi, walaupun pada akhirnya akan terhubung juga.
Masalah pendistribusian tentu akan dialami oleh perusahaan-perusahaan, terlebih apabila ternyata terdapat daerah yang sulit dijangkau sehingga memerlukan rute yang lebih jauh untuk menjangkau tempat tersebut. Masalah seperti pertimbangan efisiensi waktu, biaya dan rute dalam suatu perusahaan sangat diperhatikan. Untuk itu diperlukan rencana yang tepat agar biaya yang digunakan seminimal mungkin. Tentu diperlukan adanya suatu alat, teknik maupun metode yang dapat mengolah banyak data dengan praktis, efektif dan efisien, sehingga masalah tersebut dapat diselesaikan. Salah satu alat yang dapat digunakan adalah GNU Octave.
GNU Octave merupakan suatu bahasa pemograman tingkat lanjut yang ditulis oleh John W. Eaton. dan kawan-kawan. Program ini bersifat open source sehingga user dapat membantu mengembangkan atau memodifikasinya. Untuk itu penulis tetarik
4
untuk menyelesaikan MPDCMST dengan Algoritma Modified Prim menggunakan bahasa pemrograman GNU Octave.
1.2 Batasan Masalah
Pada penelitian ini masalah di batasi hanya pada penentuan MPDCMST dengan menggunakan GNU Octave dan Algoritma Modified Prim.
1.3 Tujuan
Tujuan dari penelitian yang diangkat adalah : 1. Mengimplementasikan Algoritma Prim untuk penentuan MST. 2. Mengimplementasi Algoritma Modified Prim untuk DCMST. 3. Mengimplementasi Algoritma Modified Prim untuk MPDCMST.
1.4 Manfaat Penelitian
Adapun manfaat dari penelitian ini adalah sebagai salah satu ilustrasi untuk menyelesaikan suatu permasalahan optimisasi jaringan yang sering ditemui. Misalnya seperti permasalahan yang timbul ketika suatu kota ingin membuat suatu jaringan air bersih. Pemerintah tentu akan membangun suatu pipa air yang dapat menghubungkan setiap gedung dengan sumber air. Sehingga, penduduk dapat menggunakan air tersebut. Tetapi ternyata pemerintah menemukan beberapa kendala seperti berikut :
5
a. Tidak semua bangunan dapat terhubung dalam suatu proses instalasi karena biaya yang dimiliki terbatas (tentu dibutuhkan lebih dari satu proses instalasi, atau multi period) b. Ada beberapa bangunan yang harus di pasang lebih awal dari bangunan lainnya (bangunan penting, seperti rumah sakit, dan bangunan fasilitas umum lainnya) c. Keterbatasan penghubung antar bangunan (degree constrained) d. Pada tahap akhir semua bangunan harus sudah selesai terhubung dengan biaya sekecil mungkin (minimum spanning tree). Untuk proses instalasi PDAM, masalah topologi dapat di antisipasi dengan memberikan tambahan kendala pada jarak yang tidak datar (menurun atau menaik). Pada penelitian ini, diasumsikan topologi daerah adalah datar.
II.`
TINJAUAN PUSTAKA
Pada bab ini akan diberikan istilah-istilah yang akan digunakan dalam penelitian ini. Graf merupakan suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari - hari graf digunakan untuk mengambarkan berbagai macam struktur yang ada.
2.1.
Konsep Dasar Teori Graf
Konsep dasar teori graf pada sub bab ini diambil dari Deo(1989). Suatu graf G terdiri dari dua struktur V(G) dan E(G) dengan V(G) adalah himpunan tak kosong yang elemen-elemennya berupa titik dan E(G) adalah himpunan pasangan tak terurut dari titik-titik di V(G) yang disebut sebagai garis atau edge.
Gambar 1. Contoh graf dengan 3 titik dan 5 sisi
7
Jenis-jenis Graf Berdasarkan ada tidaknya loop atau garis ganda pada suatu graf, maka secara umum graf dapat dibedakan sebagai berikut: 1. Graf sederhana adalah graf yang tidak mengandung loop maupun garis ganda. 2. Graf tak-sederhana adalah graf yang mengandung edge (garis) ganda atau loop. Garis pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada garis, graf dapat dibedakan sebagai berikut: 1. Graf tak-berarah yaitu graf yang garisnya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf tak-berarah, urutan pasangan tittik yang dihubungkan oleh garis tidak diperhatikan. Jadi (u, v) = (v, u) adalah garis yang sama. 2. Graf berarah adalah graf yang setiap garisnya diberikan orientasi arah disebut sebagai graf berarah dan garis berarah disebut busur. Pada graf berarah, (u, v) dan (v, u) menyatakan dua busur yang berbeda, dengan kata lain , (u, v) ≠ (v, u). Untuk busur (u, v), titik u dinamakan titik awal dan titik v dinamakan titik terminal
Perjalanan (walk) Perjalanan pada graf G adalah barisan berhingga dari titik dan garis, dimulai dan diakhiri oleh titik, sedemikian sehingga setiap garis menempel dengan titik sebelum dan sesudahnya.
8
Gambar 2. Contoh walk dari graf di atas adalah 𝑣1 , 𝑒1 , 𝑣2 , 𝑒4 , 𝑣4 , 𝑒3 , 𝑣5 , 𝑒2 , 𝑣1 Path (Lintasan) Path adalah suatu walk yang titiknya berbeda. Pada suatu path tidak ada garis yang mucul dua kali. Pada Gambar 2, v1 , e2 , v5 , e3 , v4 , e4 , v2 , e6 , v3 merupakan contoh dari path.
Graf Berbobot (Weighted Graph) Graf berbobot merupakan graf setiap garisnya memiliki bobot atau nilai
Gambar 3. Graf berbobot
Terhubung (Connected) G disebut graf terhubung jika untuk setiap pasang titik u dan v di graf terdapat lintasan dari u ke v (yang juga harus berarti ada lintasan dari u ke v). Jika tidak, maka G disebut graf tak terhubung (disconnected graph) (Munir, 2009).
9
Derajat (Degree) Derajat suatu titik pada graf tak-berarah adalah jumlah garis yang menempel dengan titik tersebut. Notasi d(v) menyatakan derajat titik v. Titik terpencil adalah titik dengan d(v) = 0, karena tidak ada satupun garis yang menempel dengan garis tersebut. Satu garis yang kembali ke titik semula (merupakan loop) dihitung berderajat dua. Secara umum, jika terdapat g loop dan e sisi bukan loop yang menempel dengan titik v, maka derajat titik v adalah d(v) = 2 g + e Titik yang berderajat satu disebut daun. Dengan kata lain, daun hanya bertetangga dengan satu titik.
Gambar 4. Derajat pada graf Contoh: Pada Gambar 4, d(v5)=1, d(v1) = d(v4) = 2, d(v2) = 3, d(v3) = 4 dan v5 adalah daun, karena d(v5)=1.
Siklus (Cycle) atau Sirkuit (Circuit) Lintasan yang berawal dan berakhir pada titik yang sama disebut sirkuit atau siklus. Contoh: Pada Gambar 4, salah satu sirkuitnya adalah v1 e1 v3 e2 v4 e3 v2 e1 v1.
10
Subgraf Merentang (Spanning Subgraph) Subgraf G1 = (V1, E1) dari G = (V, E) dikatakan subgraf merentang jika V1 = V (yaitu G1 memuat semua titik dari G).
Gambar 5. Subgraf merentang
2.2.
Tree (Pohon)
Tree (pohon) merupakan suatu graf terhubung yang tidak mengandung sirkuit.
Gambar 6. Tree Sifat – Sifat Tree Teorema (Deo, 1982) a. Hanya terdapat satu dan hanya satu path yang menghubungkan sepasang titik, maka G adalah tree. b. Jika dalam graf G hanya ada satu dan hanya satu path yang menghubungkan tiap pasang titik, maka G adalah tree. c. Suatu tree yang mempunyai n titik akan mempunyai n-1 sisi. d. Suatu graf terhubung dengan n titik dan n-1 sisi adalah tree.
11
e. Suatu graf adalah suatu tree jika dan hanya jika graf tersebut terhubung minimal f. Suatu graf dengan n titik, n-1 sisi serta tidak mengandung sirkuit, maka graf tersebut terhubung.
Rooted Tree (Pohon Berakar) Tree Berakar merupakan suatu tree yang salah satu titiknya (disebut dengan akar atau root) dibedakan dengan titik yang lainnya.
Gambar 7. Rooted tree Binary Tree (Pohon Biner) Pohon biner adalah suatu pohon yang yang tepat hanya satu titik yang mempunyai derajat dua sedangkan titik-titik lainnya berderajat satu.
Spanning Tree Suatu tree T dikatakan spanning tree dari graf terhubung G jika T adalah subgraf dari G yang memuat semua titik di G.
12
Minimum Spanning Tree Diberikan suatu graf G(V,E), dengan setiap garis 𝑒𝑖𝑗 diberi 𝑐𝑖𝑗 , 𝑐𝑖𝑗 ≥ 0; Minimum spanning tree (MST) dari graf tersebut adalah spanning tree dengan jumlah bobot yang minimum. MST merupakan salah satu struktur dasar graf yang banyak digunakan dalam terapan. Contoh terapan MST sering di temukan dalam desain jaringan telekomunikasi, jaringan transportasi, jaringan komunikasi, dan lain-lain. Untuk mendapatkan MST dapat digunakan algoritma sebagai berikut :
Algoritma Kruskal Algoritma Kruskal merupakan salah satu algoritma greedy untuk menyelesaikan MST. Langkah – langkah algoritma kruskal adalah sebagai berikut : Set T = Ø, input = Graf G (V, E) jumlah titik = n. 1. Sortir garis dari urutan bobot terkecil ke trebesar (increasing order). 2. Pilih garis terkecil dalam sortir dan masukkan ke T. 3. Pilih garis berikutnya dalam sortir. Cek apakah penambahan garis tersebut pada T menyebabkan terjadinya sirkuit. Jika Ya, buang garis tersebut dari sortir dan kembali ke langkah 2. Jika tidak, masukkan garis tersebut pada T dan langkah 4. 4. Cek apakah |T| = n-1 Jika Ya STOP, solusi didapat. Jika Tidak, kembali ke langkah 2.
Contoh : Dengan menggunakan graf berbobot pada Gambar 3 penentuan MST dengan Algoritma Kruskal adalah sebagai berikut :
13
Tabel 1. Penyelesaian MST dengan Algoritma Kruskal Iterasi
Garis yang dipilih
Membentuk cycle ? Ya
|T| = n-1 ? T
Tidak
Keterangan Ya
Tidak
1
ehg
√
{ehg}
√
2
eic
√
{ehg, eic}
√
3
efg
√
√
4
eab
√
5
ecf
√
6
eig
7
ecd
8
eih
9
eah
10
ebc
11
ede
{ehg, eic, efg} {ehg, eic, efg, eab} {ehg, eic, efg, eab, ecf} {ehg, eic, efg, eab, ecf} {ehg, eic, efg, eab, ecf, ecd} {ehg, eic, efg, eab, ecf, ecd,} {ehg, eic, efg, eab, ecf, ecd, eah} {ehg, eic, efg, eab, ecf, ecd, eah} {ehg, eic, efg, eab, ecf, ecd, eah, ede}
√ √ √ √ √ √
√ √
ehg masuk ke T dan dihapus dari list (daftar garis) eic masuk ke T dan dihapus dari list (daftar garis) efg masuk ke T dan dihapus dari list (daftar garis) eab masuk ke T dan dihapus dari list (daftar garis) ecf masuk ke T dan dihapus dari list (daftar garis) Garis eig dihapus dari list. Elemen di T tetap
√
ecd masuk ke T dan dihapus dari list (daftar garis)
√
Garis eih dihapus dari list. Elemen di T tetap eah masuk ke T dan dihapus dari list (daftar garis)
√
Karena |T| = n-1 =8, maka STOP
√
Sumber : Wamiliana (2014)
Gambar 8. Hasil penerapan Algoritma Kruskal
14
Algoritma Prim Algoritma Prim adalah suatu algoritma di dalam teori graf untuk menentukan suatu pohon rentang minimal(minimum
spanning
tree) pada suatu
graf
terhubung.
Adapun langkah-langkah Algoritma Prim adalah sebagai berikut 1. Inisiasi :𝑇 = ∅, 𝑉 = ∅ 2. Tentukan salah satu titik sebagai “root”. 3. Masukkan root ke V. 4. Tentukan sisi minimum yang terhubung dengan root, pilih dan masukkan ke T. Titik ujung sisi tersebut masukkan kedalam V. 5. Pilih sisi minimum yang terhubung dengan titik-titik di V dan cek apakah membentuk sirkuit jika ditambahkan ke T. Jika ya, maka buang sisi tersebut dan pilih lagi sisi minimum berikutnya. Jika tidak, masukkan sisinya di T dan titik nya di V. 6. Cek 𝑇 = 𝑛 − 1? Jika ya STOP. Jika tidak, ulangi langkah 4.
Contoh : Dengan menggunakan graf berbobot pada Gambar 3 penentuan MST dengan Algoritma Prim adalah sebagai berikut :
15
Tabel 2. Penyelesaian Algoritma Prim Iter asi
1 2 3 4
5
6
7
Garis yang dipertimbangkan
eab = 4, eah = 8 eab = 4, eah = 8 ebh = 11 eah = 8, ebh = 11, eci = 2, ecf = 4, ecd = 7 eah = 8, ebh = 11, ecf = 4, ecd = 7, eig = 6, eih = 7 eah = 8, ebh = 11, ecd = 7, eig = 6, eih = 7, efg = 2, efd = 14, efe = 10 eah = 8, ebh = 11, ecd = 7, eig = 6, eih = 7, efd = 14, efe = 10, egh = 1 eah = 8, ebh = 11, ecd = 7, eig = 6, eih = 7, efd = 14, efe = 10.
Garis yang dipilih eab = 4 ebc = 8
Membent uk cycle? Y Tid a ak
ecf = 4
efg = 4
egh = 4
8
eah = 8, ebh = 11, ecd = 7, eih = 7, efd = 14, efe = 10.
ecd = 7
9
eah = 8, ebh = 11, eih = 7, efd = 14, efe = 10, ede = 9
eih = 7
10
eah = 8, ebh = 11, efd = 14, efe = 10, ede = 9.
eah = 8
11
ebh = 11, efd = 14, efe = 10, ede = 9
ede = 9
Sumber : Wamiliana (2014)
T
|T|=n-1 Y a
{eab} {a,b} {eab, {a,b, ebc} c} {eab, ebc, {a,b, eci}, c,i}. {eab, ebc, {a,b, eci, ecf } c,I,f } {eab, ebc, {a,b, eci, ecf, c,i,f, efg} g}.
eci = 2
eig = 6
V
Keteran gan
Tid ak
{eab, ebc, eci, ecf, efg, egh }, {eab, ebc, eci, ecf, efg, egh },
{a,b, c,i,f, g,h}.
{a,b, c,i,f, g,h}.
{eab, ebc, eci, ecf, efg, egh, ecd} {eab, ebc, eci, ecf, efg, egh, ecd}
{a,b, c,i,f, g,h, d} {a,b, c,i,f, g,h, d}
{eab, ebc, eci, ecf, efg, egh, ecd}
{a,b, c,i,f, g,h, d}
{eab, ebc, eci, ecf, efg, egh, ecd, ede}
{a,b, c,i,f, g,h, d,e}
Garis eig dihapus dari list, T dan V tetap
Garis eih dihapus dari list, T dan V tetap Garis eah dihapus dari list, T dan V tetap Karena |T| = n1 = 8, maka STOP
16
Gambar 9. Hasil penerapan Algoritma Prim
2.3.
MST dan Beberapa Turunannya
DCMST (Degree Constrained Minimum Spanning Tree) Dalam penerapan jaringan tentu banyaknya degree di suatu titik dapat mempengaruhi beberapa faktor, seperti laju, dan tekanan. Jika degree pada suatu titik terlalu banyak, tentu laju dan tekanannya akan berkurang sehingga berakibat pada menurunnya kualitas instalasi tersebut. Oleh karena itu diperlukan suatu pembatasan degree pada setiap titik, hal tersebut dengan Degree Constrained Minimum Spanning Tree.
DCMST adalah MST yang diberikan kendala degree pada setiap titiknya. Permasalahan DCMST adalah untuk menentukan Minimum Spanning Tree T dari G dimana degree dari titik dibatasi dengan persamaan, 1 ≤ di ≤ bi dengan bi adalah batas atas derajat tiap titik (Caccetta dan Wamiliana, 2001).
MPDCMST (Multi Period Degree Constrained Minimum Spanning Tree) Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST) adalah masalah lanjutan dari permasalahan Minimum Spanning Tree yang telah diberikan kendala degree (Degree Constrained Minimum Spanning Tree Problem).
17
Pada saat dilakukan instalasi jaringan, ternyata ditemukan beberapa faktor seperti dana, cuaca, sehingga tidak semua titik dapat diinstal sekaligus. Karena proses instalasi jaringan harus dilakukan dalam beberapa tahap, maka masalah ini menjadi masalah MPDCMST (Wamiliana, dkk. 2005).
Ilustrasi untuk menyelesaikan suatu permasalahan optimisasi jaringan yang sering ditemui. Misalnya permasalahan yang timbul ketika suatu kota ingin membangun jaringan air bersih. Pemerintah tentu akan membangun suatu jaringan pipa air yang dapat menghubungkan setiap gedung dengan sumber air. Sehingga, penduduk dapat menggunakan air tersebut. Tetapi ternyata pemerintah menemukan beberapa kendala seperti berikut : a. Tidak semua bangunan dapat terhubung dalam suatu proses instalasi karena biaya yang dimiliki terbatas (tentu dibutuhkan lebih dari satu proses instalasi, atau multi period) b. Ada beberapa bangunan yang harus di pasang lebih awal dari bangunan lainnya (bangunan penting, seperti rumah sakit, dan bangunan fasilitas umum lainnya) c. Keterbatasan penghubung antar bangunan (degree constrained) d. Ketika waktu sudah habis semua bangunan harus sudah selesai terpasang, tetapi dengan menjadikan biaya yang dikeluarkan terkecil (minimum spanning tree)
18
2.4.
Konsep Dasar Matriks
Istilah dan definisi yang digunakan dalam subbab ini diambil dari (Usman,dkk. 2009). Suatu matrik A r x s adalah tatanan angka-angka atau elemen-elemen dalam bentuk empat persegi dengan banyaknya baris r dan banyaknya kolom sebanyak s. Suatu vektor Y r x 1 adalah suatu matrik dengan baris r dan satu kolom. Suatu matrik A mempunyai unsur yang dilambangkan dengan aij , dengan j menyatakan banyaknya kolom sedangkan i menyatakan banyaknya baris. Suatu matrik A dapat juga dilambangkan dengan : A = [𝒂𝒊𝒋 ] Matriks Bujur Sangkar Matriks bujursangkar adalah matriks yang memiliki baris dan kolom yang sama banyak. Matriks bujursangkar n x n dikatakan sebagai matriks dengan orde n. 𝑎11 𝐴 = [𝑎 21
𝑎12 𝑎22 ]
Matriks Segitiga Atas Matriks Segitiga Atas adalah matriks dimana semua entri di bawah diagonal utama bernilai nol. Contoh. 0 𝐴 = [0 0
2 3 0 4] 0 0
Matriks Segitiga Bawah Matriks segitiga bawah adalah matriks dimana semua entri di atas diagonal utama bernilai nol.
19
Contoh. 0 𝐴 = [4 3
0 0 0 0] 5 0
Matriks Nol Matriks nol adalah suatu matriks yang semua elemennya mempunyai nilai nol. Contoh. 0 𝐴 = [0 0 2.5.
0 0 0 0] 0 0
Hubungan Graf dan Matriks
Istilah dan definisi yang digunakan dalam subbab ini diambil dari Siang (2006). Misalkan graf G adalah graf tak berarah dengan titik-titik 𝑣1 , 𝑣2 , … , 𝑣𝑛 (n berhingga). Matriks ketetanggaan yang sesuai dengan graf G adalah matriks 𝐴 = (𝑎𝑖𝑗 ) dengan 𝑎𝑖𝑗 = jumlah sisi yang menghubungkan 𝑣𝑖 dengan 𝑣𝑗 selalu sama dengan jumlah sisi yang menghubungkan titik 𝑣𝑗 dengan titik 𝑣𝑖 . Matriks ketetanggaan selalu merupakan matriks yang simetris (𝑎𝑖𝑗 = 𝑎𝑗𝑖 untuk setiap i dan j).
Gambar 10. Contoh graf direpresentasikan ke dalam matriks.
20
Untuk mempermudah pemahaman, tiap-tiap baris dan kolom matriks diberi indeks 𝑣𝑖 yang sesuai dengan titik grafnya. Sel perpotongan baris 𝑣𝑖 dan kolom 𝑣𝑗 menyatakan sisi yang menghubungkan 𝑣𝑖 dan 𝑣𝑗 . Sehingga didapat matriks sebagai berikut :
Ada beberapa hal yang bisa dicatat dalam merepresentasikan graf dengan matriks ketetanggaan : a) Graf tidak mempunyai loop jika dan hanya jika semua elemen diagonal utamanya = 0. b) Matriks tetangga dapat dipakai untuk mendeteksi graf yang tidak terhubung secara mudah.
Suatu graf tidak terhubung terdiri dari k
komponen jika dan hanya jika matriksnya berbentuk 𝐴1 𝑂 …𝑂 𝑂 𝐴2 …𝑂 [ ] … … …… 𝑂 𝑂 … 𝐴𝑘 O adalah matriks yang semua elemennya = 0 dan 𝐴𝑖 adalah matriks bujur sangkar yang merupakan matriks dari graf terhubung yang merupakan komponen ke-i dari graf. c) Derajat titik 𝑣𝑖 adalah jumlah semua komponen matriks baris / kolom ke-i 𝑛
𝑛
𝑑(𝑣𝑖 ) = ∑ 𝑎𝑖𝑗 = ∑ 𝑎𝑖𝑗 = 𝑑(𝑣𝑗 ) 𝑗=1
𝑖=1
21
Derajat graf G adalah jumlah semua komponen matriks = ∑𝑖 ∑𝑗 𝑎𝑖𝑗 d) Graf G adalah graf bipartite (𝐾𝑚,𝑛 ) jika dan hanya jika matriks dari graf terhubung berbentuk [
𝑂 𝐼𝑛
𝐼𝑚 ] dengan: 𝑂
O = matriks yang semua elemennya = 0 𝐼𝑚 = matriks berukuran 𝑚 × 𝑛 yang semua elemennya = 1 𝐼𝑛 = matriks berukuran 𝑛 × 𝑚 yang semua elemennya = 1 e) Graf G adalah graf lengkap jika dan hanya jika semua elemen dalam diagonal utama = 0 dan semua elemen diluar diagonal utama = 1. Matriks Bersisian Misalkan G adalah graf tanpa loop dengan 𝑛 titik 𝑣1 , 𝑣2 , … , 𝑣𝑛 dan 𝑘 sisi 𝑒1 , 𝑒2 , … , 𝑒𝑘 . Matriks bersisian yang sesuai dengan graf G adalah matriks A berukuran 𝑛 × 𝑘 yang elemennya adalah: 𝑎𝑖𝑗 = {
1; 𝑗𝑖𝑘𝑎 𝑎𝑑𝑎 𝑔𝑎𝑟𝑖𝑠 𝑦𝑎𝑛𝑔 𝑚𝑒𝑛𝑔ℎ𝑢𝑏𝑢𝑛𝑔𝑘𝑎𝑛 𝑡𝑖𝑡𝑖𝑘 𝑣𝑖 𝑑𝑒𝑛𝑔𝑎𝑛 𝑡𝑖𝑡𝑖𝑘 𝑣𝑗 0; 𝑙𝑎𝑖𝑛𝑛𝑦𝑎
Dari Gambar 7, graf dapat direpresentasikan kedalam matriks bersisian sebagai berikut:
22
Ada beberapa hal yang dapat dicatat sehubungan dengan penggunaan matriks bersisian untuk menyatakan suatu graf : a) Setiap garis berhubungan degan 2 titik (karena G tidak mempunyai loop), maka dalam matriks binernya, setiap kolom mempunyai tepat 2 buah elemen 1 dan sisanya adalah elemen 0. b) Jumlah elemen pada baris ke-i adalah derajat titik 𝑣𝑖 , sedangkan derajat total graf G adalah jumlah semua elemen dalam matriks binernya. c) Jika semua elemen pada baris ke-i adalah 0, maka titik 𝑣𝑖 merupakan titik terasing. d) Dua kolom yang semua elemennya sama menyatakan sisi yang paralel. Contoh : Pada graf terhubung tidak berarah bobot sisi antara titik awal dan titik tujuan tetap. Sehingga bila dilihat graf berbobot pada gambar 3, bobot sisi dari titik a ke titik b sama dengan titik b ke a. Maka yang digunakan adalah matriks ketetanggaan, yang tentunya memiliki entri 𝑀𝑖𝑗 = 𝑀𝑗𝑖 .
Berikut bentuk matriks dari graf berbobot pada Gambar 3
𝑎 𝑏 𝑐 𝑑 𝑒 𝑓 𝑔 ℎ 𝑖
𝑎 𝑏 𝑐 𝑑 0 4 0 0 4 0 8 0 0 8 0 7 0 0 7 0 0 0 0 9 0 0 0 14 0 0 0 0 8 11 0 0 [0 0 2 0
𝑒 𝑓 0 0 0 0 0 0 9 14 0 10 10 0 0 2 0 0 0 0
𝑔 ℎ 𝑖 0 8 0 0 11 0 0 0 2 0 0 0 0 0 0 2 0 0 0 1 6 1 0 7 6 7 0]
23
Dapat dilihat pada matriks bahwa 𝑀𝑎𝑐 = 0. Ini artinya tidak ada sisi diantara titik a dan c. Sedangkan pada 𝑀𝑎𝑏 bernilai 4, artinya bobot sisi pada titik a dan b adalah 4. Dapat dilihat juga pada 𝑀𝑎𝑎 = 0, 𝑀𝑏𝑏 = 0, 𝑀𝑐𝑐 = 0, 𝑀𝑑𝑑 = 0, 𝑀𝑒𝑒 = 0, 𝑀𝑓𝑓 = 0, 𝑀𝑔𝑔 = 0, 𝑀ℎℎ = 0, 𝑀𝑖𝑖 = 0, ini berarti graf tersebut adalah graf sederhana.
2.6.
Model (Persamaan) Matematis
Istilah – istilah pada subbab ini diambil dari Sasongko (2010). Model merupakan suatu bentuk tiruan yang dapat diartikan bermacam – macam, model dapat berbentuk fisik atau nonfisik, seperti model matematis. Model matematis (nonfisik) di bentuk berdasarkan dua pendekatan. Pendekatan pertama disusun berdasarkan sekumpulan teori yang masih relevan sehingga mendapatkan sekumpulan persamaan. Pendekatan pertama ini disebut model kotak putih (white box model). Di sisi lain, pendekatan kedua disusun berdasarkan data yang didapat dari lapangan atau dari hasil suatu penelitian. Pendekatan kedua mendapatkan persamaan empiris yang merupakan hubungan antara input dan output, atau hubungan dari variable bebas (independent variable) dengan variable tak bebas (dependent variable).
Secara garis besar, model matematis dapat dibagi menjadi dua bagian, yaitu persamaan aljabar (PA) dan persamaan differential (PD). 𝑑𝑦
Sesuai namanya
persamaan differential memiliki bentuk differential, misal 𝑑𝑥 . Sedangkan PA tidak memiliki bentuk differential.
24
Penyelesaian Model Matematika Berdasarkan model (persamaan) matematis serta keperluan dalam penyelesaian model matematis, maka metode penyelesaian model dapat dibagi menjadi empat bagian, yaitu a. Sistem Persamaan Simultan Sistem persamaan simultan (SPS) merupakan sistem persamaan yang mempunyai lebih dari satu persamaan dan diselesaikan secara simultan. Sistem persamaan ini tidak terbatas pada sistem persamaan linear saja, namun juga dapat berupa gabungan dengan persamaan differensial. Contoh. 𝑎11 . 𝑥1 + 𝑎12 . 𝑥2 + 𝑎13 . 𝑥3 = 𝑦1 𝑎21 . 𝑥1 + 𝑎22 . 𝑥2 + 𝑎23 . 𝑥3 = 𝑦2
(2.1)
𝑎31 . 𝑥1 + 𝑎32 . 𝑥2 + 𝑎33 . 𝑥3 = 𝑦3
b. Akar Persamaan (AP) atau Persamaan Nonlinear Akar persamaan atau diistilahkan dengan sistem persamaan nonlinear merupakan bentuk persamaan aljabar yang nilainya sama dengan nol. Jika hanya satu variable bebas x dapat ditulis sebagai 𝑓(𝑥) ≅ 0. Bentuk ini banyak digunakan dalam bentuk persamaan teknik atau sains. Contoh bentuk penyelesaian analitis atau eksak yang dikenal adalah pencarian akar dari suatu persamaan kuadrat dengan bentuk: 𝑦 = 𝑓(𝑥) = 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 = 0
(2.2)
25
Penyelesaian secara analitis dari Persamaan 2.2 adalah 𝑥1,2 =
−𝑏±√𝑏2 −4𝑎𝑐
(2.3)
2𝑎
Sebagai indikator munculnya nilai akar dari penyelesaian analitis Persamaan 2.4 adalah 𝐷𝑎𝑘𝑟 = 𝑏 2 − 4𝑎𝑐. Apabila 𝐷𝑎𝑘𝑟 > 0, maka dua nilai akar akan didapatkan, yaitu 𝑥1 dan 𝑥2 . Apabila 𝐷𝑎𝑘𝑟 = 0, maka ada satu nilai akar yang didapatkan, yaitu 𝑥 = 𝑥1 = 𝑥2 . Apabila 𝐷𝑎𝑘𝑟 < 0, maka nilai akar imajiner.
c. Persamaan Differensial (PD) Ciri persamaan differensial adalah adanya bentuk differensial pada persamaannya, misal
𝑑𝑦 𝑑𝑥
. Pada bentuk tersebut tanda d dapat diartikan
sebagai selisih (∆) pada limit 𝑦, 𝑥 ≈ 0. Sebagai variable bebasnya (independent variable) adalah x dan variable tak bebasnya (dependent variable) adalah y.
d. Pengolah Data – Pencocokan Kurva Tahap ini digunakan untuk menyelesaikan model kotak hitam. Pendekatan kotak hitam pada dasarnya merupakan analisis data sehingga akan mendapatkan persamaan empiris atau konstanta tertentu yang selanjutnya dapat digunakan seperti pada kotak putih, yaitu untuk mengubah – ubah variabel independen atau tatapan lainnya sehingga akan mendapatkan persamaan sebagai objek kajian. Proses untuk mendapatkan persamaan
26
dengan menggunakan data dalam metode numerik di sisi yang lain disebut juga percocokan kurva (curve fitting).
2.7.
GNU Octave
GNU Octave adalah suatu bahasa pemograman tingkat tinggi yang ditunjukan untuk menyelesaikan perhitungan numerik. Program ini menyediakan fitur-fitur yang dapat digunakan untuk memecahkan permasalahan linier dan non-linear secara numerik, dan untuk melakukan percobaan numerik dengan bahasa yang sesuai dengan Matlab. Program ini juga dapat digunakan sebagai bahasa berorientasi.
GNU Octave merupakan sofware yang di sebarluaskan secara gratis. User dapat mendistribusikan atau memodifikasinya sesuai dengan ketentuan GNU General Public License (GPL) yang diterbitkan oleh Free Software Foundation. Octave ditulis oleh John W. Eaton dan kawan-kawan (Eaton, 2017).
III.
3.1.
METODE PENELITIAN
Waktu dan Tempat Penelitian
Penelitian ini dilakukan di Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Lampung tahun 2016.
3.2.
Bahan dan Alat
Bahan yang dibutuhkan untuk mendukung penelitian ini adalah data masalah dari berbagai literatur mengenai Matrix, Algoritma Prim serta implementasinya.
Alat yang digunakan dalam penyelesaian penelitian ini adalah: 1. Perangkat keras (Hardware) Notebook Acer 4732z, dengan spesifikasi : -
Processor Intel Dual-Core CPU T4300 2.1GHz
-
Hardisk 500GB
-
RAM 3GB
-
Mouse
2. Perangkat lunak (Software) -
Windows 10 Pro Build 14393.1066 32-bit
-
Aplikasi GNU Octave
28
3.3.
Alur Penelitian
Langkah-langkah yang digunakan dalam penelitian ini adalah : a) Mengumpulkan bahan literatur serta studi kepustakaan. b) Membuat program untuk memanggil data. Data diperoleh dari penelitian yang telah dilakukan oleh Wamiliana dkk. (2005). Data tersebut merupakan data yang di-generate secara acak dengan distribusi uniform. Data terbagi menjadi 10 folder dengan masing-masing folder berisi 30 file berekstensi .dat. Berikut data yang telah dimasukan kedalam GNU Octave :
Gambar 11. Tampilan data folder 10-vertex file 1.dat di Octave Program pada editor GNU Octave flie=load('O:\Data Bu Wamil\10-vertex\1.dat');
29
c) Membuat program GNU Octave yang dapat menghitung banyaknya titik yang dihasilkan oleh suatu data sisi yang diperoleh Graf yang akan diteliti merupakan graf terhubung sederhana, yang mana setiap titik terhubung dengan titik lainnya oleh satu buah sisi. Berikut tabel hubungan antara banyak titik dan sisi pada suatu graf terhubung sederhana.
Tabel 3. Tabel banyak titik dan banyak sisi pada graf terhubung sederhana Banyak Banyak sisi Banyak Banyak sisi titik titik 0 28 1 8 1 36 2 9 3 45 3 10 6 190 4 20 10 435 5 30 15 780 6 40 21 1125 7 50
Jika diperhatikan banyak sisi yang terbentuk pada tabel 3 membentuk suatu pola barisan. Sehingga dapat diperoleh rumus suku ke-Un dari pola tersebut adalah sebagai berikut: 𝑈𝑛 =
𝑛(𝑛−1) 2
2𝑈𝑛 = 𝑛2 − 𝑛
(3.1) (3.2)
Dengan menggunakan Persamaan 2.3 bisa ditemukan banyak titik dengan mensubstitusikan Persamaan 3.2. sehingga diperoleh persamaan baru yaitu : 𝑛=
1+√1+8𝑈𝑛 2
(3.3)
30
Dari Persamaan 3.3 dapat diperoleh banyak titik (banyak titik selalu bernilai positif).
Misal banyak data pada data 1 dalam folder 10-vertex adalah 45, maka program ini akan menghitung bahwa banyak titiknya adalah 10. Program pada GNU Octave function titik = cek_titik(matriks) bykisi=length(matriks); %bykisi=Un c=2*bykisi; n=(1+sqrt(1+(4*c)))/2; titik=n; end
d) Membuat program yang dapat memberikan nilai X dan Y secara otomatis pada setiap data. Dengan X adalah titik awal dan Y adalah titik yang dituju. Misal pada data 1, folder 10 vertek, terdapat 10 titik, maka program ini akan memunculkan secara otomatis sebagai berikut X=
Y=
1 2 3 4 6
2 3 5 8 8
1 2 3 4 6
1 2 3 4 6
3 4 4 5 6 7 9 10 9 10
1 2 3 5 7
5 6 8 6 8
1 2 3 5 7
1 2 3 5 7
6 7 7 8 9 10 7 8 9 10
Program pada GNU Octave function [X Y]=inputanya(n) j=1; X=[];
1 2 4 5 8
1 2 4 5 8
1 3 4 6 9
8 9 10 9 10 4 5 6 7 9 10 7 9 10 10
31
while j <= n && n > 2 %perulangan akan berjalan jika n lebih dari 2 r=n-j; k=j*ones(1,r); j=j+1; cr=length(X); rk=cr+1; dk=length(k); X(1,rk:cr+dk)=k; if j==n break end end Y=[]; p=1; while p <= n && n > 2 yh=p+1; if yh > n break end h=yh:n; p=p+1; iu=length(Y); yu=iu+1; tu=length(h); Y(1,yu:iu+tu)=h; end
e) Membuat program untuk memasukan bobot pada setiap titik X dan Y. Sehingga di hasilkan matrik sebagai berikut. Data =
Gambar 12. Hasil menggabungkan titik X dan Y dengan bobotnya
Program pada GNU Octave data=sparse(X,Y,flie)
32
f) Membuat matriks data menjadi matriks persegi dan segitiga atas RO =
Gambar 13. Bentuk matriks persegi dari data folder 10-vertex file 1.dat
Program pada GNU Octave function stgb = sgitiga(disatukan) [M, N]=size(disatukan); while M < N disatukan(N,:)=0; M=M+1; end while M > N disatukan(:,M)=0; N=N+1; end stgb=tril(disatukan + disatukan'); end
g) Membuat program untuk merubah matriks RO menjadi matriks tetangga Perubahan ini dilakukan agar entri entri pada matriks 𝑅𝑂𝑖𝑗 = 𝑅𝑂𝑗𝑖 dengan begitu analisis bisa dilihat dari baris atau kolom saja.
33
Gambar 14. Matriks Tetangga data 1 pada folder 10-vertex Program pada GNU Octave function Y =matrikstetangga(RO) [M N]=size(RO); Y=full(RO); for r=1:M for j=1:N Y(r,j)=Y(j,r); end end end
h) Membuat program Algoritma Prim. Program ini berjalan dengan membuat matriks kosong (T) berukuran M x N sesuai dengan ukuran yang dibentuk dari matriks tetangga dan v1 sebagai v pada Algoritma Prim. Matriks T berfungsi sebagai matrik yang menerima entri-entri yang telah diproses, yang nantinya akan menjadi matriks MST. v1 menginisialkan setiap kolom pada matriks, jika v1 atau titik awal tidak diberi nilai maka akan otomatis bernilai 1. Artinya Algoritma Prim yang di jalankan dimulai dari kolom 1 sebagai titik awalnya. Adapun hasil dari program ini adalah sebagai berikut
34
Gambar 15. Hasil nilai T dan V Algoritma Prim
Program pada GNU Octave function [T V1]=MSTjadi(DG) V1 = [1]; V2 = 2:length(DG); T = zeros(size(DG)); od = max(max(DG)) ; while (~isempty(V2)) min = od; for i=1:length(V1) for j=1:length(V2) if (DG(V2(j),V1(i))>0 && DG(V2(j),V1(i))<min) min = DG(V2(j),V1(i)); u = V1(i); v = V2(j); end end end T(v,u) = min; V1 = [V1 v]; V2(V2==v)=[]; end end
i) Membuat program DCMST(Degree Constrained Minimum Spanning Tree) dengan algoritma Modified Prim. Pada tahap ini sama saja dengan program MST. Namun penulis memasukkan perlakuan atau kendala bahwa setiap titik hanya boleh terhubung paling banyak 3 titik (degree ≤ 3).
35
j) Membuat program MPDCMST (Multi Period Degree Constrained Minimum Spanning Tree) dengan Algoritma Modified Prim Pada Tahap ini, penyelesaian MST dilakukan dengan memberikan kendala batasan degree ≤ 3 dan membagi proses instalasi menjadi 3 tahap. Contoh :
Gambar 16. Contoh graf dengan 10 titik
Pada permasalahan MPDCMST tersebut diberikan degree ≤ 3 dan tahap sebanyak 3 kali. v1 dianggap sebagai titik sumber. |HVTk| adalah himpunan titik-titik yang harus di-install pada tahap ke k atau sebelumnya. |HVTk| diinisiasi sebagai berikut :
Tahap 1 : titik v2 dan v4.
Tahap 2 : titik v5.
Tahap 3 : titik v10.
Tahap 1 Pada tahap ini titik yang wajib di instal adalah v 2 dan v4. Sesuai dengan Algoritma Prim dengan DCMST, diperoleh titik terdekat dari sumber yaitu v2, v3 dan v5. Diperiksa ternyata pada tahap 1, |HVTk| = v2 dan v4 ini berarti
36
titik v4 belum diinstall, maka v5 diganti dengan v4. Sehingga diperoleh graf sebagai berikut :
Gambar 17. Graf hasil MPDCMST tahap 1
Tahap 2 Pada tahap ini |HVTk| = v5. Dilakukan pengecekan kembali dengan menggunakan Algoritma Prim dan DCMST. Diperoleh titik yang diinstall adalah v2, v3, v4, v6, v5, dan v7. Dapat dilihat bahwa v5 telah diinstall pada tahap ini, maka tahap ini selesai dan di peroleh graf sebagai berikut :
Gambar 18. Graf hasil MPDCMST tahap 2
37
Tahap 3 Pada tahap ini
|HVTk| = v10. Dilakukan pemilihan sisi terdekat
menggunakan Algoritma Prim dan DCMST sehingga di peroleh titik yang telah diinstall yaitu v2, v3, v4, v6, v5, v7, v10, v8, v9. Dapat dilihat bahwa vertex v10 telah diinstall pada tahap ini. Maka tahap ini selesai dan diperoleh graf sebagai berikut :
Gambar 19. Graf hasil tahap 3
Karena seluruh vertex telah terinstall maka proses ini selesai. k)
Mengimplementasi dengan data yang telah dibangkitkan
l)
Menarik kesimpulan
V.
KESIMPULAN
Berdasarkan penelitian yang telah dilakukan didapat kesimpulan sebagai berikut: 1. Nilai optimal MST merupakan lower bound dari DCMST dan nilai optimal DCMST merupakan lower bound untuk MDCMST. 2. Hasil rata-rata bobot disetiap vertex yang diuji dengan Algoritma Modified Prim lebih tinggi dari hasil Algoritma Prim. Hal ini terjadi karena pada Algoritma Modified Prim terdapat kendala yang mempengaruhi besar bobot. 3. Pada permasalahan MPDCMST, waktu penyelesaian Algoritma Modified Prim terbaik diperoleh menggunakan Algoritma MPDCMST_awal. 4. Pada permasalahan MPDCMST, solusi Algoritma Modified Prim terbaik diperoleh menggunakan Algoritma MPDCMST_kick. 5. Dalam penyelesaian permasalahan MPDCMST dengan GNU Octave, solusi hasil dan waktu penyelesaian Algoritma Modified Prim yang terbaik diperoleh menggunakan Algoritma MPDCMST_akhir.
1
DAFTAR PUSTAKA
Caccetta, L., dan Wamiliana, 2001. Heuristics Algorithms for Defree Constrained Minimum Spanning Tree Problems, in Proceeding of the International Congress on Modelling and Simulation (MODSIM 2001), Canberra, Editors: F.Ghassemi et al., pp. 2161-2166,2001. Deo, N. 1989. Graph Theory with Applications to Engineering and Computer Science. Prentice Hall Inc., New York. Eaton, J W. 2017. https://www.gnu.org/software/octave/about.html. Diakses pada hari Jum’at, 20 Januari 2017 Munir, Rinaldi. 2009. Matematika Diskrit. Edisi Ketiga. Bandung:Informatika. Sasongko S. Budi. 2010. Metode Numerik dengan Scilab. ANDI, Yogyakarta. 206. Siang J.J. 2006. Yogyakarta.
Matematika Diskrit Pada Ilmu Komputer edisi ketiga.
ANDI,
Usman, M. dan Warsono. 2009. Teori Model Linear dan Aplikasinya. Sinar Baru Algesindo. Bandung. Wamiliana, Dwi Sakethi, Akmal J., and Edy Baskoro. 2005. ‘The Design of Greedy Algorithm for Solving the Multiperiod Degree Constrained Minimum Spanning Tree Problem’. Jurnal Sains dan Teknologi, Vol. 11 No. 2. pp 93-96. Wamiliana, 2014. Matematika Diskrit, Diktat Kuliah Matematika Diskrit, Jurusan Matematika, Universitas Lampung. Wamiliana, Usman Mustofa, Dwi Sakethi, Restu Yuniarti and Ahmad Cucus. 2015. ‘The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving The Multiperiod Degree Constrained Minimum Spanning Tree Problem’. IEEE Explore : http://ieeexplore.ieee.org/document/7516333/
