Danang Triagus Setiyawan ST,MT

Model penugasan adalah salah satu model

kuantitatif untuk mengalokasikan sumber

daya kepada tugas-tugas secara unik (one to

one basis).

Model penugasan merupakan suatu kasus

khusus dari program linear.

Dalam dunia industri, sering terjadi

permasalahan yang berhubungan dengan

penugasan optimal dari bermacam-macam

sumber daya atau personalia untuk tugas

yang bermacam-macam pula.

Tujuan model penugasan adalah mengoptimalkan hasil yang akan dicapai, biasanya meminimalkan biaya operasional ataupun memaksimalkan profit/keuntungan.

Solusi optimal diperoleh ketika satu orang/mesin melakukan tepat satu pekerjaan/proyek dan fungsi tujuan terpenuhi, yaitu minimasi biaya ataupun maksimasi profit.

Metode yang biasa dipakai untuk menyelesaikan model penugasan adalah metode Hungarian (Hungarian Method). Metode ini mula-mula dikembangkan oleh seorang ahli matematika yang berasal dari Hungaria bernama D. Konig pada tahun 1916.

Asumsi yang dipakai dalam metode Hungarian

adalah semua elemen biaya (cij) tak negatif.

Prinsip dasarnya adalah solusi optimal penugasan

tidak terpengaruh jika suatu konstanta

ditambahkan atau dikurangkan dari sebarang

baris atau kolom dari matriks biaya.

Metode Hungarian dibagi menjadi 2 jenis, yaitu:

(1) mencari penugasan untuk menghemat

(meminimalkan) biaya; dan

(2) menugaskan untuk mencari keuntungan

maksimal (tujuan maksimasi).

Salah satu teknik pemecahan masalah penugasan adalah dengan metode Hungarian. Adapun struktur algoritma dari Hungarian adalah sebagai berikut:

Langkah 0: Matriks biaya

Langkah 1: Reduksi baris. Jika diperoleh solusi layak maka berhenti dan

diperoleh solusi optimal. Jika sebaliknya, lanjutkan ke Langkah 2.

Langkah 2: Reduksi kolom. Jika diperoleh solusi layak maka berhenti

dan diperoleh solusi optimal. Jika sebaliknya, lanjutkan ke Langkah 3.

Langkah 3 Modifikasi matriks biaya. Algoritma berhenti apabila telah

diperoleh solusi layak (dan optimal).

Metode Hungarian selain untuk masalah minimasi biaya, dapat digunakan juga untuk masalah maksimasi profit.

Dalam masalah maksimasi,matriks-matriks elemen menunjukkan tingkat keuntungan (indeks produktivitas).

Langkah pertama dalam masalah maksimasi adalah mengubah matriks keuntungan menjadi suatu matriks opportunity loss.

Keuntungan tertinggi akan menjadi nilai 0, sedangkan nilai-nilai dibawahnya akan menjadi selisih dari nilai maksimal dengan nilai tersebut. Hal ini pertama kali dilakukan dengan reduksi baris.

Langkah 0: Matriks biaya

Langkah 1: Reduksi baris. Cara mereduksi adalah dengan

mengurangi nilai terbesar dengan nilai masing-masing nilai pada sel tersebut. Nilai terbesar akan menjadi 0, sedangkan nilai sel lain adalah selisih dari pengurangan nilai terbesar dengan nilai sel tersebut. Jika diperoleh solusi layak maka berhenti dan diperoleh solusi optimal. Jika sebaliknya, lanjutkan ke Langkah 2.

Langkah 2: Reduksi kolom. Cara mereduksi kolom ini dilakukan

untuk kolom yang belum ada nilai 0 nya. Jika diperoleh solusi layak maka berhenti dan diperoleh solusi optimal. Jika sebaliknya, lanjutkan ke Langkah 3.

Langkah 3 Modifikasi matriks biaya. Algoritma berhenti apabila

telah diperoleh solusi layak (dan optimal).