Ismawati, Rifka Amelia (2010) Penerapan algoritma branch and bound dalam memecahkan assignment problem / Rifka Amelia Ismawati. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Kata kunci graph masalah penugasan algoritma branch and bound Salah satu cabang matematika yang banyak berhubungan dengan masalah kehidupan sehari-hari adalah graph. Teori graph merupakan cabang matematika yang aplikasinya banyak dijumpai misalnya pada masalah penugasan. Contoh dari masalah penugasan adalah penugasan karyawan pada suatu perusahaan. Seorang pekerja akan ditugaskan ke tepat satu pekerjaan dan satu pekerjaan hanya boleh dilakukan oleh seorang pekerja saja. Permasalahannya adalah bagaimana meminimumkan total jumlah gaji yang harus dikeluarkan oleh perusahaan. Pada skripsi ini dipelajari tentang bagaimana cara menyelesaikan masalah penugasan dengan menggunakan algoritma branch and bound. Algoritma branch and bound merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status atau proses pencarian pada algoritma ini menggunakan skema algoritma Breadth-First Search (BFS). Pada skema BFS simpul yang dibangkitkan terlebih dahulu adalah simpul yang bertetanggaan dengan simpul akar. Sedangkan pada algoritma branch and bound prinsip pencarian solusinya tidak seperti pada algoritma BFS murni akan tetapi berdasarkan nilai ongkos simpul yang memiliki nilai paling ekstrem (maksimum atau minimum). Selanjutnya untuk mempermudah proses perhitungan maka dalam skripsi ini algoritma branch and bound diimplementasikan ke dalam program komputer dengan bahasa Delphi. Selain dengan menggunakan bahasa Delphi penyelesaian masalah penugasan juga menggunakan program WINQSB dan POM for WINDOWS sebagai pembanding. Dari hasil penyelesaian masalah penugasan dengan menggunakan program Borland Delphi 7.0 yang menvisualisasikan algoritma branch and bound diperoleh hasil penugasan yang sama seperti pada program bantu WINQSB dan POM for WINDOWS.
| 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: | 29 Oct 2010 04:29 |
| Last Modified: | 09 Sep 2010 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17022 |
Actions (login required)
 |
View Item |