PENUGASAN
1.
TUJUAN PRAKTIKUM PENUGASAN
1. Memahami permasalahan penugasan dalam dunia nyata dan mampu
merumuskannya.
2. Memahami bagaimana mencari solusi/menyelesaikan permasalahan penugasan
2. LANDASAN TEORI
Masalah penugasan adalah masalah pemasangan satu sumber daya dengan tepat satu aktivitas
dan satu aktivitas dengan tepat satu sumber daya, yang memenuhi tujuan (yaitu
meminimumkan biaya). Masalah penugasan ini merupakan bentuk khusus masalah
transportasi dengan n tempat asal dan n tempat tujuan. Penyelesaiannya berupa 1
(dipasangkan) atau 0 (tidak dipasangkan). Walaupun untuk menyelesaikan masalah penugasan
ini dapat digunakan metode enumeratif ataupun metode transportasi, tetapi lebih disarankan
untuk digunakan metode Hongaria.
Prinsip dari metode Hongaria adalah dengan melakukan manipulasi terhadap matriks biaya
yang diberikan. Manipulasi tersebut adalah operasi pengurangan elemen tiap baris dengan
elemen minimum barisnya. Kemudian melakukan operasi pengurangan elemen tiap kolom
dengan elemen minimum kolomnya. Setelah itu, melakukan pembuatan garis yang melalui
elemen-elemen '0'. Selanjutnya, dicari elemen minimum pada submatriks yang tidak dilewati
garis. Akhirnya, elemen minimum tersebut dikurangkan dari setiap elemen pada submatriks
yang tidak dilewati garis dan ditambahkan pada elemen yang dilalui dua garis. Manipulasi
terhadap matriks biaya tersebut dilakukan beberapa kali sampai diperoleh matriks biaya
optimum, yang dapat diidentifikasi dengan banyaknya garis (yang melalui elemen '0') tepat
sama dengan n.
Apabila banyak sumber daya tidak sama dengan aktivitas maka diperkenalkan peubah rekaan.
Apabila tujuannya adalah memaksimumkan (keuntungan) maka untuk hal ini diselesaikan
dengan
meminimumkan
negatif
dari
biaya.
Penugasan merupakan suatu kasus khusus dalam masalah pemrograman linier pada umumnya
Dalam dunia bisnis dan industri, manajemen sering menghadapi masalah-masalah yang
berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau
personalisa yang mempunyai tingkat efisiensi yang berbeda-beda untuk tugas yang berbedabeda pula. Metode Hungarian adalah salah satu dari beberapa teknik-teknik pemecahan yang
tersedia untuk masalah-masalah penugasan.
Maksud dari penugasan adalah menetapkan jumlah sumber-sumber yang tugaskan kepada
sejumlah tujuan (satu sumber untuk satu tujuan), sedemikian hingga didapat ongkos total
yang minimum atau keuntungan total yang maksimum. Biasanya yang dimaksud dengan
sumber ialah pekerja. Sedangkan yang dimaksud dengan tujuan adalah obyek dari pekerjaan
tersebut. Jadi, masalah penugasan akan mencakup sejumlah m sumber yang mempunyai n
tugas. Ada n! (n faktorial) penugasan yang mungkin dalam suatu masalah karena berpasangan
satu-satu. Apabila pekerjaan i (i= 1,2,3,....n) ditugaskan kepada obyek j (j=1,2,3,...m) akan
muncul biaya penugasan Cn maka sudah jelas bahwa tujuan dari penugasan adalah mencari
ongkos dari tiap-tiap pekerjaan kepada obyek dengan total ongkos yang minimum atau
memberikan keuntungan yang maksimum.
B.1 Model Matematis Penugasan
Masalah penugasan dapat dijelaskan dengan mudah oleh suatu matrik segi empat,dimana
baris-barisnya menunjukkan sumber-sumber dan kolomnya menunjukkan tugas-tugas
Sebelum model dapat dipecahkan dengan teknik penugasan terlebih dahulu diseimbangkan
dengan menambah pekerjaan-pekerjaan atau obyek semu (dummy) bergantung pada apakah
m<n atau m>n, sehingga diasumsikan bahwa m=n. Secara matematis, model penugasan ini
dapat
dinyatakan
sebagai
berikut
:
Dengan demikian, model persoalan penugasan ini adalah :
Minimum (maksimum)
Dengan batasan :
Dan xij >0 atau 1
B.1.1 Masalah Minimasi
Suatu perusahaan mempunyai 4 (empat) pekerjaan yang berbeda untuk diselesaikan oleh 4
(empat) karyawan. Biaya penugasan seorang karyawan berbeda-beda. Setiap karyawan
mempunyai tingkat ketrampilan. Pengalaman kerja dan latar belakang pendidikan serta latihan
yang berbeda-beda pula. Sehingga biaya penyelesaian pekerjaan yang sama oleh para
karyawan yang berlainan juga berbeda. Biaya penugasan karyawan untuk macam-macam
pekerjaan ditunjukkan pada Tabel.3.1berikut :
Tabel 3.1 Soal penugasan (minimasi)
TUGAS
OBJEK
A
B
C
D
MESIN 1
MESIN 2
MESIN 3
MESIN 4
20
24
13
16
22
23
19
17
18
17
13
18
15
13
14
22
Langkah-langkah penyelesaiannya adalah sebagai berikut :
1.
Merubah matrik biaya menjadi Opportunity Cost. Ini dicapai dengan memilih elemen
terkecil dari setiap baris dari matrik biaya mula-mula untuk mengurangi seluruh
elemen setiap baris. Dari Tabel Reduced Cost matrik sebagai berikut:
Tabel 3.2 Reduced Cost
TUGAS
OBJEK
A
B
C
D
MESIN 1
MESIN 2
MESIN 3
MESIN 4
5
11
0
0
7
10
6
1
3
4
0
2
0
0
1
6
1.
Reduced Cost Matrik diatas terus dikurangi untuk mendapatkan total opportunity cost
matrik. Hal ini dapat dicapai dengan memilih elemen terkecil dari setiap kolom pada
Reduced Cost Matrik untuk mengurangi seluruh elemen dalam kolom-kolom tersebut.
Matrik total opportunity cost ditunjukkan dalam Tabel 14 sebagai berikut:
Tabel 3.3 Matrik total opportunity cost
TUGAS
MESIN 1
OBJEK
MESIN 2
MESIN 3
MESIN 4
B
C
D
11
0
0
9
5
0
4
0
2
0
1
6
1.
Mencari jadwal penugasan dengan suatu total opportunity cost nol. Untuk mencapai
penugasan ini dibutuhkan 4 "independent/cros" (karena ada 4 pekerja atau karyawan)
dalam matrik. Ini berarti setiap karyawan harus ditugaskan hanya untuk suatu
pekerjaan dengan opportunity cost sama dengan nol. Atau setiap pekerjaan harus
diselesaikan hanya oleh satu karyawan. Prosedur praktis untuk melakukan tes
optimalisasi adalah dengan menarik sejumlah minimum garis horisontal dan/atau
vertikal untuk meliputi seluruh elemen bernilai nol dalam total opportunity cost
matrik. Bila jumlah garis sama dengan baris dan kolom, penugasan optimal adalah
layak. Bila tidak sama maka matrik harus direvisi
Tabel 3.4 .Tes optimalisasi
TUGAS
MESIN 1
MESIN 2
MESIN 3
MESIN 4
B
C
D
11
0
0
9
5
0
4
0
2
0
1
6
OBJEK
Dalam Tabel 3.4 ada tiga baris yang meliputi seluruh nilai nol dibanding empat baris atau
kolom, sehingga langkah berikutnya untuk merevisi matrik.
1.
Untuk merevisi total opportunity cost matrik, pilih elemen terkecil yang belum terliput
garis-garis (yaitu opportunity cost terendah, atau pada contoh diatas = 3) 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 (1 pada baris C dan 6 pada baris D). Jadi hasil
perbaikannya adalah 4 pada baris C dan 9 pada baris D. Matrik yang telah direvisi
dapat dilihat pada tabel 5 yang didapat dengan mengikuti prosedur diatas.
Tabel 3.5 : Revised Matriks and Test for Optimality
TUGAS
MESIN 1
MESIN 2
MESIN 3
MESIN 4
B
C
D
8
0
0
6
5
0
1
0
2
0
4
9
OBJEK
1.
Dalam tabel 16 dibutuhkan minimal empat garis untuk meliputi seluruh nilai nol atau
sama dengan jumlah baris atau kolom, sehingga matrik penugasan optimal telah
tercapai. Jadwal penugasan optimal dengan biaya minimum adalah sebagai berikut:
JADWAL PENUGASAN
A-MESIN3
B-MESIN3
C-MESIN3
D-MESIN3
BIAYA
Rp 18
Rp 13
Rp 13
Rp 17
B.1.2 Masalah Maksimisasi
Metode penugasan Hungarian untuk minimisasi juga dapat diterapkan untuk
masalahpenugasan yang menyangkut maksimisasi. Dalam masalah maksimisasi, matrik
elemen-elemen menunjukkan tingkat keuntungan (atau indeks produktivitas). Efektivitas
pelaksanan tugas olehkaryawan-karyawan individual diukur dengan jumlah kontribusi
keuntungan. Langkah penyelesaianmaksimisasi sama dengan penyelesaian minimisasi, yang
berbeda hanya pada langkah pertama.Langkah pertama dalam masalah maksimasi adalah
merubah matrik keuntungan menjadi suatumatrik opportunity-loss (lihat Tabel 18). Dalam
masalah ini, A menyumbang keuntungan tertinggiRp 17,- bila dia ditugaskan pada pekerjaan
Mesin 5. Oleh karena itu bila A ditugaskan padapekerjaan Mesin1 (yang kontribusi
keuntungannya Rp 13,-). Ada sebesar Rp 4,- sebagai opportunity-loss yang terjadi dengan
penugasan ini dan seterusnya. Seluruh elemen dalam dalams etiap baris dikurangi dengan
nilai maksimum dalam baris yang sama. Prosedur ini menghasilkan matrik opportunity-loss
yang ditunjukkan dalam Tabel 18. Matrik ini sebenarnya bernilai negatif.
Tabel 3.6 Soal penugasan (maksimasi)
TUGAS
MESIN 1
OBJEK
MESIN 2
MESIN 3
MESIN 4
MESIN 5
13
14
13
10
17
B
C
D
E
16
12
14
9
9
13
15
12
10
8
12
13
13
11
8
4
15
16
11
15
MESIN 1
MESIN 2
MESIN 3
MESIN 4
MESIN 5
B
C
D
e
0
1
6
7
3
0
3
6
8
3
2
3
5
7
1
1
0
4
0
Tabel 3.7. Opportunity loss
TUGAS
OBJEK
Untuk langkah kedua dan seterusnya sama dengan masalah minimisasi.
1. PERMASALAHAN
2.
Soal/ kode praktikum : p3/2
Manager pemasaran sebuah industri pakaian memepunyai 4 orang karyawan
pemasaran yang akan di minta untuk memasarkan 5 buah jenis produk yaitu: jas,
kemeja, rok, blouse, dan celana. Kepada khalayak umum masing-masing karyawan
mempuyai kontribusi keuntungan yang berdeda-beda berikut adalah keuntungan
masing-masing karyawan untuk setiap produk
1.
Karyawan A = 15, 42, 38, 54, 29
2.
Karyawan B = 45, 19, 27, 32, 20
3.
Karyawan C = 21, 30, 41, 39, 23
4.
Karyawan D = 39, 28, 26, 22, 29
bagai mana seharusnya manager tersebut memberikan tugas pemasaran tersebut
sebagai keuntungan yang di peroleh maksimal.
3. Penyelesaian dengan menggunakan manual
TUGAS
OBJEK
Karyawan A
Karyawan B
Karyawan C
Karyawan D
dummy
Jas
Kemeja
Rock
blouse
Celana
15
45
21
39
0
42
19
30
28
0
38
27
41
16
0
54
32
39
22
0
29
20
23
19
0
1.
Merubah matrik biaya menjadi Opportunity Cost. Ini dicapai dengan memilih elemen
terbesar dari setiap baris dari matrik biaya mula-mula untuk mengurangi seluruh
elemen setiap baris. Dari Tabel Reduced Cost matrik sebagai berikut:
TUGAS
OBJEK
Karyawan A
Karyawan B
Karyawan C
Karyawan D
dummy
1.
Jas
Kemeja
Rock
blouse
Celana
39
0
20
0
0
12
26
11
11
0
16
18
0
23
0
0
13
2
17
0
25
25
18
20
0
Reduced Cost Matrik diatas terus dikurangi untuk mendapatkan total opportunity cost
matrik. Hal ini dapat dicapai dengan memilih elemen terkecil dari setiap kolom pada
Reduced Cost Matrik untuk mengurangi seluruh elemen dalam kolom-kolom tersebut.
Matrik total opportunity cost ditunjukkan dalam Tabel diatas sebagai berikut:
TUGAS
OBJEK
Karyawan A
Karyawan B
Karyawan C
Karyawan D
dummy
Jas
Kemeja
Rock
blouse
Celana
39
0
20
0
0
1
15
0
0
0
16
18
0
23
0
0
13
2
17
0
25
25
18
20
0
1.
Test apakah penempatan tugas sudah maksimal atau belum yaitu dengan manarik garis
pada kolom dan baris yang melintasi semua nilai nol, jika jumlah garis sama dengan
jumlah baris maka penugasan sudah optimal.
2.
Tugas pemasaran dari penugasan yang optimal adalah sebagai berikut:
JADWAL PENUGASAN
BIAYA
Karyawan A blouse
Karyawan B Jas
Karyawan C Rock
Karyawan D Kemeja
Dummy Celana
Total keuntungan maksimal yang di peroleh adalah Rp. 168,-
Rp 54,Rp 45,Rp 41,Rp 28,Rp 0,-
1.
Penyelesaian Dengan Menggunakan Software WinQSB
1. Buka program WinQSB dan pilih menu network modeling.
2. Buka file|new problem sampai muncul kotak dialog pada Gambar berikut:
Gambar 3.8. Kotak dialog problem specification
1. Kemudian isi data sesuai Gambar 3.8 dan klik OK
2. Kemudian akan mucul tabel penginputan data seperti pada Gambar 3.9 dan ketikkan
data yang telah didapatkan pada tabel tersebut (lihat Gambar 3.9)
Gambar 3.9. Tabel peng-input-an data
Setelah penginputan data selesai klik solve and analize|solve the problem sehingga akan
muncul solusi yang diperlihatkan oleh Gambar 3.10
Gambar 3.10. Solusi optimal
Pada Gambar 3.10 dapat dilihat bahwa solusi optimal dari permasalahan penugasan di atas
adalah
1.
Karyawan a memasarkan blouse dengan biaya Rp. 54
2.
Karyawan b memasarkan Jas dengan biaya Rp.45
3.
Karyawan c memasarkan Rock dengan biaya Rp.41
4.
Karyawan d memasarkan Kemeja dengan biaya Rp.28
5.
Dummy memasarkan Celana dengan biaya Rp.0
Sehingga total keuntungan maksimal yang di peroleh adalah Rp. 168,-
1. KESIMPULAN
Masalah penugasan adalah masalah pemasangan satu sumber daya dengan tepat satu aktivitas
dan satu aktivitas dengan tepat satu sumber daya, yang memenuhi tujuan (yaitu
meminimumkan biaya). Masalah penugasan ini merupakan bentuk khusus masalah
transportasi dengan n tempat asal dan n tempat tujuan. Penyelesaiannya berupa 1
(dipasangkan) atau 0 (tidak dipasangkan). Walaupun untuk menyelesaikan masalah penugasan
ini dapat digunakan metode enumeratif ataupun metode transportasi, tetapi lebih disarankan
untuk digunakan metode Hongaria.
Prinsip dari metode Hongaria adalah dengan melakukan manipulasi terhadap matriks biaya
yang diberikan. Manipulasi tersebut adalah operasi pengurangan elemen tiap baris dengan
elemen minimum barisnya. Kemudian melakukan operasi pengurangan elemen tiap kolom
dengan elemen minimum kolomnya
Dengan menggunakan program WinQSB dan menggunakan hitungan manual tentang
penugasan. Untuk mendapatkan keuntungan yang maksimal yaitu sebesar Rp. 168,- Maka
manager pemasaran tersebut harus memberikan tugas pemasaran sebagai berikut:
1.
Karyawan a memasarkan blouse dengan biaya Rp. 54
2.
Karyawan b memasarkan Jas dengan biaya Rp.45
3.
Karyawan c memasarkan Rock dengan biaya Rp.41
4.
Karyawan d memasarkan Kemeja dengan biaya Rp.28
5.
Dummy memasarkan Celana dengan biaya Rp.0
Sehingga total keuntungan maksimal yang di peroleh adalah Rp. 168,-
