## ALGORITMA FORD-FULKERSON UNTUK MEMAKSIMUMKAN FLOW DALAM PENDISTRIBUSIAN BARANG
1 Fahrun Nisa’, 2 Wahyu Henky Irawan
1 Jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang
2 jurusan Matematika, Universitas Islam Negeri Maulana Malik Ibrahim Malang
Email: fahrunnisa33@gmail.com

## ABSTRAK
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.
Kata kunci : Algoritma Ford-Fulkerson, flow maksimum, jaringan, jaringan bipartisi

## ABSTRACT
Ford-Fulkerson algorithms used to find the maximum flow in a network that has a single point source and a sink point . By defining the goods distribution channels as the network , then the network has several source point  and  several  sink  point.  To  solve  the  problems  of  the  maximum  flow  in  the  network  is  then  used  a modified  Ford-Fulkerson  algorithm.  This  article  can  be  shown  the  steps  looking  for  maximum  flow  and obtained results by using a modified Ford-Fulkerson algorithm on simulated data on the distribution of goods with a five source point and five sink.point. The results of this study is a modified form of the Ford-Fulkerson algorithm  ,  which  formed  a  new  network  by  adding  a  main  source  point  and  a  sink  point  on  a  major  new network  ,and  formed  capacity  in  an  arc  from  primary  sources  point  to  a  few  source  point  and  established capacity in the bow of some sink point to point the main goal with the value of the maximum capacity and provide initial flow value of zero . Furthermore, to maximize a flow of the main source point to a major sink point by using the Ford - Fulkerson algorithm , namely by labeling a point , using the reverse procedure and to  seek  increase  trajectory  till  all  the  labeled  points  have  been  observed  and  a  major  sink  point  has  not labeled  so  the  iteration  is  stopped  .  Based  on  the  results  of  the  calculation,  the  maximum  flow  on  a unpartitioned network on a partitioned network and by creating a program in Matlab R2010a with a value of 45.
Keywords : Ford-Fulkerson Algorithm, flow maximum, network, bipartite network

## PENDAHULUAN

## 1. Latar Belakang
Teori graf merupakan salah satu cabang dari ilmu matematika,  dimana  teori-teori  yang  digunakan
tergolong  aplikatif  dan  dapat  digunakan  untuk memecahkan masalah alam kehidupan sehari-hari. Salah  satu  pembahasan  dalam  teori  graf  adalah jaringan  ( network ).  Permasalahan  dalam  suatu jaringan  dapat  dicari  penyelesaiannya  yaitu  salah satunya  dengan  mencari flow maksimum.  Artikel
ini  membahas  tentang  pendistribusian  barang yang didefinisikan sebagai jaringan.
Dalam  konsep  pendistribusian  barang,  semakin banyak  barang  yang  dijual,  maka  kemungkinan barang yang laku terjual semakin banya, sehingga keuntungan  yang  didapatkan  oleh  perusahaan akan  semakin  banyak.  Berdasarkan  prinsip ekonomi “Dengan modal sekecil-kecilnya memperoleh keuntungan sebesar-besarnya”, maka permasalahan  matematika  yang  sesuai  dalam kasus  ini  yaitu  pencarian flow maksimum, sehingga flow maksimum  digunakan  dalam jaringan ini.
Sebuah  penelitian  yang  dilakukan  oleh  [1]  yaitu tentang  pencarian flow maksimum  pada  jaringan yang  memiliki  satu  titik  sumber  dan  satu  titik tujuan  menggunakan  Algoritma  Ford-Fulkerson. Menurut  Farizal,  algoritma  ini  selalu  memberikan hasil  yang  benar  dalam  mencari  lintasan peningkatan
( augmenting-path ) sehingga Algoritma
Ford-Fulkerson sesuai dengan permasalahan dalam artikel ini.
Dalam  penelitian  ini  akan  dicari flow maksimum pada  jaringan  pendistribusian  barang,  dimana jaringan  tersebut  memiliki  beberapa  titik  sumber dan  beberapa  titik  tujuan,  sehingga  akan dilakukan  modifikasi  Algoritma  Ford-Fulkerson. Harapan  dari  adanya  penelitian  ini  yaitu pendistribusian  barang  dapat  dilakukan  secara maksimum  sehingga  keuntungan  yang  diperoleh suatu perusahaan akan lebih banyak.

## 2. Metode Penelitian
Penelitian  ini  menggunakan  jenis  penelitian kualitatif dengan langkah-langkah penelitiannya:
a. Menyediakan  data  simulasi  yaitu  tentang pendistribusian barang.
b. Data  simulasi  yang  disediakan  memiliki  lima titik  sumber  dan  lima  titik  tujuan,  sehingga dilakukan modifikasi Algoritma
Ford- Fulkerson  agar  algoritma  ini  dapat  digunakan untuk mencari flow maksimum pada jaringan.
c. Menyusun Flow Maksimum pada jaringan.
d. Membuat Program di Matlab R2010a.

## KAJIAN TEORI

## 1. Graf
Suatu graf 𝐺 adalah suatu himpunan tidak kosong dan  berhingga  dari  objek-objek  yang  disebut sebagai vertex (titik)  dan  himpunan  (mungkin kosong)  pasangan  tak  berurutan  dari  titik-titik berbeda pada 𝐺 yang disebut edge (sisi).
Contoh:
Gambar 1. Graf 𝐺
Graf 𝐺 pada  Gambar  1  dapat  dinyatakan  dengan 𝐺 = (𝑉(𝐺), 𝐸(𝐺)) dengan 𝑉(𝐺) = {𝑎, 𝑏, 𝑐, 𝑑} dan 𝐸(𝐺) = {𝑎𝑏, 𝑎𝑑, 𝑎𝑐, 𝑏𝑐, 𝑐𝑑} [2] .
Sebuah sisi graf yang menghubungkan sebuah titik dengan  dirinya  sendiri  disebut  gelung  (loop).  Jika terdapat lebih dari satu sisi yang menghubungkan dua  titik  pada  suatu  graf,  maka  sisi-sisi  tersebut disebut  sisi  rangkap  atau  sisi  ganda.  Graf  yang tidak  mempunyai  sisi  rangkap  dan  tidak  memiliki gelung disebut graf sederhana [3] .

## 2. Digraf
Graf  berarah  atau  digraf 𝐷 adalah  struktur  yang terdiri  dari  himpunan  tak  kosong  dan  berhingga, yang  unsurnya  disebut  titik,  beserta  himpunan pasangan  berurutan  dari  dua  titik  berbeda  yang disebut busur.
Contoh:
Gambar 2. Digraf 𝐺
Pada Gambar 2 titik 𝑢 terhubung langsung ke 𝑣 . Di lain  pihak,  titik 𝑣 tidak  terhubung  langsung  ke 𝑢 [2].

## 3. Derajat Titik pada Digraf
Misalkan 𝑣 adalah  titik  pada  digraf 𝐷 .  Banyaknya titik yang terhubung langsung ke 𝑣 disebut derajat masuk  ( indegree )  dari 𝑣 ,  dan  dinotasikan  dengan 𝑖𝑑(𝑣) .  Banyaknya  titik  yang  terhubung  langsung dari 𝑣 disebut  derajat  keluar  ( outdegree )  dari 𝑣 , dan dinotasikan dengan 𝑜𝑑(𝑣) [2].
Contoh:
Gambar 3. Derajat Titik pada Graf 𝐻

## 4. Digraf Terhubung
Misalkan 𝐷 adalah  suatu  graf  berarah.  Graf berarah 𝐷 dikatakan  terhubung  kuat  jika  untuk setiap  dua  titik  di 𝐷 ada  lintasan  berarah  yang menghubungkan  dua  titik  tersebut.  Sedangkan graf 𝐷 dikatakan  terhubung  lemah  jika 𝐷 tidak terhubung  kuat  tetapi  graf  tak  berarah  yang bersesuaian dengan graf 𝐷 terhubung [2].
Contoh:
Gambar 4. Graf 𝐷 Terhubung Lemah; Graf 𝐻 Terhubung Kuat
5. Jaringan ( Network )
Jaringan 𝑁 = (𝑉(𝑁), Γ(𝑁)) merupakan  sebuah graf  berarah  sederhana  terhubung  lemah  yang setiap  unsurnya  dikaitkan  dengan  bilangan  real non  negatif.  Bilangan  real  non  negatif  yang dikaitkan pada busur (𝑉 𝑖 , 𝑉 𝑗 ) di jaringan 𝑁 disebut
kapasitas  busur  dan  dilambangkan 𝑐(𝑉 𝑖 , 𝑉 𝑗 ) . Sebuah  titik 𝑠 di  jaringan 𝑁 disebut  titik  sumber jika 𝑖𝑑(𝑠) = 0 dan  sebuah  titik 𝑡 di  jaringan 𝑁 disebut titik tujuan jika 𝑜𝑑(𝑡) = 0 , sedangkan titik yang  lain  di  jaringan 𝑁 disebut  titik-titik  antara [3].
Contoh:
Gambar 5. Jaringan 𝑁 dengan Titik Sumber 𝑣 𝑠 dan Titik Tujuan 𝑣 𝑡

## 6. Pemutus pada Jaringan
Misalkan 𝑁 sebuah jaringan dengan titik sumber 𝑠 dan  titik  tujuan 𝑡 .  Misalkan  himpunan 𝑋 adalah himpunan  bagian  tak  kosong  dari 𝑉(𝑁) dan 𝑋 1 = 𝑉(𝑁) − 𝑋 .  Jika 𝑠 ∈ 𝑋 ,  dan 𝑡 ∈ 𝑋 1 ,  maka  himpunan busur 𝐵(𝑋, 𝑋 1 ) disebut  sebuah  pemutus −(𝑠, 𝑡) dari jaringan 𝑁 , karena penghapusan semua busur 𝐵(𝑋, 𝑋 1 ) dari 𝑁 , memutus semua lintasan berarah dari titik 𝑠 ke titik 𝑡 pada jaringan 𝑁 [3].

## 7. Konsep Flow pada Jaringan
Sebuah flow di jaringan 𝑁 dari titik sumber 𝑠 dan titik  tujuan 𝑡 adalah  sebuah  fungsi  yang memetakan setiap busur (𝑖, 𝑗) di 𝑁 dengan sebuah bilangan non negatif yang memenuhi syarat-syarat berikut:
1. 0 ≤ 𝑓(𝑖, 𝑗) ≤ 𝑐(𝑖, 𝑗) ∀(𝑖, 𝑗) ∈ Γ(𝑁) (disebut kapasita pembatas)
2. ∑ 𝑓(𝑖, 𝑗) (𝑖,𝑗)∈𝑂(𝑠) = ∑ 𝑓(𝑖, 𝑗) (𝑖,𝑗)∈𝐼(𝑡) (disebut nilai flow 𝑓 ) 3. ∑ 𝑓(𝑖, 𝑗) (𝑖,𝑗)∈𝑂(𝑠) = ∑ 𝑓(𝑖, 𝑗) (𝑖,𝑗)∈𝐼(𝑡) ∀𝑥 ∈ 𝑉(𝑁) − {𝑠, 𝑡} (disebut sebagai “konservasi flow ”) [3].

## 8. Flow Maksimum pada Jaringan
Flow 𝑓 bernilai 𝑓 𝑠,𝑡 dari titik 𝑠 ke titik tujuan 𝑡 pada jaringan 𝑁 dikatakan flow maksimum  jika 𝑓 𝑠,𝑡 = min {𝑐(𝑋, 𝑋 1 )|𝐵(𝑋, 𝑋 1 ) suatu  pemutus −(𝑠, 𝑡) pada jaringan 𝑁 } [3].

## 9. Algoritma Ford-Fulkerson
Secara sistematis, langkah-langkah pada Algoritma Ford-Fulkerson yaitu:
Input       : Jaringan 𝑁 = (𝑉, 𝐺) dengan titik sumber 𝑠 dan titik tujuan 𝑡 .
Langkah  1  :  Misalkan 𝑓 sebuah flow dari 𝑠 ke 𝑡 pada 𝑁 . (Boleh dimulai dengan flow 𝑓
bernilai nol, yaitu 𝑓(𝑖, 𝑗) =
0, ∀ (𝑖, 𝑗) ∈ Γ ).  Dilanjutkan  ke  Rutin- Pelabelan.
Langkah 2   : Rutin-Pelabelan.
a. Label 𝑣 𝑠 = (𝑠, +, 𝜀(𝑠) = ~) .  Titik 𝑣 𝑠 telah  terlabel  dan  belum “teramati”.  (Catatan:  Semua  titik 𝑣 dikatakan  telah  teramati  jika semua  titik  yang  dapat  dilabel dari titik 𝑣 sudah terlabel).
b. Pilih  sebarang  titik  yang  terlabel tetapi  belum  teramati,  misalkan titik tersebut 𝑣 𝑥 . Untuk ∀ 𝑣 𝑦 ∃ (𝑦, 𝑥) ∈ Γ, 𝑣 𝑦 belum
terlabel  dan 𝑓(𝑦, 𝑥) > 0 ,  maka label 𝑣 𝑦 = (𝑥, −, 𝜀(𝑦)) dengan 𝜀(𝑦) = min {𝜀(𝑥), 𝑓(𝑦, 𝑥)} . Sekarang  titik 𝑣
𝑦 telah  terlabel, tetapi  belum  teramati.  Untuk ∀ 𝑣 𝑦 ∃ (𝑦, 𝑥) ∈ Γ, 𝑣 𝑦 belum terlabel  dan 𝑐(𝑥, 𝑦) > 𝑓(𝑥, 𝑦) , maka label 𝑣 𝑦 = (𝑥, +, 𝜀(𝑦)) dengan 𝜀(𝑦) = min
{𝜀(𝑥), 𝑐(𝑥, 𝑦) − 𝑓(𝑥, 𝑦)} .  Sekarang titik 𝑣 𝑦 terlabel,  tetapi  belum teramati.  Diubah  label 𝑣 𝑥 dengan cara  melingkari  tanda  +  atau  -. Sekarang  titik 𝑣 𝑥 terlabel  dan teramati.
c. Ulangi langkah a. sampai:
1) Titik 𝑣 𝑡 terlabel  atau  semua titik  terlabel  telah  teramati tetapi titik 𝑣 𝑡 tak terlabel.
2) Jika  titik 𝑣 𝑡 terlabel,  lanjut  ke langkah 3 atau jika semua titik yang  terlabel  telah  teramati tetapi  titik 𝑣 𝑡 tak  terlabel, maka  iterasi  dihentikan  dan flow 𝑓 adalah flow maksimum dana jaringan 𝑁 .
Langkah  3  :  Dengan  prosedur  “balik”,  temukan lintasan  peningkatan 𝑃 dengan 𝑖(𝑃) adalah label 𝑣 𝑡 .
Langkah  4  :  Tingkatkan  nilai flow 𝑓 sebesar  label 𝑣 𝑡 , berdasarkan lintasan peningkatan
𝑃 dengan  menggunakan  “Rutin Peningkatan”. Rutin Peningkatan:
a. Misalkan 𝑍 = 𝑡 lanjutkan  ke langkah b.
b. Jika label 𝑣 𝑧 = (𝑞, +, 𝜀(𝑡)) tingkatkan  nilai 𝑓(𝑞, 𝑧) dengan 𝜀(𝑡) = 𝑖(𝑃) .
c. Jika 𝑞 = 𝑠 ,  hapus  semua  label. Pada  tahap  ini  diperoleh flow 𝑓 baru  dengan  nilai = 𝑖(𝑃) + nilai flow 𝑓 lama.  Ganti flow 𝑓 dengan flow 𝑓 yang  baru, dan kembali ke langkah 1.
[3].

## 10. Jaringan Bipartisi
Sebuah jaringan 𝐺 = (𝑉, 𝐸) dikatakan bipartisi jika himpunan titik 𝑉 dapat dipartisi menjadi dua sub- himpunan 𝑉 1 dan 𝑉 2 sehingga  semua  sisi  dari 𝐺 mempunyai  ujung  di 𝑉 1 dan  ujung  lainnya  di 𝑉 2 , sebagaimana contoh berikut [4]:

## Gambar 6. Jaringan Bipartisi

## PEMBAHASAN
Data  simulasi  yang  disediakan  merupakan  data pendistribusian  barang  yang  memiliki  lima  titik sumber  dan  lima  titik  tujuan  dimana  untuk mencari flow maksimum pada data tersebut, maka dengan memodifikasi Algoritma Ford-Fulkerson.
Bentuk modifikasi algoritma ini adalah:
Input          : Jaringan 𝐴 = (𝑉, 𝐺) dengan beberapa titik sumber (𝑠 𝑖 ) dan beberapa titik tujuan 𝑡(𝑡 𝑗 ) .
Langkah 1 : Dibentuk sebuah jaringan baru dari 𝐴 yang dimisalkan 𝐴 ∗ , dengan
menambahkan  satu  titik  sumber 𝑠 dan  satu  titik  tujuan 𝑡 sedemikian hingga 𝑠 merupakan  satu-satunya titik  sumber  di  jaringan 𝐴 ∗ dan 𝑡
merupakan satu-satunya titik tujuan di 𝐴 ∗ .
Langkah  2  :  Dibuat  kapasitas  busur (𝑠, 𝑠 𝑖 ) dan (𝑡 𝑖 , 𝑡) dengan  nilai  kapasitas  tak hingga  atau  dilambangkan ∞ ,  dan nilai flow dapat dimulai dari 0.
Langkah  selanjutnya  yaitu  memaksimumkan flow 𝑠 − 𝑡 dengan  menggunakan  algoritma flow maksimum, yaitu:
Langkah 3  : Lakukan rutin pelabelan.
Langkah 4  : Gunakan prosedur balik.
Langkah 5  : Lakukan rutin peningkatan.
Langkah  6  :  Apabila  titik-titik  di 𝐴 ∗ yang  terlabel telah  teramati  semua,  dan  titik 𝑡 tidak
terlabel
maka iterasi
dihentikan.
Selanjutnya  data  dibentuk  menjadi  sebuah jaringan yang dimisalkan jaringan 𝑀 , sebagaimana dapat dicontohkan pada gambar berikut:
Gambar 7. Jaringan 𝑀
Jaringan 𝑀 pada  Gambar  7  akan  dicari flow maksimumnya
menggunakan modifikasi Algoritma Ford-Fulkerson dengan langkah- langkah sebagai berikut:
Langkah 1 :  Dibentuk  sebuah  jaringan  baru 𝑀 ∗ dari 𝑀 dengan  menambahkan  satu titik  sumber  baru  dan  satu  titik tujuan  baru  sedemikian  hingga merupakan  titik  sumber  utama  dan
titik tujuan utama di 𝑀 ∗ dimana titik sumber utama dan titik tujuan utama pada jaringan 𝑀 ∗ diberi warna biru.
Langkah 2 : Dibuat kapasitas busur (𝑠, 𝑠1), (𝑠, 𝑠2), (𝑠, 𝑠3), (𝑠, 𝑠4) dan (𝑠, 𝑠5) serta
(𝑡1, 𝑡), (𝑡2, 𝑡), (𝑡3, 𝑡), (𝑡4, 𝑡) dan (𝑡5, 𝑡) yang  juga  diberi  warna  biru  dengan nilai  kapasitas  utama  yaitu  stok persediaan  barang  dengan  nilai  45 dan nilai flow awal 0.
Gambar 8. Jaringan 𝑀 ∗ dengan Nilai Flow Awal 𝑓 = 0
Jaringan 𝑀 ∗ pada Gambar 8 mempunyai kapasitas di titik sumber utama dengan nilai 45, sedangkan total  kapasitas  di  beberapa  titik  sumber  dengan nilai  50.  Sebagaimana  prosedur  Algoritma  Ford- Fulkerson  pada  bab  sebelumnya,  agar  nilai flow segera  terpenuhi  maka  strategi flow maksimum yang  dilakukan  yaitu  dipilih  lintasan  dari  titik sumber  utama  ke  titik  yang  mempunyai  busur terhubungnya  paling  banyak  serta  titik  yang mempunyai  kapasitas  terbesar,  sehingga  urutan iterasi  untuk  lintasan  peningkatan  yaitu  di  titik 𝑠2, 𝑠4, 𝑠1, 𝑠3, 𝑠5 .
Langkah  selanjutnya  dalam  pencarian flow maksimum  menggunakan  modifikasi  Algoritma Ford-Fulkerson  untuk  iterasi  pertama  yaitu sebagai berikut:
1) Dari titik 𝑠 , diberi label titik 𝑠1, 𝑠2, 𝑠3, 𝑠4 dan 𝑠5 masing-masing 𝑠1 = (𝑠, +,45) , 𝑠2 = (𝑠, +,45) , 𝑠3 = (𝑠, +,45) , 𝑠4 = (𝑠, +,45) dan 𝑠5 = (𝑠, +,45) .  Sekarang  titik 𝑠 telah  terlabel  dan teramati dengan label 𝑠 = (𝑠,⊕ ,45) .
2) Dari  titik 𝑠2 ,  diberi  label  untuk  titik 𝑡1, 𝑡2, 𝑡3 masing-masing
𝑡1 = (𝑠2, +,14), 𝑡2 =
(𝑠2, +,2), 𝑡3 = (𝑠2, +,7) .  Titik 𝑠2 telah  terlabel dan teramati dengan label 𝑠2 = (𝑠, +,45) .
3) Dari  titik 𝑡1 ,  diberi  label  untuk  titik 𝑡 dengan label 𝑡 = (𝑡1, +, 45) .  Titik t 1 telah  terlabel  dan teramati dengan label 𝑡1 = (𝑠2, +,14) .
Langkah 4 : Gunakan prosedur balik.
Titik 𝑡 dilabel  dari  titik 𝑡1 ,  titik 𝑡1 dilabel dari 𝑠2 dan titik 𝑠2 dilabel dari titik 𝑠 .  Dengan  demikian  diperoleh lintasan  peningkatan 𝑃 = (𝑠, 𝑠2, 𝑡1, 𝑡) dan 𝑖(𝑃) = min (45,14,45) = 14 .
Langkah 5 : Rutin peningkatan.
Titik 𝑡 = ( 𝑡1, +, 45 )  maka  nilai flow pada busur ( 𝑡1, 𝑡 ) ditambah 14.
Titik 𝑡1 = ( 𝑠2, +, 14 )  maka  nilai flow pada busur ( 𝑠2, 𝑡1 ) ditambah 14.
Titik 𝑠2 = ( 𝑠, +,45 )  maka  nilai flow pada busur ( 𝑠, 𝑠2 ) ditambah 14.
Setelah  dilakukan  penghapusan  terhadap  semua label,  diperoleh  nilai flow baru 𝑓 1 = 14 .  Lintasan peningkatan  pada  jaringan 𝑀 ∗ diberi  warna orange  dan  ditunjukkan  sebagaimana  pada gambar berikut:
Gambar 9. Jaringan 𝑀 ∗ dengan Nilai Flow Baru 𝑓 1 =  14
Iterasi  selanjutnya  diulangi  pencarian flow maksimum menggunakan Algoritma Ford- Fulkerson  dari  titik  sumber  ke  titik  tujuan  di 𝑀 ∗ dengan  kembali  ke  langkah  2  sampai  iterasi  ke  8 yaitu  untuk  lintasan  peningkatan  di  titik 𝑠5 dan diperoleh nilai flow maksimum sebesar 45.
Berdasarkan  jaringan  yang  telah  terbentuk  pada Gambar 7, jaringan 𝑀 merupakan bentuk jaringan bipartisi dimana himpunan titik-titik di jaringan 𝑀 dapat  dipartisi  menjadi  dua  sub-himpunan, sehingga  jaringan 𝑀 akan  dipartisi  berdasarkan titik  sumber  dan  dicari flow maksimumnya  untuk
menunjukkan bahwasanya nilai flow maksimumnya  sama  antara  jaringan  yang  tidak dipartisi  dengan  jaringan  yang  dipartisi.  Jaringan 𝑀 dipartisi  menjadi  lima  karena  memiliki  lima titik  sumber,  karena  mempunyai  lima  titik  tujuan maka dengan memanfaatkan modifikasi Algoritma Ford-Fulkerson,  akan  ditambahkan  satu  titik tujuan  baru  dengan  kapasitasnya  adalah  stok persediaan  barang  sebesar  45.  Selanjutnya dilakukan  iterasi  dengan  mencari  lintasan peningkatan  dari  masing-masing  titik  sumber  ke titik  tujuan  utama  sampai  tidak  ditemukan  lagi lintasan  peningkatan,  yaitu  pada  saat  semua  titik sumber  telah  diselidiki.  Sehingga  nilai flow maksimum pada jaringan diperoleh dari total flow maksimum  untuk  semua  titik  sumber  di  jaringan, dan  didapatkan flow maksimum  dengan  iterasi sebanyak lima nilainya 45.
Pencarian flow maksimum  pada  jaringan 𝑀 juga dapat  dilakukan  dengan  membuat  program menggunakan  Matlab  R2010a  dengan  langkah iterasi  sebagaimana  prosedur  yang  dimiliki Algoritma  Ford-Fulkerson.  Tujuan  membuat program  ini  yaitu  agar  pencarian flow maksimum dapat  diketahui  dengan  lebih  mudah,  dimana hasilnya  dengan  iterasi  sebanyak  8  nilai flow maksimum sebesar 45.
Berdasarkan  hasil  contoh  pendistribusian  barang dengan  pencarian flow maksimum  pada  jaringan 𝑀 di atas didapatkan flow maksimum dengan nilai 𝑓 8 = 45 ,  pada  jaringan  yang  dipartisi  didapatkan flow maksimum dengan nilai 𝑓 5 = 45 serta dengan program  di  Matlab  R2010a  dengan  iterasi sebanyak  8  didapatkan flow maksimum  sebesar 45 .

## KESIMPULAN
Bentuk  modifikasi  Algoritma  Ford-Fulkerson untuk menentukan flow maksimum pada jaringan yaitu:
a. Membuat jaringan baru dari jaringan distribusi barang  dengan  menambahkan  satu  titik sumber  utama  dan  satu  titik  tujuan  utama  di jaringan baru tersebut.
b. Membuat  kapasitas  busur  dari  titik  sumber utama ke beberapa titik sumber dan membuat kapasitas  busur  dari  beberapa  titik  tujuan  ke titik tujuan utama dengan kapasitas maksimum dan  memberikan  nilai flow awal  pada  semua busur di jaringan baru dengan nilai 0.
Setelah  itu  memaksimumkan flow dari  titik sumber baru ke titik tujuan baru dengan:
c. Melakukan pelabelan titik.
d. Menggunakan prosedur balik.
e. Mencari lintasan peningkatan sampai titik-titik di  jaringan  yang  terlabel  telah  teramati  semua dan titik tujuan baru tidak terlabel maka iterasi dihentikan.
Dari  bentuk  modifikasi  di  atas,  didapatkan flow maksimum  pada  jaringan  tersebut  dengan  nilai 𝑓 8 = 45 ,  pada  jaringan  yang  dipartisi  didapatkan flow maksimum dengan nilai 𝑓 5 = 45 serta dengan membuat  program  di  Matlab  R2010a  didapatkan flow maksimum  dengan  iterasi  sebanyak  8 nilainya 45 .

## DAFTAR PUSTAKA
[1] T. Farizal, "Pencarian Flow Maksimum dengan Algoritma Ford-Fulkerson," Universitas Negeri Semarang, Semarang, 2013.
[2]  G.  Charland  and  L.  Lesniak,  Graf  and  Digraf, London: Chapman & Hall/CRC, 1996.
[3]  I.  Budayasa,  Teori  Graph  dan  Aplikasinya, Surabaya: Unesa University Press, 2007.
[4]  R. K. Ahuja, J. B. Orlin, C. Stein and R. E. Tarjan, "Improved  Algorithms  for  Bipartite  Network Flow," SIAMJ COMPUT, pp. 906-933, 1994.