JURNAL DINAMIKA, APRIL 2016, HALAMAN 50-61 ISSN 2087

Download 28 Apr 2016 ... PENERAPAN ALGORITMA PRIM UNTUK MEMBANGUN POHON ... Teori Graf merupakan salah satu kajian dalam matematika diskrit yang ...

0 downloads 406 Views 1MB Size
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