Selasa, 08 Juni 2010

METODE HUNGARIAN

Metode Hungarian

Adalah suatu metode yang dikembangkan oleh ahli matematika bernama D.Konig asal Hungaria pada tahun 1916, 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 factorial) karena perpasangan satu-satu.

Masalah Minimisasi

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 bahwa sumber daya harus ditugaskan hanya untuk satu pekerjaan, maka ada 6! (6.5.4.3.2.1 = 720) kemungkinan penugasan Dan langkah pemecahannya adalah sebagai berikut :

1. Langkah pertama adalah mengubah matriks biaya menjadi matriks opportunity cost. Ini dicapai dengan memilih elemen terkecil dari setiap baris dari matriks biaya mula-mula untuk mengurangi seluruh elemen (bilangan) dalam setiap baris. Sebagai contoh, Suatu perusahaan kecil mempunyai 4 (empat) pekerjaan yang berbeda untuk diselesaikan oleh 4 (empat) karyawan.Biaya penugasan seorang karyawan untuk pekerjaan berbeda-beda.Matriks pada Tabel 1 menunjukkan biaya penugasan karyawan untuk bermacam-macam pekerjaan. Sebagai contoh A dapat menyelesaikan pekerjaan I pada biaya Rp15,00, pekerjaan II pada biaya Rp20,00, dan seterusnya.

Tabel 1 Matriks Biaya

Pekerjaan

Karyawan

I

II

III

IV

A

B

C

D

Rp 15,00

14,00

25,00

17,00

Rp 20,00

16,00

20,00

18,00

Rp 18,00

21,00

23,00

18,00

Rp 22,00

17,00

20,00

16,00

Elemen terkecil baris A (=15) digunakan untuk mengurangi seluruh elemen (bilangan) dalam setiap baris A.Sehingga paling sedikit akan diperoleh satu elemen yang bernilai nol sebagai hasilnya.Prosedur yang sama diulang untuk setiap baris pada Tabel 3.1 untuk mendapatkan matriks biaya yang telah dikurangi (reduced-cost matriks) seperti yang telah ditunjukkan Tabel 2.

Tabel 2 Reduced-cost matrix

Pekerjaan

Karyawan

I

II

III

IV

A

B

C

D

0

0

5

1

5

2

0

2

3

7

3

2

7

3

0

0

2. Reduced cost-matrix diatas terus dikurangi untuk mendapatkan total-opportunity-cost-matrix.Hal ini dapat dicapai dengan memilih elemen terkecil dari setiap kolom pada reduced-cost matrix untukmengurangi seluruh elemen dalam kolom-kolom tersebut.Pada contoh diatas hanya dilakukan pada kolom III karena semua kolom lainnya telah mempunyai elemen yang bernilai nol.Bila langkah pertama telah menghasilkan paling sedikit satu nilai nol pada setiap kolom, langkah kedua ini dapat dihilangkan.Matrix total-opportunity-cost ditunjukkan dalam Tabel 3.

Tabel 3 Total-opportunity-cost matrix

Pekerjaan

Karyawan

I

II

III

IV

A

B

C

D

0

0

5

1

5

2

0

2

1

5

1

0

7

3

0

0

Dalam contoh total-opportunity-cost matrix pada Tabel 3, terdapat paling sedikit satu nilai nol, dalam setiap baris dan setiap kolom.

3. Langkah berikutnya adalah mencari skedul penugasan dengan suatu total-opportunity-cost nol.Untuk mencapai penugasan ini dibutuhkan 4 (empat) “independent zeros” dalam matrix.Ini berarti setiap karyawan harus ditugaskan hanya untuk satu pekerjaan dengan opportunity cost nol.Prosedur praktis untuk melakukan test optimalisasi adalah dengan menarik sejumlah minimum garis horizontal atau vertikal untuk meliputi seluruh elemen bernilai nol dalam total-opportunity-cost matrix (lihat Tabel 4).Bila jumlah garis sama dengan jumlah baris atau kolom penugasan optimal adalah feasible.Bila tidak sama maka matriks harus direvisi.

Tabel 4 Test for optimality

Pekerjaan

Karyawan

I

II

III

IV

A

B

C

D

0

0

5

1

5

2

0

2

1

5

1

0

7

3

0

0

Dalam Tabel 4 ada tiga baris yang meliput seluruh nilai nol disbanding empat baris atau kolom, sehingga langkah berikutnya diperlukan untuk merevisi matriks.

4. Untuk merevisi total-opportunity-cost matrix,pilih elemen terkecil yang belum terliput garis-garis (yaitu opportunity-cost terendah,atau pada kolom diatas=1) untuk mengurangi seluruh elemen yang belum terliput,kemudian tambahkan dengan jumlah yang sama (nilai elemen terkecil) pada seluruh elemen-elemen yang mempunyai dua garis yang saling bersilangan (5 pada baris C dan 1 baris D) atau sama dengan 6 Dan 2.Masukkan hasil ini pada matriks,dan menyelesaikan matriks dengan seluruh elemen-elemen yang telah terliput tanpa perubahan,ulangi langkah 3.Matriks yang telah direvisi pada Tabel 5 berikut didapatkan dengan mengikuti prosedur diatas.

Tabel 5 Revised matrix dan test for optimality

Pekerjaan

Karyawan

I

II

III

IV

A

B

C

D

0

0

6

2

4

1

0

2

0

4

1

0

6

2

0

0

5. Dalam Tabel 5 dibutuhkan empat garis untuk meliput seluruh nilai nol atau sama dengan jumlah baris atau kolom, sehingga matriks penugasan optimal telah tercapai.Karyawan B ditugaskan untuk pekerjaan I karena baris B hanya mempunyai satu nilai nol pada kolom I.Kolom II berisi satu nol pada baris C, jadi karyawan C ditugaskan untuk pekerjaan III,karena pekerjaan I telah ditugaskan karyawan B.Karyawan D ditugaskan untuk pekerjaan terakhir IV.Skedul penugasan optimal dengan biaya minimum adalah sebagai berikut:

Tabel 6 Skedul Penugasan Optimal

Skedul penugasan

biaya

A-III

B-I

C-II

D-IV

Rp 18,00

14,00

20,00

10,00

Rp 68,00

Secara matematik, masalah penugasan dapat dinyatakan dalam bentuk linier programming sebagai berikut :

n n

Z = CijXij

i = 1 j = 1

Dengan batasan-batasan

n n

Xij = Xij = 1

i = 1 j = 1

dan

Xij 0 ( Xij = X2ij )

dengan keterangan bahwa Cij adalah tetapan yang telah diketahui.

Keterangan : Z = Total biaya distribusi

Cij = Biaya distribusi per unit

Xij = Jumlah barang yang didistribusikan dari sumber (i)

Ketujuan (j)

i = Sumber

j = Tujuan

n = Mesin/barang

1 komentar:

  1. untuk nomor 3 kenapa pada kolom IV tidak di garis? kan memiliki 2 nol, sehingga jika kolom tersebut di garis maka akan optimal, sepertinya ada kekeliruan dalam soal ini, jika saya salah, saya minta penjelasannya, terimakasih

    BalasHapus