PENCARIAN PERFECT MATCHING MAKSIMUM PADA GRAPH BIPARTISI BERBOBOT DENGAN MENGGUNAKAN ALGORITMA PRIMAL DUAL MATCHING Siti Muyasaroh1, Sapti Wahyuningsih2, Susy Kuspambudi A3 Universitas Negeri Malang E-mail:
[email protected] Abstrak : Matching merupakan permasalahan yang memasangkan tepat satu. Sedangkan perfect matching di G=(V,E) adalah matching M dengan setiap titik di V terkait dengan tepat satu sisi di M sedangkan matching berukuran maksimum di graph G adalah matching M yang mempunyai ukuran terbesar. Algoritma primal dual matching merupakan salah satu algoritma yang dapat digunakan ke n untuk menyelesaikan permasalahan matching. Pada algoritma primal dual matching, pemilihan sisi ditentukan oleh feasible vertex labeling di man bobot sisi terbesar di pilih untuk dijadikan sisi pada graph baru. Penerapan algoritma primal dual matching pada permasalahan matching dapat memperoleh solusi yang optimum. Hal ini terjadi karena pemilihan sisinya ditentukan dengan memilih sisi yang mempunyai sisi yang memiliki bobot maksimum. Selain itu, algoritma primal dual matching lebih efisien di banding algoritma lain karena pencarian perfect matching lebih cepat. Kata Kunci: Algoritma Primal Dual Matching, Matching, Perfect Matching Maksimum Abstract: Matching is a problem that pairing the right one. While perfect matching in G = (V, E) is a matching M with every point in V associated with exactly one sided in M while the maximum size matching in graph G is matching M that has the largest size. Primal dual matching algorithm is one of algorithms which can be used to n to resolve matching problems. In the primal dual matching algorithm, the selection of the feasible vertex labeling is determined by the weight of the largest in the man chosen to be on the side of the new graph. Application of primal dual algorithm matching the matching problem can obtain the optimum solution. This occurs because the selection is determined by choosing the side that has the side that has the maximum weight. In addition, primal dual matching algorithm more efficient than other algorithms for perfect matching search faster. Keywords: Primal Dual Algorithm Matching, Matching, Perfect Matching Maximum Matching merupakan permasalahan dengan ketentuan berpasangan tepat satu-satu, misalnya saja pada masalah penugasan, penjodohan dan masalah pengujian obat. Perfect matching di G=(V,E) adalah matching M dengan setiap titik di V terkait dengan tepat satu sisi di M sedangkan matching maksimum adalah matching berukuran maksimum di G adalah matching M yang mempunyai ukuran .Pada artikel ini membahas penyelesaian permasalahan Matching dengan menggunakan algoritma primal dual matching. Untuk menyelesaikan permasalahan matching dapat digunakan berbagai algoritma, diantaranya adalah algoritma path augmenting dan algoritma greedy. Algoritma primal dual matching merupakan algoritma yang dapat memperluas atau memprsempit matching dari batasan-batasan yang ada, sehingga terdapat beberapa alternatif dalam menentukan solusi. Algoritma primal dual matching diawali dengan pemilihan feasible vertex labeling di mana sisi yang memiliki bobot maksimum terpilih untuk dijadikan graph baru.Untuk mambahas permasalahan ini, diperlukan formulasi sebagai berikut :
Primal Variabel
didefinisikan sebagai berikut 1, jika sisi (i,j) adalah sisi matching 0, jika sisi (i,j) adalah bukan sisi matching
Untuk memaksimalkan matching , berdasarkan teori dualitas maka diproleh ∑ fungsi tujuan : Dengan batasan-batasan sebagai berikut : ∑
∑
Dalam hal ini, 1 merupakan banyaknya kapasitas sumber yang diharapkan sedangkan Dual Untuk meminimalkan banyaknya titik yang terkait pada sisi matching, berdasarkan teori ∑ dualitas diperoleh fungsi tujuan : adalah titik yang terkait pada sisi matching Batasan-batasan
Keterangan : : sisi yang terhubung : bobot sisi : titik sumber : titik tujuan : titik yang terkait dengan matching : titik yang terkait yang berada di himpunan titik : titik yang terkait yang berada di himpunan titik Hasil yang diharapkan Hasil yang diharapkan pada artikel ini adalah dengan primal dual matching dapat menghasilkan alternatif solusi yang lebih bervariasi. Algoritma primal dual matching juga dapat menghasilkan solusi yang optimum karena memasangkan sisi yang mempunyai bobot yang maksimum. Algoritma primal dual matching dapat lebih efektif dan efisien dari pada algoritma lain karena pada pemilihan sisi hanya dilakukan pada sisi yang nilai feasible vertex labelling-nya sama dengan nol. Pembahasan Algoritma Primal Dual Matching pada Matching Berdasarkan pada Penyelesaian permasalahan matching dengan menggunakan algoritma primal dual matching melalui beberapa langkah. Langkah – Langkah penyelesaian yang dimaksud yaitu : Langkah I 1. Gambar graph bipartisi 2. Representasikan bobot ke dalam matrik berbobot 3. Definisikan y sebagai feasible vertex labeling dengan ( ) , Bentuk tabel untuk mempermudah pemberian feasible vertex labeling
Langkah II : primal Step 4. Bangun graph Gy , di mana Gy=( ) | ( ) } 5. Pilih sembarang Mathing M di Gy dengan menggunakan algoritma path augmenting, jika tidak ditemukan titik bebas dan sisinya insident maka M adalah perfect matching. Jika tidak, bentuk : kemudian himpun { } lanjutkan ke Dual step Langkah III : Dual Step 6. Cari nilai , di mana 7. Perluas dengan
{
8. Perbesar matching M dengan menggunakan path augmenting kemudian cari sehingga menghasilkan perfect matching maksimum M* dengan ∑ nilai dual ∑ , jika belum perfect matching maksimum maka kembali ke langkah 7 Contoh Permasalahan matching menggunakan algoritma primal dual matching Sebagai gambaran pembahasan permasalahan Matching menggunakan algoritma primal dual matching, diberikan contoh permasalahan beserta penyelesaiannya yaitu : Misalkan jika terdapat pelamar kerja sebanyak 4 orang dan 4 posisi kerja yang diinginkan, seperti yang digambarkan pada tabel di bawah ini : Tabel 1 pelamar kerja dan posisi kerja
Nama Pelamar Kerja Aziz Fuad Rama Andri
Posisi Kerja Marketing Admin Customer Service HRD
Untuk menentukan perfect matching maksimum dari graph G pada Gambar 3.1 diatas dipergunakan algoritma primal-dual oleh Mohammad R. Salavatipour. Langkah-langkah penyelesaiannya adalah sebagai berikut : Langkah I 1. Representasi graph
A
B
a 1 a
b
1 7
2
1
8 0 8 6 5
9 a 3 a
2
5 7
6
b
b
8
3
6
b
4
4
Gambar 1 : Reperentasi Graph
2. Representasi matrik berbobot 6 10 5 8 7
9
6 9
8
5
8 6
(8 7 8 6) 3. Dengan menggunakan feasible vertex labeling diperoleh tabel sebagai berikut Tabel 2 : feasible vertex labelling
yai
ybj
6
10
5
8
10
7
9
6
9
9
8
5
7
6
7
8
8
6
8 8
0
0
0
0
Langkah II : Primal Step 4. Membangun graph Gy , di mana Gy= ( ) , sehingga diperoleh matrik baru berikut : 6 0 5 8 7 0 6 0 0 5 0 6 (0 7 0 6) A a1
B b1 b2
a2
b3
a3 a4
b4 Gambar 2 : Hasil iterasi primal 1
5. Dengan menggunakan algoritma path aughmenting diperoleh M = {(a1,b2),(a2,b4),(a4,b3)}
A
B
a1
b1
a2
b2 b3
a3 a4
b4 Gambar 3: hasil iterasi primal 2
karena masih ada titik bebas maka ditemukan S = {a3}, : maka L = {a3-b3-a4} dilanjutkan ke dual step Langkah III : Dual step 6. Karena diperoleh L = {a3-b3-a4} sehingga untuk menghitung adalah
7. Diperoleh nilai minimum
Sehingga pilih sisi
adalah
= 1,untuk
Maka :
ditambahkan ke Ey.
8. Ditemukan path augmenting P = {(a3,b3),(a4,b3),(a4,b1)}, dengan M = {(a1,b2),(a2,b4),(a4,b3)} sehingga
Tabel 3: hasil iterasi akhir
yai
ybj
5
0
6
8
10
7
9
6
9
9
8
5
0
6
8
0
7
8
6
7
1
0
0
0
Dari tabel di atas diperoleh : ∑ Nilai Dual : ∑ ∑ Karena ∑ matching maksimum dengan M*={
dan semua sisi incident maka diperoleh perfect }
A
B
a 1 a 2
7
a
1
8 0 8 6 5
9
a 3
b
1
2
5 7
6
b
b
8
3
6
b
4
4
Gambar 4 : hasil iterasi terakhir
Analisa Algoritma Primal Dual Matching pada Matching Permasalahan matching menggunakan algoritma primal dual matching dimulai dengan pemilihan feasible vertex labelling yaitu dengan mencari sisi yang memiliki bobot maksimum. Proses pencarian perfect matching relatif cepat karena adanya pemilihan sisi dengan tidak akan terpilih lagi untuk iterasi selanjutnya,dan langsung ditemukan perfect matching. Selain itu, langkah pencarian perfect mathing maksimum sangat unik karena terdiri dari beberapa step, sehingga hasil yang diperolehpun lebih optimal. Namun, dalam proses penyelesaiannya algoritma primal dual membutuhkan ketelitian dalam menghitung banyaknya sisi dan menentukan titik yang memiliki sisi minimum. Algoritma ini juga tidak bisa berdiri sendiri dalam pencarian matching.
Kesimpulan dan Saran 1. Untuk menentukan perfect matching maksimum pada graph bipartisi berbobot dapat digunakan algoritma primal dual matching . Pencarian dengan menggunakan algoritma ini dimulai dengan langkah mencari bobot terbesar untuk dijadikan Graph baru dalam proses pencarian matching maksimum dalam primal step, jika matching yang ditemukan belum perfect matching maka bentuk : kemudian himpun { } kemudian pencarian tetap dilanjutkan sampai ke dual step. Selanjutnya adalah menghitung nilai , di mana ,Perluas dengan {
2.
Dari perhitungan memperbesar matching M dengan menggunakan algoritma greedy atau algoritma path augmenting kemudian cari sehingga ∑ menghasilkan perfect matching maksimum M* dengan nilai dual ∑ Algoritma primal dual matching dapat diterapkan dalam beberapa kasus. Salah satu kasus yang diterapkan pada artikel ini adalah pada kasus penempatan karyawan. Dalam algoritma primal dual matching, proses graph pencarian perfect matching maksimum dengan menggunakan algoritma primal dual matching relatif lebih cepat hal ini dikarenakan pada algoritma primal dual matching penghitungan selisih bobot sisi minimum yang nantinya tidak dapat dipilih kembali sehingga proses menenentukan perfect matching lebih cepat. Sedangkan kelemahannya adalah membutuhkan ketelitian yang lebih dalam menghitung dan menentukan titik yang memilki sisi paling minimum serta algoritma ini membutuhkan algoritma lain dalam penyelesaiannya. Namun algoritma ini merupakan metode alternatif dalam menyelesaikan masalah matching pada graph bipartisi khususnya graph bipartisi lengkap maupun tidak lengkap.
Daftar Rujukan Slavatipour,Mohammad R. 2009. Primal Dual Matching Algoritma and Non-Bipartite Graph.Journal Mathematic,CMPUT675 Wolsey, Laurence A. 1998. Integer Programing. John Willy and Sons.Inc.Canada
