Apa Itu Assignment Problem?
Jika kamu pernah belajar matematika terapan atau operasi riset, pasti pernah mendengar istilah assignment problem. Assignment problem adalah masalah optimisasi yang fokus pada penugasan sumber daya ke tugas tertentu dengan cara meminimalkan biaya atau memaksimalkan keuntungan.
Misalnya, kamu memiliki beberapa pekerja dan beberapa proyek, dan ingin menugaskan setiap pekerja ke proyek tertentu agar total biaya kerja menjadi paling kecil, atau keuntungan proyek menjadi paling besar.
Masalah ini sering muncul dalam manajemen proyek, logistik, bahkan algoritma komputer. Nah, agar lebih mudah dipahami, mari kita lihat contoh soal assignment problem berikut.
Baca juga:Panduan Santai Tapi Efektif Masuk Dunia Kerja Accessibility Specialist
Contoh Soal Assignment Problem
Studi Kasus 1: Penugasan Pekerja ke Tugas
Misalkan ada 4 pekerja: A, B, C, dan D, dan 4 tugas: T1, T2, T3, T4. Biaya setiap pekerja untuk menyelesaikan masing-masing tugas diberikan dalam tabel berikut:
| T1 | T2 | T3 | T4 | |
|---|---|---|---|---|
| A | 9 | 2 | 7 | 8 |
| B | 6 | 4 | 3 | 7 |
| C | 5 | 8 | 1 | 8 |
| D | 7 | 6 | 9 | 4 |
Tugas kamu: Tentukan penugasan pekerja ke tugas sehingga total biaya minimum.
Langkah-Langkah Penyelesaian Assignment Problem
1. Metode Brute Force (Pencarian Semua Kombinasi)
Cara paling sederhana tapi memakan waktu: cek semua kemungkinan kombinasi pekerja dan tugas.
- Ada 4 pekerja dan 4 tugas → jumlah kombinasi = 4! = 24
- Hitung total biaya setiap kombinasi → pilih yang paling kecil
Kelemahan: metode ini mudah dipahami tapi tidak efisien untuk jumlah pekerja atau tugas yang banyak.
2. Metode Hungarian (Lebih Efisien)
Metode Hungarian adalah algoritma yang dirancang khusus untuk menyelesaikan assignment problem secara efisien. Langkahnya sebagai berikut:
a. Buat Matriks Biaya
Gunakan tabel biaya seperti yang sudah diberikan.
b. Kurangi Baris
- Ambil nilai terkecil pada setiap baris, lalu kurangi seluruh elemen di baris tersebut dengan nilai terkecil itu.
- Hasilnya, setiap baris minimal memiliki angka 0.
c. Kurangi Kolom
- Lakukan hal sama untuk kolom.
- Pastikan setiap kolom memiliki angka 0.
d. Buat Garis Minimum
- Tarik garis horizontal dan vertikal untuk menutupi semua angka 0.
- Jumlah garis minimal = jumlah pekerja (atau tugas).
e. Tentukan Penugasan
- Pilih angka 0 sedemikian rupa sehingga tidak ada dua angka 0 berada pada baris atau kolom yang sama.
- Ini adalah solusi optimal dengan biaya minimum.
Penyelesaian Studi Kasus 1
Setelah menggunakan metode Hungarian (atau bisa juga brute force jika mau cek satu per satu), penugasan optimal bisa ditemukan sebagai berikut:
| Pekerja | Tugas |
|---|---|
| A | T2 |
| B | T3 |
| C | T1 |
| D | T4 |
Total biaya minimum:
A→T2 = 2, B→T3 = 3, C→T1 = 5, D→T4 = 4
Total = 2 + 3 + 5 + 4 = 14
Jadi, total biaya minimum adalah 14. Mudah, kan?
Studi Kasus 2: Assignment Problem dengan Keuntungan
Assignment problem juga bisa memaksimalkan keuntungan. Misal, ada 3 salesman: X, Y, Z dan 3 kota: C1, C2, C3. Keuntungan tiap salesman untuk setiap kota:
| C1 | C2 | C3 | |
|---|---|---|---|
| X | 40 | 60 | 20 |
| Y | 30 | 50 | 70 |
| Z | 20 | 40 | 60 |
Kamu ingin memaksimalkan total keuntungan.
Langkah Penyelesaian
- Untuk memaksimalkan keuntungan, bisa ubah masalah menjadi minimisasi biaya:
Misal, ubah semua angka menjadi maks keuntungan – keuntungan. - Kemudian gunakan metode Hungarian untuk mencari penugasan dengan “biaya” minimum.
- Hasil akhirnya adalah penugasan optimal yang memberikan keuntungan maksimum.
Tips Memahami Assignment Problem
- Kenali Tujuan: apakah ingin minimalkan biaya atau maksimalkan keuntungan.
- Buat Tabel Biaya/Keuntungan: selalu jelas agar mudah diterapkan algoritma.
- Mulai dari Kasus Kecil: jika baru belajar, gunakan 3–4 pekerja/tugas dulu.
- Gunakan Algoritma: Hungarian algorithm lebih cepat daripada brute force untuk kasus besar.
- Latihan dengan Soal Nyata: misalnya penjadwalan pegawai, distribusi logistik, atau pembagian proyek.
Baca juga:Mahasiswa Teknokrat Raih Juara 1 dan Best Presentation di Pesta Ilmiah Sriwijaya 2025
Kesimpulan
Assignment problem adalah masalah optimisasi klasik yang sangat berguna dalam dunia nyata. Dengan memahami tabel biaya, metode brute force, dan Hungarian algorithm, kita bisa menentukan penugasan optimal dengan mudah.
Contoh soal yang sederhana saja bisa membantu memahami konsep ini sebelum menghadapi kasus yang lebih kompleks. Dengan latihan, assignment problem yang awalnya terlihat sulit akan menjadi mudah dan menyenangkan untuk diselesaikan.
Penulis: Emi kurniasih.
