Algoritma Hungaria
Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini.
Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan.
|
Metode Hungaria adalah algoritme optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial.[1] Algoritme ini mudah dimengerti dan diterapkan untuk menyelesaikan soal yang berupa penugasan dengan cara menemukan pemasangan sempurna.[2]
Pada dasarnya, proses algorima ini melibatkan perubahan biaya di dalam array sampai beberapa menjadi nol. Meski begitu, hal ini tidak mempengaruhi hasil optimasi dengan metode ini.
Penjelasan yang mudah
suntingDalam contoh ini, ada empat pekerja: Andre, Budi, Corry, dan Durian. Setiap pekerja bisa melakukan empat tugas yang berbeda: menggosok kamar mandi, menanam bunga, membersihkan lantai, dan melap jendela. Tetapi, setiap pekerja meminta bayaran yang berbeda-beda untuk tugas yang sama. Diilustrasikan dalam tabel di bawah ini:
| Menggosok kamar mandi | Menanam bunga | Membersihkan lantai | Melap jendela | |
|---|---|---|---|---|
| Andre | Rp. 80,000 | Rp. 40,000 | Rp. 50,000 | Rp. 46,000 |
| Budi | Rp. 40,000 | Rp. 70,000 | Rp. 20,000 | Rp. 25,000 |
| Corry | Rp. 30,000 | Rp. 10,000 | Rp. 20,000 | Rp. 30,000 |
| Durian | Rp. 35,000 | Rp. 20,000 | Rp. 25,000 | Rp. 30,000 |
Tujuan atas menyelesaikan soal ini adalah untuk menugaskan pekerjaan untuk setiap individu yang terlibat dan mendapatkan hasil optimal dengan biaya yang paling minim.
Untuk memodifikasi beberapa angka (yang dalam hal ini adalah biaya) menjadi nol, kurangi angka minimal dari setiap kolom dan barisan sampai salah satunya menjadi nol.
Langkah 1
suntingSoal pembagian kerja di atas dapat diubah dalam bentuk matriks, akan tetapi, tabel akan tetap digunakan untuk penjelasan yang lebih jelas, seperti di bawah ini:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 80 | 40 | 50 | 46 |
| B | 40 | 70 | 20 | 25 |
| C | 30 | 10 | 20 | 30 |
| D | 35 | 20 | 25 | 30 |
- Unit angka dalam tabel = 1000 Rupiah
Dalam matriks di atas, kurangi angka minimal dari setiap barisan
| (-) | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| A | (-40) | 40 | 0 | 10 | 6 |
| B | 40 | 70 | 20 | 25 | |
| C | 30 | 10 | 20 | 30 | |
| D | 35 | 20 | 25 | 30 |
Ulangi langkah 1 untuk setiap baris:
| (-) | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| A | (-40) | 40 | 0 | 10 | 6 |
| B | (-20) | 20 | 50 | 0 | 5 |
| C | (-10) | 20 | 0 | 10 | 20 |
| D | (-20) | 15 | 0 | 5 | 10 |
Jumlah total angka minus adalah -90, yang menyatakan bahwa biaya lebih dari Rp. 90,000 ekstra (atau penalti) yang akan dibayar. Jika angka 0 telah diperoleh untuk setiap baris dan kolom, Rp. 90,000 telah menjadi biaya minimum yang tetap. Namun, dalam hal ini belum diperoleh. Maka, langkah-langkah selanjutnya diperlukan.
Langkah 2
suntingSeperti di langkah 1, kurangi angka minimal dari setiap kolom tanpa memperhatikan kolom yang telah mempunyai nilai nol.
| (-) | 1 (-15) | 2 | 3 | 4 (-5) | |
|---|---|---|---|---|---|
| A | (-40) | 25 | 0 | 10 | 1 |
| B | (-20) | 5 | 50 | 0 | 0 |
| C | (-10) | 5 | 0 | 10 | 15 |
| D | (-20) | 0 | 0 | 5 | 5 |
Untuk memperoleh biaya minimal, tambahkan Rp. 15,000 dan Rp. 5,000 yang telah dikurangi dalam kolom 1 dan 4 ke dalam biaya total Rp. 90,000, sehingga biaya total sekarang menjadi Rp. 110,000.
Walaupun sekarang bilangan 0 bisa terlihat di setiap baris dan kolom, pembagian tugas belum bisa dilakukan dengan memilih tugas dengan memilih setiap angka nol untuk setiap orang.
Melihat angka dalam anti-diagonal bernilai 0 kecuali nilai 1 di kolom keempat, pembagian tugas dapat dilakukan dengan syarat biaya total menjadi 111, atau tepatnya Rp. 111,000. Untuk mencari total biaya minimum yang kurang dari itu, penugasan yang sempurna bisa didapat dengan menyusun kembali untuk mendapatkan pemasangan sempurna (perfect matching).
Langkah 3
suntingCobalah untuk membagi tugas supaya biaya penalti menjadi nol. Kalau angka 0 telah diperoleh di dalam setiap baris dan kolom setelah penugasan, algoritme bisa diberhentikan karena penugasan optimal telah diperoleh. Jika tidak, lanjutkan dengan mengambil hanya angka 0 dalam tabel sebelumnya.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 0 | |||
| B | 0 | 0 | ||
| C | 0 | |||
| D | 0 | 0 |
Langkah 4
suntingDengan menggunakan metode di atas, temukan angka minimal dalam setiap garis horizonal dan vertikal yang memiliki nilai nol paling banyak. Dalam soal ini, coret barisan B dan D secara horizontal dan kolom 2 secara vertikal. Setiap barisan atau kolom itu dicoret saat mereka telah dinilai minimal.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 25 | 0 | 10 | 1 |
| B | 5 | 50 | 0 | 0 |
| C | 5 | 0 | 10 | 15 |
| D | 0 | 0 | 5 | 5 |
Langkah 5
suntingModifikasi semua entri di dalam matrix dengan cara mengurangi angka minimum yang didapat dari entri yang tidak termodifikasi. Dalam soal ini, kurangi nilai 1 untuk memperoleh nilai nol dalam anti-diagonal dan tambahkan nilai 1 untuk entri yang tidak tersentuh.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 24 | 0 | 9 | 0 |
| B | 5 | 51 | 0 | 0 |
| C | 4 | 0 | 9 | 14 |
| D | 0 | 1 | 5 | 5 |
Langkah 6
suntingTetapkan pekerjaan berdasarkan angka minimal dari setiap baris.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| A | 24 | 0 | 9 | 0 |
| B | 5 | 51 | 0 | 0 |
| C | 4 | 0 | 9 | 14 |
| D | 0 | 1 | 5 | 5 |
Dalam soal ini, total biaya minimal adalah Rp. 111,000 dengan penugasan:
Andre = melap jendela
Budi = membersihkan lantai
Corry = menanam bunga
Durian = menggosok kamar mandi
Dengan penugasan seperti di atas, biaya minimal dengan melibatkan seluruh individual dengan satu pekerjaan dapat diperoleh.
Referensi
sunting- ^ Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
- ^ http://www.hungarianalgorithm.com/
Bacaan lanjutan
sunting- Van Meter, Rodney. "Optimization Theory (DS2) Lecture #9 Minimum Cost Perfect Matching in Bipartite Graphs and the Hungarian Algorithm." Optimization Theory (DS2) Lecture #9Minimum Cost Perfect Matching in Bipartite Graphs and the Hungarian Algorithm. Shonan Fujisawa Campus, Keio University, 6 Dec. 2016. Web. 24 Jan. 2017.<http://web.sfc.keio.ac.jp/~rdv/keio/sfc/teaching/optimization-theory/optimization-theory-2016/Opt-Lec09-notes-bipartite.html>.