Lutfi Nova Andrieanto (2009) Pencarian perfect matching optimal dalam masalah penugasan dengan menggunakan algoritma Kuhn-Munkres / Lutfi Nova Andrieanto. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Matematika banyak digunakan untuk menyelesaikan permasalahan dalam kehidupan sehari-hari. Salah satu cabang matematika adalah teori graph sedangkan salah satu bahasan yang terdapat pada teori graph adalah matching. Penugasan merupakan permasalahan yang dapat diselesaikan dengan konsep matching. Masalah tersebut diselesaikan dengan menemukan perfect matching maksimal. Pada skripsi ini diberikan metode untuk memperoleh perfect matching maksimal pada graph bipartisi. Graph bipartisi tak berbobot menggunakan metode pencarian perfect matching. Pada metode tersebut suatu perfect matching dikatakan maksimal jika setiap sisi matching meng-saturate setiap titik di X dan tidak ditemukan lagi suatu lintasan augmenting yang berkaitan dengan matching tersebut. Sedangkan pada graph bipartisi berbobot menggunakan algoritma Kuhn-Munkres. Pada prinsipnya proses memperoleh perfect matching pada algoritma Kuhn-Munkres sama dengan proses memperoleh perfect matching pada metode pencarian perfect matching tetapi bedanya pada algoritma ini dimulai dengan suatu feasible vertex labelling yang merupakan sisi yang berbobot maksimum. Contoh penggunaan metode pencarian perfect matching adalah penugasan pada staf pengajar dan contoh penggunaan algoritma Kuhn-Munkres adalah penugasan pemain futsal. Untuk algoritma Kuhn-Munkres pada graph bipartisi berbobot dibuat program bantu dengan menggunakan Borland Delphi 7.0. Dalam program yang memvisualisasikan algoritma Kuhn-Munkres terdapat fungsi random yang akan memilih sembarang matching pada graph bipartisi berbobot sehingga memungkinkan solusi yang diperoleh berbeda-beda. Selain menggunakan program Borland Delphi penyelesaian masalah penugasan pada graph bipartisi berbobot dapat juga menggunakan program WINQSB sebagai pembanding. Dari hasil penyelesaian masalah penugasan pemain futsal pada graph bipartisi berbobot dengan program Borland Delphi yang memvisualisasikan algoritma Kuhn-Munkres dan program bantu WINQSB ternyata diperoleh total bobot yang sama tetapi penugasan yang dihasilkan berbeda.
| 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: | 12 Jan 2009 04:29 |
| Last Modified: | 09 Sep 2009 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/16797 |
Actions (login required)
 |
View Item |