E-Jurnal Matematika Vol. 10(1), Januari 2021, pp. 41-45

DOI: https://doi.org/10.24843/MTK.2021.v10.i01.p318

ISSN: 2303-1751

ANALISIS SENSIVITAS MODEL PENUGASAN DENGAN METODE HUNGARIAN

Elfrida Riani Tsani§, Ni Ketut Tari Tastrawati2, Kartika Sari3

1Jurusan Matematika, Fakultas MIPA – Universitas Udayana [Email: [email protected]]

2Jurusan Matematika, Fakultas MIPA – Universitas Udayana [Email: [email protected]]

3Jurusan Matematika, Fakultas MIPA – Universitas Udayana [Email: [email protected]]

§Corresponding Author

ABSTRACT

In linear programming the assignment problem can be solved by the Hungarian method. This method produces an optimal solution for the placement of employees on their assignments. The purpose of this research is to determine the sensitivity analysis of the optimal results from the assignment that has been obtained by the Hungarian Method. Sensitivity analysis is used to determine the extent to which changes can occur without changing the optimal decisions that have been obtained. The results of this research obtain interval working time that can be tolerated without changing the optimal decision that has been obtained. So, no matter how much working time of the Employee changes, as long as the change is still within the interval, it does not interfere with the optimal solution that has been obtained previously.

Keywords:Assignment Problem, Hungarian Method, Sensitivity Analysis.

  • 1.    PENDAHULUAN

Riset Operasi merupakan proses pengambilan keputusan dari suatu kegiatan yang berkaitan dengan kehidupan nyata (Hillier & Lieberman, 2010). Salah satu bagian dari Riset Operasi adalah pemrograman linier. Sejak diperkenalkannya pada tahun 1940an, pemrograman linier menjadi salah satu alat yang efektif dalam Riset Operasi(Taha, 1997).

Ada beberapa metode yang terdapat pada pemrograman linier, salah satu diantaranya adalah metode penugasan. Metode ini bentuk khusus dari persoalan transportasi yang merupakan turunan dari metode Simpleks. Metode penugasan pertama kali dikembangkan oleh D. Konig ahli matematika dari Hungarian. Itu sebabnya, metode penugasan disebut juga dengan HungarianMethod (Aminuddin, 2005).

Menempatkan suatu sumber ketujuan yang tepat merupakan penerapan dari metode Hungarian. Karakteristik dari metode Hungarian adalah jumlah sumber (petugas) harus sama dengan jumlah tujuan (penugasan). Apabila jumlah sumber dan tujuan tidak sama, maka perlu ditambahkan sumber atau tujuan rekaan (dummy). Selain

itu, dalam model penugasan pada Metode Hungarian memiliki jumlah batasan kendala sama dengan 1 (Taha, 1997).

Penyelesaian pada pemrograman linier boleh mengalami perubahan pada koefisien fungsi tujuan yang memengaruhi optimalitas sertaperubahan biasanya pada ruas sisi kanan kendala yang memengaruhi kelayakan. Hal ini bisa dikaji dengan analisis sensitivitas. Analisis ini memberikan pemecahan terkait sejauh mana suatu perubahan boleh dilakukan sehingga tidak mengubah keputusan optimalnya (Hillier & Lieberman, 2010).Mengingat batasan semua kendala pada MetodeHungarian bernilai satu, maka analisis sensitivitas hanya bisa dilakukan pada perubahan koefisien fungsi tujuan saja. Hal ini seperti dinyatakan oleh Ling & Wen (2003).

Metode Hungarian dapat diterapkan pada perusahaan produksi yang memiliki petugas dengan penugasan yang variatif, antara lain perusahaan produksi perak. Umumnya perusahaan produksi perak memproduksi berbagai macam jenis perhiasan. Salah satu perusahaan produksi perak di Bali yaitu CV Jani Silver.

CV Jani Silver adalah salah satu usaha kerajinan perak di Bali yang terletak di Kemenuh, Gianyar. Perusahaan tersebut mampu memproduksi beberapa macam produk, seperti cincin (ring), kalung (necklace), liontin (pendant), rantai(link) dengan berbagai tipe.

Sampai penelitian ini dilakukan, belum ada metode khusus yang digunakan oleh perusahaan mengenai penempatan petugas produksi di CV Jani Silver. Pada kesempatan ini, akan dicoba menyelesaikan masalah penugasan ini dengan metode Hungarian. Selanjutnya, hasil optimal yang diperoleh dari penyelesaian dengan metode Hungarian dikaji dengan analisis sensitivitas. Analisis ini dilakukan untuk mengetahui seberapa jauh perubahan waktu pengerjaan setiap produk yang boleh dilakukan setiap petugas pada setiap penugasannya tanpa mengubah keputusan optimal yang telah diperoleh.

Berdasarkan hal tersebut, tujuan dari penelitian ini adalah mengetahui waktu minimal penugasan dengan metode Hungarian dan melakukan analisis dari hasil optimal penugasan dengan Metode Hungarian pada CV Jani Silver.

  • 2.    METODE PENELITIAN

Data yang digunakan dalam penelitian ini adalah data kuantitatif berupa rata-rata waktu pengerjaan setiap produk yang dihasilkan oleh setiap pekerja pada setiap penugasannyadi CV Jani Silver yang terletak di Jalan Ir. Sutami, Kemenuh, Gianyar selama Januari 2018 - Juli 2019. Adapun petugas yang dianalisis sebanyak 8 dengan penugasan pembuatan kerajinan : 1. Silver Pendant

  • 2.    Silver Mountain & Ocean with Bronze Sun

  • 3.    Silver Wave Ring Size 8

  • 4.    Silver Wave RingSize 7

  • 5.    Silver Wave Ring Size 6

  • 6.    Silver Big and Little Infinity Link,

  • 7.    Silver Infinity Link

  • 8.    Silver Heart Pendant with Riveted & Bronze Heart

Adapun langkah-langkah yang dilakukan adalah (Winston, 2003) :

  • 1.    Menghitung rata-rata waktu pengerjaan (menit/pcs) setiap barang yang dihasilkan oleh setiap petugas.

  • 2.    Memodelkan data penugasan.

min∑  ∑            (1)

Dengan

∑'∣ - 1 Xu = 1 ,untuk i = 1,2,...,8

∑it XxH = 1,untuk j = 1,2,.,8

=0 atau 1

dengan,

= Variabel keputusan petugas terhadap penugasan j

= Suatu besaran yang menyangkut petugas terhadap penugasan j

  • 3.    Menyusun matriks penugasan.

    [ ¾ι

    ⅜ι


    …

    …

    …


Cinl C2∏

C88-I

  • 4.    Mengurangi setiap nilai elemen dengan nilai elemen terendah pada baris tersebut.

  • 5.    Memeriksa kolom, jika terdapat kolom yang belum memiliki nilai nol, maka semua nilai elemen pada kolom tersebut kembali dikurangi dengan nilaielemen terendah yang ada pada kolom yang bersangkutan.

  • 6.    Menarik garis secara vertikal/horizontal yang memilkinilai nol terbanyak.

  • 7.    Memeriksa apakah solusi sudah optimal, dikatakan optimal apabila jumlah garis yang terbentuk sama dengan jumlah baris/kolom. Jika solusi untuk waktu optimal belum diperoleh, mengurangi semua nilai yang tidak dilewati garis dengan nilai elemen terendah, dan tambahkan nilai elemen terendah tersebut pada   nilai   yang terletak pada

perpotongan garis. Nilai elemen lainnya (yang dilewati garis tapi tidak terletak pada perpotongan) tidak berubah.

  • 8.    Kembali ke langkah 7 sampai hasil optimal telah diperoleh. Penempatan petugas     dengan     penugasannya

ditunjukkan dengan nilai nol yang harus menempati setiap baris dan kolom yang berbeda.

  • 9.    Melakukan      analisis      sensitivitas

perubahan kofisien fungsi tujuan. Koefisien fungsi tujuan dibagi menjadi 2, yaitu koefisien fungsi tujuan variabel non basis dan koefisien fungsi tujuan variabel basis. Adapun untuk analisis sensitivitas perubahan koefisien fungsi tujuan variabel basis sebagai berikut :

  • a.    Menentukan batas atas dan batas bawah koefisien fungsi tujuan variabel basis dengan mengurangi /

menambah nilai Δ (nilai terkecil koefisien variabel non basis pada matriks optimal).

(cU-∆)≤Xij≤(cU +∆)    (2)

  • b.    Menurunkan batas bawah  untuk

koefisien solusi optimal hingga -∞.

Sedangkan  untuk variabel  basis

sebagai berikut :

  • a. Menentukan batas atas dan batas

bawah koefisien fungsi tujuan variabel non basis. Adapun untuk mencari batas bawahnya sebagai berikut :

c ij =     - cij          (3)

dengan batas atas ∞.

Setelah diperoleh interval batas atas dan batas bawah seluruh koefisien fungsi tujuan selanjutnya mengiriskan batas atas dan batas bawah dengan waktu pengerjaan tercepat dan terlama sesuai data.

  • 3.    HASIL DAN PEMBAHASAN

Data yang diperoleh pada penelitian ini berupa berupa 8 jenis kerajinan yang dikerjakan oleh 8 petugas, banyak setiap kerajinan yang

bisa diselesaikan oleh setiap petugas, dan banyaknya hari pengerjaan setiap kerajinan oleh setiap petugas selama periode Januari 2018 – Juli 2019. Dari data tersebut dihitung rata-rata pengerjaan setiap jenis kerajinan oleh setiap petugas dengan membagi banyaknya hari pengerjaan (menit) dengan banyaknya kerajinan yang dihasilkan (pcs)dengan menggunakan persamaan :

=     ; wii =ℎ ×300     (4)

∙ ∙ j                                                                         × '

dengan,

ci] = Rata-rata waktu yang diperlukan petugas j untuk menyelesaikan kerajinan i (menit/pcs).

wij = Banyaknya waktu yang diperlukan petugas j dalam menyelesaikan kerajinan i selama periode waktu tertentu (dalam menit).

nij = Banyaknya kerajinan i yang diselesaikan oleh petugas j selama periode waktu tertentu (pcs).

ℎij = Banyaknya waktu yang diperlukan diperlukan petugas j dalam menyelesaikan kerajinan i selama periode waktu tertentu (dalam hari).

Tabel 1. Data penugasan CV Jani Silver

Kerajinan

Petugas

1

2

3

4

5

6

7

8

1

68

50

150

57

53

75

64

137

2

74

97

107

102

80

79

80

70

3

45

67

39

52

47

59

78

46

4

44

52

60

51

43

57

52

58

5

17

13

12

15

16

14

52

58

6

20

17

22

22

20

29

20

24

7

17

12

15

22

14

16

13

14

8

18

18

18

28

36

26

18

18


Dari data penugasan Tabel 1 dilakukan

Selanjutnya, elemen pada setiap baris

optimasi    dengan   metode    Hungarian.

dikurangi dengan elemen terendah pada baris

Berdasarkan   Tabel   1,   bentuk   matriks

tersebut, diperoleh :


penugasannya yaitu :

68

50

150

57

53

75

64

137

18

0

100

7

3

25

14

87

⎡74

97

107

102

80

79

80

70

4

27

37

32

10

9

10

0

45

67

39

52

47

59

78

46

⎥

6

28

0

13

8

20

39

7

⎢44

52

60

51

43

57

52

51

⎢1

9

17

8

0

14

9

8⎥

⎢17

13

12

15

16

14

52

58

⎢5

1

0

3

4

2

40

46⎥

⎢20

17

22

22

20

29

20

24

⎥

⎢3

0

5

5

3

12

3

7⎥

⎢17

12

15

22

14

16

13

14

⎥

5

0

3

10

2

4

1

2⎥

⎣18

18

18

28

36

26

18

18⎦

⎣0

0

0

10

18

8

0

0⎦


Kemudian, memeriksa kolom yang belum memiliki nilai nol. Apabila terdapat kolom yang belum memiliki nilai nol, maka semua nilai elemen pada kolom tersebut kembali dikurangi dengan nilai elemen terendah yang ada pada kolom yang bersangkutan.Dengan demikian matriks penugasannya menjadi :

17  0  99 2   1  21  13  86

4  28  3728  9    6  10  0

6  29   0 9   7   17  39  7

⎥

2  11  185   0  12  9   9

6   3   1 0   4   0  40  47

2   0   40   1   8   2   6

4   0   25   0   0   0   1

⎣0   1   0 6  17   5   0   0⎦

⎥

⎥⎥

18

0

100 4

3

23

14

87

⎡4

27

37 29

10

7

10

0

6

28

0

10

8

18

39

7

⎢1

9

17

5

0

12

9

8⎥

⎢5

1

0

0

4

0

40

46⎥

⎢3

0

5

2

3

10

3

7⎥

⎢5

0

3

7

2

2

1

2⎥

⎣0

0

0

7

18

6

0

0⎦

Lalu, memeriksa apakah solusi telah optimal dengan menarik garis yang melewati nilai nol terbanyak. Matriks dikatakan optimal apabila garis yang terbentuk sudah sebanyak baris/kolom yakni sebanyak 8. Berikut pemeriksaannya :

18

4

0

9

7

100 4

97 90

3

1 n

23

7

14

10

87

0

⎢

r)

⎥

⎢

6

2

8

0

10

8

18

39

7

⎥

⎢

1

r-

17

5

0

12

9

8

⎥

⎢ ⎢⎢

51

30

50

⎣0   0

t—

)

F-

0

5

3

0

0

2

7

7

4

3

2

18

0

10

2

6

40

3

1 0

46

7

2

0⎦

⎥ ⎥⎥


Garis yang terbentuk belum sebanyak 8, artinya matriks belum optimal. Dilanjutkan langkah berikutnya dengan mengurangi semua nilai yang tidak dilewati garis dengan nilai elemen terendah, dan tambahkan nilaielemen terendah tersebut pada nilai yang terletak pada perpotongan garis. Nilaielemen lainnya (yang dilewati garis tapi tidak terletak pada perpotongan) tidak berubah. Dengan demikian matriks penugasannya menjadi :

17

0

99 3

2

22

13

86

⎡4

28

3729

10

7

10

0 ⎤

6

29

0 10

8

18

39

7

⎢1

10

17 5

0

12

9

8 ⎥⎥

⎢5

2

00

4

0

40

46⎥

⎢2

0

41

2

9

2

6⎥

⎢4

0

26

1

1

0

1⎥

⎣0

1

07

18

6

0

0⎦

Demikian dilakukan seterusnya sampai diperoleh matriks optimal yaitu :

Setelah matriks telah optimal, selanjutnya menentukan penempatan petugas. Penempatan petugas ditujukan dengan nilai nol yang menempati baris dan kolom berbeda. Dengan demikian penempatan petugas sebagai berikut :

17

0

99 2

1

21

13

86

⎡4

28

3728

9

6

10

0

6

29

09

7

17

39

7

⎢2

11

18 5

0

12

9

9⎥

⎢6

3

10

4

0

40

47⎥

⎢2

0

40

1

8

2

6⎥

⎢4

0

25

0

0

0

1⎥

⎣0

1

06

17

5

0

0⎦

Berdasarkan matriks di atas dapat

disimpulkan bahwa kerajinan jenis1 dikerjakan

oleh petugas 2, kerajinanjenis 2 dikerjakan oleh

petugas 8, kerajinan petugas 3, kerajinan petugas 5, kerajinan petugas 6, kerajinan petugas 4, kerajinan


jenis 3 dikerjakan oleh jenis 4 dikerjakan oleh jenis 5 dikerjakan oleh jenis 6 dikerjakan oleh jenis 7 dikerjakan oleh

petugas 7, dan kerajinan jenis 8 dikerjakan oleh petugas 1. Waktu minimum dan penempatan petugas dapat dilihat pada Tabel 2.

Tabel 2. Hasil Optimal Penugasan CV Jani Silver

Kerajinan

Petugas

Rata-rata Waktu Pengerjaan

1

2

50 menit/pcs

2

8

70 menit/pcs

3

3

39 menit/pcs

4

5

43 menit/pcs

5

6

14 menit/pcs

6

4

22 menit/pcs

7

7

13 menit/pcs

8

1

18 menit/pcs

Total

269 menit

Dengan demikian dari seluruh penempatan penugasan yang telah didapat, diperoleh total waktu optimum sebesar 269 menit. Selanjutnya hasil optimal akan dilakukan analisis sensitivitas, dimana pada model penugasan

analisis sensitivitas dilakukan pada koefisien dengan Metode Hungarian pada penugasan di fungsi tujuan.Adapun hasil dari analisis CV Jani Silver sebagai berikut sensitivitas pada hasil optimal penugasan

Tabel 3. Interval Waktu Penugasan CV Jani Silver

Kerajinan

Petugas

1

2

3

4

5

6

7

8

1

[66,70]

[37,51]

[150]

[57,70]

[53.67]

[75]

[53,80]

[136,150]

2

[70,96]

[84,120]

[96,120]

[96,108]

[71,108]

[73,108]

[70,100]

[60,71]

3

[42,50]

[50,84]

[30,40]

[43,60]

[40,66]

[48,84]

[68,100]

[39,78]

4

[42,48]

[42,70]

[48,68]

[46,90]

[20,44]

[46,54]

[42,66]

[42,96]

5

[13,21]

[12,15]

[12]

[14,15]

[12,18]

[12,15]

[48,59]

[55,60]

6

[15,24]

[17,18]

[18,33]

[15,23]

[19,24]

[18,45]

[18,24]

[18,36]

7

[14,24]

[12,13]

[13,21]

[17,39]

[14,15]

[15,17]

[12,14]

[13,18]

8

[18]

[18]

[18]

[24,30]

[24,48]

[24,48]

[18]

[18]

  • 4.    KESIMPULAN DAN SARAN

Setelah dilakukan optimalisasi masalah penugasan pada CV Jani Silver terhadap 8 petugas dan 8 penugasan periode Januari 2018-Juli 2019 dengan       Metode Hungarian

diperoleh total waktu optimal sebanyak 269 menit.    Adapun untuk penempatan

penugasannya yaitu, kerajinan jenis 1 dikerjakan oleh petugas 2, kerajinan jenis2

dikerjakan oleh petugas 8, kerajinan jenis3

dikerjakan oleh petugas 3, kerajinan jenis4

dikerjakan oleh petugas 5, kerajinan jenis 5 dikerjakan oleh petugas 6, kerajinan jenis6

dikerjakan oleh petugas 4, kerajinan jenis7

dikerjakan oleh petugas 7, dan kerajinan jenis 8 dikerjakan oleh petugas 1. Selanjutnya, analisis sensitivitas pada hasil optimal masalah penugasan di CV Jani Silver menghasilkan interval waktu pengerjaan setiap jenis kerajinan oleh setiap petugas yang tidak mengubah keputusan optimal yang telah diperoleh.

DAFTAR PUSTAKA

Aminuddin. (2005). Prinsip-prinsip Riset Operasi. Jakarta: Erlangga.

Hillier, F. S., & Lieberman, G. J. (2010). Introduction to Operation Research Ninth Edition. New York: McGraw-Hill.

Ling, C. J., & Wen, U. P. (2003). Sensitivity Analysis Of The Optimal Assignment. European Journal Of Operational Research, 149, 35-46.

Siburian, N. F. (2010). Analisis Sensitivitas Pada Optimalisasi Assignment Problem dengan Metode Hungarian. Sumatera Utara: Universitas Sumatera Utara.

Supian, S., Wahyuni, S., Nahar, J.,  &

Subiyanto. (2017). Optimization of Personnel Assignment Problem Based on Traveling Time by Using Hungarian Methods: Case Study on the Central Post Office Bandung. IOP Conference Series: Materials Science and Engineering, 1-5.

Taha, H. A. (1997). Operations Research An Introduction. United States of America: Macmillan Publishing Company.

Winston, W. L. (2003). Operation Research: Application and Algorithms. Canada: Duxbury Press.

45