1

MEMAKSIMALKAN VOLUME ALIRAN AIR

DALAM DISTRIBUSI AIR PDAM KELURAHAN ’’GADING KASRI’’

DENGAN ALGORITMA-ALGORITMA PADA MAXIMUM FLOW

PROPOSAL

Disusun Oleh :

Berlian Trifal Mahendra 409312417670

Mohammad Zakaria 409312417685

Halin Suharto 406312400862

Risa Wijayanti 406312403702

UNIVERSITAS NEGERI MALANG

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

JURUSAN MATEMATIKA

FEBRUARI 2012

i

DAFTAR ISI

Halaman Judul

Daftar Isi……………………………………………………………… i

Abstrak…………………………………………………………………. ii

BAB I Pendahuluan

I. Latar Belakang………………………………………………….. 1

II. Tujuan………………………………………………………….. 2

III. Manfaat………………………………………………………… 3

BAB II Kajian Teori

2.1 Dasar Teori Graph…………………………………………… 4

2.2 Maximum flow problem……………………………………… 5

2.3 Algoritma………………………………………………………. 6

2.4 Penelitian yang sudah dilakukan……………………………….. 15

BAB III Metodologi Penelitian

3.1 Unsur dalam maksimum flow…………………………………… 17

3.2 Alat Bantu Program ………………………………………… 22

3.3 Contoh Kasus Maximum Flow………………………………….. 23

BAB IV Pembahasan

4.1 Narasi Permasalahan……………………………………………. 27

4.2 Penyelesaian Masalah dengan algoritma……………………… 29

4.3 Penyelesaian Masalah dengan alat bantu……………………… 35

4.4 Analisa Hasil……………………………………………………. 37

BAB V Kesimpulan

5.1 Kesimpulan……………………………………………………… 38

ii

ABSTRAK

Teori graph merupakan salah satu cabang matematika yang penting dan

banyak manfaatnya dalam memecahkan masalah sehari-hari" Salah satu teori graph

yang diterapkan adalah masalah maksimum flow, yaitu bagaimana mencari besar

penugasan aliran pada suatu jaringan kerja sehingga aliran yang sampai ke tujuan

maksimal" Penyelesaian masalah maximum flow dapat diselesaikan dengan

menggunakan tiga algoritma yaitu Algoritma Pelabelan Aka, Algoritma Lintasan

Penambah, dan Algoritma Preflow Push" Untuk Algoritma Pelabelan Aka telah

dikerjakan pada skripsi terdahulu, operasi dasar algoritma Pelabelan Aka yaitu

berulang-ulang mencari suatu lintasan dari titik sumber ke titik tujuan dan

menghitung nilai kapasitas sisaannya yang digunakan untuk mengembangkan aliran

pada lintasan yang terpilih" Perulangan berhenti jika tidak ada lagi lintasan dan titik

sumber ke tujuan" Pada skripsi kali ini untuk menyelesaikan masalah maximum

flow akan digunakan Algoritma Lintasan Penambah" Pengerjaan Algoritma

Lintasan Penambah lebih sederhana dibandingkan dengan Algoritma Pelabelan

Aka" Prosesnya diawali dengan merubah graph dasar kedalam bentuk suatu

jaringan kerja dengan memberikan aliran awal pada setiap sisi sebesar 0 barulah

dapat melakukan langkah pertama yaitu pilih terlebih dahulu lintasan yang akan

dilalui yang berasal dari titik sumber ke titik tujuan, langkah kedua cari kapasitas

sisaan dari lintasan penambah dengan cara mencari nilai MIN (?) pada lintasan

yang terpilih, langkah ketiga kurangkan kapasitas sebesar ? dan tambahkan aliran

sebesar ? pada setiap sisi yang berada pada lintasan yang dipilih" Setelah tidak ada

lagi lintasan yang dipilih maka lintasan tersebut telah mencapai nilai maksimum"

Untuk mempermudah penyelesaian masalah maximum flow dengan algoritma

Ford-Fulkerson dan Algoritma Lintasan Penambah digunakan komputer dengan

program GIDEN dan Grin" Penyelesaian dengan menggunakan Algoritma Lintasan

Penambah dapat diterapkan untuk mengoptimalkan volume aliran air pada jaringan

pipa PDAM daerah Gading Kasri" Dengan Algoritma Lintasan Penambah dapat

diketahui bahwa aliran dapat dicapai secara maksimum dalam 5 iterasi dengan hasil

maximum flow sebesar 280 liter/detik"

1

BAB I

PENDAHULUAN

I. Latar Belakang

Matematika merupakan disiplin ilmu yang tercipta berkat kemampuan

abstraksi manusia sebagai makhluk alam. Dewasa ini semakin banyak disiplin ilmu

yang menggunakan model matematika maupun penalaran matematika sebagai alat

bantu untuk menyelesaikan permasalahan yang dihadapi. Dalam kehidupan sehari-

hari kita pasti dihadapkan oleh berbagai masalah. Untuk menyelesaikan masalah

tersebut perlu tentunya pendekatan ilmu, karena hidup dengan ilmu itu akan

menjadi mudah. Dalam ilmu matematika, banyak hal yang kita jumpai yang sulit

untuk memberi batasan, misalnya dalam teori graph, dimana teori ini begitu banyak

manfaatnya. Akan tetapi tidak banyak orang yang menyadari bahwa teori ini

memiliki aplikasi yang begitu luas.

Teori graph merupakan salah satu cabang matematika yang penting dan banyak

model teori graph yang dapat diterapkan adalah masalah maksimum flow, yaitu

masalah bagaimana cara menentukan besarnya penugasan flow pada suatu jaringan

kerja sehingga flow yang sampai ke tujuan maksimal". Salah satu bentuk graph

yang popular digunakan adalah flow network, yaitu graph berarah yang tiap sisinya

mempunyai kapasitas tertentu.

Flow network ini memilik banyak aplikasi dalam kehidupan sehari-hari. Flow

network sering digunakan untuk memodelkan sistem lalu lintas, suatu sistem yang

sering menjadi masalah utama dalam kehidupan, terutama di kota besar.

Salah satu masalah yang sering muncul dalam flow network adalah maximum

flow problem. Secara sederhana, maximum flow problem dapat dideskripsikan

sebagai masalah pencarian untuk mencari arus maksimum yang dapat mengalir

pada sebuah network yang hanya memiliki satu source dan sink.

Sebagai contoh penerapan maximum flow problem adalah sebagai berikut:

suatu perusahaan memiliki pabrik di kota A dimana barang yang sudah diproduksi

harus dikirim ke kota B. Kita memiliki data jalan satu arah yang menghubungkan

setiap kota, dan jumlah maksimum truk yang dapat melewati jalan tersebut.

2

Masalah yang harus dipecahkan adalah menentukan jumlah maksimum truk yang

dapat dikirimkan sekali jalan.

Banyak penelitian yang telah dilakukan dalam penyelesaian maximum flow.

Contohnya adalah skripsi berjudul Eksplorasi Kerja Algoritma Edmons Karp dalam

Menyelesaikan Maximum Flow Problem yang disusun oleh Ardanu Pratama Putra,

Analisis Kerja Algoritma Dinits yang disusun oleh Bahrul Ulum, Penerapan Model

Maximum Flow dalam Teori Graph pada Lalu Lintas Kendaraan yang ditulis oleh

Rosyidah tahun 2006. Serta Laporan PKL berjudul Optmalisasi pendistribusian

produk PT Coca Cola Indonesia dengan menggunakan Algoritma-algoritma pada

maximum Flow pada tahun 2010.

Merujuk pada masalah di atas, maka keberadaan aplikasi maximum flow

problem sangat penting. Baik bagi perusaahan maupun bagi pelaku atau peneliti.

Bagi peneliti merupakan kesempatan yang penting untuk menerapkan ilmu atau

keahlian yang telah diperoleh dari pendidikan formal. Pihak yang paling

diuntungkan dari pengembangan maximum flow problem adalah perusahaan.

Dengan memberikan kesempatan kepada peneliti mengaplikasikan ilmunya serta

memberikan kesempatan untuk belajar maka perusaahaan telah memberikan

kesempatan kepada dirinya untuk terus berkembang dan terus menambah

keuntungan.

Dalam teori graph, ada banyak algoritma yang digunakan untuk menentukan

aliran terpendek dari suatu tempat ke tempat lain. Algoritma-algoritma pada aliran

terpendek tersebut antara lain Algoritma Lintasan Penambah, Algoritma Preflow

Push, Algoritma Dijkstra, Algoritma Ford Fulkerson, Algoritma Edmons Karp,

Algoritma Pelabelan Aka, Algoritma Incremental, Algoritma Formal Stat ement,

dll. Namun dalam pembahasan masalah ini, hanya akan digunakan beberapa

algoritma yang digunakan untuk membahas suatu masalah yang kami beri nama

judul ”Memaksimalisasi Volume Aliran Air dalam Distribusi Air PDAM dengan

Algoritma-algoritma pada Maksimum Flow”

II. Tujuan

Adapun tujuan dari pelaksanaan observasi adalah :

1. Secara khusus, tujuan dari pelaksanaan observasi kami adalah:

3

a) Identifikasi masalah pengoptimalan volume aliran air pada distribusi

air di PDAM kelurahan„‟Gading Kasri‟‟.

b) Menerapkan algoritma Maksimum Flow dalam pengoptimalan

volume aliran air pada distribusi air PDAM kelurahan „‟Gading

Kasri‟‟ .

c) Memberikan solusi untuk pengoptimalan volume aliran air pada

distribusi air PDAM kelurahan „‟Gading Kasri‟‟ .

III. Manfaat

MANFAAT OBSERVASI

a. Untuk mengetahui pengoptimalan volume aliran air pada distribusi air

PDAM kelurahan „‟Gading Kasri‟‟.

b. Memberikan solusi untuk pengoptimalan volume aliran air pada distribusi

air PDAM kelurahan „‟Gading Kasri‟‟.

4

BAB II

Kajian Teori

2.1.Dasar Teori Graph

Definisi dari graph yaitu suatu himpunan tak kosong yang masing-masing

unsurnya disebut titik (vertex) dan suatu himpunan pasangan tak berurutan dari

titik-titik tersebut yang disebut sisi (edge).

Contoh graph:

Digraph adalah graph yang tiap sisinya memiliki arah

Contoh digraph:

Digraph berbobot adalah digraph yang tiap sisi berarahnya memiliki

bobot (nilai).

Contoh digraph berbobot:

Network adalah digraph berbobot yang memiliki suatu titik sumber dan

satu titik tujuan. Pada titik sumber, tidak terdapat sisi masuk, sedangkan pada

7

9

6 6

11

5

8

5

5

titik tujuan tidak terdapat sisi keluar, bobot tiap sisi pada suatu network adalah

kapasitas (C) sisi tersebut.

Contoh network:

Residual network adalah network dengan ketentuan pelabelan sisinya

sebagai berikut:

C‟(i,j) = C(i,j) – F(i,j),

C‟(j,i) = F(i,j).

Definisi flow (F) adalah suatu bilangan tak negatif yang didefinisikan

pada tiap sisi pada suatu network yang memenuhi Fij < Cij untuk sebarang sisi

(i,j) pada network tersebut.Setiap arus(flow) dalam network,harus memenuhi

suatu batasan yaitu arus yang masuk pada suatu simpul harus sama dengan arus

yang keluar pada simpul tersebut, kecuali pada source, yang arus keluarnya

lebih besar dari arus masuk, dan sink, yang arus masuknya lebih besar dari arus

keluar.

2.2 Maximum Flow Problem

Pada maximum flow problem, sering dijumpai istilah sebagai berikut:

Network N

Network adalah digraph berbobot yang memiliki suatu titik sumber

dan satu titik tujuan. Pada titik sumber, tidak terdapat sisi masuk,

sedangkan pada titik tujuan tidak terdapat sisi keluar, bobot tiap sisi

pada suatu network adalah kapasitas (C) sisi tersebut.

Walk(Jalan)

Misalkan titik dan (tidak harus berbeda) pada suatu graph . Jalan

(walk) ( ) di adalah barisan dengan

, adalah titik, adalah sisi, dan

menghubungkan titik dan ,

Flow (F)

Titik sumber S

Titik tujuan

T

7

9

6 6

11

5

8

5

6

Flow (F) merupakan suatu bilangan tak negatif yang didefinisikan

pada tiap sisi pada suatu network yang memenuhi Fij<Cij untuk

sebarang sisi (i,j) pada network tersebut.Setiap arus(flow) yang ada

dalam network,harus memenuhi sebuah batasan yaitu arus yang masuk

pada suatu simpul harus sama dengan arus yang keluar pada simpul

tersebut, kecuali pada source, yang arus keluarnya lebih besar dari

arus masuk, dan sink, yang arus masuknya lebih besar dari arus

keluar.

Residual Network

Residual network merupakan network dengan ketentuan pelabelan

sisinya adalah sebagai berikut:

C‟(i,j) = C(i,j) – F(i,j),

C‟(j,i) = F(i,j).

Flow di G=(V,E) adalah bilangan tak negatif Fij sedemikian sehingga

a. Fij < Cij, Cij adalah bobot sisi (i,j)

b. i

ji

i

ij FFsjtjGVj ,,),(

Nilai flow adalah jumlah semua flow yang meninggalkan titik sumber (s).

2.3 Algoritma

Beberapa algoritma yang dapat digunakan dalam pencarian maximum

flow antara lain:

a. Algoritma Lintasan Penambah (Augmenting Path Algorithm)

Lintasan penambah adalah suatu lintasan berarah dari titik S ke titik

tujuan T dalam suatu jaringan berarah sisaan sehingga setiap sisinya memiliki

kapasitas lebih dari nol.

Langkah-langkah:

1. Tentukan suatu lintasan penambah.

2. Tentukan nilai minimum kapasitas semua sisinya, yang dinotasikan dengan

.

3. Jika telah ditentukan, operasikan dengan kapasitas setiap sisi lintasan

penambah tersebut, yakni:

Cij*= Cij - dan Cji*= Cji +

7

dengan :

ij = sisi pada lintasan penambah

ji = sisi berarah kebalikan dari sisi ij

Cij = kapasitas sisi ij sebelum iterasi n

Cji = kapasitas sisi ji sebelum iterasi n

Cij* = kapasitas sisi ij setelah iterasi n

Cji* = kapasitas sisi ji setelah iterasi n

Ulangi langkah 1 sampai dengan langkah 3 sampai tidak ada lintasan

penambah yang lain, hitung aliran dari jaringan berasal asli, yakni :

Fij = Cij – Cij*

dengan:

Fij = aliran sisi ij pada jaringan berarah asli

Cij= kapasitas sisi ij pada jaringan berarah asli

Cij*= kapasitas ij pada jaringan berarah sisaan iterasi terakhir.

Lihat Contoh berikut

Iteration 1:Dalam gambar tampak bahwa , salah satu lintasan potensial adalah O -

B- E- T, yang mempunyai kapasitas sisa min{7, 5, 6} = 5. Dengan mengalirkan 5

ke dalam lintasan ini, didapatkan network residual

8

Iteration 2: Alirkan lagi sebanyak 3 ke lintasan potensial O - A- D - T. didapatkan

network residual

Iteration 3: alirkan 1 ke lintasan potensial O _ A-B-D-T.

Iteration 4: alirkan 2 ke lintasan O-B-D-T. Nework yang dihasilkan

Iteration 5: : alirkan 1 ke lintasan potensial O-C-E-D-T.

Iteration 6: : alirkan 1 ke lintasan potensial O-C-E-T. Hasilnya adalah

9

Iteration 7: : alirkan 1 ke lintasan potensial O-C-E-B-D-T.

Network yang dihasilkan adalah

10

b. Algoritma Preflow-Push

Langkah-langkah:

1. Persiapan

Tentukan flow awal tiap sisi adalah nol. Hitung distance label tiap vertex

(banyaknya sisi berarah pada lintasan terpendek yang menghubungkan suatu

vertex ke vertex tujuan). Tentukan Fsj=Csj, )(DVj dengan s adalah

vertex asal.

2. Iterasi

Jika terdapat vertex i (bukan vertex awal maupun tujuan) yang aktif

(excess(i)>0) maka pilih vertex tersebut lalu:

a. Jika ada sisi (i,j) yang admissible (distance label (i) = distance label (j) +

1) maka push=min{excess(i),rij}

Catatan: excess(i) adalah jumlah flow yang masuk ke vertex i dikurangi

jumlah flow yang keluar dari vertex i.

b. Jika tidak ada sisi (i,j) yang admissible maka ganti distance label (i)

dengan min{ distance label (j)+1| )(),( GVji }, rij adalah kapasitas

residu yaitu ijij FC .

Ulangi langkah 2 sampai tidak ada lagi titik yang aktif.

c. Algoritma Pelabelan Aka (Aka’s Labelling Algorithm)

Langkah-langkah:

1. Beri label pada titik sebarang (s) dengan (-,∞) dan berikan flow awal

sebesar nol untuk setiap label sisi pada jaringan kerja. Tanda (-)

11

menunjukkan bahwa semua flow berasal dari sumber, tanda (∞)

menunjukkan bahwa flow dari sumber nilainya tak terbatas.

a. Label titik: (±i, Pf) dengan i merupakan titik dan Pf merupakan potensial

A pada titik i.

b. Label sisi: (Cij,Fij) dengan Cij merupakan kapasitas sisi (i,j) dan Fij

merupakan flow aktual pada sisi (i,j).

2. Lanjutkan ke langkah selanjutnya jika terdapat (salah satu atau keduanya)

suatau lintasan pada digraph D yang berkarakteristik sebagai berikut:

a. Sisi terorientasi tepat (arahnya dari sumber ke tujuan) dan memenuhi

Fij<Cij

b. Sisi terorientasi tak tepat (arahnya dari tujuan ke sumber) dan memenuhi

0<Fij

3. Misal (i,j) adalah suatau sisi pada digraph D, maka label untuk titik (i,j):

a. Jika (i,j) terorientasi tepat maka label j: [+i,MIN{Cij-Fij, Pf pada i}]

b. Jika (i,j) terorientasi tak tepat maka label j: [-i,MIN{ Fij, Pf pada i}]

4. Misal menjadi Pf dari titk tujuan, maka sisi (i,j) berubah menjadi:

a. Jika label pada j adalah [+i,] maka label (i,j) menjadi [Cij,Fij+ ]

b. Jika label pada j adalah [-i,] maka label (i,j) menjadi [Cij,Fij- ]

5. Kembali ke langkah dua.

Nilai maximum flow merupakan jumlah dari semua yang didapat dari

iterasi-iterasi yang telah dilakukan.

d. Algoritma Ford Fulkerson

Langkah-langkah :

1. Buatlah graph c simetris jika ada c [u,v sementara c[v,u] tidak ada dengan

membuat c[v,u]=0.

2. Inisialisai f[u,v]= f[v,u]=0, untuk setiap (u,v) dalam graph

3. Inisialisai G[u,v] c[u,v], ),( vu G, G suatu graph.

4. Dapatkan lintasan residual antara s dant,jika ada maka

a. Aliri melalui lintasan dengan kapasitas sesuai dengan residu terkecil di

dalam lintasan tersebut.

b. Update setiap f [u,v] untuk setiap (u,v) dalam lintasan sesuai debit

tersebut.

12

c. Hitung residual e [u,v] = c [u,v] – f [u,v] dalam lintasan sebagai residual

terbaru.

d. Ulangi hingga tidak ada lintasan residual antar s dan t.

5. Graph maximum flow adalah graph f [u,v] dengan hanya mengambil sisi

(u,v), jika f [u,v] > 0

e. Algoritma Djikstra

Pada dasarnya, algoritma ini merupakan salah satu bentuk algoritma

greedy. Algoritma ini temasuk algoritma pencarian graph yang digunakan untuk

menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah

graph yang tidak memiliki cost sisi negatif, dan menghasilkan sebuah pohon

lintasan terpendek.

Untuk menyelesaikan Maximum Flow Problem dengan algoritma

Djikstra, langkahnya adalah sebagai berikut:

1. Cari sebuah lintasan yang belum dipilih yang menghubungkan simpul awal

dengan simpul tujuan.

2. Carilah sebuah sisi dengan kapasitas minimum. Kapasitas sisa minimum

didapat dari kapasitas sisi tersbut dikurangi arus yang sudah mengalir pada

sisi itu (c-f). Bila kapasitas minimum sisa sama dengan 0, langsung ke

langkah 4.

3. Alirkan arus sejumlah kapasitas minimum sisi pada lintasan yang dipilih.

4. Kembali ke langkah 1 sampai semua lintasan diperiksa.

f. Algoritma Edmonds Karp

Berikut ini langkah-langkah algoritma BFS untuk menemukan lintasan

penambah terpendek pada suatu residual network.

Input: suatu residual network R dengan titik sumber s, titik tujuan t, dan

himpunan semua titik V(R).

1. Inisialisasi himpunan Vs = {s}.

2. Labeli titik s dengan nol (ℓ(s)=0).

3. Inisialisasi label penghitung i = 1.

4. Selama Vs tidak memuat t, lakukan langkah berikut

Jika terdapat busur yang titik awalnya termuat di Vs dan titik akhirnya termuat di

V(R) - Vs, untuk selanjutnya disebut usable arc,maka

13

Misal e suatu usable arc dengan titik awal v yang memiliki label terkecil,

Misalkan w adalah titik akhir dari e yang belum memiliki label,

atur v sebagai backpoint dari w,

ℓ(w) = i

Vs = Vs {w}

i = i+1

Jika tidak terdapat usable arc, maka tidak ada lagi lintasan penambah di R.

Susun ulang lintasan penambah Q dengan menelusuri backpoint dari titik t.

Output: lintasan penambah Q

Berikut ini langkah-langkah algoritma Edmons Karp

Input: suatu network N

1. Tentukan residual network dari N.

2. Inisialisasi flow Untuk setiap busur ij pada N sebesar nol (Fij = 0)

3. Identifikasikan suatu lintasan penambah pada residual network dengan

menggunakan algoritma BFS.

4. Jika telah diperoleh suatu lintasan penambah, maka tentukan kapasitas residu

lintasan penambah tersebut yang dinotasikan dengan .

5. Tambahkan flow sebesar ke setiap busur pada lintasan penambah tersebut.

Jika masih ada lintasan penambah yang lain, ulangi langkah 3 sampai dengan

langkah 5. Jika tidak ada lintasan penambah yang lain, hitung aliran pada setiap

busur, yaitu:

Fij = Cji

dengan:

Fij = flow busur ij pada network asli

Cji= kapasitas busur ij pada residual network

Output: flow (F) pada N merupakan jumlah semua flow yang meninggalkan sumber,

yaitu i

siFF .

g. Algoritma Dinitz Blocking Flow

Algoritma ini terdiri dari tiga bagian algoritma yaitu: Algoritma Dinitz,

Algoritma Konstruksi Layered Network, dan Algoritma Blocking Flow.

Algoritma ini tergolong baru karena dikembangkan mulai tahun 2006.

14

h. Algoritma Dinitz (G, s, c, t)

Langkah-langkah:

1. f ← 0; bentuk Residual Network Nf = (Gf, cf, s, t)

2. Selama terdapat lintasan dari s ke t di Gf lakukan

3. ►Invariant assertion: f adalah flow di N

4. Bentuk Layered Network Lf = (Lf, cf, s, t)

5. Temukan Blocking Flow b untuk Lf: assertion: df+b(t) > df(t)

6. f ← f + b

7. Buat Residual Network Nf

8. f adalah maksimum flow di N

i. Algoritma Konstruksi Layered Network

Langkah-langkah:

1. V0 ← {s}; i ← 0

2. Selama (Vi ≠ ) dan (t bukan Vi) lakukan

3. Vi+1 ← ; Ei+1 ←

4. Untuk setiap u Vi lakukan

5. Untuik setiap v V sedemikian sehingga (<u, v> Ef) dan (v bukan elemen

Vj untuk setiap j ≤ i) lakukan

6. Jika ( v bukan elemen Vi+1) maka

7. Tambahkan u ke Vi+1

8. Tambahkan <u, v> ke Ei+1

9. i ← i + 1

10. Jika (Vi = ) maka

11. Kembali Lf = ( , cf, s, t) ; assertion: tidak terdapat lintasan dari s ke t di Nf

12. Lf ← (V0 …Vi, E1 …Ei)

13. Kembali Lf = (Lf, cf, s, t)

14. Jika t telah dicapai dari s di Nf, maka Lf adalah Layered Network dari Nf

j. Algoritma Blocking Flow

1. b ← 0; M ← Lf; c ← cf

15

2. Ulangi

3. Assertion: hanya s yang merupakan titik di M dengan 0 derajat masuk

4. Temukan lintasan p dari s ke t di M

5. Untuk setiap sisi <u, v> p lakukan

6. b(u, v) ← b(u,v) + c(p); b(v.u) ← -b(u, v)

7. c(u, v) ← c(u, v) – c(p)

8. jika c(u, v) = 0 maka

9. pindahkan <u, v> dari M

10. Hapus dari M

11. Jika derajat masuk (v) = 0 maka

12. Clean Forward (v, M)

Sampai derajat masuk (t) = 0

k. Algoritma Recap

l. Algoritma Edmonds Karp-fat pipes

m. General push-relabel maximum flow algorithm

n. Push-relabel algorithm with FIFO vertex selection rule

o. Dinitz Blocking Flow algorithm with dynamic trees

p. Push-relabel algorithm with using dynamic trees

q. Binary blocking flow algorithm

r. Algoritma Formal Statement

2.4 Penelitian Yang Sudah Dilakukan

Banyak penelitian yang sudah dilakukan tentang penyelesaian masalah

maksimum flow baik itu mahasiswa maupun instansi pendidikan diantaranya :

1. Skripsi berjudul Penerapan Model Maximum Flow dalam Teori Graph pada

Lalu Lintas Kendaraan yang ditulis oleh Rosyidah tahun 2006.

2. Ber-arcs Kaliurang dan Penghitung Maximum Flow di Ruas Jalan Kawi

Pasar Besar Kota Malang yang ditulis oleh Titin Wahyuningsih dan Dian

Lestari pada tahun 2007.

16

3. Skripsi berjudul Eksplorasi Kerja Algoritma Edmons Karp dalam

Menyelesaikan Maximum Flow Problem yang ditulis Ardanu Pratama Putra

tahun 2010.

4. Optimalisasi Pendistribusian Produk PT Cocacola Indonesia Dengan

Menggunakan Algoritma-Algoritma Pada Maximum Flow disusun oleh

Elly Astutik, Septa Paramitha dan Iip Regianto pada tahun 2010.

17

BAB III

METODOLOGI

3.1 Unsur Dalam Maksimum Flow

Dalam mengaplikasikan algoritma-algoritma yang ada pada maksimum

flow problem dibutuhkan unsur-unsur yang dapat di representasikan sebagai

elemen – elemen dalam graph yaitu vertex, edge dan bobot untuk setiap sisi.

Unsur-unsur beserta representasinya adalah sebagai berikut :

Salah satu kantor PDAM yang ada di Malang

Tandon air sebagai vertex (titik)

Pipa dari satu tandon ke tandon yang lainnya sebagai edge (sisi)

Sedangkan kapasitas pipa sebagai bobot dari sisinya.

Algoritma-algoritma yang digunakan dalam laporan ini antara lain:

Algoritma Lintasan Penambah

Algoritma Preflow Push

Algoritma Ford Fulkerson

Langkah-langkah penerapan :

1. Mengumpulkan data-data berupa :

Jalur pipa yang dilewati

Kapasitas pipa

Arus yang melewati pipa

2. Penerapan algoritma-algoritma maksimum flow, yaitu Algoritma Lintasan

Penambah, Algoritma Ford Fulkerson, dan Algoritma Preflow Push.

3. Menentukan banyaknya volume aliran air PDAM di kelurahan Gading Kasri

berdasarkan hasil dari penyelesaian masalah maksimum flow.

18

3.2 Alat Bantu Program

Dalam penyelesaian masalah maksimum flow terdapat alat bantu berupa

software untuk menyelesaikan masalah maksimum flow yaitu Giden dan Grin.

Sebagai contoh, misal akan dicari maximum flow dari titik A sebagai titik

sumber ke titik E sebagai titik tujuan yang akan diselesaikan dengan

menggunakan software giden.

Rute yang dapat dilalui dari titik A ke titik E beserta kapasitasnya di

representasikan ke dalam graph berikut ini:

Langkah-langkah penggunaan software GIDEN dalam penyelesian masalah

Maksimum Flow:

a. Buka aplikasi software GIDEN

b. Klik file, lalu pilih new

19

c. Pilih new node untuk menggambar titik

Kemudian beri nama titiknya

d. Pilih new edge untuk menggambar sisi, kemudian beri nilai pada

sisinya

Gambar titik dan sisi sesuai bentuk asli

e. Untuk memberi nama pada pilih menunode dataadd data field,

lalu isi nama pada enter field nameOK, lalu klik edit pada GIDEN

f. Untuk memberi nilai pada sisi, pilih menuadd data field, lalu isi

nilai pada enter field nameOK, lalu klik edit pada GIDEN

20

g. Untuk menampilkan atau menghilangkan arah pada edge, pilih

menueditdirected edges

h. Untuk menyelesaikannya, pilih menusolverpilih cara

penyelesaiannya. Misalnya pilih maximum fowpre-flow push.

Maximum flow dapat dilihat pada nilai edge yang menuju k t, yaitu 6+4=10.

Jadi maksimum flow dari kota A ke kota E adalah 10.

a. Langkah – langkah penggunaan software grin dalam

penyelesian masalah Maksimum Flow:

Pilih Grin pada tampilan Windows kemudian Klik dua kali

untuk membukanya. Tampilannya sebagai berikut

Pilih File kemudian New, tampilannya sebagai berikut.

21

Klik Add Point untuk membuat titik. Klik Add Edge untuk

membuat sisi,pilih Move Point untuk mengubah letak titik

(sesuaikan posisinya).

Untuk mengisi muatan pada sisi,menamai tiik, klik Table-

edit, lalu isikan setiap muatan,namai titik pada kolom yang

disediakan. Titik pada sisi atas tabel merupakan titik tujuan j dan

titik pada sisi kiri tabel merupakan titik asal i untuk setiap arc ij.

22

Untuk melihat jaringan yang diubah klik Network, diperoleh

jaringan berikut

Untuk mencari maximum flow pada jaringan kerja tersebut

pilih Property – Network - Maximal Flow. Pilih titik 1(S)

sbgai titik smber dan titik 6(T) sebagai tujuan.

Diperoleh maksial flow pada jaringan sebesar 7. Hasilnya

adalah sebagai berikut

23

3.3 Contoh Kasus Maximum Flow

Untuk lebih memahami masalah arus maksimum, kembali kita ambil contoh

dari Istec Corporation. Kali ini masalah yang diangkat adalah masalah

maximum flow of cars (arus kendaraan maksimum) yang melewati jalan

penghubung antara Mess karyawan dengan kantor baru. Jalan penghubung

tersebut dapat digambarkan dalam gambar jaringan di bawah ini.

Sebelum menjelaskan ke pemecahan masalah, maka perlu dijelaskan terlebih

dahulu arti dari angka-angka yang terdapat pada tiap cabang. Cabang yang

menghubungkan antara node-1 dengan node-2 memuat angka 2 dan 0, maksudnya

adalah :

- arus maksimal kendaraan yang dapat melintasi jalan dari node-1 ke node-2

adalah 200 mobil per jam

- arus dari node-2 ke node-1 adalah 0 mobil per jam, artinya tidak ada arus dari

node-2 ke node-1 (arus hanya searah dari node-1 ke node-2)

Interpretasi di atas juga dapat diterapkan pada cabang-cabang lain yang

menghubungkan antar node. Permasalahannya adalah berapakah arus maksimum

dari jalan yang menghubungkan mess karyawan dengan kantor?

24

Berikut ini adalah penerapan langkah-langkah penyelesaian arus maksimal untuk

menjawab permasalahan arus maksimal dari mess karyawan Istec Corporation ke

kantor barunya.

Secara arbitrer diambil garis edar 1-2-5-7-8

Arus maksimal dari node-1 ke node-8 yang melewati garis edar 1-2-5-7-8 adalah

sebesar 2 atau 200 mobil per jam. Tiap arus menuju ke node-8 dikurangi 2 dan arus

yang berlawanan ditambah 2, sehingga menghasilkan hasil sebagai berikut.

Hasil di atas memperlihatkan bahwa tidak ada lagi jalan yang dapat ditempuh

melalui node-1 ke node-2, karena arus maksimumnya adalah nol (0). Secara arbitrer

diambil garis edar 1-3-6-8. Arus maksimum pada garis edar ini adalah 2 atau 200

mobil per jam, sehingga total arus maksimum yang dapat masuk adalah sebesar 4

atau 400 mobil per jam.

Karena arus maksimum pada garis edar 1-3-6-8 adalah 2, maka tiap arus menuju

node-8 dikurangi 2 dan tiap arus berlawanan ditambah 2.

25

Jalur lain atau garis edar lain yang masih memungkinkan untuk dilewati adalah

jalur 1-4-6-8 dan 1-4-8 dengan arus maksimum masing-masing jalur adalah 1 atau

100 mobil per jam, sehingga meningkatkan total arus maksimum yang dapat masuk

sebesar 5 atau 500 mobil per jam.

Secara arbitrer diambil garis edar 1-4-8. Tiap arus menuju node-8 dikurangi 1 dan

tiap arus berlawanan ditambah 1.

Pada langkah ini tidak ada lagi jalur atau garis edar yang dapat menghubungkan

arus dari node-1 ke node-8. Agar lebih jelasnya diagram jaringan disajikan dengan

tanda-tanda panah berikut :

26

Karena tidak ada lagi arus yang dapat mengalir dari node-1 ke node-8, maka proses

iterasi telah mencapai penyelesaian optimun. Dari sini dapat diambil kesimpulan

bahwa arus maksimum yang menghubungkan antara lokasi mess karyawan dengan

kantor baru adalah sebesar 5 atau 500 mobil per jam dengan rincian sebagai berikut

Jalur Maksimum Arus Mobil

1 – 2 – 5 – 7 – 8 200

1 – 3 – 6 – 8 200

1 – 4 – 8 100

Total 500

27

BAB IV

PEMBAHASAN

4.1. Narasi Permasalahan

Kota malang sebagian besar penduduknya menggunakan air PDAM untuk

kebutuhan sehari-hari.Setiap harinya,pihak PDAM menyuplai air di setiap

kelurahan yang ada di kota Malang.Dan setiap kelurahan oleh pihak PDAM

dibangun Tandon yang gunanya untuk dapat menampung volume air agar

penyuplaian debit air di setiap rumah terbagi dengan teratur.Akhir-akhir ini tidak

sedikit warga yang komplain akibat kurangnya penyuplaian air PDAM di rumahnya

khususnya di daerah antara tendon Betek sampai tendon kelurahan Gading

Kasri.Agar permasalahan tentang kurangnya suplai air,bagaimana cara/solusi yg

digunakan untuk memenuhi penyuplaian air di setiap rumah di kelurahan Betek-

Gading Kasri? Berikut diberikan data-data tentang debit air setiap tendon dan gr

aliran pipa air PDAM.

Dari survey yang telah kami lakukan di PDAM BETEK yang terletak di Mayjen

Panjaitan kita dapatkan bahwa besarnya aliran air tiap kelurahan berbeda – beda.

Selain itu kami juga memperoleh data tentang pipa penghubung antar tandon yang

dijadikan sebagai sisi dan kelurahan sebagai titik yang disajikan pada tabel dibawah

ini.

Tabel Daftar Titik

NO Daftar Titik (Vertex) Keterangan

1 Tandon PDAM Betek Titik S

2 Tandon Kelurahan Oro – oro Dowo Titik A

3 Tandon Kelurahan Kauman Titik B

4 Tandon Kelurahan Gading Kasri Titik T

5 Tandon Kelurahan Rampal Celaket Titik C

6 Tandon Kelurahan Bareng Titik D

7 Tandon Kelurahan Klojen Titik E

28

Tabel Daftar Sisi

No. Daftar sisi (Edge) Keterangan

1. Pipa Betek – Oro-oro Dowo

2. Pipa Oro-oro Dowo – Kauman

3. Pipa Oro-oro Dowo – Klojen

4. Pipa Kauman – Gading Kasri

5. Pipa Kauman – Rampal Celaket

6. Pipa Betek – Klojen

7. Pipa Klojen – Bareng

8. Pipa Klojen – Rampal Celaket

9. Pipa Bareng – Gading Kasri

10. Pipa Bareng – Rampal Celaket

11. Pipa Rampal Celaket – Gading Kasri

Data-data yang didapatkan dari hasil pengamatan yang dilakukan secara

langsung terdapat pada table berikut ini :

No. Pipa Aliran Kapasitas

Aliran Air

1. Pipa Betek – Oro-oro Dowo 135 l/s

2. Pipa Oro-oro Dowo – Kauman 124 l/s

3. Pipa Oro-oro Dowo – Klojen 103 l/s

4. Pipa Kauman – Gading Kasri 105 l/s

5. Pipa Kauman – Rampal Celaket 102 l/s

6. Pipa Betek – Klojen 145 l/s

7. Pipa Klojen – Bareng 121 l/s

8. Pipa Klojen – Rampal Celaket 110 l/s

9. Pipa Bareng – Gading Kasri 70 l/s

10. Pipa Bareng – Rampal Celaket 100 l/s

11. Pipa Rampal Celaket – Gading

Kasri

114 l/s

29

Dengan memisalkan Pipa Aliran, Tandon Kelurahan, dan Kapasitas

Aliran air berturut-turut sebagai sisi, titik, dan bobot. Maka diperoleh

model graph seperti dibawah ini.

4.2 Penyelesaian Masalah dengan algoritma

a. Dengan Menggunakan Algoritma Lintasan Penambah Diperoleh

Sebagai Berikut :

Iterasi 1

1. Pilih Lintasan Penambah (S – A – B – T)

2. Δ = Min {CSA; CAB; CBT} = Min {135;124;105} = 105 l/s

3. CSA*= CSA – Δ = 135 – 105 = 20 l/s dan CAS*= CAS + Δ = 0 + 105 =

105 l/s

CAB*= CAB – Δ = 124 – 105 = 19 l/s dan CBA*= CBA + Δ = 0 + 105 =

105 l/s

CBT*= CBT – Δ = 105 – 105 = 0 l/s dan CTB*= CTB + Δ = 0 + 105 = 105

l/s

S

A B

T

E D

C

135 l/s

124 l/s

103 l/s

105 l/s

102 l/s

70 l/s

145 l/s

121 l/s

110 l/s 100 l/s

114 l/s

105 l/s

105 l/s 105 l/s

S

A B

T

E D

C

30 l/s

19 l/s

103 l/s

0 l/s

102 l/s

70 l/s

145 l/s

121 l/s

110 l/s 100 l/s

114 l/s

30

Iterasi 2

1. Pilih Lintasan Penambah (S – A – B – C – T)

2. Δ = Min {CSA; CAB; CBC; CCT} = Min {30;19;102;114} = 19 l/s

3. CSA*= CSA – Δ = 30 – 19 = 11 l/s dan CAS*= CAS + Δ = 105 + 19 = 124

l/s

CAB*= CAB – Δ = 19 – 19 = 0 l/s dan CBA*= CBA + Δ = 105 + 19 = 124

l/s

CBC*= CBC – Δ = 102 – 19 = 83 l/s dan CCB*= CCB + Δ = 0 + 19 = 19

l/s

CCT*= CCT – Δ = 114 – 19 = 95 l/s dan CTC*= CTC + Δ = 0 + 19 = 19

l/s

Iterasi 3

1. Pilih Lintasan Penambah (S – A – E – C – T)

2. Δ = Min {CSA; CAE; CEC; CCT} = Min {11;103;110;105} = 11 l/s

3. CSA*= CSA – Δ = 11 – 11 = 0 l/s dan CAS*= CAS + Δ = 124 + 11 = 135

l/s

19 l/s

19 l/s

124 l/s

124 l/s

105 l/s

S

A B

T

E D

C

11 l/s

0 l/s

103 l/s

0 l/s

83 l/s

70 l/s

145 l/s

121 l/s

110 l/s 100 l/s

95 l/s

31

CAE*= CAE – Δ = 103 – 11 = 92 l/s dan CEA*= CEA + Δ = 0 + 11 = 11

l/s

CEC*= CEC – Δ = 110 – 11 = 99 l/s dan CCE*= CCE + Δ = 0 + 11 = 11

l/s

CCT*= CCT – Δ = 95 – 11 = 84 l/s dan CTC*= CTC + Δ = 19 + 11 = 30

l/s

Iterasi 4

1. Pilih Lintasan Penambah (S – E – D – T)

2. Δ = Min {CSE; CED; CDC; CCT} = Min {145;121;70} = 70 l/s

3. CSE*= CSE – Δ = 145 – 70 = 75 l/s dan CES*= CES + Δ = 0 + 70 = 70 l/s

CED*= CED– Δ = 121 – 70 = 51 l/s dan CDE*= CDE + Δ = 0 + 70 = 70

l/s

CDT*= CDT – Δ = 100 – 70 = 30 l/s dan CTD*= CTD + Δ = 0 + 70 = 70

l/s

0 l/s

11 l/s

11 l/s

19 l/s

30 l/s

135 l/s

124 l/s 105 l/s

S

A B

T

E D

C

0 l/s

92 l/s

0 l/s

83 l/s

70 l/s

145 l/s

121 l/s

99 l/s 100 l/s

84 l/s

11 l/s

11 l/s

19 l/s

30 l/s

135 l/s

124 l/s 105 l/s

S

A B

T

E D

C

0 l/s

0 l/s

92 l/s

0 l/s

93 l/s

0 l/s

75 l/s

51 l/s

99 l/s 100 l/s

84 l/s

70 l/s

70 l/s

70 l/s

32

Iterasi 5

1. Pilih Lintasan Penambah (S – E – D – C – T)

2. Δ = Min {CSE; CED;CDC; CDT} = Min {75;51;100;84} = 51 l/s

3. CSE*= CSE – Δ = 75 – 51 = 24 l/s dan CES*= CES + Δ = 70 + 51 = 121

l/s

CED*= CED– Δ = 51 – 51 = 0 l/s dan CDE*= CDE + Δ = 70 + 51 = 121

l/s

CDC*= CDC – Δ = 100 – 51 = 49 l/s dan CTC*= CTC + Δ = 0 + 51 = 51

l/s

CCT*= CCT – Δ = 84 – 51 = 33 l/s dan CTC*= CTC + Δ = 30 + 51 = 81

l/s

Iterasi 6

1. Pilih Lintasan Penambah (S – E – C – T)

2. Δ = Min {CSE; CEC; CCT} = Min {24;99;33} = 24 l/s

3. CSE*= CSE – Δ = 24 – 24 = 0 l/s dan CES*= CES + Δ = 121 + 24 = 145

l/s

CEC*= CEC– Δ = 99 – 24 = 75 l/s dan CCE*= CCE + Δ = 11 + 24 = 35 l/s

16 l/s

11 l/s

19 l/s

81 l/s

135 l/s

124 l/s 105 l/s

S

A B

T

E D

C

0 l/s

0 l/s

87 l/s

0 l/s

83 l/s

0 l/s

24 l/s

0 l/s

99 l/s 49 l/s

33 l/s

121 l/s

121 l/s

51 l/s

70 l/s

33

CCT*= CCT – Δ = 33 – 24 = 9 l/s dan CTC*= CTC + Δ = 81 + 24 = 105

l/s

b. Dengan Menggunakan Algoritma Ford-Fulkerson diperoleh

Sebagai Berikut :

Iterasi 1

Pilih lintasan S-E-D-T ,tambah flow sebesar 70 l/s ke setiap sisi pada

lintsan S-E-D-T sehingga terjadi perubahan kapasitas beberapa sisi pada

residual network

Iterasi 2

Pilih lintasan S-E-C-T,tambah flow sebesar 75 l/s ke setiap sisi pada

lintasan S-E-C-T

S

A B

T

E D

C

135 l/s

124 l/s

103 l/s

105 l/s

102 l/s

0 l/s

75 l/s

51 l/s

110 l/s 100 l/s

114 l/s

16 l/s

35 l/s

19 l/s

105 l/s

135 l/s

124 l/s 105 l/s

S

A B

T

E D

C

0 l/s

0 l/s

87 l/s

0 l/s

83 l/s

0 l/s

0 l/s

0 l/s

75 l/s 49 l/s

9 l/s

145 l/s

121 l/s

51 l/s

70 l/s

70 l/s

70 l/s

34

Itarasi 3

Pilih lintasan S-A-B-T,tambah flow sebesar 105 l/s ke setiap sisi pada

lintasan S-A-B-T

Iterasi 4

Pilih lintasan S-A-E-C-T,tambah flow sebesar 30 l/s ke setiap sisi

pada lintasan S-A-E-C-T

Hasil akhir iterasinya

S

A B

T

E D

C

0 l/s

19 l/s

73 l/s

0 l/s

102 l/s

0 l/s

0 l/s

51 l/s

5 l/s 100 l/s

9 l/s

S

A B

T

E D

C

30 l/s

19 l/s

103 l/s

0 l/s

102 l/s

0 l/s

0 l/s

51 l/s

35 l/s 100 l/s

39 l/s

S

A B

T

E D

C

135 l/s

124 l/s

103 l/s

105 l/s

102 l/s

0 l/s

0 l/s

51 l/s

35 l/s 100 l/s

39 l/s

280 l/s

145 l/s

250 l/s

145 l/s

250 l/s

280 l/s

35

4.3 Penyelesaian Masalah dengan alat bantu

Dengan menggunakan algoritma Preflow-Push dari giden diperoleh

sebagai berikut:

1. Buka Giden

2. Klik File ⟶ New

3. Pilih New Node dan posisikan node-node tersebut seperti

gambar berikut

4. Klik Node Data ⟶ Add Data Field... beri nama Field dengan

“titik”, beri nilai awal dengan “0”, ganti tipe data Field dengan

text, klik OK

5. Pilih New Edge dan sambungkan node-node seperti gambar

berikut

30 l/s

105 l/s

0 l/s

105 l/s

135 l/s

105 l/s 105 l/s

S

A B

T

E D

C

0 l/s

19 l/s

73 l/s

0 l/s

102 l/s

0 l/s

0 l/s

51 l/s

5 l/s 100 l/s

9 l/s

145 l/s

70 l/s

0 l/s

70 l/s

36

6. Klik Edge Data⟶Add Data Field... beri nama Field dengan

“bobot”, beri nilai awal dengan “0”, ganti tipe data Field

dengan integer, klik OK

7. Pilih Edit Value dan beri nama/nilai pada masing-masing titik

dan sisi seperti gambar berikut

8. Klik Solvers ⟶ Maximum Flow ⟶ Pre-Flow Push, ganti

kapasitas dengan „‟bobot”

9. Klik Trace ⟶ klik sink ⟶ klik source ⟶ yes

10. Klik Trace berulang kali sampai iterasi berhenti ditandai

dengan berubahnya Trace menjadi Reset

11. Nilai akhir dapat dilihat pada bagian atas seperti pada gambar

berikut

37

4.4Analisis Hasil

Dari permasalahan diatas,untuk memperoleh solusi menggunakan 3

algoritma yaitu algoritma lintasan penambah,algoritma ford-fulkerson dan

algoritma preflow-push.

Pada algoritma lintasan penambah dan algoritma ford-fulkerson

menggunakan penghitungan manual,dimana algoritma lintasan penambah

menghasilkan 6 iterasi.Pada iterasi pertama mengalirkan arus sebesar 105

l/s,iterasi kedua mengalirkan aliran 19 l/s,iterasi ketiga 11 l/s,iterasi keempat

70 l/s,iterasi kelima 51 l/s,dan iterasi keenam 24 l/s.Sedangkan dengan

menggunakan algoritma ford-fulkersen menghasilkan 4 iterasi.Iterasi

pertama mengalirkan arus 70 l/s,iterasi kedua 75 l/s,iterasi ketiga 105 l/s,dan

iterasi keempat 30 l/s.Pada algoritma preflow-push dilakukan penghitungan

dengan menggunakan program giden.

Setelah dilakukan penghitungan baik manual maupundenga program

semuanya menghasilkan arus yang maksimal sebesar 280 l/s.

38

BAB V

KESIMPULAN

5.1 Kesimpulan

1. Pendistribusian air PDAM kota Malang dibagi disetiap tandon-tandon air

yang menampung Debit air yang berasal dari pusat tepatnya di daerah

sawojajar, malang.Tandon-tandon seperti dikelurahan Betek,kelurahan Oro-

oro dowo,kelurahan Gading kasri,kelurahan Kauman,kelurahan Klojen

memiliki kapasitas yang cukup untuk dapat menyuplai debit air di setiap

rumah.Pipa-pipa air yang berdekatan harus saling memenuhi suplai air

sehingga air yang masuk di setiap rumah dapat digunakan untuk kebutuhan

sehari-hari seperti pipa air kelurahan betek dengan pipa air kelurahan

Gading Kasri.Oleh karena itu,disini kita akan menganalisa “Jumlah volume

aliran air dari kelurahan Betek ke kelurahan Gading Kasri dalam

pendistribusiannya” dengan mempertimbangkan aliran air yang masuk

dari setiap jalur pipa yang lain.

2. Dengan adanya data yang ada seperti aliaran air/debit pada setiap jalur pipa

(sisi) dan jalur pipa itu sendiri memudahkan untuk menerapkan algoritma

yang ada pada maksimum flow.Dalam hal ini digunakan algoritma

augmenting path,algoritma ford-fulkerson dan algoritma preflow-push.

3. Dari data yang telah direpresentasikan, selain dapat diselesaikan dengan

menggunakan algoritma yang dihitung secara manual, permasalahn tersebut

juga dapat dihitung menggunakan alat bantu giden sehingga akan

menghasilkan solusi yang sama dengan perhitungan manual

Dari penerapan Algoritma pada permasalahan Tandon PDAM Betek, baik

menggunakan alat bantu program maupun perhitungan manual diperoleh hasil

nilai maximum flow sebesar 280 l/s yang kemudian dikonversikan ke dalam

jumlah volume air/debit air untuk menghasilkan solusi permasalahan yang

diinginkan.

39

40

DAFTAR PUSTAKA

Oktaviana, Sri Syahadatina.2007. Aplikasi Teori Graph dengan Menggunakan

Maximum Flow sebagai Upaya Pengoptimalan Aliran Air pada Jaringan

pipa PDAM Daerah Sawojajar Blok H-1. Skripsi. Universitas Negeri

Malang.

Enni, Elizabeth dan Wuntikaratri, Inu. 2007. Penerapan Graph Kompantibel

dan Maximum Flow dalam Teori Graph pada Lalu Lintas

Kendaraan.Laporan

Rosyidah. 2006. Penerapan Model Maximum Flow dalam Teori Graph pada

Lalu Lintas Kendaraan. Skripsi. Universitas Negeri Malang.

Willson.1990.Graph An Introduction Approach.Canada:Wiley.

http://www.informatika.org/~rinaldi/Stmik/2007-2008/Makalah2008

http://carbon.cudenver.edu/hgreenbe/

http://en.wikipedia.org/wiki/Maximum_flow_problem

41