REPRESENTASI ALGORITMA KUHN-MUNKRES PADA GRAF BIPARTIT UNTUK MENYELESAIKAN OPTIMAL ASSIGNMENT PROBLEM
SKRIPSI
DESNI RAHMALINA. P 070823014
PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
REPRESENTASI ALGORITMA KUHN-MUNKRES PADA GRAF BIPARTIT UNTUK MENYELESAIKAN OPTIMAL ASSIGNMENT PROBLEM
SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
DESNI RAHMALINA. P 070823014
PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
PERSETUJUAN
JUDUL Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
Medan,
: REPRESENTASI ALGORITMA KUHN-MUNKRES PADAGRAF BIPARTIT : SKRIPSI : DESNI RAHMALINA PULUNGAN : 070823014 : SARJANA (S1) MATEMATIKA : MATEMATIKA :MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Juni 2010
KOMISI PEMBIMBING:
PEMBIMBING 2,
Drs. Sawaluddin, M.IT NIP 195912311998021001
PEMBIMBING 1
Drs. Marwan Harahap,M.Eng NIP194612251974031001
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,
Dr. Saib Suwilo, M,Sc NIP. 196401091988031004
Universitas Sumatera Utara
PERNYATAAN REPRESENTASI ALGORITMA KUHN-MUNKRES PADA GRAF BIPARTIT UNTUK MENYELESAIKAN OPTIMAL ASSIGNMENT PROBLEM
SKRIPSI Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing- masing disebutkan sumbernya.
Medan,
Juni 2010
Desni Rahmalina Pulungan 070823014
Universitas Sumatera Utara
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Allah SWT, dengan limpahan dan karuniaNya skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan.
Ucapan terima kasih saya sampaikan kepada Drs. Marwan Harahap, M.Eng dan Drs. Sawaluddin, M. IT selaku pembimbing pada penyelesaian skripsi ini yang telah
memberikan
panduan
dan
penuh
kepercayaan
kepada
saya
untuk
menyempurnakan kajian ini. Panduan ringkas, padat dan professional telah diberikan kepada saya agar penulis dapat menyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Matematika FMIPA USU Dr. Saib Suwilo, M.Sc dan Drs Henry Rani Sitepu, M.Si, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara,semua dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU, dan rekan-rekan kuliah. Akhirnya, tidak terlupakan kepada orang tua dan semua ahli keluarga dan rekan terdekat saya yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Allah SWT memberikan balasan yang layak.
Universitas Sumatera Utara
ABSTRAK
Semakin meningkatnya kompetisi global menuntut setiap perusahaan untuk meningkatkan kualitas serta efektifitas kinerja karyawannya yang pada akhirnya diharapkan dapat mendongkrak profit ( keuntungan). Salah satu cara yang sering digunakan adalah dengan mengadakan rolling. Sistem ini dapat digunakan untuk mengetahui penempatan terbaik (optimal) bagi karyawan. Pencarian solusi pada optimal assignment problem ini dapat diperoleh dengan menerapkan konsep teori graf. Dalam hal ini permasalahan dinyatakan sebagai graf bipartit khususnya graf bipartit lengkap berbobot yang menerapkan konsep matching, yaitu pencarian matching sempurna dengan bobot paling optimal. Pencarian matching sempurna pada graf bipartit lengkap berbobot mempunyai kemungkinan sebanyak n!. Oleh karena itu mengefisienkan yaitu algoritma optimal tersebut, maka dapat digunakan sebuah algoritma optimasi yaitu algoritma Kuhn-Munkres.
Universitas Sumatera Utara
ABSTRACT
Increasing global competition requires each company to improve the quality and effectiveness of employee performance which in turn is expected to increase profits. One frequently used way is by performing rolling. This system is used to determine the best placement(optimal) for employees. On the optimum placement of some x employees at y type of job, if the number of employees likened equal to the amount of job by considering the optimization benefits.finding solution to optimal assignment problem can be obtained by applying the concept of graphs teory. in this case the problems are stated as a bipartite graph, especially the complete weighted bipartite graph that implements the concept of matching, Search is perfectly matched with the optimal weights. Searching perfectly to the weighted bipertite graph has the possibility of as many as n!. Therefore, the search is inefficient for a large value of n. then to further streamline the search for optimal solutions can be used an optimization algorithm is Kuhn-munkres algorithm.
Universitas Sumatera Utara
DAFTAR ISI
Persetujuan
ii
Pernyataan
iii
Penghargaan
iv
Abstrak
v
Abstract
vi
Daftar Isi
vii
Daftar Tabel
ix
Daftar Gambar
xii
BAB1. PENDAHULUAN
1
1.1 Latar Belakang
1
1.2 Perumusan Masalah
2
1.3 Batasan Masalah
3
1.4 Tujuan Masalah
3
1.5 Kontribusi Penelitian
3
1.6 Tinjauan Pustaka
3
1.7 Metode Penelitian
4
BAB2. LANDASAN TEORI
5
2.1 Himpunan
5
2.1.1 Beda Simetri 2.2 Pengertian Graf 2.2.1 Istilah-istilah dalam Graf
6 7 9
2.2.2 Graf Bipartit
13
2.2.3 Spanning Subgraph
14
2.3 Matching Graf 2.3.1 Matching pada Graf Bipartit
BAB3. REPRESENTASI ALGORITMA KUHN-MUNKRES 3.1 Deskripsi Proble Assignment
16 23
26 26
Universitas Sumatera Utara
3.1.1 Feasible vertex Labeling
28
3.1.2 Equality Subgraph
31
3.2 Algoritma Kuhn- Munkres
33
3.3 Penentuan Bobot Minimum
38
3.4 Implementasi dan Pengujian
51
3.4.1 Tampilan Program dan Hasil Pengujian
BAB4. KESIMPULAN DAN SARAN
52
54
4.1 Kesimpulan
54
4.2 Saran
55
DAFTAR PUSTAKA
56
LAMPIRAN
57
Universitas Sumatera Utara
DAFTAR TABEL
TABEL 3.1 Daftar Nilai Karyawan
26
TABEL 3.2 Daftar Bobot
29
TABEL 3.3 l (y)=0
30
TABEL 3.4 Nilai x Maksimum
30
TABEL 3.5 Feasible vertex labelling dari Graf Bipartit
31
TABEL 3.6 Feasible vertex labelling ke-1
35
TABEL 3.7 Feasible vertex labelling ke-2
37
TABEL 3.8 Daftar kecepatan kinerja tim
39
TABEL 3.9 Bobot W*
40
TABEL 3.10 Feasible vertex labelling ke-1
41
TABEL 3.11 Feasible vertex labelling ke-2
43
TABEL 3.12 l’’
45
TABEL 3.13 l’’’
48
TABEL 3.14 Spesifikasi minimum sistem
51
Universitas Sumatera Utara
DAFTAR GAMBAR . Gambar 2.1 Graf G
8
Gambar 2.2 Simpul Terisolasi
10
Gambar 2.3 Graf Sederhana dan Graf bukan Sederhana
12
Gambar 2.4 Graf Kosong
12
Gambar 2.5 Graf lengkap dengan 4 simpul
13
Gambar 2.6 Graf berbobot
13
Gambar 2.7 Graf bipartit lengkap
14
Gambar 2.8 Graf H (Spanning subgraph dari Graf G)
15
Gambar 2.9 Contoh matching
16
Gambar 2.10 Contoh Simpul unsaturated M
17
Gambar 2.11 Contoh M-augmenting dan M-alternating
18
Gambar 2.12 Graf dengan matching M dan matching M’
19
Gambar 2.13 H= G(M∆M’)
19
Gambar 2.14 Graf G dengan matching M dan matching M’
20
Gambar 2.15 H = G(M∆M’) dari Graf
21
Gambar 3.1 Graf bipartit berbobot
26
Gambar 3.2 Contoh Graf Bipartit berbobot
29
Gambar 3.3 Equality subgraph dari Graf bipartit berbobot
32
Gambar 3.4 Bentuk Flowchart algoritma Kuhn-Munkres
34
Gambar 3.4 Equality subgraph ke-1
36
Gambar 3.5 Sebarang matching M
36
Gambar 3.6 Equality subgraph ke-2
38
Gambar 3.7 Equality subgraph ke-1
41
Gambar3.8 Graf dengan matching M
42
Gambar 3.9 Equality subgraph ke-2
44
Gambar 3.10 Equality subgraph ke-3
46
Gambar 3.11 Matching pada Gl’’
47
Gambar 3.12 Equality subgraph dan sebarang matching
48
Gambar 3.13 Matching sempurna
49
Universitas Sumatera Utara
Gambar 3.14 Permasalahan maksimum
52
Gambar 3.15 Hasil Perhitungan maksimum
52
Gambar 3.16 Permasalahan minimum
53
Gambar 3.17 Hasil perhitungan permasalahan
53
Universitas Sumatera Utara
