Algoritma Ford-Fulkerson untuk Memaksimumkan Flow dalam Pendistribusian Barang

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