Teori penugasan adalah salah satu konsep penting dalam operasi riset dan matematika terapan yang digunakan untuk menentukan cara optimal dalam menugaskan sejumlah pekerjaan ke sejumlah pekerja atau agen. Tujuannya adalah meminimalkan biaya, waktu, atau tenaga dalam menyelesaikan pekerjaan. Salah satu metode yang paling populer untuk menyelesaikan masalah penugasan adalah metode Hungarian, yang dikembangkan oleh Harold Kuhn pada tahun 1955 dan sangat efektif untuk matriks biaya persegi. Metode ini melibatkan reduksi baris dan kolom serta pemilihan nol optimal untuk menentukan kombinasi penugasan terbaik. Dalam artikel ini, akan dibahas contoh soal teori penugasan metode Hungarian beserta jawaban secara lengkap agar pembaca dapat memahami konsep, langkah-langkah, dan penerapannya.
Baca juga:Download Contoh Soal MAPSI SD Lengkap untuk Kelas 4, 5,
1. Contoh Soal Penugasan Sederhana 3×3
Soal: Tiga pekerja A, B, dan C harus menyelesaikan tiga tugas 1, 2, dan 3. Matriks biaya:
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 8 | 6 | 10 |
| B | 9 | 12 | 7 |
| C | 14 | 9 | 6 |
| Tentukan penugasan dengan total biaya minimum menggunakan metode Hungarian. | |||
| Jawaban: | |||
| Langkah 1: Kurangi nilai terkecil di setiap baris: |
- A: 8,6,10 → 8 minimal → baris dikurangi 6 → 2,0,4
- B: 9,12,7 → 7 minimal → 2,5,0
- C: 14,9,6 → 6 minimal → 8,3,0
Langkah 2: Kurangi nilai terkecil di setiap kolom: - Kolom 1: 2,2,8 → minimal = 2 → 0,0,6
- Kolom 2: 0,5,3 → minimal = 0 → tetap 0,5,3
- Kolom 3: 4,0,0 → minimal = 0 → tetap 4,0,0
Langkah 3: Tentukan nol optimal → pilih penugasan: - A → 2, B → 3, C → 1
Langkah 4: Hitung total biaya: 6 + 7 + 14 = 27
Hasil: Penugasan optimal A→2, B→3, C→1, total biaya 27
2. Contoh Soal Penugasan 4×4
Soal: Empat pekerja W, X, Y, Z harus menyelesaikan empat tugas A, B, C, D dengan biaya:
| A | B | C | D | |
|---|---|---|---|---|
| W | 9 | 2 | 7 | 8 |
| X | 6 | 4 | 3 | 7 |
| Y | 5 | 8 | 1 | 8 |
| Z | 7 | 6 | 9 | 4 |
| Jawaban: | ||||
| Langkah 1: Kurangi setiap baris dengan nilai terkecil di barisnya: |
- W: 7,0,5,6
- X: 3,1,0,4
- Y: 4,7,0,7
- Z: 3,2,5,0
Langkah 2: Kurangi setiap kolom dengan nilai terkecil di kolom: - Kolom A: 3,0,1,3 → minimal 0 → 3,0,1,3
- Kolom B: 0,1,7,2 → minimal 0 → tetap 0,1,7,2
- Kolom C: 5,0,0,5 → minimal 0 → 5,0,0,5
- Kolom D: 6,4,7,0 → minimal 0 → 6,4,7,0
Langkah 3: Tentukan nol optimal → W→B, X→C, Y→A, Z→D
Langkah 4: Total biaya = 2 + 3 + 5 + 4 = 14
3. Contoh Soal Penugasan Waktu 3×3
Soal: Tiga pekerja harus menyelesaikan tiga pekerjaan dengan waktu pengerjaan (jam):
| P1 | P2 | P3 | |
|---|---|---|---|
| Pekerja 1 | 4 | 2 | 3 |
| Pekerja 2 | 3 | 5 | 2 |
| Pekerja 3 | 2 | 3 | 4 |
| Jawaban: | |||
| Langkah 1: Kurangi nilai terkecil di tiap baris: |
- P1: 2,0,1
- P2: 1,3,0
- P3: 0,1,2
Langkah 2: Kurangi nilai terkecil tiap kolom: - Kolom 1: 2,1,0 → minimal = 0 → tetap 2,1,0
- Kolom 2: 0,3,1 → minimal = 0 → tetap 0,3,1
- Kolom 3: 1,0,2 → minimal = 0 → tetap 1,0,2
Langkah 3: Pilih nol optimal → P1→P2, P2→P3, P3→P1
Langkah 4: Total waktu = 2 + 2 + 2 = 6 jam
4. Contoh Soal Penugasan dengan Biaya Sama
Soal: Dua pekerja dan dua tugas, biaya:
| T1 | T2 | |
|---|---|---|
| P1 | 4 | 4 |
| P2 | 4 | 4 |
| Jawaban: |
- Semua biaya sama → penugasan fleksibel
- P1→T1, P2→T2 atau P1→T2, P2→T1
- Total biaya = 8
5. Contoh Soal Penugasan Tidak Seimbang 5×4
Soal: Lima pekerja dan empat tugas, biaya (tugas tidak dapat dilakukan = tanda -):
| T1 | T2 | T3 | T4 | |
|---|---|---|---|---|
| P1 | 9 | 2 | 7 | 8 |
| P2 | 6 | 4 | 3 | 7 |
| P3 | 5 | 8 | 1 | 8 |
| P4 | 7 | 6 | 9 | 4 |
| P5 | – | – | – | – |
| Jawaban: |
- Tambahkan kolom dummy → matriks menjadi 5×5
- Lanjutkan metode Hungarian untuk menemukan penugasan optimal
- P5 tidak mendapat tugas, empat pekerja lainnya mendapatkan tugas sesuai biaya minimum
6. Contoh Soal Penugasan Biaya Tinggi dan Rendah 3×3
Soal: Tiga pekerja, tiga tugas:
| A | B | C | |
|---|---|---|---|
| 1 | 15 | 20 | 30 |
| 2 | 10 | 25 | 20 |
| 3 | 20 | 15 | 25 |
| Jawaban: |
- Kurangi tiap baris → 1:0,5,15; 2:0,15,10; 3:5,0,10
- Kurangi tiap kolom → kolom A minimal 0 → nol optimal
- Tentukan penugasan → 1→A, 2→B, 3→C
- Total biaya = 15 + 25 + 25 = 65
7. Contoh Soal Matriks Besar 4×4
Soal:
| T1 | T2 | T3 | T4 | |
|---|---|---|---|---|
| P1 | 9 | 2 | 7 | 8 |
| P2 | 6 | 4 | 3 | 7 |
| P3 | 5 | 8 | 1 | 8 |
| P4 | 7 | 6 | 9 | 4 |
| Jawaban: |
- Reduksi baris dan kolom → P1:7,0,5,6; P2:3,1,0,4; P3:4,7,0,7; P4:3,2,5,0
- Tentukan nol optimal → P1→T2, P2→T3, P3→T1, P4→T4
- Total biaya = 2 + 3 + 5 + 4 = 14
8. Contoh Soal Penugasan Biaya Sama pada Baris
Soal:
| T1 | T2 | T3 | |
|---|---|---|---|
| W1 | 4 | 4 | 4 |
| W2 | 3 | 3 | 3 |
| W3 | 5 | 5 | 5 |
| Jawaban: |
- Pilih penugasan minimal → W2→T1, W1→T2, W3→T3
- Total biaya = 3 + 4 + 5 = 12
9. Contoh Soal Biaya Nol Tersebar
Soal:
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 0 | 2 | 3 | 1 |
| 2 | 2 | 0 | 4 | 3 |
| 3 | 3 | 4 | 0 | 2 |
| 4 | 1 | 3 | 2 | 0 |
| Jawaban: |
- Kurangi baris dan kolom → nol tersebar
- Pilih nol optimal → 1→A, 2→B, 3→C, 4→D
- Total biaya = 0
10. Contoh Soal Penugasan Campuran Biaya dan Waktu 3×3
Soal:
| T1 | T2 | T3 | |
|---|---|---|---|
| P1 | 8 | 6 | 7 |
| P2 | 5 | 9 | 6 |
| P3 | 7 | 8 | 5 |
| Jawaban: |
- Kurangi baris → P1:2,0,1; P2:0,4,1; P3:2,3,0
- Tentukan nol optimal → P1→T2, P2→T1, P3→T3
- Total skor = 6 + 5 + 5 = 16
Kesimpulan
Dari 10 contoh soal teori penugasan metode Hungarian beserta jawaban di atas, terlihat bahwa penguasaan reduksi baris dan kolom serta pemilihan nol optimal adalah kunci dalam menyelesaikan soal penugasan. Metode Hungarian efektif untuk meminimalkan biaya atau waktu dalam penugasan pekerjaan ke pekerja atau agen. Latihan soal ini membantu siswa atau profesional memahami konsep, mengasah kemampuan analisis, dan siap menghadapi masalah nyata dalam logistik, manajemen, maupun operasi riset.
Penulis: Maharani Noeralifa
Post Comment