MODIFIKASI METODE HUNGARIAN UNTUK PENYELESAIAN MASALAH PENUGASAN Idris1*, Endang Lily2, Sukamto2 1
Mahasiswa Program S1 Matematika 2 Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Binawidya Pekanbaru (28293), Indonesia *
[email protected]
ABSTRACT This paper discusses a new method resulting from the Hungarian method modification to solve an assignment problem. This new method uses one of the basic properties of determinant to reduced the cost matrix in assignment problem to obtain the optimal solution. This method can be utilized for different types of assignment problem with minimize or maximize objective functions. Keywords: assignment problem, Hungarian method, linear programming ABSTRAK Pada artikel ini dibahas mengenai bagaimana cara menyelesaikan suatu persoalan penugasan dengan menggunakan metode baru yang dihasilkan dari modifikasi metode Hungarian. Metode baru ini menggunakan salah satu sifat dasar determinan matriks untuk mereduksi matriks biaya pada persoalan penugasan sehingga mendapatkan solusi yang optimal. Metode ini dapat digunakan untuk berbagai jenis masalah penugasan, baik untuk masalah minimisasi maupun masalah maksimisasi. Kata kunci: masalah penugasan, metode Hungarian, program linear.
1
1. PENDAHULUAN Masalah penugasan (assigment problem) adalah masalah khusus dari program linear yang mirip dengan masalah transportasi. Perbedaannya adalah setiap penawaran pada setiap sumber dan permintaan pada setiap tujuan dibatasi hanya satu unit saja. Untuk menyelesaikan masalah penugasan ini dapat digunakan metode transportasi, tetapi pada umumnya diselesaikan dengan menggunakan metode Hungarian. Pada metode Hungarian diuraikan untuk setiap baris atau kolom pada matriks biaya dikurangi oleh elemen terkecil pada masing-masing baris atau kolom. Proses ini dapat dilakukan berulang–ulang sehingga ditemukan sebuah elemen nol pada setiap baris dengan kolom yang berbeda. Dalam artikel ini, penulis mengusulkan suatu metode baru yang terdapat pada artikel yang ditulis oleh Basirzadeh, 2012 [2, h. 2347] yang berjudul “Ones Assignment Method for Solving Assignment Problem”. Diharapkan metode baru ini dapat menjadi alternatif untuk menyelesaikan masalah penugasan.
2. MASALAH PENUGASAN Masalah penugasan ini muncul pada kasus membuat keputusan siapa dari n operator yang harus mengoperasikan masing-masing satu mesin dari unit mesin, sehingga mendapatkan hasil total biaya masalah penugasan yang optimum. 2.1 Bentuk Masalah Penugasan Masalah penugasan muncul pada kasus membuat keputusan siapa dari n operator yang harus mengoperasikan masing-masing satu mesin dari unit mesin, sehingga mendapatkan hasil total biaya masalah penugasan yang minimum.
Operator
Mesin 3
1
2
1
c11
c12
c13
2 3
c 21
c 22
c 23
c31 c n1
c32 cn 2
c33 cn3
n
n
c1n c2n c3n c nn
Gambar 1. Biaya Penugasan Operator. Misalkan 0, jika operator i tidak ditugaskan ke mesin j. = 1, jika operator i ditugaskan ke mesin j. Selanjutnya permasalahan penugasan pada Gambar 1 dapat dibentuk ke dalam program linear sebagai berikut [8, h. 226] :
2
(1) dengan batas–batas = 1,
(2)
= 1,
(3) ,
Dengan persamaan (1) menunjukkan menunjukkan fungsi obyektif, persamaan (2) adalah batasan penawaran dan persamaan (3) adalah kendala permintaan. 2.2 Metode Hungarian Metode Hungarian dikembangkan oleh seorang ahli matematika berkebangsaan Hungarian yang bernama D Konig pada tahun 1916 [5, h. 109]. Melalui metode Hungarian fungsi obyektif dari persoalan penugasan direduksi dengan cara mengurangi tiap elemen pada masing-masing baris dan kolom dengan elemen tekecil yang ada pada masing-masing baris dan kolom tersebut untuk mendapatkan solusi optimal pada persoalan penugasan.
3. MODIFIKASI METODE HUNGARIAN Metode alternatif ini menggunakan salah satu sifat dasar determinan matriks untuk mereduksi matriks penugasan. Selanjutnya untuk menguraikan metode tersebut terlebih dahulu diuraikan beberapa teori matriks yang akan digunakan untuk membentuk sebuah matriks biaya pada persoalan penugasan. 3.1 Determinan Matriks Definisi 3.1 [1, h. 77] Jika matriks , , maka didefinisikan minor elemen ditulis yaitu determinan matriks setelah baris ke-i dan kolom ke-j dieleminasi. Selanjutnya, didefinisikan dengan adalah kofaktor elemen . Melalui Definisi 3.1 dapat dibentuk determinan matriks seperti yang diuraikan pada Definisi 3.2. Definisi 3.2 [1, h. 79] Determinan matriks yang berukuran dapat dihitung dengan mengalikan elemenelemen dalam suatu baris atau kolom dengan kofaktor-kofaktornya dan menambahkan hasil-hasil kali yang dihasilkan untuk setiap , maka dapat ditulis sebagai berikut: , ( untuk kofaktor sepanjang kolom ke-j )
3
dan . ( untuk kofaktor sepanjang baris ke-i ) Proposisi 3.1 [2, h. 2349] Misalkan adalah matriks dan adalah determinan matriks tidak nol. Jika adalah faktor pada baris ke-i dari , maka dan
adalah matriks
yang telah dieleminasikan faktor
nya.
Bukti Misalkan > 0 adalah faktor baris ke-k dari matriks = dengan sehingga elemen-elemen baris ke-k adalah , , ..., . Dengan demikian diperoleh, = = = ( ) , dengan = ( ) adalah matriks yang telah dieleminasi faktor nya. Selanjutnya, Proposisi 3.1 juga menunjukkan jika masing-masing adalah faktor-faktor baris ke-i, dari matriks , maka dan adalah matriks masing dari baris ke-i,
yang telah dieleminasi faktor .■
masing-
Proposisi 3.2 [ 2, h. 2349] Misalkan adalah matriks dan adalah determinan matriks tidak nol. Jika adalah faktor pada baris ke-i dari matriks , dan > 0 adalah faktor kolom ke-l dari matriks . Maka berdasarkan proposisi 3.1 didapat, dengan adalah matriks faktor dari tiap kolomnya.
yang telah dieleminasi faktor
dari tiap barisnya dan
Bukti Misalkan = ( ) adalah matriks A yang telah dieleminasi nya, dan > 0 adalah faktor kolom ke-l dari matriks . Sehingga elemen-elemen kolom ke-l adalah , , ..., . Dengan demikian diperoleh, = = = (
) ,
4
Berdasarkan Proposisi 3.1 diperoleh adalah matriks yang telah dieleminasi faktor
, sehingga dan faktor nya.■
. Dan
3.2 Modifikasi Metode Hungarian Di bagian ini diuraikan metode baru untuk mereduksi matriks yang termuat pada masalah penugasan, sehingga pada fungsi obyektif dicapai nilai optimal. Metode ini menggunakan salah satu sifat determinan matriks untuk memperoleh solusi optimal masalah penugasan. Pemecahan optimal dari persoalan penugasan pada persamaan (1) tidak berubah jika pada baris atau kolom matriks biaya dibagi atau dikali dengan sebuah konstanta. Hal ini dapat dibuktikan sebagai berikut : Jika setiap elemen dari baris ke-i dan kolom ke-j masing-masing dibagi dengan dan , elemen biaya yang baru menjadi . Ini menghasilkan fungsi tujuan yang baru.
dengan dan . maka diperoleh konstanta. Ini menunjukkan bahwa minimisasi fungsi tujuan menghasilkan pemecahan yang sama dengan minimisasi . 3.2.1 Masalah Minimum Jika adalah elemen terkecil dari baris
pada matriks biaya
maka diperoleh hasil reduksinya
5
dan ditulis
dengan
,
Jika pada matriks dengan kolom berbeda kolom matriks ditulis,
Dari matriks
dengan
belum ditemukan elemen 1 pada maka ditentukan elemen terkecil
setiap baris pada setiap
diperoleh hasil reduksinya,
=
,
proses reduksi dapat dilakukan berulang–ulang sehingga diperoleh nilai total minimum, yaitu elemen setiap baris dengan kolom berbeda memiliki elemen 1. 3.2.2 Masalah Maksimum Pada masalah maksimum proses reduksi matriks biaya sama dengan proses masalah minimum, tetapi faktor baris dan kolom ditentukan oleh elemen terbesar.
6
4. CONTOH PERSOALAN PENUGASAN Sebuah perusahaan memiliki lima orang karyawan yaitu , dan yang akan mengerjakan lima jenis pekerjaan yaitu 1, 2, 3, 4 dan 5. Adapun biaya keuntungan karyawan mengerjakan pekerjaan ke-j dimana disajikan dalam bentuk matriks biaya penugasan sebagai berikut:
Tentukan produk apa yang harus dijual tiap karyawan agar diperoleh keuntungan maksimum. Penyelesaian : Langkah 1. Tentukan elemen terbesar pada masing-masing baris, dan tuliskan di kanan matriks tersebut. maks
Langkah 2. Kemudian bagi tiap elemen pada masing-masing baris dengan elemen yang bernilai paling besar pada baris tersebut. Sehingga didapat
karena belum terdapat elemen 1 pada tiap baris dengan kolom berbeda, maka lanjutkan le langkah selanjutnya. Langkah 3. Tentukan elemen terbesar pada masing-masing kolom dan tuliskan di bawah matriks tersebut.
7
Langkah 4. Kemudian bagi tiap elemen pada masing-masing kolom dengan elemen yang bernilai paling besar pada kolom tersebut. Sehingga didapat
selanjutnya, periksa apakah telah terdapat elemen 1 pada masing-masing baris dengan kolom yang berbeda.
Karena belum ditemukan elemen 1 pada tiap baris dengan kolom yang berbeda, maka lanjutkan ke langkah selanjutnya. Langkah 5. Tarik beberapa garis yang melewati tiap elemen 1. Namun jumlah garis yang terbentuk harus seminimal mungkin.
Kemudian pilih elemen yang bernilai paling besar yang tidak terlewati oleh garis, dalam persoalan ini adalah 0.83. Lalu gunakan nilai tersebut untuk membagi semua nilai yang berada pada kolom yang sama dengan elemen yang memiliki nilai paling besar tersebut, pada persoalan ini yaitu kolom ketiga. Sehingga menjadi
8
langkah selanjutnya adalah periksa apakah sudah terdapat elemen 1 pada masingmasing baris dengan kolom yang berbeda.
Karena telah ditemukan elemen 1 pada masing-masing baris dengan kolom yang berbeda, maka hasil optimalnya telah didapat, yaitu : mengerjakan pekerjaan 3 mengerjakan pekerjaan 5 mengerjakan pekerjaan 4 mengerjakan pekerjaan 2 mengerjakan pekerjaan 1. Dengan keuntungan maksimumnya adalah 10 + 5 + 14 + 14 + 17 = 50 5. KESIMPULAN Modifikasi metode Hungarian menghasilkan sebuah metode baru yang menggunakan salah satu sifat dasar determinan matriks untuk mereduksi matriks penugasan guna mendapatkan hasil yang optimal. Metode baru ini dapat dijadikan sebagai alternatif untuk menyelesaikan berbagai jenis persoalan penugasan, baik untuk masalah minimisasi maupun masalah maksimisasi. Perbedaan antara metode baru ini dan metode Hungarian adalah nilai optimal pada masing-masing matriks penugasannya ditunjukkan oleh elemen satu dan nol, namun kedua metode ini tetap memiliki solusi optimal yang sama. DAFTAR PUSTAKA [1] Anton, H. 1987. Aljabar Linier Elementer. Terj. dari Elementary Linear Algebra, Fifth Edition, oleh Silaban, P & Susila, I.N. Penerbit Erlangga, Jakarta. [2] Bazirzadeh, H. 2012. Ones Assignment Method for Solving Assignment Problems, Journal Applied Mathematical Science, 47, 2345-2355. [3] Dimyati, T. T. & Ahmad D. 1992. Operations Research : Model-model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. [4] Gamal, M. D. H. 2007. Program Linear dan Integer. Penerbit Pusat Pengembangan Pendidikan Universitas Riau, Pekanbaru.
9
[5] Subagyo, P., A. Marwan, & T. H. Handoko, 1985. Dasar-Dasar Operations Research. PT BPFE, Yogyakarta. [6] Supranto, J. 1988. Linier Programming Edisi Kedua. Penerbit Fakultas Ekonomi Universitas Indonesia, Jakarta. [7] Supranto, J. 1988. Riset Operasi: Untuk Pengambilan Keputusan. Penerbit Universitas Indonesia, Jakarta. [8] Taha, H. A. 2007. Riset Operasi, Suatu Pengantar Edisi Kelima: Jilid 1. Terj. dari Operations Research, an introduction, 5th Ed, oleh Wirajaya, D. Penerbit Binarupa Aksara, Jakarta.
10
