Algoritma Ford-Fulkerson untuk Memaksimumkan Flow dalam Pendistribusian Barang

Fahrun Nisa, Wahyu Henky Irawan

Abstract


Algoritma Ford Fulkerson digunakan untuk mencari flow maksimum pada jaringan yang mempunyai satu titik sumber dan satu titik tujuan. Dengan mendefinisikan jalur pendistribusian barang sebagai jaringan, maka jaringan tersebut memiliki beberapa titik sumber dan beberapa titik tujuan. Untuk menyelesaikan permasalahan flow maksimum pada jaringan ini maka digunakan modifikasi Algoritma Ford-Fulkerson. Pada artikel ini akan ditunjukkan langkah-langkah mencari flow maksimum serta hasil yang diperoleh dengan menggunakan modifikasi Algoritma Ford-Fulkerson pada data simulasi tentang pendistribusian barang dengan lima titik sumber dan lima titik tujuan. Hasil dari penelitian ini merupakan bentuk modifikasi Algoritma Ford-Fulkerson, yaitu membentuk jaringan baru dengan menambahkan satu titik sumber utama dan satu titik tujuan utama pada jaringan baru, membentuk kapasitas di busur dari titik sumber utama ke beberapa titik sumber serta membentuk kapasitas di busur dari beberapa titik tujuan ke titik tujuan utama dengan nilai kapasitas maksimum dan memberi nilai flow awal sebesar nol. Selanjutnya memaksimumkan flow dari titik sumber utama ke titik tujuan utama menggunakan Algoritma Ford-Fulkerson, yaitu dengan melakukan pelabelan titik, menggunakan prosedur balik, dan mencari lintasan peningkatan sampai semua titik yang terlabel telah teramati dan titik tujuan utama tidak terlabel sehingga iterasi dihentikan. Berdasarkan hasil perhitungan didapatkan flow maksimum pada jaringan yang tidak dipartisi, pada jaringan yang dipartisi serta dengan membuat program di Matlab R2010a dengan nilai 45

Keywords


Algoritma Ford-Fulkerson; flow maksimum; jaringan; jaringan bipartisi

Full Text:

PDF

References


T. Farizal, "Pencarian Flow Maksimum dengan Algoritma Ford-Fulkerson," Universitas Negeri Semarang, Semarang, 2013.

G. Charland and L. Lesniak, Graf and Digraf, London: Chapman & Hall/CRC, 1996.

I. Budayasa, Teori Graph dan Aplikasinya, Surabaya: Unesa University Press, 2007.

R. K. Ahuja, J. B. Orlin, C. Stein and R. E. Tarjan, "Improved Algorithms for Bipartite Network Flow," SIAMJ COMPUT, pp. 906-933, 1994.




DOI: http://dx.doi.org/10.18860/ca.v3i4.2968

Refbacks

  • There are currently no refbacks.




Editorial Office
Mathematics Department,
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Jalan Gajayana 50 Malang, Jawa Timur, Indonesia 65144
Phone (+62) 81336397956, Faximile (+62) 341 558933
e-mail: cauchy@uin-malang.ac.id
 

Creative Commons License
Cauchy (ISSN: 2086-0382 / E-ISSN: 2477-3344) by http://ejournal.uin-malang.ac.id/index.php/Math is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.