Jurnal Dinamika, April 2016, halaman 50-61 ISSN 2087 - 7889
Vol. 07. No. 1
PENERAPAN ALGORITMA PRIM UNTUK MEMBANGUN POHON MERENTANG MINIMUM (MINIMUM SPANNING TREE) DALAM PENGOPTIMALAN JARINGAN TRANSMISI NASIONAL PROVINSI SULAWESI SELATAN Marwan Sam, Yuliani Program Studi Matematika Fakultas Sains Universitas Cokroaminoto Palopo, Sulawesi Selatan Email:
[email protected]
ABSTRAK Teori Graf merupakan salah satu kajian dalam matematika diskrit yang digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek diskrit tersebut. Teori Graf banyak diterapkan dalam berbagai bidang keilmuan diantaranya : optimalisasi jaringan (baik itu jaringan transmisi nasional, jaringan listrik PLN, saluran air PDAM maupun jaringan komunikasi), ekonomi, psikologi genetika dan riset operasi. Tulisan ini membahas tentang pohon merentang minimum (minimum spanning tree), khususnya algoritma prim, dan penerapannya dalam jaringan transmisi khususnya jaringan transmisi nasional provinsi Sulawesi Selatan, sehingga jaringan transmisi tersebut dapat optimal (minimum). Kata kunci: graf, pohon, pohon merentang (spanning tree), pohon merentang minimum (minimum spanning tree), algoritma prim, jaringan transmisi nasional.
PENDAHULUAN
Representasi visual dari graf adalah dengan menyatakan objek
Teori graf merupakan pokok bahasan yang sudah tua namun memiliki banyak penerapan hingga saat ini. Dalam kehidupan seharihari, banyak persoalan yang dapat disimpulkan sebagai persoalan yang berhubungan dengan himpunan, yang mana logika dari persoalan tersebut seringkali dapat digambarkan dengan sebuah graf (Aidil, 2012).
sebagai noktah, bulatan atau titik, sedangkan hubungan antar objek dinyatakan dengan garis (Munir, 2012). Di Indonesia sendiri, jaringan listrik bisa dikatakan belum optimal. Sebagai contoh kasus: berdasarkan data yang diperoleh dari Departemen Energi dan Sumber Daya Mineral Republik Indonesia yang tertuang dalam Keputusan Menteri Energi dan Sumber Daya Mineral Nomor : 55
50
Marwan Sam, Yuliani (2016)
K/30/MEM/2003 tentang Jaringan
Dari definisi di atas, dapat
Transmisi Nasional (JTN) bahwa
diketahui bahwa V tidak boleh
panjang
transmisi
kosong (harus ada minimal satu buah
nasional provinsi Sulawesi Selatan
titik atau simpul) sedangkan E boleh
untuk jenis transmisi 70 kV adalah
saja kosong (tidak ada), dalam hal ini
74 kms
jika
total
jaringan
sedangkan
untuk
jenis
E
kosong
dinamakan
graf
transmisi 150 kV adalah 1093 kms,
kosong (null graf) sedangkan graf
sehingga
Jaringan
yang hanya mempunyai satu simpul
Transmisi Nasional untuk Provini
dan tidak memiliki sisi dinamakan
Sulawesi Selatan adalah 1167 kms
graf trivial. (Munir, 2012).
total
panjang
(www.djlpe.go.id).
Berdasarkan orientasi arah pada
Ada dua jenis algoritma yang dapat
digunakan
untuk
menyelesaikan masalah seperti ini,
sisi,
maka
secara
umum
graf
dibedakan atas 2 jenis (Aidil, 2012): 1.
Graf tak berarah (undirected
yaitu: Algoritma Prim dan Algoritma
graph)
Kruskal (Munir, 2012).
Graf tak berarah adalah graf
Tujuan penelitian ini adalah
yang sisi-sisinya tidak mempunyai
menerapkan algoritma prim untuk
orientasi arah, sehingga (vi,vj) =
mengoptimumkan jaringan listrik.
(vj,vi).
TINJAUAN PUSTAKA Graf Secara didefinisikan
matematis, sebagai
graf pasangan
himpunan (V, E), ditulis dengan notasi G(V,E), dalam hal ini V
Gambar 1. Graf tak berarah.
adalah himpunan tidak kosong dari
Pada Gambar 1, himpunan V =
simpul-simpul (vertices atau node)
{1, 2, 3, 4} adalah himpunan titik,
sedangkan E adalah himpunan sisi-
sedangkan himpunan E = {e1, e2, e3,
sisi
e4, e5, e6, e7} adalah himpunan sisi.
(edges
atau
arcs)
yang
menghubungkan antara simpul yang
2.
Graf berarah (directed graph)
satu dengan simpul yang lain (Munir, 2012).
51
Simulasi Perbandingan Metode Peramalan Model Generalized Seasonal Autoregresive Integrate Moving Average (GSARIMA) dengan Seasonal Autoregressive Integrated Moving Average (SARIMA) Graf berarah adalah graf yang
tersebut, tapi tidak bersisian dengan
setiap sisinya mempunyai orientasi
simpul 4 maupun 3.
arah, sehingga (u,v)
3.
(v,u).
Simpul
terpencil
(isolated
vertex) Jika memiliki
suatu sisi
simpul yang
tidak
bersisian
dengannya maka disebut simpul terpencil. Perhatikan gambar berikut! Gambar 2. Graf berarah Terminologi Dasar Graf Berikut
ini
adalah
beberapa
terminologi atau istilah-istilah yang sering digunakan dalam graf.
Gambar 3. Salah satu contoh graf
1.
dengan simpul terpencil
Bertetangga (adjacent) Dua
buah
bertetangga
simpul
jika
dikatakan
Pada Gambar 3 di atas simpul T
simpul
dan U merupakan simpul terpencil
kedua
tersebut terhubung oleh suatu sisi. Pada Gambar 1, simpul 1 dan 2 dikatakan
bertetangga
karena
karena
tidak
bersisian
dengan
simpul-simpul lainnya. 4.
Derajat (degree)
dihubungkan oleh sisi e1, sedangakan
Derajat
simpul 1 dan 4 tidak bertetangga
menyatakan
karena
bersisian dengan simpul tersebut.
tidak
ada
sisi
yang
menghubungkan keduanya. 2.
suatu jumlah
simpul sisi
yang
Pada Gambar 1, derajat untuk
Bersisian (incidency)
tiap simpul yaitu: d(1) = 3, d(2) = 3,
Suatu sisi e dikatakan bersisian
d(3) = 5, d(4) = 3.
dengan simpul v1 dan v2 jika e menghubungkan
kedua
simpul
tersebut.
5.
Lintasan (path) Lintasan yang panjangnya n dari
simpul awal v0 ke simpul tujuan vn
Pada Gambar 1, e1 bersisian
dalam sebuah graf ialah barisan
dengan simpul 1 dan 2 karena
berselang-seling simpul-simpul dan
menghubungkan
kedua
simpul
52
Marwan Sam, Yuliani (2016)
sisi-sisi yang berbentuk v0, v1, v2, v3,
kota, biaya perjalanan dua buah kota,
..., vn.
waktu tempuh pesan dari sebuah
Pada Gambar 1, salah satu
simpul
komunikasi
ke
simpul
contoh lintasan adalah 1, 2, 3, 1, 3, 4.
komunikasi yang lain pada jaringan
6.
komputer atau jaringan komunikasi,
Siklus
(cycle)
atau
sirkuit
(circuit)
ongkos produksi, dan sebagainya.
Suatu lintasan yang berawal dan
8.
berakhir
di
simpul
yang
sama
dinamakan siklus atau sirkuit.
Dua
buah
simpul
dikatakan
terhubung jika terdapat lintasan dari
Pada Gambar 1, terdapat siklus,
kedua simpul tersebut.
yaitu 2, 3, 4, 2. 7.
Keterhubungan
Jika setiap pasang simpul pada
Graf berbobot (weighted graph)
sebuah graf terdapat lintasan, maka
Graf berbobot adalah graf yang
graf
tersebut
dinamakan
Graf
setiap sisinya diberi sebuah harga
Terhubung (connected graph), jika
(bobot atau nilai).
tidak maka graf tesebut dinamakan
Perhatikan gambar berikut!
Graf Tak Terhubung (disconnected graph).
Gambar 5. Graf roda merupakan salah satu graf terhubung. Gambar 4. Graf berbobot Bobot pada setiap graf berbedabeda tergantung pada masalah yang dimodelkan
graf.
Bobot
dapat
menyatakan jarak antara dua buah
9.
Subgraf Misalkan G = (V,E) adalah
sebuah graf. G1 = (V1,E1) dinamakan subgraf dari G jika
dan
.
53
Simulasi Perbandingan Metode Peramalan Model Generalized Seasonal Autoregresive Integrate Moving Average (GSARIMA) dengan Seasonal Autoregressive Integrated Moving Average (SARIMA)
(a)
(b)
Gambar 6. Graf (b) merupakan subgraf dari graf (a) Pohon (Tree) Pohon merupakan salah satu
Gambar 7 merupakan salah satu
bentuk khusus dari suatu graf. Munir
contoh graf yang berbentuk pohon
(2012) mendifinisikan pohon sebagai
sedangkan Gambar 8 bukan karena
graf
mengandung sirkuit. Sirkuit yang
tak
berarah
yang
tidak
mengandung sirkuit atau siklus.
terbentuk pada Gambar 8 adalah a, d, f, a. Pohon Merentang (Spanning Tree) Misalkan G = (V,E) adalah graf tak berarah terhubung yang bukan pohon, yang berarti di G terdapat satu atau lebih sirkuit. G dapat diubah menjadi pohon T = (V1,E1)
Gambar 7. Graf yang berbentuk
dengan cara memutuskan sirkuit-
pohon.
sirkuit yang ada. Caranya, mula-mula dipilih sebuah sirkuit, lalu hapus satu buah sisi dari sirkuit ini. G akan tetap terhubung dan jumlah sirkuitnya berkurang. Jika sirkuitnya lebih dari satu, maka proses ini dilakukan berulang-ulang hingga semua sirkuit di G hilang, maka G menjadi sebuah pohon T yang dinamakan pohon
Gambar
8.
Graf
berbentuk pohon.
yang
bukan
merentang (spanning tree). Disebut pohon
merentang
karena
semua
54
Marwan Sam, Yuliani (2016)
simpul pada pohon T = semua simpul
pada G. Dengan kata lain, V1 = V dan
pada G, dan sisi pada T
E1
sisi-sisi
E
(a)
(Munir,
2012).
(b)
Gambar 9. Graf (b) merupakan 2 buah pohon merentang dari graf (a) Pohon
Merentang
Minimum
cara yaitu Algoritma Prim dan Algoritma Kruskal (Munir, 2012).
(Minimum Spanning Tree) Pohon rentang yang memiliki
Algoritma
Prim
memiliki
bobot minimum dinamakan pohon
langkah-langkah sebagai berikut :
merentang minimum (Aidil, 2012).
1.
Pilih sisi dari graf G yang
Dalam kehidupan nyata, salah satu
berbobot minimum, masukkan
contoh
ke dalam T.
aplikasi
merentang
dari
minimum
pohon adalah
2.
Pilih
sisi
dalam
G
yang
menentukan panjang kabel terpendek
mempunyai bobot minimum dan
yang
untuk
bersisian dengan simpul di T,
menghubungkan tiap rumah pada
dengan syarat sisi tersebut tidak
jaringan listrik sebuah desa/kota atau
membentuk
perumahan,
dimana
rumah
masukkan ke dalam T.
dinyatakan
sebagai
simpul
sedangkan
kabel
yang
n – 2 kali. Atau dengan kata lain
rumah
hingga semua simpul yang ada
dapat
menghubungkan
digunakan
antar
dinyatakan sebagai sisi. Algoritma Prim Dalam menentukan suatu pohon
3.
siklus
di
T,
Ulangi langkah ke dua sebanyak
di G masuk ke dalam T. Jaringan Transmisi Transmisi
adalah
proses
merentang minimum dari suatu graf
penyaluran energy listrik dari satu
terhubung berbobot, terdapat dua
tempat ke tempat lainnya pada
55
Simulasi Perbandingan Metode Peramalan Model Generalized Seasonal Autoregresive Integrate Moving Average (GSARIMA) dengan Seasonal Autoregressive Integrated Moving Average (SARIMA) tingkat tegangan yang lebih tinggi
3.
dari tegangan di generator ke gardu
Saluran Udara Tegangan Rendah (SUTR) :
70 kV.
induk atau pada tingkat tgangan yang telah dinaikkan atau ditinggikan di
HASIL DAN PEMBAHASAN
atas generator (Ayu Astari, dkk :
Jaringan
2015)
(JTN)
Transmisi
Nasional
dari
Pada bagian sebelumnya telah
klasifikasi tegangannya terbagi atas
dijelaskan bahwa jenis transmisi ada
(Ayu Astari, dkk : 2015, Yelfianhar :
tiga.
2011) :
Selatan, hanya terdapat dua jenis
1.
Saluran Udara Tegangan Ekstra
transmisi, yaitu SUTR (70 kV) dan
Tinggi (SUTET) : 200 – 500 kV.
SUTT (150 kV) yang tersebar di
Saluran Udara Tegangan Tinggi
berbagai daerah di Provinsi Sulawesi
(SUTT) : 70 – 150 kV.
Selatan.
2.
ditinjau
Transmisi
Untuk
Provinsi
Sulawesi
Tabel 1. Lokasi Jaringan Transmisi Nasional Provinsi Sulawesi Selatan Jenis Transmisi 70 kV.
Transmisi 150 kV.
Lokasi Asal
Lokasi Tujuan
Panjang (km)
Tello Lama
Bontoala
4
Tello
Borongloe
12
Tello
Daya
5
Daya
Mandai
7
Mandai
Tonasa 1
23
Tonasa 1
Tonasa/Pangkep
15
Tonasa
Tonasa 3 / 4
4
Tello
Panakukang
4
PLTA Bakaru
Tuppu
68
Tuppu
Pinrang
34
Pinrang
Pare-pare
27
Pare-pare
Barru
44
Barru
Pangkep
44
Pangkep
Tello
44
Tello
Tello lama
6
Tello
Sungguminasa
39
56
Marwan Sam, Yuliani (2016)
Sungguminasa
Takalar
35
Takalar
Jeneponto
52
Jeneponto
Bulukumba
63
Bulukumba
Bone
178
Bone
Soppeng
44
Soppeng
Sidrap
54
Sidrap
Pare-pare
19
Soppeng
Sengkang
35
Sungguminasa
Tanjung bunga
12
Tuppu
Polmas
38
Polmas
Majene
35
Sidrap
Makale
132
Makale
Palopo
90
Total
1168
Sumber : Keputusan Menteri Energi dan Sumber Daya Mineral Nomor : 55 K/30/MEM/2003
Tabel
1
di
atas
dapat
representasikan
ke
dalam
peta
Jaringan Transmisi Nasional berikut.
Sumber : Keputusan Menteri Energi dan Sumber Daya Mineral Nomor : 55 K/30/MEM/2003
Gambar 10. Jaringan Transmisi Nasional (JTN) Provinsi Sulawesi Selatan.
57
Simulasi Perbandingan Metode Peramalan Model Generalized Seasonal Autoregresive Integrate Moving Average (GSARIMA) dengan Seasonal Autoregressive Integrated Moving Average (SARIMA) Berdasarkan tabel 1 dan Gambar
sisi-sisi melambangkan panjang jabel
10 di atas akan dibuat graf dengan
yang menghubungkan antara lokasi
simpul-simpul sebagai lokasi dan
yang satu dengan lokasi yang lain.
Gambar 11. Graf Jaringan Transmisi Nasional (JTN) Provinsi Sulawesi Selatan. Adapun daftar simpul dari graf di atas adalah sebagai berikut : Tabel 2. Daftar simpul dari graf Jaringan Transmisi Nasional Provinsi Sulawesi Selatan Simpul Kota/Lokasi Simpul Kota/Lokasi 1 Tello Lama 16 Tanjung Bunga 2
Tello
17
Sungguminasa
3
Daya
18
Takalar
4
Mandai
19
Jeneponto
5
Tonasa 1
20
Bulukumba
6
Tonasa
21
Bone
7
Bontoala
22
Soppeng
58
Marwan Sam, Yuliani (2016)
8
Borongloe
23
Polmas
9
Tonasa 3 / 4
24
Sengkang
10
Panakukang
25
Makale
11
PLTA Bakaru
26
Majenne
12
Tuppu
27
Palopo
13
Pinrang
28
Sidrap
14
Pare-pare
15
Barru
Dari Gambar 11 dan Tabel 2, stelah dilakukan algoritma Prim diperoleh hasil sebagai berikut.
Gambar 12. Graf hasil Algoritma Prim JTN Provinsi Sulsel Berdasarkan
hasil
yang
simpul 2 ke 6 dan simpul 20 ke 21,
diperoleh antara Gambar 11 dan
sehingga dapat dikatakan bahwa
Gambar 12 terdapat perbedaan yang
dengan
sangat jelas. Pada Gambar 12, tidak
Prim ini penghematan kabel dapat
ada sisi yang menghubungkan antara
dilakukan sepanjang 222 km.
menggunakan
Algoritma
59
Simulasi Perbandingan Metode Peramalan Model Generalized Seasonal Autoregresive Integrate Moving Average (GSARIMA) dengan Seasonal Autoregressive Integrated Moving Average (SARIMA) Menteri Energi dan Sumber
KESIMPULAN Berdasarkan
hasil
penelitian
Daya Mineral Nomor : 55
yang dilakukan dapat disimpulkan
K/30/MEM/2003. (Online).
bahwa
(https://www.minerba.esdm.
dengan
penggunaan
Algoritma Prim ini penghematan
go.id/library/sijh/kepmen-
kabel dapat dilakukan sepanjang 222
55-2003.pdf,
km.
April 2016).
28
Ayu, Astari, dkk. 2015. Jaringan
DAFTAR PUSTAKA Adiwijaya.
Diakses
Matematika
Diskrit.
Transmisi Listrik. (Online),
Bandung. Sekolah Tinggi
(http://www.slideshare.net/
Teknologi Telkom.
MakmurSaini1/jaringantransmisisi-listrik/,Diakses
Alfiyah,
Siti.
2011.
Optimasi
29 April 2016).
Jaringan Listrik Kecamatan Mantrijeron
Yogyakarta
Habibi,
Mohammad.
dengan Algoritma Kruskal
Jaringan
dan
Perumahan Jember Permai
Prim.
Yogyakarta.
Universitas
Islam
Negeri
Sunan Kalijaga.
Listrik
Analisis
dengan Algoritma
di
Menggunakan Prim.
(http://digilib.unej.ac.id/gdl.p Alius, Heri Septiadi, dkk. 2014.
hp?mod=browse&op=read&
Perancangan
Sistem
id=gdlhub-gdl-
Transmisi
Listrik
mohammadha-3874, Diakses
Daya
Bertegangan 150 kV dan
28 April 2016)
Berkapasitas 35 mVA di Kabupaten Kalimantan
Bulungan
Munir, Rinaldi. 2012. Matematika
Timur.
Diskrit. Bandung. Penerbit
Bandung. ITB.
Informatika.
Anonim. . 2003. Jaringan Transmisi Nasional (JTN) Keputusan
60
Marwan Sam, Yuliani (2016)
Syahfitri, Rayi. 2009. Penerapan Algoritma
Prim
pada
Wikipedia.
Teori
Graf.
(http://id.wikipedia.org/wiki
Jaringan Listrik Perumahan
/Teori_graf,
PT. Inalum (Studi Kasus).
April 2016)
Diakses
28
Medan. USU. Yelfianhar, Ichwan. 2011. Sistem Syaputra,
Aidil.
2012.
Aplikasi
Penyaluran.
(Online),
Pohon Merentang (Spanning
(https://iwan78.files.wordpr
Tree) dalam Pengoptimalan
ess.com/2011/04/sistem-
Jaringan Listrik. Bandung.
penyaluran.pdf, Diakses 29
ITB.
April 2016).
61
