Sierra1010′s Blog

Just another WordPress.com weblog

Penyelesaian Masalah Assignment (Penugasan) dengan Menggunakan Metode Hungarian

Assignment problem

Assignment problem adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas (kegiatan), sehingga dengan demikian biaya yang dikeluarkan untuk pelaksanaan penugasan tersebut dapat diminimalkan. Salah satu dalam menyelesaikan persoalan ini adalah dengan menggunakan algoritma Hungarian. Algoritma Hungarian adalah salah satu algoritma yang digunakan untuk menyelesaikan persoalan masalah assignment. Versi awalnya, yang dikenal dengan metode Hungarian, ditemukan dan dipublikasikan oleh Harold Kuhn pada tahun 1955. Algoritma ini kemudian diperbaiki oleh James Munkres pada tahun 1957. Oleh karena itu, algoritma ini kemudian dikenal juga dengan nama algoritma Kuhn-Munkres. Algoritma yang dikembangkan oleh Kuhn ini didasarkan pada hasil kerja dua orang matematikawan asal Hungaria lainnya, yaitu Denes Konig dan Jeno Egervary. Keberhasilan Kuhn menggabungkan dua buah penemuan matematis dari Jeno Egervary menjadi satu bagian merupakan hal utama yang menginspirasikan lahirnya Algoritma Hungarian. Dengan menggunakan algoritma ini, solusi optimum sudah pasti akan ditemukan. Namun untuk hal ini kasusnya dibatasi, yaitu bila ingin menemukan solusi terbaik dengan nilai minimum (least cost search).

Keuntungan terbesar penggunaan algoritma Hungarian adalah kompleksitas algoritmanya yang polinomial. Metode yang digunakan dalam algoritma Hungarian dalam memecahkan masalah sangat sederhana dan mudah dipahami. Penerapannya  bahwa setiap sumber daya harus ditugasklan hanya untuk satu pekerjaan. Untuk suatu masalah penugasan n x n , jumlah penugasan yang mungkin dilakukan sama dengan n! (n faktorial) karena berpasangan satu-satu.

Masalah Minimisasi dalam suatu penugasan pekerjaan

Pada umumnya tingkat keterampilan, pengalaman kerja, latar belakang pendidikan, dan latihan setiap karyawan berbeda-beda.Sehingga dalam waktu penyelesaian pekerjaan yang sama itu berbeda juga. Dalam metode Hungarian sumber daya harus ditugaskan hanya untuk satu pekerjaan. Sebagai contoh, Suatu perusahaan kotak hadiah mempunyai lima pekerjaan yang berbeda, yaitu memotong karton, merekatkan kertas warna, memberi hiasan, merekatkan pita, dan membungkus. Dimana tugas-tugas tersebut akan diselesaikan oleh lima karyawan. Biaya penugasan seorang karyawan untuk masing-masing pekerjaan berbeda-beda.

Data pada table di bawah ini menunjukkan biaya penugasan karyawan perusahaan kotak kado untuk masing-masing  pekerjaan.

Karyawan/ pekerjaan I(Rp) II(Rp) III(Rp) IV(Rp) V(Rp)
A 17.000,00 15.000,00 19.000,00 21.000,00 18.00,00
B 15.000,00 17.000,00 22.000,00 18.000,00 14.000,00
C 26.000,00 21.000,00 24.000,00 21.000,00 19.000,00
D 18.000,00 19.000,00 19.000,00 17.000,00 20.000,00
E 15.000,00 20.000,00 23.000,00 19.000,00 17.000,00

Langkah  pemecahannya adalah sebagai berikut :

selengkapnya…..

  1. Membuat tabel matriks

Bila disederhanakan, maka tabel datanya dapat diubah menjadi tabel matriks di bawah ini

Karyawan/ pekerjaan I II III IV V
A 17 15 19 21 18
B 15 17 22 18 14
C 26 21 24 21 19
D 18 19 19 17 20
E 15 20 23 19 17
  1. Mencari nilai opportunity cost (elemen terkecil) tiap baris
Karyawan/ pekerjaan I II III IV V
A 17 15 19 21 18
B 15 17 22 18 14
C 26 21 24 21 19
D 18 19 19 17 20
E 15 20 23 19 17

3. Menolkan OC

Nilai OC tiap baris digunakan untuk mengurangi tiap elemen dalam baris tersebut. Sehingga paling sedikit akan diperoleh satu elemen yang bernilai nol sebagai hasilnya. Seperti dalam tabel di bawah ini.

Karyawan/ pekerjaan I II III IV V
A 2 0 4 6 3
B 1 3 8 4 0
C 7 2 5 2 0
D 1 2 2 0 3
E 0 5 8 4 2
  1. Cek 0 di kolom

Cek setiap kolom, apakah sudah mengandung elemen 0.

Karyawan/ pekerjaan I II III IV V
A 2 0 4 6 3
B 1 3 8 4 0
C 7 2 5 2 0
D 1 2 2 0 3
E 0 5 8 4 2

Pada kasus ini, kolom ketiga belum mempunyai elemen 0. Untuk itu, dilakukan langkah selanjutnya.

  1. Mencari opportunity cost kolom yang belum mengandung 0 (kolom III)
Karyawan/ pekerjaan I II III IV V
A 2 0 4 6 3
B 1 3 8 4 0
C 7 2 5 2 0
D 1 2 2 0 3
E 0 5 8 4 2

Selanjutnya, tiap elemen di kolom III dikurangi dengan OC kolom

Karyawan/ pekerjaan I II III IV V
A 2 0 2 6 3
B 1 3 6 4 0
C 7 2 3 2 0
D 1 2 0 0 3
E 0 5 6 4 2
  1. Membuat garis bantu
Karyawan/ pekerjaan I II III IV V
A 2 0 2 6 3
B 1 3 6 4 0
C 7 2 3 2 0
D 1 2 0 0 3
E 0 5 6 4 2

Jumlah garis harus = jumlah pekerjaan

Jumlah garis pada tabel di atas adalah empat, jadi masih kurang satu.

  1. Menentukan elemen yang belum dikenai garis bantu, lalu mencari  OC total
Karyawan/ pekerjaan I II III IV V
A 2 0 2 6 3
B 1 3 6 4 0
C 7 2 3 2 0
D 1 2 0 0 3
E 0 5 6 4 2

Elemen yang belum dikenai garis bantu adalah elemen di kolom III baris A,B,C dan di kolom IV baris A, B, dan C. Sedangkan nilai opportunity costnya adalah 2.

  1. Menolkan OC
Karyawan/ pekerjaan I II III IV V
A 2 0 0 4 3
B 1 3 4 2 0
C 7 2 1 0 0
D 1 2 0 0 3
E 0 5 6 4 2
  1. Membuat garis bantu total
Karyawan/ pekerjaan I II III IV V
A 2 0 0 4 3
B 1 3 4 2 0
C 7 2 1 0 0
D 1 2 0 0 3
E 0 5 6 4 2

Tabel sudah optimal, karena jumlah garis = jumlah pekerjaan.

Jadi, berdasrkan tabel dapat dilihat bahwa:

Karyawan A cocok untuk pekerjaan I & II

Karyawan B cocok untuk pekerjaan V

Karyawan C cocok untuk pekerjaan IV & V

Karyawan D cocok untuk pekerjaan III & IV

Karyawan E cocok untuk pekerjaan I

  1. Penugasan optimal

Karyawan A : pekerjaan II (merekatkan kertas warna)

Karyawan B : pekerjaan V (membungkus)

Karyawan C : pekerjaan IV (merekatkan pita)

Karyawan D : pekerjaan III (memberi hiasan)

Karyawan E : pekerjaan I (memotong karton)

10.  Kesimpulan

Jadi, penugasan di perusahaan kotak kado ialah:

Karyawan A mendapat tugas merekatkan kertas warna dengan biaya Rp15.000,00

Karyawan B mendapat tugas membungkus  dengan biaya Rp 14.000,00

Karyawan C mendapat tugas merekatkan pita dengan biaya Rp21.000,00

Karyawan D mendapat tugas memberi hiasan dengan biaya Rp19.000,00

Karyawan E mendapat tugas memotong karton dengan biaya Rp15.000,00

Sumber :  http:// cupzard.blogspot.com/2010/06/metode-hungarian.html

About these ads

July 10, 2010 - Posted by | matematika

2 Comments »

  1. seandainya ada masalah yang matriksnya tidak berbentuk nxn. jdi gimana y mbak…???
    cuz di soal musti di selesaikan dg metode hungarian…
    ap kita mesti bikin jadi nxn(kalo mungkin)
    or dia gx bisa pake hunggarian y mbak..??
    tolong y mbak,,saya dapet tgs nih..

    Comment by Putri | October 31, 2010 | Reply

    • maaf ya…. saya emang jarang blogging akhir2 ne, tugas kuliah numpuk. jadi ga bisa bantu.

      Comment by sierra1010 | December 12, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: