Saputri, Reni Dian (2013) Algoritma capacity scaling dalam menyelesaikan minimum cost flow problem dan implementasi programnya / Reni Dian Saputri. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
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.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 09 Sep 2013 04:29 |
| Last Modified: | 09 Sep 2013 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17193 |
Actions (login required)
 |
View Item |