Teori penugasan adalah bagian penting dari matematika terapan dan operasi riset yang digunakan untuk menentukan cara optimal dalam menugaskan sejumlah pekerjaan kepada sejumlah pekerja atau agen dengan tujuan meminimalkan biaya, waktu, atau usaha. Konsep ini sering digunakan dalam bidang manajemen, logistik, ekonomi, dan bahkan teknologi informasi untuk meningkatkan efisiensi dan mengurangi pemborosan sumber daya. Teori penugasan menggunakan matriks biaya atau waktu yang menggambarkan biaya masing-masing pekerja dalam menyelesaikan pekerjaan tertentu. Dengan memahami teori penugasan, kita dapat menentukan kombinasi penugasan yang paling efisien. Artikel ini menyajikan kumpulan contoh soal teori penugasan dan cara penyelesaiannya agar pembaca dapat memahami langkah-langkah dan strategi penyelesaian masalah penugasan dengan mudah.
Baca juga:Download Contoh Soal MAPSI SD Lengkap untuk Kelas 4, 5,
1. Contoh Soal Penugasan Sederhana dan Cara Penyelesaiannya
Soal: Tiga pekerja A, B, dan C harus menyelesaikan tiga tugas 1, 2, dan 3. Biaya pengerjaan masing-masing pekerja:
| 1 | 2 | 3 | |
|---|---|---|---|
| A | 8 | 6 | 10 |
| B | 9 | 12 | 7 |
| C | 14 | 9 | 6 |
| Tentukan penugasan dengan total biaya minimum. | |||
| Cara Penyelesaian: | |||
| Gunakan metode Hungarian: |
- Kurangi setiap baris dengan nilai terkecil pada baris tersebut → A: 2,0,4; B:2,5,0; C:8,3,0
- Kurangi setiap kolom dengan nilai terkecil pada kolom tersebut → kolom 1:0,0,6; kolom 2:0,5,3; kolom 3:4,0,0
- Tentukan penugasan optimal → A → 2, B → 3, C → 1
- Total biaya = 6 + 7 + 14 = 27
2. Contoh Soal Penugasan dengan Matriks 4×4 dan Cara Penyelesaiannya
Soal: Empat pekerja W, X, Y, Z harus menyelesaikan empat tugas A, B, C, D dengan biaya pengerjaan:
| A | B | C | D | |
|---|---|---|---|---|
| W | 9 | 2 | 7 | 8 |
| X | 6 | 4 | 3 | 7 |
| Y | 5 | 8 | 1 | 8 |
| Z | 7 | 6 | 9 | 4 |
| Cara Penyelesaian: |
- Kurangi setiap baris dengan nilai minimum baris → W: 7,0,5,6; X:3,1,0,4; Y:4,7,0,7; Z:3,2,5,0
- Kurangi setiap kolom dengan nilai minimum kolom → kolom A:3,0,1,0; kolom B:0,1,7,2; kolom C:5,0,0,5; kolom D:6,4,7,0
- Tentukan nol optimal dan penugasan → W → B, X → C, Y → A, Z → D
- Total biaya = 2 + 3 + 5 + 4 = 14
3. Contoh Soal Penugasan Waktu dan Cara Penyelesaiannya
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 |
| Cara Penyelesaian: |
- Kurangi setiap baris → P1:2,0,1; P2:1,3,0; P3:0,1,2
- Kurangi setiap kolom → kolom P1:2,1,0 →0,1,0? Periksa → kolom minimal P1=0, P2=0, P3=0
- Tentukan penugasan optimal → P1 → P2, P2 → P3, P3 → P1
- Total waktu = 2 + 2 + 2 = 6 jam
4. Contoh Soal Penugasan dengan Biaya Sama dan Cara Penyelesaiannya
Soal: Dua tugas harus diselesaikan oleh dua pekerja, biaya pengerjaan:
| T1 | T2 | |
|---|---|---|
| P1 | 4 | 4 |
| P2 | 4 | 4 |
| Cara Penyelesaian: |
- Semua biaya sama → penugasan bisa fleksibel.
- P1 → T1, P2 → T2 atau P1 → T2, P2 → T1
- Total biaya = 8
5. Contoh Soal Penugasan Tidak Seimbang dan Cara Penyelesaiannya
Soal: Lima pekerja dan empat tugas, dengan biaya pengerjaan (tugas tidak bisa 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 | – | – | – | – |
| Cara Penyelesaian: |
- Tambahkan kolom nol dummy → membuat matriks 5×5
- Lanjutkan metode Hungarian → tentukan penugasan minimum
- P5 tidak mendapat tugas, penugasan optimal ditemukan dari empat pekerja pertama
6. Contoh Soal Penugasan Biaya Tinggi dan Rendah dan Cara Penyelesaiannya
Soal: Tiga pekerja menyelesaikan tiga tugas, biaya:
| A | B | C | |
|---|---|---|---|
| 1 | 15 | 20 | 30 |
| 2 | 10 | 25 | 20 |
| 3 | 20 | 15 | 25 |
| Cara Penyelesaian: |
- Kurangi setiap baris → 1:0,5,15; 2:0,15,10; 3:5,0,10
- Kurangi setiap kolom → kolom minimal → nol pada posisi optimal
- Tentukan penugasan → 1→A, 2→B, 3→C
- Total biaya = 15 + 25 + 25 = 65
7. Contoh Soal Penugasan Matriks Besar dan Cara Penyelesaiannya
Soal: Empat pekerja dan empat tugas, matriks biaya:
| T1 | T2 | T3 | T4 | |
|---|---|---|---|---|
| P1 | 9 | 2 | 7 | 8 |
| P2 | 6 | 4 | 3 | 7 |
| P3 | 5 | 8 | 1 | 8 |
| P4 | 7 | 6 | 9 | 4 |
| Cara Penyelesaian: |
- Kurangi baris → P1:7,0,5,6; P2:3,1,0,4; P3:4,7,0,7; P4:3,2,5,0
- Kurangi kolom → hasil nol optimal → P1→B, P2→C, P3→A, P4→D
- Total biaya = 2 + 3 + 5 + 4 = 14
8. Contoh Soal Penugasan Biaya Sama pada Baris dan Cara Penyelesaiannya
Soal:
| T1 | T2 | T3 | |
|---|---|---|---|
| W1 | 4 | 4 | 4 |
| W2 | 3 | 3 | 3 |
| W3 | 5 | 5 | 5 |
| Cara Penyelesaian: |
- Pilih penugasan minimal → W2 → T1, W1 → T2, W3 → T3
- Total biaya = 3 + 4 + 5 = 12
9. Contoh Soal Penugasan Biaya Nol Tersebar dan Cara Penyelesaiannya
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 |
| Cara Penyelesaian: |
- Kurangi baris → semua baris sudah memiliki nol
- Kurangi kolom → semua kolom memiliki nol
- Tentukan penugasan optimal → 1→A, 2→B, 3→C, 4→D
- Total biaya = 0 + 0 + 0 + 0 = 0
10. Contoh Soal Penugasan Campuran Biaya dan Waktu dan Cara Penyelesaiannya
Soal: Tiga pekerja dan tiga tugas, matriks biaya dan waktu (digabung sebagai skor):
| T1 | T2 | T3 | |
|---|---|---|---|
| P1 | 8 | 6 | 7 |
| P2 | 5 | 9 | 6 |
| P3 | 7 | 8 | 5 |
| Cara Penyelesaian: |
- Kurangi baris → P1:2,0,1; P2:0,4,1; P3:2,3,0
- Kurangi kolom → tentukan nol optimal
- Penugasan optimal → P1→T2, P2→T1, P3→T3
- Total skor = 6 + 5 + 5 = 16
Kesimpulan
Dari 10 contoh soal teori penugasan dan cara penyelesaiannya di atas, dapat disimpulkan bahwa penguasaan metode Hungarian, reduksi baris dan kolom, serta strategi menentukan nol optimal sangat penting untuk menyelesaikan soal penugasan dengan efisien. Teori penugasan membantu meminimalkan biaya, waktu, dan usaha dalam pekerjaan nyata. Latihan soal ini juga memperkuat kemampuan analisis dan optimisasi sehingga siswa atau praktisi siap menghadapi berbagai persoalan penugasan dalam akademik maupun dunia kerja.
Penulis: Maharani Noeralifa
Post Comment