Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
2 Oktober 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 DOI: https://doi.
org/10.
55606/jurrimipa.
Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal Yosua Mangapul Situmorang Universitas Negeri Medan Abil Mansyur Universitas Negeri Medan Korespondensi penulis: jojositumorang0@gmail.
Abstract: Kruskal's algorithm in searching for minimum spanning trees can be applied to pipelines installed at the location of PDAM Tirtanadi Tuasan where problem identification starts with the water discharge reaching the consumer is small but the discharge flowing from the reservoir is sufficient, so this research is used as a solution to this problem and also as an optimization of the clean water distribution network in the Tirtanadi Regional Drinking Water Company (PDAM) of the Tuasan Branch with the intention of cutting the direction of the pipe flow to overcome this problem.
The data obtained from PDAM Tirtanadi Tuasan Branch is in the form of a floor plan and formed into a weighted graph.
After the data is obtained, then it is calculated manually that the length of the installed water pipe is 32,645 m with 86 vertices and 100 edges, then the pipe length is represented as a set of paths and the pipe connection ends are represented as nodes.
The pipe length obtained using Kruskal's algorithm and inspection of iterations using the QM for windows software is 22,095 m, with 86 vertices and 85 edges.
So, using the Kruskal Algorithm and the help of the QM for windows software, the difference in pipe length obtained is 10,610 m.
Keywords: Forecasting.
GRDP.
Matlab.
Regression.
Abstrak: Algoritma Kruskal dalam pencarian pohon merentang minimum dapat di aplikasikan pada jaringan pipa yang terpasang di lokasi PDAM Tirtanadi Tuasan dimana identifikasi permasalahan berawal dari debit air yang sampai kepada konsumen kecil namun debit yang dialirkan dari reservoir cukup, sehingga adanya penelitian ini guna sebagai solusi untuk permasalahan tersebut dan juga sebagai pengoptimalan jaringan distribusi air bersih di Perusahaan Daerah Air Minum (PDAM) Tirtanadi Cabang Tuasan dengan bermaksud memotong arah aliran pipa untuk mengatasi permasalahan tersebut.
Data yang diperoleh dari PDAM Tirtanadi Cabang Tuasan berupa peta denah dan dibentuk menjadi graf berbobot.
Setelah data diperoleh, kemudian dihitung secara manual panjang pipa air yang terpasang adalah 32.
645 m dengan 86 verteks dan 100 edges, kemudian panjang pipa dipresentasikan sebagai himpunan jalur-jalur dan ujung pipa sambungan dipresentasikan sebagai simpul-simpul.
Panjang pipa yang diperoleh dengan menggunakan algoritma Kruskal serta pemeriksaan iterasi menggunakan bantuan software QM for windows adalah 22.
095 m yaitu dengan 86 verteks dan 85 edges.
Jadi, dengan menggunakan Algoritma Kruskal serta bantuan software QM for windows selisih panjang pipa yang diperoleh sebesar 10.
610 m.
Kata kunci: Jaringan.
Algoritma Kruskal.
QM for windows.
LATAR BELAKANG
Air merupakan salah satu unsur paling utama dalam menunjang kehidupan manusia dan makhluk hidup lainnya, dimana peranannya tidak dapat digantikan oleh unsur lainnya.
Seiring dengan bertambahnya jumlah penduduk maka kebutuhan akan air bersih juga semakin bertambah, oleh sebab itu pemerintah mengelola sebuah perusahaan milik daerah yaitu Perusahaan Daerah Air Minum (PDAM) yang bertugas untuk memberikan pelayanan kepada masyarakat dalam memenuhi kebutuhan air bersih untuk keperluan rumah tangga maupun Berbagai aktivitas manusia senantiasa membutuhkan air dalam jumlah besar seperti yang digunakan untuk keperluan sehari-hari.
Dari hasil observasi penulis dengan masyarakat Received Mei 30, 2023.
Revised Juni 28, 2023.
Accepted Juli 31, 2023 * Yosua Mangapul Situmorang, jojositumorang0@gmail.
Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal sekitar, banyak masyarakat yang terkadang mengeluh dengan kualitas air yang didapatkan kurang memuaskan salah satunya di Perusahaan Daerah Air Minum (PDAM) Tuasan, dimana produksi air yang diterima masyarakat terkadang keruh atau ada rasa bau serta tidak lancar dan air yang didapatkan selalu dengan debit yang kecil, artinya penyaluran air dari PDAM Tuasan ini memiliki kualitas dan pelayanan yang belum memuaskan karena belum bisa mendistribusikan air yang sesuai dengan kebutuhan masyarakat sekitar pancing.
Seiring berjalannya waktu, tingkat pertumbuhan penduduk setiap tahunnya mengalami peningkatan begitu pula dengan peningkatan kebutuhan air bersih.
peningkatan kebutuhan ataupun permintaan akan air bersih tersebut mengakibatkan Perusahaan Daerah Air Minum (PDAM) juga harus meningkatkan pelayanannya terkhusus dalam pendistribusian air bersih terhadap pelanggan seperti pergantian pipa baru bilamana terjadi kerusakan, bahkan penambahan pipa baru juga harus dilakukan.
Masalahnya, apakah jaringan pipa yang di pasang oleh PDAM sudah optimal atau belum, dalam arti jaringan air yang terpasang efisien dan dapat mengalirkan air ke seluruh perumahan penduduk dengan menekan permasalahan yang ada pada studi kasus PDAM tirtanadi cabang Tuasan.
maka untuk itu perlu dilakukan penncarian solusi yang tepat guna mengatasi permasalahan tersebut.
KAJIAN TEORITIS
Teori graf adalah ilmu yang mempelajari tentang graf struktur matematika.
Aplikasi dari teori graf sangat luas dan dapat digunakan dalam berbagai disiplin ilmu maupun dalam kehidupan sehari-hari.
Dalam implementasinya teori ini sering dimanfaatkan di dalam bidang informatika .
enerapan graf pada jaringa.
, kimia .
emodelkan senyawa dalam bentuk gra.
dan kelistrikan .
aringan listri.
Pemanfaatan teori graf yang sangat umum digunakan pada pencarian Minimum Spanning Tree (MST).
Travelling Salesman Problem (TSP) dan Coloring graph (Monifani 2.
Graf dimanfaatkan untuk mempresentasikan objek-objek diskrit dan relasi antar objekobjek.
Graf G diartikan sebagai pasangan himpunan .
cO, y.
, ditulis dengan notasi ya = .
cO, y.
Dalam hal ini, ycO adalah himpunan tidak kosong dari simpul-simpul .
ertex atau nod.
digambarkan dalam titik- titik, dan E merupakan himpunan sisi-sisi .
digambarkan dalam garis-garis yang menghubungkan sepasang simpul (Munir 2.
Adapun penelitian yang relevan pada kasus Minimum Spanning Tree yaitu pernah dilakukan oleh (Devi Lastri 2.
, mengenai pengujian Aplikasi Algoritma Kruskal dalam Pembuatan Saluran Air PDAM di Wilayah KLU.
Dari data penelitian dapat disimpulkan bahwa penerapan algoritma kruskal dapat menjadi alternatif dalam upaya optimalisasi pembuatan JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 saluran air PDAM di wilayah Kabupaten Lombok Utara (KLU), karena dapat ditemukan rute terpendek lintasan pipa air dengan metode kruskal tersebut, sehingga diperoleh pembuatan saluran air dengan rute pipa air terpendek menjadi optimal dengan total panjang lintasan atau rute yakni 259,4 km.
Selanjutnya, pada penelitian yang relevan lainnya yang dilakukan oleh (Azizatul Mualimah 2.
mengenai pencarian pohon merentang minimum jaringan pipa PDAM Tirta Dharma Lamongan dengan menggunakan Algoritma Kruskal.
Dalam penelitian tersebut ditarik kesimpulan bahwa pencarian pohon merentang minimum dalam jalur distribusi pipa PDAM Tirta Dharma Lamongan menggunakan Algoritma Kruskal yaitu 27.
364,55 meter dari semua total panjang jaringan pipa PDAM Tirta Dharma Lamongan yaitu 41.
608,15 meter dan dengan demikian jaringan pipa PDAM Tirta Dharma Lamongan dikatakan sudah optimum karena dapat menghemat pipa sepanjang 14.
243,6 meter, dengan sisi yang terpilih sebanyak 81 dari 102 sisi.
Algoritma Kruskal merupakan salah satu algoritma dalam teori graf untuk menyelesaikan persoalan pohon merentang minimum.
Algoritma Kruskal ditemukan pada tahun 1956 oleh seorang ilmuwan matematika, statistika, komputer dan pisikometrika Joseph yaitu Bernard Kruskal,Jr yang berasal dari Amerika.
Dasar pembentukan Algoritma Kruskal berasar dari analogi growing forest.
Growing forest maksudnya adalah untuk membentuk pohon merentang minimum ycN dari graf ya adalah dengan cara mengambil satu-persatu sisi dari graf ya dan memasukannya dalam pohon yang telah terbentuk sebelumnya.
Seiring dengan berjalannya iterasi pada setiap sisi maka forest akan memiliki pohon yang semakin sedikit.
Oleh sebab itu analogi ini disebut growing forest.
Algoritma Kruskal akan terus menambahkan sisi-sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest, melainkan hanyalah sebuah pohon merentang minimum (Wattimena 2.
Adapun langkah-langkah menggunakan Algoritma Kruskal, antara lain:
Sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya.
T masih kosong Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T.
Masukkan e ke dalam T.
Ulangi langkah 3 sebanyak n-1 kali.
METODE PENELITIAN
Data yang digunakan dalam penelitian ini berupa data kuantitatif dimana, data yang diambil berupa data sekunder, yaitu gambar denah jaringan pipa PDAM di kantor Tirtanadi Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal Cabang Tuasan.
Data tersebut akan diminta dari Perusahaan Daerah Air Minum (PDAM) Tirtanadi Kota Medan Jl.
Tuasan.
SUMATERA UTARA dan untuk memperoleh jarak antar tiap titik diperoleh dengan bantuan Google Maps.
Langkah-langkah penelitian ini adalah sebagai berikut.
Melakukan studi literatur dengan megumpulkan bahan bacaan yang berkaitan dengan Mengambil data berupa peta denah di Perusahaan Daerah Air Minum (PDAM) Tirtanadi Kota Medan Jl.
Tuasan dengan cara mengukur jarak antar tiap titik jaringan pipa dengan menggunakan bantuan Google maps.
Membuat Model Graf.
Menganalisis data dengan Algoritma Kruskal.
Membuat Graf Pohon Merentang Minimum.
Penarikan Kesimpulan.
HASIL DAN PEMBAHASAN
Data yang digunakan dalam penelitian ini merupakan data bobot panjang jaringan pipa primer PDAM Tirtanadi yang sudah diurutkan bobot panjangnya dari yang terkecil ke terbesar dalam tabel berikut:
Tabel 1: Data Panjang Pipa Pendistribusian Air Bobot panjang pipa .
Jalur Sisi .
82 Oe v84 ) .
76 Oe v77 ) .
8 Oe v9 ) .
42 Oe v47 ) .
80 Oe v82 ) .
77 Oe v80 ) .
12 Oe v13 ) .
42 Oe v43 ) .
73 Oe v76 ) .
74 Oe v78 ) JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 .
43 Oe v48 ) .
47 Oe v50 ) .
50 Oe v54 ) .
23 Oe v27 ) .
24 Oe v28 ) .
53 Oe v56 ) .
70 Oe v73 ) .
35 Oe v37 ) .
20 Oe v24 ) .
61 Oe v64 ) .
15 Oe v19 ) .
19 Oe v23 ) .
32 Oe v35 ) .
27 Oe v30 ) .
28 Oe v31 ) .
5 Oe v7 ) .
6 Oe v9 ) .
11 Oe v15 ) .
16 Oe v20 ) .
32 Oe v33 ) .
1 Oe v3 ) .
2 Oe v4 ) .
56 Oe v60 ) .
57 Oe v61 ) Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal .
3 Oe v5 ) .
4 Oe v6 ) .
7 Oe v11 ) .
8 Oe v12 ) .
9 Oe v13 ) .
37 Oe v38 ) .
10 Oe v11 ) .
50 Oe v51 ) .
54 Oe v55 ) .
78 Oe v85 ) .
45 Oe v53 ) .
43 Oe v44 ) .
26 Oe v27 ) .
14 Oe v15 ) .
18 Oe v19 ) .
22 Oe v23 ) .
40 Oe v45 ) .
41 Oe v46 ) .
52 Oe v53 ) .
66 Oe v67 ) .
55 Oe v63 ) .
60 Oe v61 ) .
64 Oe v70 ) .
59 Oe v60 ) JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 .
56 Oe v57 ) .
37 Oe v42 ) .
39 Oe v40 ) .
62 Oe v67 ) .
63 Oe v68 ) .
30 Oe v40 ) .
62 Oe v63 ) .
67 Oe v68 ) .
57 Oe v58 ) .
64 Oe v65 ) .
68 Oe v86 ) .
15 Oe v16 ) .
30 Oe v31 ) .
40 Oe v41 ) .
45 Oe v46 ) .
77 Oe v78 ) .
34 Oe v35 ) .
69 Oe v70 ) .
70 Oe v71 ) .
73 Oe v74 ) .
84 Oe v85 ) .
85 Oe v86 ) .
49 Oe v50 ) .
72 Oe v73 ) Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal .
75 Oe v76 ) .
81 Oe v82 ) .
83 Oe v84 ) .
28 Oe v29 ) .
31 Oe v32 ) .
36 Oe v37 ) .
46 Oe v47 ) .
79 Oe v80 ) .
20 Oe v21 ) .
24 Oe v25 ) .
61 Oe v62 ) .
16 Oe v17 ) .
3 Oe v4 ) .
11 Oe v12 ) .
5 Oe v6 ) .
7 Oe v8 ) .
53 Oe v54 ) .
1 Oe v2 ) Total Berdasarkan data yang diperoleh tersebut, gambar jaringan pipa representasi graf pendistribusian air PDAM Tirtanadi Cabang Tuasan dapat disajikan dalam Gambar 1.
Dalam pencarian pohon rentang minimal digunakan algoritma Kruskal dan algoritma Sollin.
Langkah-langkah pada algoritma Kruskal adalah sebagai berikut.
Lakukan pengurutan terhadap setiap sisi di graf G mulai dari sisi dengan bobot terkecil.
Pilih sisi .
yang mempunyai bobot minimum yang tidak membentuk sirkuit di T.
Tambahkan .
ke dalam T.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang T berjumlah n - 1 .
adalah jumlah simpul pada gra.
Dari data yang diperoleh dari PDAM Tirtanadi Cabang Tuasan di iterasikan menggunakan algoritma Kruskal.
Hasil iterasi terakhir menggunakan algoritma Kruskal yce.
cN) = .
ce96 , yce89 , yce94 , yce50 , yce12 , yce90 , yce17 , yce51 , yce85 , yce87 , yce53 , yce57 , yce59 , yce30 , yce31 , yce62 , yce82 , yce42 yce27 , yce72 , yce22 , yce26 , yce39 , yce34 , yce35 , yce7 , yce9 , yce18 , yce23 , yce40 , yce1 , yce3 , yce66 , yce68 , yce4 , yce6 , yce10 , yce13 , yce44 , yce15 , yce60 , yce64 , yce92 , yce54 , yce52 , yce32 , yce19 , yce24 , yce28 , yce48 , yce49 , yce61 , yce79 , yce65 , yce71 , yce77 , yce70 , yce47 , yce45 , yce74 , yce76 , yce36 , yce75 , yce69 , yce78 , yce100 , yce20 , yce46 , yce91 , yce41 , yce81 , yce83 , yce99 , yce58 , yce84 , yce88 , yce95 , yce97 , yce33 , yce43 , yce93 , yce25 , yce29 , yce21 , yce5 } Dari sisi-sisi yang terpilih pada iterasi terakhir menggunakan algoritma Kruskal diperoleh bobot dari pohon rentang minimal yaitu 22095 m.
POM-QM adalah sebuah perangkat lunak untuk produksi/manajemen operasi, kuantitatif metode, manajemen ilmu pengetahuan, dan operasi penelitian.
QM adalah kepanjangan dari quantitatif method yang merupakan perangkat lunak dan menyertai buku-buku teks seputar manajemen operasi.
QM for windows merupakan gabungan dari program terdahulu DS dan POM for windoes, jadi jika dibandingkan dengan program POM for windows modul-modul yang tersedia pada QM for windows lebih banyak.
Namun ada modul-modul yang hanya tersedia pada program POM for windows, atau hanya tersedia di program DS for windows dan tidak tersedia di QM for windows.
Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal Gambar 4.
1 Graf G Representasi denah jaringan distribusi pipa JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 Gambar 4.
2 Graf T Pohon Merentang Minimum Pengoptimalan Jaringan Pipa Primer PDAM Tirtanadi Cabang Tuasan Dengan Menggunakan Algoritma Kruskal Hasil output juga akan memberikan hasil pohon merentang minimum dari titik awal ke semua pasangan titik.
Berikut ini disajikan input dan hasil output dari minimum spanning tree menggunakan QM for windows.
Gambar 4.
3 Tampilan hasil program QM for windows Dari hasil perhitungan menggunakan program software QM for Windows pada gambar 3 diperoleh hasil yaitu 22.
095 m.
maka dapat disimpulkan hasil perhitungan minimum spanning tree pada graf G menggunakan Algoritma Kruskal dan dengan software QM for Windows adalah sama.
Dengan demikian hasil pohon merentang minimum dapat dipresentasikan pada graf T.
Berdasarkan data yang diperoleh tersebut, gambar jaringan pipa pohon merentang minimum pendistribusian air PDAM Tirtanadi Cabang Tuasan dapat disajikan dalam Gambar2.
KESIMPULAN DAN SARAN
Kesimpulan Dari hasil penelitian dan pembahasan maka dapat diperoleh simpulan yaitu banyaknya sisi pohon merentang minimumnya adalah 85 sisi dengan jumlah iterasi sebanyak 85 iterasi.
Sisi .
ce2 , yce8 , yce11 , yce14 , yce16 , yce37 , yce38 , yce55 , yce56 , yce63 , yce67 , yce73 , yce80 , yce86 , yce98 ).
Dimana panjang pipa yang terpasang awalnya pada jaringan pipa PDAM Tirtanadi Tuasan adalah 32.
645 m dengan 86 verteks dan 100 edges.
Hasil yang diperoleh dengan menggunakan Algoritma Kruskal secara manual adalah 22.
095 m dengan 86 verteks dan 85 edges dengan sisi yang terpilih dimana 15 JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 221-237 sisi dihilangkan karena membentuk sirkuit yang menyebabkan banyaknya terjadi pemborosan rute aliran air sehingga mengakibatkan penyaluran air pada pipa PDAM Tirtanadi tidak efisien.
Dalam penelitian ini, penulis juga menggunakan software komputer yakni program Qm for Windows sebagai output secara langsung yang dapat memberikan hasil berupa pembandingnya, yang hasilnya mempunyai panjang sama yaitu 22.
095 m.
Saran Berikut ini adalah saran yang dapat digunakan untuk mengebangkan penelitian ini antara lain.
Pada penelitian-penelitian selanjutnya diharapkan dapat menggunakan serta mengembangkan program penerapan algoritma Kruskal untuk kasus-kasus umum dalam pencarian pohon rentang minimum.
UCAPAN TERIMA KASIH