Masalah Penugasan

Masalah penugasan adalah masalah pemasangan satu sumber daya dengan tepat satu aktivitas dan satu aktivitas dengan tepat satu sumber daya, yang memenuhi tujuan (yaitu meminimumkan biaya). Masalah penugasan ini merupakan bentuk khusus masalah transportasi dengan n tempat asal dan n tempat tujuan. Penyelesaiannya berupa 1 (dipasangkan) atau 0 (tidak dipasangkan). Walaupun untuk menyelesaikan masalah penugasan ini dapat digunakan metode enumeratif ataupun metode transportasi, tetapi lebih disarankan untuk digunakan metode Hongaria.

1.      Metode Hongaria

Prinsip dari metode Hongaria adalah dengan melakukan manipulasi terhadap matriks biaya yang diberikan. Manipulasi tersebut adalah operasi pengurangan elemen tiap baris dengan elemen minimum barisnya. Kemudian melakukan operasi pengurangan elemen tiap kolom dengan elemen minimum kolomnya. Setelah itu, melakukan pembuatan garis yang melalui elemen-elemen ‘0’. Selanjutnya, dicari elemen minimum pada submatriks yang tidak dilewati garis. Akhirnya, elemen minimum tersebut dikurangkan dari setiap elemen pada submatriks yang tidak dilewati garis dan ditambahkan pada elemen yang dilalui dua garis. Manipulasi terhadap matriks biaya tersebut dilakukan beberapa kali sampai diperoleh matriks biaya optimum, yang dapat diidentifikasi dengan banyaknya garis (yang melalui elemen ‘0’) tepat sama dengan n.

Kasus-kasus yang dapat diselesaikan dengan metode penugasan adalah :

1.      Penugasan beberapa karyawan untuk menyelesaikan beberapa pekerjaan

2.      Beberapa mesin untuk menyelesaikan beberapa pekerjaan

Perhatikan contoh soal berikut ini:

a.       Masalah Minimisasi

Misalkan sebuah perusahaan memiliki 3 tenaga ahli yang berdomisili di tiga daerah. Mereka akan dikirim ketiga daerah lain yang membutuhkan dengan alokasi biaya dalam jutaan. Alokasikan tenaga ahli tersebut sehingga hanya satu tenaga ahli hanya untuk satu lokasi tujuan dengan meminimalisasi biaya perjalanan

        Langkah-langkah penyelesaian dengan metoda hungarian untuk masalah minimisasi adalahh sebagai dberikut :

1)      Ditentukan nilai tekecil dari setiap baris, lalu mengurangi semua nilai dalam bari tersebut dengan nilai terkecilnya.

2)      Diperiksa apakah setiap kolom telah mempunyai nilai nol. Bilasudah dilanjutkan ke langkah 3, bila belum, dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilaii padakolom tersebut dikurangi dengan nilai terkecilnya.

3)      Ditentukan apakah terdapat n elemen nol dimana tidak ada 2 nilai nol yang berada pada baris/kolom yang sama, diamana nadalah jumlah kolom/baris. Jika ada, maka tabel telah optimal, jika tidak dilanjutkan ke langkah 4.

4)      Dilakuukan penutupan semua nol dengan menggunakan garis vertikal horizontal seminimal mungkin.

5)      Ditentukan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Lalu semua nilai yang tidak tertutup garis dikurangi dengan nilai terkecil tersebut, dan nilai yangg tertutup oleh dua garis ditambahkan dengan nilai terkecil tersebut.

6)      Kembali ke langkah 3.