Pencarian perfect matching optimal dalam masalah penugasan dengan menggunakan algoritma Kuhn-Munkres / Lutfi Nova Andrieanto
| Main Author: | Lutfi Nova Andrieanto |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16797/ |
Daftar Isi:
- Matematikabanyakdigunakanuntukmenyelesaikanpermasalahandalamkehidupansehari-hari.Salahsatucabangmatematikaadalahteorigraphsedangkansalahsatubahasanyangterdapatpadateorigraphadalahmatching.Penugasanmerupakanpermasalahanyangdapatdiselesaikandengankonsepmatching.Masalahtersebutdiselesaikandenganmenemukanperfectmatchingmaksimal.Padaskripsiinidiberikanmetodeuntukmemperolehperfectmatchingmaksimalpadagraphbipartisi.Graphbipartisitakberbobotmenggunakanmetodepencarianperfectmatching.Padametodetersebutsuatuperfectmatchingdikatakanmaksimaljikasetiapsisimatchingmeng-saturatesetiaptitikdiXdantidakditemukanlagisuatulintasanaugmentingyangberkaitandenganmatchingtersebut.SedangkanpadagraphbipartisiberbobotmenggunakanalgoritmaKuhn-Munkres.PadaprinsipnyaprosesmemperolehperfectmatchingpadaalgoritmaKuhn-Munkressamadenganprosesmemperolehperfectmatchingpadametodepencarianperfectmatchingtetapibedanyapadaalgoritmainidimulaidengansuatufeasiblevertexlabellingyangmerupakansisiyangberbobotmaksimum.ContohpenggunaanmetodepencarianperfectmatchingadalahpenugasanpadastafpengajardancontohpenggunaanalgoritmaKuhn-Munkresadalahpenugasanpemainfutsal.UntukalgoritmaKuhn-MunkrespadagraphbipartisiberbobotdibuatprogrambantudenganmenggunakanBorlandDelphi7.0.DalamprogramyangmemvisualisasikanalgoritmaKuhn-Munkresterdapatfungsirandomyangakanmemilihsembarangmatchingpadagraphbipartisiberbobotsehinggamemungkinkansolusiyangdiperolehberbeda-beda.SelainmenggunakanprogramBorlandDelphipenyelesaianmasalahpenugasanpadagraphbipartisiberbobotdapatjugamenggunakanprogramWINQSBsebagaipembanding.DarihasilpenyelesaianmasalahpenugasanpemainfutsalpadagraphbipartisiberbobotdenganprogramBorlandDelphiyangmemvisualisasikanalgoritmaKuhn-MunkresdanprogrambantuWINQSBternyatadiperolehtotalbobotyangsamatetapipenugasanyangdihasilkanberbeda.