Langkah-Langkah Menentukan Biaya Alokasi Minimum
1. Pengurangan Baris
Langkah pertama dalam metode penugasan adalah mengurangi setiap elemen dalam baris dengan nilai terkecil di baris tersebut.
Matriks Awal:
| Mesin | A | B | C | D | E |
|---|---|---|---|---|---|
| a | 9 | 6 | 5 | 4 | 2 |
| b | 7 | 6 | 3 | 2 | 8 |
| c | 6 | 7 | 4 | 5 | 3 |
| d | 2 | 6 | 4 | 9 | 6 |
Matriks Setelah Pengurangan Baris:
| Mesin | A | B | C | D | E |
|---|---|---|---|---|---|
| a | 7 | 4 | 3 | 2 | 0 |
| b | 5 | 4 | 1 | 0 | 6 |
| c | 3 | 4 | 1 | 2 | 0 |
| d | 0 | 4 | 2 | 7 | 4 |
2. Pengurangan Kolom
Langkah kedua adalah mengurangi setiap elemen dalam kolom dengan nilai terkecil di kolom tersebut.
Matriks Setelah Pengurangan Kolom:
| Mesin | A | B | C | D | E |
|---|---|---|---|---|---|
| a | 7 | 0 | 2 | 2 | 0 |
| b | 5 | 0 | 0 | 0 | 6 |
| c | 3 | 0 | 0 | 2 | 0 |
| d | 0 | 0 | 1 | 7 | 4 |
3. Penandaan Nol dengan Garis
Langkah ketiga adalah menandai setiap baris dan kolom yang memiliki nol dengan garis. Jika jumlah garis sama dengan jumlah baris atau kolom, solusi optimal telah ditemukan. Jika tidak, lanjutkan ke langkah selanjutnya.
Dalam matriks di atas, kita menandai baris b dan c serta kolom B dan E. Namun, jumlah garis tidak sama dengan jumlah baris atau kolom, sehingga kita harus melanjutkan ke langkah berikutnya.
4. Pengulangan Langkah Penandaan
Ulangi langkah sebelumnya sampai solusi optimal ditemukan.
Matriks Setelah Penandaan:
| Mesin | A | B | C | D | E |
|---|---|---|---|---|---|
| a | 6 | 0 | 1 | 3 | 0 |
| b | 4 | 0 | 0 | 1 | 5 |
| c | 2 | 0 | 0 | 3 | 0 |
| d | 0 | 0 | 1 | 8 | 3 |
5. Solusi Optimal
Jika jumlah garis sama dengan jumlah baris atau kolom, solusi optimal telah ditemukan. Dalam kasus ini, kita dapat menandai baris a, b, dan c serta kolom B dan E. Jumlah garis sama dengan jumlah baris atau kolom, sehingga solusi optimal telah ditemukan.
Alokasi Optimal:
- Tugas A dialokasikan ke Mesin B dengan biaya Rp6.000,-
- Tugas B dialokasikan ke Mesin D dengan biaya Rp2.000,-
- Tugas C dialokasikan ke Mesin E dengan biaya Rp3.000,-
- Tugas D dialokasikan ke Mesin A dengan biaya Rp2.000,-
Total biaya alokasi minimum adalah Rp6.000 + Rp2.000 + Rp3.000 + Rp2.000 = Rp13.000.
Penjelasan Detail Langkah-Langkah
Pengurangan Baris
Pengurangan baris dilakukan untuk mempermudah proses pengurangan kolom selanjutnya. Setiap elemen dalam baris dikurangi dengan nilai terkecil dari baris tersebut.
Misalnya, untuk baris pertama (a):
- Nilai terkecil di baris a adalah 2.
- Setelah dikurangi, baris a menjadi: [7, 4, 3, 2, 0].
Pengurangan Kolom
Setelah pengurangan baris, kita lakukan pengurangan kolom untuk mempermudah identifikasi elemen-elemen nol yang akan kita tandai.
Misalnya, untuk kolom B:
- Nilai terkecil di kolom B adalah 0.
- Setelah dikurangi, kolom B tetap: [0, 0, 0, 0].
Penandaan Nol dengan Garis
Proses ini penting untuk mengidentifikasi potensi alokasi minimum. Garis horizontal dan vertikal digunakan untuk menandai nol pada matriks.
Penyesuaian Matriks
Jika jumlah garis belum sama dengan jumlah baris atau kolom, kita melakukan penyesuaian pada matriks dengan mengurangi elemen terkecil yang tidak ditandai oleh garis dari elemen-elemen lain yang tidak ditandai.
Contoh Langkah Penyesuaian Matriks
Misalnya, setelah penandaan pertama:
- Kita menemukan bahwa elemen terkecil yang tidak ditandai adalah 1.
- Kurangi 1 dari elemen-elemen yang tidak ditandai oleh garis.
Penandaan Ulang dan Penyelesaian
Proses ini diulang sampai jumlah garis sama dengan jumlah baris atau kolom. Setelah itu, kita dapat menentukan alokasi optimal dan biaya total.
Kesimpulan
Dalam studi kasus ini, kita menggunakan metode penugasan untuk menentukan alokasi minimum lima tugas ke empat mesin. Dengan langkah-langkah yang sistematis dan detail, kita berhasil menemukan alokasi optimal dengan total biaya minimum Rp13.000. Metode ini sangat efektif dan dapat diterapkan dalam berbagai situasi penugasan lainnya untuk mengoptimalkan biaya dan sumber daya.
