2016. Azwar Anas, M. Kom - STIE-GK Muara Bulian

Azwar Anas, M. Kom

11/1/2016

Azwar Anas, M. Kom - STIE-GK Muara Bulian

1

Pemecahan Persoalan Minimasi



 Algoritma lainnya yang digunakan dalam persoalan program linier adalah metode penugasan. Seperti halnya metode transportasi, metode penugasan bisa lebih efisien daripada metode simpleks, untuk jenis-jenis persoalan tertentu. Akan dijelaskan pula bahwa persoalan penugasan merupakan kasus khusus dari persoalan transportasi. Dengan kata lain, kita dapat memecahkan suatu persoalan penugasan dengan menggunakan metode transportasi. Model penugasan pertama kali dikembangkan oleh D. Konig, ahli matematika dari Hungaria. Itulah sebabnya, untuk mengabadikan hasil karyanya, metode penugasan sering disebut sebagai Hungarian Metdhod. 11/1/2016


2

Tabel Persoalan Penugasan



11/1/2016


3

Contoh  1)

11/1/2016

Bengkel Zhivanna menangani pekerjaan logam untuk sejumlah proyek di daerah sekitarnya. Saat ini Zhivanna mempunyai empat pekerjaan yang harus digarapnya (A, B, C dan D). Zhivanna juga mempunyai empat mesin yang mengerjakan pekerjaan tersebut (P, Q, R dan S). Setiap pekerjaan dapat diproses secara penuh pada setiap mesin, selanjutnya biaya pemrosesan tiap pekerjaan pada tiap mesin sudah diketahui. Penugasan pekerjaan ke mesin harus dilakukan atas basis satu ke satu, yaitu tiap pekerjaan harus ditugaskan sepenuhnya ke satu dan hanya satu mesin. Tujuan akhir penugasan ini adalah meminimumkan biaya. Azwar Anas, M. Kom - STIE-GK Muara Bulian

4

Biaya Pengoperasian Mesin

 Pekerjaan

11/1/2016

Mesin P

Q

R

S

A

10

4

6

10

B

13

8

12

14

C

14

16

13

17

D

19

11

17

20


5

Langkah-langkah pemecahan

 1.

2.

11/1/2016

Tentukan tabel biaya kesempatan. a. Kurangkan biaya terendah dalam tiap baris pada tabel biaya tertentu dari semua biaya dalam baris tersebut. b. Kurangkan biaya terendah dalam tiap kolom tabel yang diperoleh dari langkah a dari semua biaya dalam kolom. Tentukan apakah penugasan optimal dapat dibuat. Prosedurnya adalah menarik garis lurus (vertikal dan horizontal) terhadap tabel total biaya kesempatan sedemikian rupa guna meminimumkan jumlah garis yang melintasi semua elemen nol. Suatu penugasan optimal dapat dibuat bila jumlah garis sama dengan jumlah baris. Azwar Anas, M. Kom - STIE-GK Muara Bulian

6

 3. Memperbaiki tabel total biaya kesempatan. a. Pilihlah angka terkecil dalam tabel yang tak dilalui garis lurus dan kurangkan angka ini dari semua angka yang tak dilalui oleh garis lurus. b. Tambahkan angka yang sama pada perpotongan antara dua garis dan kembali ke langkah 2.

11/1/2016


7

Langkah 1 bagian a   Biaya kesempatan (i) Pekj

Biaya kesempatan (ii)

Mesin

P

Q

R

S

A

5

0

2

2

6

B

4

0

4

2

0

4

C

0

3

0

0

6

9

D

7

0

6

5

P

Q

R

S

A

6

0

2

6

B

5

0

4

C

1

3

D

8

0

11/1/2016

Pekj

Mesin


8

Langkah 2. Pengujian Optimalitas Penugasan



 Tujuannya adalah merumuskan penugasan pekerjaan untuk mesin agar meminimumkan total biaya. Melalui tabel total biaya kesempatan, tujuan ini dapat dicapai dengan menugaskan pekerjaan untuk mesin sedemikian rupa sehingga didapat total biaya kesempatan nol. Jadi kemungkinan penugasan pekerjaan pada mesin yang paling baik, akan mengandung biaya kesempatan nol.

11/1/2016


9

  Berdasarkan total biaya kesempatan dalam tabel (ii) kita dapatkan 6 segi empat bernilai nol. Oleh karena itu kita harus menugaskan pekerjaan A ke mesin Q, dan pekerjaan C ke mesin P, R atau S, karena itulah penugasan yang terbaik (biaya kesempatan nol). Tetapi tidak bisa menugaskan pekerjaan B dan D ke mesin Q, karena penugasan pekerjaan A untuk mesin Q menghalangi penugasan B dan D ke mesin Q. Penyelesaian penugasan semacam itu hanya dapat dibuat dengan total biaya kesempatan nol. 11/1/2016


10

Langkah 3. Revisi Tabel Biaya Kesempatan



 Tentu saja penugasan dengan biaya kesempatan terkecil yang terpilih dalam persoalan kita adalah penugasan pekerjaan A ke mesin R atau S dan juga pekerjaan B ke mesin S yang mempunyai biaya kesempatan 2. Dengan kata lain kita harus merubah biaya kesempatan penugasan itu dari 2 menjadi nol. Caranya adalah dengan mengurangkan angka 2 (terkecil) pada tabel (ii) dari semua angka yang ada.

11/1/2016


11

Revisi Uji Optimal  Pekj

Mesin P

Q

R

S

A

5

0

2

2

B

4

0

4

2

C

0

3

0

0

D

7

0

6

5

11/1/2016

Pekj

Mesin P

Q

R

S

A

3

0

0

0

B

2

0

2

0

C

0

1

0

0

D

5

0

4

3


12

  Langkah berikutnya adalah penugasan optimal dengan cara identifikasi baris atau kolom yang memuat hanya satu angka (biaya kesempatan) nol.  Dalam hal ini baris D memuat hanya satu angka nol berpotongan dengan kolom Q, elemen lain pada kolom Q disilang untuk menandai bahwa mesin Q telah terpakai.

11/1/2016


13

Visualisasi Total Biaya Penugasan Optimal



Pekj

Mesin

Penugasan

Biaya ($)

P

Q

R

S

A ke R

6

A

3

0

[0]

0

B ke S

14

B

2

0

2

[0]

C ke P

14

C

[0]

1

0

0

D ke Q

11

D

5

[0]

4

3

Total

$45

11/1/2016


14

Exercise   Buatlah kasus sendiri, dan selesaikan dengan metode penugasan!

11/1/2016


15

11/1/2016


16

  Metode penugasan Hungarian untuk persoalan minimasi juga dapat digunakan untuk menyelesaikan persoalan maksimasi. Dalam persoalan maksimasi, tabel angka-angka menunjukkan tingkat kinerja (atau indeks produktivitas). Efektivitas penugasan diukur berdasarkan jumlah maksimum kontribusi yang dapat diperoleh.

11/1/2016


17

Contoh   Bagian personalia IBM baru saja mengadakan seleksi calon karyawan yang akan ditugaskan pada empat jenis jabatan, kita sebut saja 1, 2, 3 dan 4. Dari hasil seleksi terpilih empat orang yang memiliki hasil tes tertinggi. Keempat calon tersebut yaitu A, B, C dan D, dan kemudian diujicobakan pada empat jabatan itu secara bergilir selama dua bulan. Selama uji coba tersebut kinerja mereka diukur dan hasilnya bisa dilihat pada tabel berikut. 11/1/2016


18

Tabel Kinerja Karyawan  Karyawan

11/1/2016

Jabatan P

Q

R

S

A

3

2

4

8

B

10

11

11

6

C

5

11

14

10

D

9

11

12

11


19

  Setelah dua bulan dalam masa uji coba tersebut, manajer personalia kemudian mengadakan evaluasi dengan tujuan untuk menugaskan keempat karyawan tersebut pada empat jabatan yang tersedia. Dasar yang akan digunakan dalam penugasan ini adalah kinerja mereka selama uji coba, sebagaimana yang terlihat dalam tabel berikut.

11/1/2016


20

  Tujuan dari pemecahan persoalan ini dengan menggunakan program linier adalah memaksimumkan kinerja total. Oleh karena itu, sesuai dengan model penugasan, variabel keputusan kasus ini adalah Xij yaitu penugasan karyawan i = A, B, C, D ke jabatan j = P, Q, R, S. Dengan demikian ada 16 (4 x 4) variabel keputusan. Tabel berikut menjelaskan penugasan kasus IBM dengan 16 variabel keputusan. 11/1/2016


21

Tabel Persoalan Penugasan



11/1/2016


22

Model Program Liniernya sbb:

  Maksimumkan:  Z = 3XA1 + 2 XA2 + 4XA3 + 8XA4 + 10XB1 + 11XB2 + 11XB3 + 6XB4 + 5XC1 + 11XC2 + 14XC3 + 10XC4 + 9XD1 + 11XC2 + 12XD3 + 11XD4

11/1/2016


23

  Batasan-batasan: XA1 + XA2 + XA3 + XA4 = 1 XB1 + XB2 + XB3 + XB4 = 1 XC1 + XC2 + XC3+ XC4 = 1 XD1 + XD2 + XD3 + XD4 = 1 XA1 + XB1 + XC1 + XD1 = 1 XA2 + XB2 + XC2 + XD2 = 1 XA3 + XB3 + XC3+ XD3 = 1 XA4 + XB4 + XC4 + XD4 = 1 Xij = 0 atau 1 11/1/2016


24

  Fungsi batasan kasus ini memaksa seluruh variabel keputusan hanya bernilai 0 atau 1, meskipun kita tidak menggunakan program linier integer biner. Hal ini terjadi karena nilai baris atau kolom pasti sama dengan 1.

11/1/2016


25

Pemecahan   Langkah pertama dalam persoalan maksimasi adalah merubah tabel kinerja menjadi suatu tabel opportunity loss. Dalam persoalan ini, A mempunyai kinerja tertinggi yakni 8, bila ditugaskan pada jabatan 4. oleh karena itu, bila A ditugaskan pada jabatan 1 ada sebesar 5 poin sebagai opportunity loss yang terjadi dengan penugasan ini, dan seterusnya. Seluruh elemen dalam setiap baris dikurangi dengan nilai maksimum dalam baris yang sama. Prosedur ini menghasilkan tabel opportunity loss yang ditunjukkan dalam tabel berikutnya. Tabel ini sebenarnya bernilai negatif. 11/1/2016


26

Opportunity Loss  Karyawan

11/1/2016

Jabatan P

Q

R

S

A

5

6

4

0

B

1

0

0

5

C

9

3

0

4

D

3

1

0

1


27

  Seperti pada pembahasan sebelumnya, tabel ini akan berisi paling tidak satu angka nol untuk tiap barisnya. Langkah berikutnya dengan meminimumkan opportunity loss akan memaksimumkan total kontribusi keuntungan (dalam hal ini kinerja karyawan). Tabel opportunity loss diperoleh melalui pengurangan seluruh elemen dalam setiap kolom dengan elemen terkecil dari kolom tersebut. 11/1/2016


28

Uji Optimalitas OL  Karyawan

11/1/2016

Jabatan P

Q

R

S

A

4

6

4

0

B

0

0

0

5

C

8

3

0

4

D

2

1

0

1


29

  Sama seperti pada pembahasan sebelumnya, uji optimalitas dilakukan melalui pembuatan sejumlah minimal garis horizontal dan vertikal yang melalui seluruh elemen nol. Dalam tabel di atas seluruh elemen nol terliput hanya dengan tiga garis, jadi penugasan optimal belum bisa dilakukan. Jadi perlu tahap perbaikan tabel opportunity loss dengan cara kurangkan elemen terkecil (1) dari elemen yang tak terliput garis dan tambahkan pada elemen yang terliput dua garis (vertikal dan horizontal), hasilnya dapat dilihat pada tabel berikut. 11/1/2016


30

Revisi Total OL  Karyawan

11/1/2016

Jabatan P

Q

R

S

A

4

6

4

0

B

0

0

1

5

C

7

2

0

3

D

1

0

0

0


31

Visualisasi dan Total Kinerja Penugasan Optimal



Jabatan

Penugasan

Biaya ($)

S

A ke S

8

4

[0]

B ke P

10

0

1

5

C ke R

14

7

2

[0]

3

D ke Q

11

1

[0]

0

0

Total

$43

Karya wan

P

Q

R

A

4

6

B

[0]

C D

11/1/2016


32

2016. Azwar Anas, M. Kom - STIE-GK Muara Bulian

Recommend Documents