SEMINAR HASIL
PENGGUNAAN ALGORITMA KRUSKAL DALAM JARINGAN PIPA AIR MINUM KECAMATAN NGANJUK KABUPATEN NGANJUK Oleh: Angga Putra Pratama 1209 100 040
Dosen Pembimbing Drs. Sumarno, DEA Dr. Darmaji, S.Si, MT
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2013
Latar Belakang Air merupakan salah satu kebutuhan makhluk hidup yang penting Jaringan pipa air minum dapat diselesaikan dengan pohon merentang minimum Terdapat 2 algoritma yang sering digunakan dalam mencari pohon merentang minimum Kondisi jaringan pipa air minum Kecamatan Nganjuk Kabupaten Nganjuk
Pendahuluan
PERUMUSAN MASALAH Bagaimana menentukan penyelesaian optimal dalam jaringan pipa air minum serta database pipa di Kecamatan Nganjuk Kabupaten Nganjuk dengan menggunakan Algoritma Kruskal.
Pendahuluan
BATASAN MASALAH Jaringan pipa air minum yang dikaji adalah jaringan pipa utama atau primer. Tidak memperhatikan volume air, jenis pipa, dan sumber air. Tidak memperhatikan debit air. Perangkat lunak yang digunakan adalah Matlab.
Pendahuluan
TUJUAN Untuk menentukan penyelesaian optimal dalam jaringan pipa air minum serta database pipa di Kecamatan Nganjuk Kabupaten Nganjuk dengan menggunakan Algoritma Kruskal.
Pendahuluan
MANFAAT Memberi kontribusi pada implementasi Teori Graf. Memberi kontribusi pada implementasi Algoritma Kruskal dalam penyelesaian pohon merentang minimum. Memberi salah satu dasar pertimbangan alternatif dalam pengambilan keputusan tentang pembangunan jaringan pipa air minum
Pendahuluan
TEORI GRAF Graf G didefinisikan sebagai pasangan himpunan (V,E) ditulis dengan notasi G=(V,E), yang dalam hal ini V adalah himpunan tak kosong dari simpul-simpul (vertices) dan E adalah himpunan sisisisi (edges) yang menghubungkan sepasang simpul [5].
Tinjauan Pustaka
Dengan memperhatikan kondisi sisinya atau orientasi pada arah sisi, suatu graf dapat dibagi menjadi dua, yaitu graf berarah (directed graph) dan graf tidak berarah (undirected graph).
Tinjauan Pustaka
POHON Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Pohon adalah suatu graf terhubung yang tidak mempunyai subgraf yang memuat sikel [6]. Sedangkan sikel (cycle) dalam graf adalah lintasan dalam graf dimana simpul awal dan simpul akhir sama.
Tinjauan Pustaka
POHON MERENTANG MINIMUM Pohon merentang (spanning tree) dari suatu graf adalah subgraf yang merentang dan merupakan sebuah pohon [5]. Pohon merentang diperoleh dengan cara menghilangkan sikel yang terdapat didalam graf tersebut. Setiap graf terhubung berbobot paling sedikit mempunyai satu pohon merentang. Pohon merentang yang memiliki bobot minimum dinamakan pohon merentang minimum (minimum spanning tree).
Tinjauan Pustaka
ALGORITMA KRUSKAL Langkah-langkah Algoritma Kruskal dalam pencarian pohon merentang minimum (minimum spanning tree) adalah sebagai berikut [7] : 1. Lakukan pengurutan terhadap semua sisi di graf mulai dari sisi dengan bobot kecil sampai besar. 2. Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sikel. Tambahkan sisi tersebut di dalam pohon. 3. Ulangi langkah 2 diatas sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).
Tinjauan Pustaka
CONTOH ALGORITMA KRUSKAL
graf H
Menentukan pohon merentang minimum dari Graf H dengan menggunakan Algoritma Kruskal
Tinjauan Pustaka
Langkah-langkah Algoritma Kruskal dalam penentuan pohon merentang minimum pada graf H pada adalah 1. Lakukan pengurutan terhadap semua sisi di graf H mulai dari sisi dengan bobot kecil sampai besar, yaitu Sisi v3v4 memiliki bobot 5; Sisi v3v5 memiliki bobot 6; Sisi v1v2 memiliki bobot 8; Sisi v2v3 memiliki bobot 9; Sisi v4v5 memiliki bobot 10; Sisi v1v6 memiliki bobot 11; Sisi v3v6 memiliki bobot 13 2. Pilih sisi yang mempunyai bobot dari yang kecil ke yang besar, yang tidak membentuk sikel. Tambahkan sisi tersebut di dalam pohon. Proses pemilihan sisi diulangi sampai semua simpul terhubung.
Tinjauan Pustaka
Tabel 1 Langkah-langkah Penyelesaian Menggunakan Algoritma Kruskal pada Graf H Iterasi ke
Sisi
Bobot
1
v3 v4
5
2
v3 v5
6
3
v1 v2
8
4
v2 v3
9
5
v4 v5
10
6
v1 v6
11
7
v3 v6
13
Tinjauan Pustaka
Keterangan
Karena membentuk sebuah sikel didalam pohon, maka sisi v4v5 dihilangkan
Karena membentuk sebuah sikel didalam pohon, maka sisi v3v6 dihilangkan
Setelah dilakukan 7 iterasi sebagaimana terlihat pada Tabel 1, maka Graf H mempunyai pohon merentang minimum sebagai berikut:
Tinjauan Pustaka
JARINGAN Jaringan (network) adalah istilah model untuk memvisualisasikan sebuah jaringan agar sistem jaringan yang sesungguhnya bisa diketahui dan dipahami secara mudah, cepat, dan tepat.
Tinjauan Pustaka
METODOLOGI PENELITIAN 1. Studi Literatur 2. Pengumpulan Data 3. Pengolahan Data 4. Analisis hasil dan Evaluasi 5. Penulisan Tugas Akhir
Metodologi Penelitian
HASIL STUDI LOKASI PENELITIAN Tahun 2012 jumlah pelanggan kecamatan Nganjuk yang dimiliki PDAM adalah sebesar 38,98% dari total jumlah pelanggan yang berada di daerah pelayanan PDAM Kabupaten Nganjuk yang mencakup seluruh wilayah. Pipa distribusi pada umumnya terbagi menjadi beberapa bagian. Untuk pipa distribui PDAM Kabupaten Nganjuk terdiri atas 3 bagian, yaitu: 1. Pipa primer berdiameter 300 mm sampai dengan 150 mm 2. Pipa sekunder berdiameter 100 mm 3. Pipa tersier berdiameter 75 mm sampai dengan 25 mm
Pembahasan
Peta Jaringan Pipa Primer Kecamatan Nganjuk Kabupaten Nganjuk adalah sebagai berikut:
Pembahasan
PENYELESAIAN JARINGAN PIPA AIR MINUM DENGAN ALGORITMA KRUSKAL Langkah-langkah dalam menggunakan Algoritma Kruskal untuk menyelesaikan persoalan jaringan pipa primer distribusi air minum Kecamatan Nganjuk Kabupaten Nganjuk adalah sebagai berikut: 1. Lakukan pengurutan terhadap semua sisi dalam jaringan pipa air minum Kecamatan Nganjuk mulai dari sisi dengan bobot kecil sampai besar,
Pembahasan
Tabel 2 Panjang jaringan pipa primer air minum Kecamatan Nganjuk Kabupaten Nganjuk No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Jalur Pipa p12p13 p36p39 p44p45 p46p47 p49p50 p3p4 p4p15 p41p42 p16p17 p24p25 p40p41 p43p44 p47p48 p48p49 p8p9 p45p46 p30p31 p33p34 p11p12 p7p8 p5p6
Pembahasan
Panjang (m)
No
34 34 50 50 50 84 84 84 100 100 100 100 117 117 134 134 140 167 183 200 217
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
Jalur Pipa p15p16 p21p22 p32p33 p42p43 p50p51 p22p26 p1p9 b p18p19 p11p14 p12p28 p20p21 p31p32 p32p36 p29p30 p10p11 p26p40 p39p40 p9p10 p1p9 a p23p24 p28p29
Panjang (m)
No
227 234 250 250 250 284 300 300 325 334 334 334 334 340 358 384 400 417 441 450 458
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Jalur Pipa p53p54 p34p35 p58p59 p19p20 p55p57 p36p37 p58p60 p6p7 p17p18 p8p23 p37p38 p50p52 p51p53 p4p5 p55p56 p6p19 p2p5 p57p58 p49p55b p49p55 a p26p27
Panjang (m) 467 484 500 617 750 834 917 1034 1050 1067 1084 1084 1100 1167 1500 1650 1750 2167 2417 2457 2617
2. Pilih sisi yang mempunyai bobot dari yang kecil ke yang besar, yang tidak mempunyai sikel. Tambahkan sisi tersebut di dalam jaringan pipa primer air minum Kecamatan Nganjuk. Proses pemilihan sisi diulangi sampai semua simpul terhubung. •Iterasi 1: dipilih sisi p12p13 dengan panjang pipa 34 meter, kemudian ditambahkan ke dalam pohon merentang minimum jaringan pipa primer. •Iterasi 2: dipilih sisi p36p39 dengan panjang pipa 34 meter, kemudian ditambahkan ke dalam pohon merentang minimum jaringan pipa primer •dst Berdasarkan iterasi, panjang pipa primer yang membentuk sebuah pohon merentang minimum adalah 30.281 meter, sedangkan panjang pipa primer adalah 35.996 meter, sehingga mempunyai selisih sepanjang pipa primer sebesar 5.715 meter.
Pembahasan
Pohon merentang minimum jaringan pipa primer air minum Kecamatan Nganjuk Kabupaten Nganjuk yang diselesaikan dengan Algoritma Kruskal.
Pembahasan
PENYELESAIAN JARINGAN PIPA AIR MINUM DAN DATABASE DENGAN MATLAB Halaman Beranda Halaman Implementasi Kruskal Halaman Data Pipa Primer
Pembahasan
PENYELESAIAN JARINGAN PIPA AIR MINUM DAN DATABASE DENGAN MATLAB Halaman Beranda
Pembahasan
Halaman Implementasi Kruskal
Pembahasan
Gambar Jaringan Pipa Primer Air Minum Kecamatan Nganjuk Kabupaten Nganjuk oleh Matlab
Pembahasan
Gambar Pohon Merentang Minimum Jaringan Pipa Primer Air Minum Kecamatan Nganjuk Kabupaten Nganjuk oleh Matlab
Pembahasan
Halaman Data Pipa Primer
Pembahasan
SIMPULAN Penentuan pohon merentang minimum dalam jaringan pipa primer air minum ini menggunakan Algoritma Kruskal dalam pencaran pohon merentang minimum. Total panjang jaringan pipa primer yang digunakan saat ini adalah sepanjang 35.996 meter dan total pohon merentang minimum jaringan pipa primer adalah sepanjang 30.281 meter.
Simpulan
SARAN Objek yng digunakan pada Tugas Akhir ini adalah Kecamatan Nganjuk Kabupaten Nganjuk, sehingga dapat memungkinkan untuk menggunakan objek yang lebih luas Algoritma yang digunakan pada Tugas Akhir ini adalah Algoritma Kruskal, sehingga dapat memungkinkan menggunakan Algoritma yang lainnya dalam menentukan pohon merentang minimum
Simpulan
DAFTAR PUSTAKA 1. Oktaviani, Dian N. (2007). “Pengoptimalan Jaringan Air Bersih Di Kecamatan Jatibarang Kabupaten Brebes Menggunakan Algoritma Prim Dengan Program Maple”. Semarang: Universitas Negeri Semarang. 2. Effendi, Restiyan. (2009). “Evaluasi Dan Perencanaan Penyempurnaan Jaringan Distribusi Air Minum Di Kecamatan Nganjuk Kabupaten Nganjuk”. Surabaya: Institut Teknologi Sepuluh Nopember Surabaya. 3. Khoiroh, Mufidatul. (2010). “Keefektifan Penggunaan Algoritma Boruvka, Algoritma Prim, Algoritma Kruskal, Dan Algoritma Sollin Dalam Menentukan Pohon Merentang Minimum”. Malang: Universitas Islam Negeri Maulana Malik Ibrahim Malang. 4. Sugeng. (2010). http://www.harianbhirawa.co.id/utama/20497-kerugianpdam-karena-jaringan-pipa-usang-dan-tarif-murah. Diakses pada tanggal 3 September 2012 pukul 09:50.
5. Sugeng. (2010). http://www.harianbhirawa.co.id/utama/20497-kerugianpdam-karena-jaringan-pipa-usang-dan-tarif-murah. Diakses pada tanggal 3 September 2012 pukul 09:50. 6. Hartsfield, Nora. Ringel, Gerhard. (1990). “Pearls in Graph Theory: A Comprehensive Introduction”. United State of America: Academic Press. 7. Siswanto. (2007). “Operations Research Jilid 1”. Jakarta: Erlangga. 8. Wiria N, Deny. (2011). http://www.teknikelektroteknologiinformasi.blogspot.com/2011/12/algoritma-kruskal.html. Diakses pada tanggal 29 Oktober 2012 pukul 13:16. 9. Hiller, Frederick S. Lieberman, Gerald J. (1994). “Pengantar Riset Operasi Edisi kelima Jilid 1”. Jakarta: Erlangga. 10. Adiwijaya. “Matematika Diskrit”. Bandung: Sekolah Tinggi Teknologi Bandung
