Skripsi

Algoritma capacity scaling dalam menyelesaikan minimum cost flow problem dan implementasi programnya / Reni Dian Saputri

Abstrak
Saputri Reni Dian. 2013. Algoritma Capacity Scaling dalam Menyelesaikan Minimum Cost Flow Problem dan Implementasi Programnya. Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I) Dra. Sapti Wahyuningsih M.Si (II) Darmawan Satyananda S.T M.T Kata Kunci minimum cost flow capacity scaling algoritma capacity scaling 12288 12288 12288 12288 Teori graph merupakan salah satu cabang ilmu matematika yang memiliki banyak aplikasi dalam kehidupan sehari-hari. Salah satu penerapan graph yang sering digunakan adalah masalah optimalisasi biaya pengiriman barang dari produsen ke konsumen. Minimum cost flow adalah permasalahan menentukan biaya minimum yang digunakan untuk mendistribusikan barang dari produsen atau distributor ke konsumen. 12288 12288 12288 12288 Algoritma capacity scaling ini dapat digunakan untuk menyelesaikan permasalahan maximum flow dengan melakukan penskalaan terhadap kapasitas sisinya. Permasalahan minimum cost flow juga memiliki kapasitas pada setiap sisinya sehingga algoritma capacity scaling ini akan dikembangkan dalam menyelesaikan permasalahan minimum cost flow. Ide dari algoritma capacity scaling ini adalah dengan menambahkan aliran sepanjang lintasan yang memiliki kapasitas sisa cukup besar yang telah ditetapkan. 12288 12288 12288 12288 Algoritma capacity scaling ini dimulai dengan menginisialisasi semua aliran dengan nol. Dilanjutkan dengan pencarian nilai dengan menggunakan data kapasitas terbesar . Adapun rumus mencari adalah . Jika dari perhitungan diperoleh maka dapat dilanjutkan pada langkah selanjutnya yakni pencarian lintasan terpendek yang akan ditambahkan aliran sebanyak . Namun jika hasil perhitungan menunjukkan bahwa maka algoritma berhenti. Pencarian lintasan terpendek pada algoritma capacity scaling ini menggunakan bantuan dari Algoritma Dijkstra. 12288 12288 12288 12288 Dari analisis contoh (4 titik 8 titik 34 titik serta 44 titik) yang telah dikerjakan menggunakan Algoritma capacity scaling serta algoritma penghapusan sikel dan algoritma lintasan terpendek Berulang sebagai algoritma pembanding diperoleh biaya minimum yang sama. Perbedaan yang mendasar dari algoritma capacity scaling dengan algoritma penghapusan sikel dan algoritma lintasan terpendek berulang adalah pada penskalaan kapasitas sisinya sehingga alirannya bergantung dari hasil penskalaan tersebut. Pada skripsi ini dibuat alat bantu dengan menggunakan bahasa pemrograman Delphi. Program ini dibuat untuk mengatasi permasalahan jaringan yang memiliki banyak titik. Dari program ini dapat diketahui aliran yang mengalir pada masing-masing sisi yang terdapat pada jaringan sehingga didapatkan biaya yang minimum.

Informasi Detail

DDC

Rs 511.8 SAP a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

x, 140 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

04028/KI/13

Edisi

Skripsi (Sarjana)-- Universitas Negeri Malang, 2013

Subjek

1. ALGORITMA

Pembimbing

1. Sapti Wahyuningsih ; 2. Darmawan Satyananda

Lampiran Berkas