Skripsi

Aplikasi teori graph dengan menggunakan maximum flow sebagai upaya mengoptimalkan volume aliran air pada jaringan pipa PDAM daerah Sawojajar blok H-1 / Sri Syahadatina Oktavianty

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 ( 916 ) pada lintasan yang terpilih langkah ketiga kurangkan kapasitas sebesar 916 dan tambahkan aliran sebesar 916 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 Pelabelan Aka 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 Sawojajar Blok H-1. Dengan Algoritma Lintasan Penambah dapat diketahui bahwa aliran dapat dicapai secara maksimum dalam 5 iterasi dengan hasil maximum flow sebesar 13 m3/ jam.

Informasi Detail

DDC

Rs 511.5 SRI a

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2007.

Deskripsi Fisik

xi, 115 hlm. : il. : tab. ; 29 cm

Bahasa

Indonesia

No Reg

01657/KI/07

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2007

Subjek

1. GRAPH, TEORI - APLIKASI
2. AIR, ALIRAN - VOLUME OPTIMAL

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. SUSY KUSPAMBUDI

Lampiran Berkas