TEKNIK RISET OPERASIONALMetode Penugasan 2 SKS | D3 | MI

MODEL PENUGASAN

❑ Model Penugasan adalah suatu model khusus dari model program linier yang serupa dengan model transportasi.

❑ Perbedaannya adalah, dalam model penugasan penawaran pada tiapsumber dan permintaan pada tiap tempat tujuan dibatasi sebanyak satuunit barang saja.

MASALAH PENUGASAN(ASSIGMENT PROBLEM)

Masalah yang berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda untuk

tugas-tugas yang berbeda-beda pula

Langkah – Langkah Penyelesaian (1)

1. Membuat suatu tabel biaya Opportuniti (opportunity cost table) yakni dengan membuat reduksi baris dan kolom

2. Buat tabel Reduksi baris : dengan cara mengurangkan semua biaya dalam tiap baris dengan biaya terkecil yang ada pada tiap baris tersebut.

3. Buat tabel reduksi kolom : dengan cara mengurangkan semua biaya yang ada pada semua kolom dari tabel reduksi baris dengan biaya terkecil yang ada pada tiap kolomnya

Langkah – Langkah Penyelesaian (2)

4. Buat tabel biaya pengujian : yakni tambahkan garis pada tabel yang sudah direduksi baik secara vertikal maupun secara horisontal dimana terdapat minimal 2 angka nol.

5. Untuk mencapai tabel yang optimal, maka jumlah minimal garis = jumlah baris atau kolom, jika belum maka buat tabel pengulangan model penugasan dengan cara kurangkan semua biaya yang tidak dilalui garis dengan biaya yang terkecil yang juga tidak dilalui garis dan untuk semua angka nol pada perpotongan garis harus ditambahkan dengan biaya yang terkecil. Kemudian tarik garis secara vertikal dan horisontal seperti langkah sebelumnya.

Langkah – Langkah Penyelesaian (3)

6. Apabila jumlah minimal garis = jumlah baris

atau kolom, maka tabel tersebut sudah

opitmal. Maka tentukanlah penugasan

berdasarkan sel di mana terdapat angka nol.

Masalah Minimisasi

Pekerjaan

KaryawanI II III IV

A Rp 15 Rp 20 Rp 18 Rp 22

B 14 16 21 17

C 25 20 23 20

D 17 18 18 16

Suatu perusahaan mempunyai 4 pekerjaan yangberbeda untuk diselesaikan oleh 4 karyawan

Tabel Matrik biaya

Contoh :

Langkah-langkah (Metode Hungarian)1. Mengubah Matriks biaya menjadi matriks

opportunity cost:

Caranya: pilih elemen terkecil dari setiap

baris, kurangkan pada seluruh elemenbaris tersebut

Pekerjaan

KaryawanI II III IV

A Rp 15 Rp 20 Rp 18 Rp 22

B 14 16 21 17

C 25 20 23 20

D 17 18 18 16

Langkah-langkah (Metode Hungarian)1. Mengubah Matriks biaya menjadi matriks

opportunity cost:

Caranya: pilih elemen terkecil dari setiap

baris, kurangkan pada seluruh elemenbaris tersebut

Pekerjaan

KaryawanI II III IV

A Rp 15 Rp 20 Rp 18 Rp 22

B 14 16 21 17

C 25 20 23 20

D 17 18 18 16

Reduced cost matrix (Reduksi Baris)

5 3 70

2 7 3

5 3

1 2 2

0

0

0

0

2. Reduced-cost matrix (RCM) terus dikurangi untuk mendapatkan total-opportunity-cost matrix.

Caranya: pilih elemen terkecil dari setiap kolom pada RCM

yang tidak mempunyai nilai nol, kurangkan pada seluruh elemen dalam kolom tersebut.

Pekerjaan

KaryawanI II III IV

A Rp 15 Rp 20 Rp 18 Rp 22

B 14 16 21 17

C 25 20 23 20

D 17 18 18 16

Reduced cost matrix (Reduksi Baris)

5 3 70

2 7 3

5 3

1 2 2

0

0

0

0

Reduced cost matrix

2. Reduced-cost matrix (RCM) terus dikurangi untuk mendapatkan total-opportunity-cost matrix.

Caranya: pilih elemen terkecil dari setiap kolom pada RCM

yang tidak mempunyai nilai nol, kurangkan pada seluruh elemen dalam kolom tersebut.

Pekerjaan

KaryawanI II III IV

A 0 5 3 7

B 0 2 7 3

C 5 0 3 0

D 1 2 2 00

1

5

1

Total opportunity cost matrix

3. Melakukan test optimalisasi dengan menarik

sejumlah minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol

Penugasan optimal adalah feasible jika :

jumlah garis = jumlah baris atau kolom

Pekerjaan

KaryawanI II III IV

A 0 5 1 7

B 0 2 5 3

C 5 0 1 0

D 1 2 0 0

Test of optimality

4. Untuk merevisi total-opportunity matrix, pilih elemen

terkecil yang belum terliput garis (1) untuk mengurangi seluruh elemen yang belum terliput

Tambahkan jumlah yang sama pada seluruh

elemen yang mempunyai dua garis yang saling bersilangan

Pekerjaan

KaryawanI II III IV

A 0 5 1 7

B 0 2 5 3

C 5 0 1 0

D 1 2 0 0

04 6

1 4 2

6

2

Revised matrix dan Test of optimalityUlangi langkah 3

Revised matrix dan Test of optimality

0021D

0105C

3520B

7150A

IVIIIIIIPekerjaan

Karyawan

04 6

1 4 2

6

2

Karena jumlah garis = jumlah baris atau kolom

maka matrik penugasan optimal telah tercapai

Melakukan test optimalisasi dengan menarik sejumlah

minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol

Matrix optimal

0021D

0105C

3520B

7150A

IVIIIIIIPekerjaan

Karyawan

04 6

1 4 2

6

0

Pekerjaan

KaryawanI II III IV

A Rp 15 Rp 20 Rp 18 Rp 22

B 14 16 21 17

C 25 20 23 20

D 17 18 18 16

Tabel Matrik biaya

1

2

3

4

Skedul penugasan optimal

Skedul penugasan

A - III Rp 18

B - I 14

C - II 20

D - IV 16

Rp 68

Karyawan B ditugaskan untuk pekerjaan satu karena baris B hanya mempunyai satu nilai nol

Masalah Maksimisasi

Pekerjaan

KaryawanI II III IV V

A Rp 10 Rp 12 Rp 10 Rp 8 Rp 15

B 14 10 9 15 13

C 9 8 7 8 12

D 13 15 8 16 11

E 10 13 14 11 17

Contoh :

Suatu perusahaan mempunyai 5 pekerjaan yangberbeda untuk diselesaikan oleh 5 karyawan

Tabel Matrik keuntungan

Langkah-langkah Metode Hungarian

1. Mengubah Matriks biaya menjadi matriksopportunity-loss:

Caranya: pilih elemen terbesar dari setiap

baris, kurangkan pada seluruh elemen baristersebut

Pekerjaan

KaryawanI II III IV V

A Rp 10 Rp 12 Rp 10 Rp 8 Rp 15

B 14 10 9 15 13

C 9 8 7 8 12

D 13 15 8 16 11

E 10 13 14 11 17

Tabel Matrik keuntungan

Pekerjaan

KaryawanI II III IV V

A Rp 10 Rp 12 Rp 10 Rp 8 Rp 15

B 14 10 9 15 13

C 9 8 7 8 12

D 13 15 8 16 11

E 10 13 14 11 17

Langkah-langkah Metode Hungarian

1. Mengubah Matriks biaya menjadi matriksopportunity-loss:

Caranya: pilih elemen terbesar dari setiap

baris, kurangkan pada seluruh elemen baristersebut

Opportunity-loss matrix (Reduksi Baris)

07535

0

0

0

0

1 5 6 2

3 4 5 4

3 1 8 5

7 4 3 6

2. Reduced-Lost matrix (RLM) terus dikurangi untuk mendapatkan total-opportunity-Lost matrix.

Caranya: pilih elemen terkecil dari setiap kolom pada RCM

yang tidak mempunyai nilai nol, kurangkan pada seluruh elemen dalam kolom tersebut.

Pekerjaan

KaryawanI II III IV V

A Rp 10 Rp 12 Rp 10 Rp 8 Rp 15

B 14 10 9 15 13

C 9 8 7 8 12

D 13 15 8 16 11

E 10 13 14 11 17

Opportunity-loss matrix (Reduksi Baris)

07535

0

0

0

0

1 5 6 2

3 4 5 4

3 1 8 5

7 4 3 6

Total Opportunity-loss matrix

1711141310E

11

12

13

Rp 15

V

1681513D

8789C

1591014B

Rp 8Rp 10Rp 12Rp 10A

IVIIIIIIPekerjaan

Karyawan

07535

0

0

0

0

1 5 6 2

3 4 5 4

3 1 8 5

7 4 3 60

2

3

2

50

2

4

3

3

0

4

2

2

6

2 2 74

2 3 2 4

2

5

0

Total Opportunity-loss matrix

1711141310E

11

12

13

Rp 15

V

1681513D

8789C

1591014B

Rp 8Rp 10Rp 12Rp 10A

IVIIIIIIPekerjaan

Karyawan

07535

0

0

0

0

1 5 6 2

3 4 5 4

3 1 8 5

7 4 3 60

2

3

2

50

2

4

3

3

0

4

2

2

6

0 0 52

0 1 0 2

4

7

2

Karena jumlah garis = jumlah baris atau kolom

maka matrik penugasan optimal telah tercapai

1

2

3

4

5

Latihan

Soal 1:

Latihan

Soal 2: