Skripsi

Pencarian perfect matching optimal dalam masalah penugasan dengan menggunakan algoritma Kuhn-Munkres / Lutfi Nova Andrieanto

Abstrak
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.

Informasi Detail

DDC

Rs 511.8 LUT p

Prodi

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

Deskripsi Fisik

ix, 84 hlm : il. : tab. ; 30 cm

Bahasa

Indonesia

No Reg

00172/KI/08

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2007

Subjek

1. ALGORITMA KUHN-MUNKRES
2. PENUGASAN, MASALAH

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. DARMAWAN SATYANANDA

Lampiran Berkas