METODE PENUGASAN
BAB
I
PENDAHULUAN
A.
Latar Belakang
Pemrograman Linier disingkat PL merupakan
metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai
suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL
banyak diterapkan dalam masalah ekonomi, industri, militer, social dan
lain-lain. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai
suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan
beberapa kendala linier.
Masalah
transportasi berkaitan dengan keterbatasan sumber daya atau kapasitas
perusahaan yang harus didistribusikan ke berbagai tujuan, kebutuhan atau
aktivitas. Dengan demikian manfaat utama dari mempelajari masalah transportasi
ini adalah mengoptimalkan distribusi sumberdaya tersebut sehingga mendapatkan
hasil atau biaya yang optimal.
Masalah penugasan (assignment problem),
seperti juga masalah transportasi merupakan suatu kasus khusus yang ditemui
dalam pemrograman linear. Permasalahan penugasan atauassignment
problem adalah suatu persoalan dimana harus melakukan penugasan terhadap
sekumpulan orang yang kepada sekumpulan job yang ada, sehingga tepat satu orang
yang bersesuaian dengan tepat satu job yang ada. Misalkan setiap 4 orang dengan
4 job yang ada menghasilkan 4! yaitu 24 kemungkinan yang ada. Namun yang dicari
disini atau fungsi objektifnya adalah mencari biaya seminimum mungkin sehingga
dalam penugasan ini bagi orang yang melakukan penugasan dapat mengeluarkan
biaya seminimum mungkin. Walaupun untuk menyelesaikan masalah penugasan
ini dapat digunakan metode numeratif ataupun metode transportasi, tetapi lebih
disarankan untuk digunakan metode
Hungarian. Metode Hungarian dikembangkan oleh seorang ahli matematika
berkebangsaan Hungaria yang bernama D Konig pada tahun 1916.
B.
Rumusan Masalah
Dalam masalah penugasan, kita akan
mendelegasikan sejumlah tugas (assignment) kepada sejumlah penerima tugas
(assignee) dalam basis satu-satu sehingga mendapatkan keuntungan yang maksimal
atau kerugian yang minimal.
C.
Tujuan
Tujuan yang akan dicapai dengan
menyelesaikan masalah ini adalah berusaha untuk menjadwalkan
setiap assignee pada suatu assigment sedemikian rupa
sehingga kerugian yang ditimbulkan minimal atau keuntungan yang didapat
maksimal. Yang dimaksud dengan kerugian dalam masalah ini adalah biaya dan
waktu, sedangkan yang termasuk keuntungan adalah pendapatan,laba, dan nilai
kemenangan.
D.
Metode Penulisan
Dalam menyelesaikan makalah ini, penyusun
melakukan metode penelaahan melalui studi pustaka dan studi kasus untuk
melengkapi materi atau data-data dalam penyusunan makalah ini. Penyusun
melakukan studi pustaka dan studi kasus dari berbagai sumber buku,dan internet
BAB
II
LANDASAN
TEORI
A.
DEFINISI MASALAH PENUGASAN
Masalah penugasan berkaitan dengan
keinginan perusahaan dalam mendapatkan pembagian atau alokasi tugas (penugasan)
yang optimal, dala arti apabila penugasan tersebut berkaitan dengan keuntungan
maka bagaimana alokasi tugas atau penugasan tersebut dapat memberikan
keuntugan yang maksimal, begitu pula sebaliknya bila menyangkut biaya.
Contoh kegiatan yang termasuk masalah penugasan antara lain yaitu: penempatan
karyawan pada suatu posisi jabatan di perusahaan, pembagian wilayah tugas
salesman, pembagian tugas dalam suatu tim renang estafet.
Pada bagian terdahulu telah disebutkan
bahwa pada masalah penugasan disyaratkan suatu penugasan satu-satu, sehingga
jumlah assignee dan assignment harus sama. Bila dalam suatu
masalah ditemui jumlah assignee dan assignment berbeda, maka perlu ditambahkan
suatu assignee/assignment dummy untuk menyamakan jumlahnya. Setelah data
terpresentasi dalam bentuk tabel penugasan, maka kita dapat langsung
menyelesaikan menggunakan metode Hungarian. Dalam penyelesaiannya, masalah
penugasan terbagi menjadi dua, yaitu masalah minimalisasi dan masalah
maksimalisasi.
Secara
umum langkah-langkah penyelesaian masalah penugasan adalah:
1. Identifikasi
dan penyederhanaan masalah dalam bentuk tabel penugasan.
2. Untuk
kasus minimalisasi, mencari biaya terkecil untuk setiap baris, dan kemudian
menggunakan biaya terkecil tersebut untuk mengurangi semua biaya
yang ada pada baris yang sama. Sedangkan untuk kasus maksimalisasi, mencari
nilai tertinggi untuk setiap baris yang kemudian nilai tertinggi tersebut
dikurangi dengan semua nilai yang ada dalam baris tersebut.
3. Memastikan
semua baris dan kolom sudah memiliki nilai nol. Apabila masih ada kolom yang
belum memiliki nilai nol, maka dicari nilai terkecil pada kolom tersebut untuk
selanjutnya digunakan untuk mengurangi semua nilai yang ada pada kolom
tersebut.
4. Setelah
semua baris dan kolom memiliki nilai nol, maka langkah selanjutnya adalah
memastikan atau mengecek apakah dalam tabel penugasan tersebut, telah
berhasil ditemukan nilai nol, sebanyak sumber daya (bisa karyawan, mesin, alat
transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah
barisnya. Misalnya bila yang akan ditugaskan adalah 4 karyawan, maka harus
ditemukan nilai nol sebanyak 4 buah yang terletak di baris dan kolom yang
berbeda. Sebaiknya dimulai dari baris yang hanya memiliki 1 nilai nol. Langkah
ini menganduk arti bahwa setiap karyawan hanya dapan ditugaskan pada satu
pekerjaan saja.
5. Apabila
belum, maka langkah selanjutnya adalah menarik garis yang menghubungkan minimal
dua buah nilai nol dalam tabel penugasan tersebut.
6. Selanjutnya,
perhatikan nilai-nilai yang belum terkena garis. Pilih nilai yang paling kecil,
kemudian pergunakan untuk mengurangi nilai-nilai lain yang belum terkena garis,
dan gunakan untuk menambah nilai-nilai yang terkena garis dua kali.
7. Dari
hasil lagkah ke-6 tersebut, apakah sekarang telah berhasil ditemukan nilai nol
sejumlah atau sebanyak sumber daya (bisa karyawan, mesin, alat transportasi,
atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya.
8. Jika
sudah, maka masalah penugasan telah optimal, dan apabila belum maka
perlu diulangi langkah penyelesaian ke-5 di atas.
Sebagai
catatan, kasus penugasan dianggap normal apabila jumlah sumber daya yang akan
ditugaskan dan jumlah pekerjaan atau tujuan adalah sama.
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.
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
Dengan batasan :
Dan xij >0 atau 1
BAB
III
STUDI
KASUS
A.
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
2.1 Soal penugasan (minimasi)
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
A
|
20
|
22
|
18
|
15
|
B
|
24
|
23
|
17
|
13
|
C
|
13
|
19
|
13
|
14
|
D
|
16
|
17
|
18
|
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
2.2 Reduced Cost
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
A
|
5
|
7
|
3
|
0
|
B
|
11
|
10
|
4
|
0
|
C
|
0
|
6
|
0
|
1
|
D
|
0
|
1
|
2
|
6
|
1. Reduced
Cost Matrik diatas terus dikurangi untuk mendapatkan
total opportunity costmatrik. Hal ini dapat dicapai dengan memilih elemen
terkecil dari setiap kolom padaReduced Cost Matrik untuk mengurangi
seluruh elemen dalam kolom-kolom tersebut. Matrik total opportunity
cost ditunjukkan dalam Tabel 14 sebagai berikut:
Tabel
2.3 Matrik total opportunity cost
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
A
|
5
|
6
|
3
|
0
|
B
|
11
|
9
|
4
|
0
|
C
|
0
|
5
|
0
|
1
|
D
|
0
|
0
|
2
|
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
2.4 .Tes optimalisasi
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
A
|
5
|
6
|
3
|
0
|
B
|
11
|
9
|
4
|
0
|
C
|
0
|
5
|
0
|
1
|
D
|
0
|
0
|
2
|
6
|
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
2.5 : Revised Matriks and Test for Optimality
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
A
|
2
|
3
|
0
|
0
|
B
|
8
|
6
|
1
|
0
|
C
|
0
|
5
|
0
|
4
|
D
|
0
|
0
|
2
|
9
|
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
|
BIAYA
|
A-MESIN3
|
Rp
18
|
B-MESIN3
|
Rp
13
|
C-MESIN3
|
Rp
13
|
D-MESIN3
|
Rp
17
|
B.
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 2.6). 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 2.6. Matrik ini
sebenarnya bernilai negatif.
Tabel
2.6 Soal penugasan (maksimasi)
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
MESIN
5
|
A
|
13
|
14
|
13
|
10
|
17
|
B
|
16
|
9
|
10
|
13
|
15
|
C
|
12
|
13
|
8
|
11
|
16
|
D
|
14
|
15
|
12
|
8
|
11
|
E
|
9
|
12
|
13
|
4
|
15
|
Tabel
2.7. Opportunity loss
TUGAS
OBJEK |
MESIN
1
|
MESIN
2
|
MESIN
3
|
MESIN
4
|
MESIN
5
|
A
|
4
|
3
|
4
|
7
|
0
|
B
|
0
|
7
|
6
|
3
|
1
|
C
|
1
|
3
|
8
|
5
|
0
|
D
|
6
|
0
|
3
|
7
|
4
|
E
|
2
|
3
|
2
|
1
|
0
|
Untuk langkah kedua dan seterusnya sama dengan masalah minimisasi.
· CONTOH
KASUS :
Manager
pemasaran sebuah industri pakaian mempunyai 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
Pertanyaannya
bagaimana seharusnya manager tersebut memberikan tugas pemasaran tersebut sebagai
keuntungan yang di peroleh maksimal????
2. Penyelesaian
dengan menggunakan manual
TUGAS
OBJEK |
Jas
|
Kemeja
|
Rock
|
blouse
|
Celana
|
Karyawan
A
|
15
|
42
|
38
|
54
|
29
|
Karyawan
B
|
45
|
19
|
27
|
32
|
20
|
Karyawan
C
|
21
|
30
|
41
|
39
|
23
|
Karyawan
D
|
39
|
28
|
16
|
22
|
19
|
dummy
|
0
|
0
|
0
|
0
|
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 |
Jas
|
Kemeja
|
Rock
|
blouse
|
Celana
|
Karyawan
A
|
39
|
12
|
16
|
0
|
25
|
Karyawan
B
|
0
|
26
|
18
|
13
|
25
|
Karyawan
C
|
20
|
11
|
0
|
2
|
18
|
Karyawan
D
|
0
|
11
|
23
|
17
|
20
|
dummy
|
0
|
0
|
0
|
0
|
0
|
TUGAS
OBJEK |
Jas
|
Kemeja
|
Rock
|
blouse
|
Celana
|
Karyawan A
|
39
|
1
|
16
|
0
|
25
|
Karyawan B
|
0
|
15
|
18
|
13
|
25
|
Karyawan C
|
20
|
0
|
0
|
2
|
18
|
Karyawan D
|
0
|
0
|
23
|
17
|
20
|
dummy
|
0
|
0
|
0
|
0
|
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
|
Rp
54,-
|
Karyawan
B ® Jas
|
Rp
45,-
|
Karyawan
C ® Rock
|
Rp
41,-
|
Karyawan
D ® Kemeja
|
Rp
28,-
|
Dummy
® Celana
|
Rp
0,-
|
Total
keuntungan maksimal yang di peroleh adalah Rp. 168,-
|
|
Sehingga
total keuntungan maksimal yang di peroleh adalah Rp. 168,-
PENUTUP
KESIMPULAN
Masalah
penugasan (assignment problem), seperti juga masalah transportasi merupakan
suatu kasus khusus yang ditemui dalam pemrograman linear. Masalah penugasan
berkaitan dengan keinginan perusahaan dalam mendapatkan pembagian atau alokasi
tugas (penugasan) yang optimal, dala arti apabila penugasan tersebut berkaitan
dengan keuntungan maka bagaimana alokasi tugas atau penugasan tersebut
dapat memberikan keuntugan yang maksimal. Setelah data
terpresentasi dalam bentuk tabel penugasan, maka kita dapat langsung menyelesaikan
menggunakan metode Hungarian. Dalam penyelesaiannya, masalah penugasan terbagi
menjadi dua, yaitu masalah minimalisasi dan masalah maksimalisasi.
Kolom/baris
dummy ditambahkan bila jumlah assignee tidak sama dengan assignment, atau
terkadang disebut sebagai masalah tak seimbang. Pada kolom/baris dummy ini
diberikan nilai keuntungan/kerugian sebesar nol. Sedangkan untuk suatu hubungan
assignee dan assignment yang tidak mungkin terjadi, untuk keduanya diberikan
nilai keuntungan sebesar –M atau nilai kerugian sebesar M.
Dari
hasil perhitungan diperoleh hasil keuntungan maksimal. Sehingga totalkeuntungan
maksimal yang di peroleh adalah Rp. 168,-
DAFTAR PUSTAKA
Kenapa pada kolom kemeja dikurangkan dgn elemen terkecil? Sdgkan pada kolom celana tidak?
BalasHapus