Aplikasi Aliran Maksimum Pada Jaringan Listrik Menggunakan Metode Ford-Fulkerson

Intan Neila Rahma, Yurika Permanasari, Respitawulan Respitawulan

Abstract


Aliran maksimum bertujuan memaksimumkan jumlah aliran dari source ke sink yaitu jumlah yang dikeluarkan sesuai dengan jumlah yang diterima. Metode Ford-Fulkerson akan efektif digunakan dalam pemecahan masalah aliran maksimum seperti pada jaringan listrik yaitu jumlah aliran listrik di gardu induk sesuai dengan gardu yang dituju tanpa melanggar batas kapasitas maksimum tiap kabel (edge) yang menghubungkan masing-masing gardu (verteks).Metode Ford-Fulkerson memiliki tiga komponen penting residual networks (sisa jaringan) diperoleh dengan cara mengurangi kapasitas dengan aliran ,kemudian didapatkan minimum dari hasil pengurangan yang menjadi nilai yang akan dialirkan pada jalur yang telah dipilih, augmenting paths (penambah jalur) ditemukan jika masih terdpat sisa aliran hasil pengurangan jumlah total aliran dengan jumlah aliran pada setiap iterasi. Iterasi akan berhenti apabila tidak detemukan lagi augmenting pathCuts (pemotongan) akan terjadi apabila jumlah aliran sama dengan jumlah kapasitas. Dari contoh kasus jaringan listrik sebanyak 1850 Amper dari gardu induk S ke gardu T yang melewati 13 gardu, didistribusikan dengan 7 jalur  berbeda dengan jumlah aliran pada masing-masing jalur yaitu pada jalur 1 mengalirkan 30 Ampere, jalur 2 mengalirkan 30 Amper, jalur 3 mengalirkan 35 Amper, jalur 4 mengalirkan, 15 Amper jalur 5 mengalirkan 15 Amper, jalur 6 mengalirkan 30 Amper, jalur 7 mengalirkan 30 Amper. Aliran maksimum yang diperoleh memiliki 4 buah cuts  pada edgenya yang berarti bahwa kabel tersebut memiliki kapasitas yang sudah maksimum sehingga tidak dapat dialiri lagi.


The maximum flow is aimed to maximize the amount of flow from source to sink which the amount spent in accordance with the amount received. Ford-Fulkerson method will be effectively used in solving problems as in the electricity network, named the amount of electricity in the main substation in accordance with the intended substations without breaking the limits of the maximum capacity of each cable (edge) that connects each substation (vertex).Ford-Fulkerson method has three important components:  residual networksobtained by means of reducing capacity with the flow, then the minimum is obtained from the results of the reduction values which will be streamed on the path thathas been chosen. Augmenting paths (enhancer lane)found if there is still residual stream flow reduction in the totalnumberof resultswiththe amountof flow ateach iteration. Iteration stops when not finding  again augmenting path. Cutswill occur if the amount of flow is equal to the amount of capacity. The study case of the electricity network transports 1850 Ampere from substation S to substation T which passes through 13 substations, which is distributed in 7 different paths with the number of streams in each lane :  lane 1 flows 30 Ampere, lane 2 flows 30 Ampere, lane 3 flows 35 Ampere, line 4 flows 15 Ampere, line 5 flows 15 Ampere, line 6 flows 30 Ampere, line 7 flows 30 Ampere. The obtained maximum flow has 4 cuts at the edge which means that the cable has maximum capacity so that it cannot be flowed anymore.


Keywords


maximum flow, Ford-Fulkerson, residual networks, augmenting paths, cut, electricity networks

References


Arus listrik (Online) ( https://id.wikipedia.org/wiki/Arus_listrik, 9 Agustus 2016)

Cormen, Thomas H., dkk.1990.Introduction To Algorithm, second edition.Cambridge, Massachusetts:The MIT Press.

Hiller, Ferderick S., dan Lieberman Gerald J.,2008.Introduction To Opratian Reserch (eghth edition).Yogyakarta:ANDI.

Jaringan Distribusi dan Tenaga Listrik (Online) (http://repository.usu.ac.id/bitstream/123456789/31916/3/Chapter%20II.pdf, 9 Agustus 2016)

Johnsonbaugh, Richard.Matematika Diskrit (jilid 2).

Munir, Rinaldi.2005.Matematika Diskrit.Bandung:Informatika.

Wibson, Samuel.2008.Matematika Diskret.Yogyakarta:Graha Ilmu.




Flag Counter