BAB I
PENDAHULUAN
1.1
Latas 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 penugasan (assignment problem), seperti
juga masalah transportasi merupakan suatu kasus khusus yang ditemui dalam
pemrograman linear. Permasalahan penugasan atau assignment
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. MetodeHungarian dikembangkan oleh seorang ahli matematika
berkebangsaan Hungaria yang bernama D Konig pada tahun 1916.
1.2
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.
1.3
Tujuan Penulisan
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.
1.4
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
2.1 Sejarah Definisi Teori Antrian
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.
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.
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.
2.2
Metode Penyelesaian
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 mn, sehingga diasumsikan bahwa m=n.
Secara matematis, model penugasan ini dapat dinyatakan sebagai berikut: Dengan demikian, model persoalan penugasan
ini adalah Minimum (maksimum) Denganbatasan : Dan xij >0 atau 1.
BAB III
STUDI KASUS
3.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 berikut :
|
assignee
|
Rudi
|
Bobby
|
Islan
|
Rendy
|
|
|
assigment
|
|||||
|
K3
|
50
|
54
|
46
|
40
|
|
|
Sem
|
58
|
56
|
44
|
36
|
|
|
Som
|
36
|
48
|
36
|
38
|
|
|
Sam
|
42
|
44
|
46
|
54
|
|
Tabel
3.1 Soal Penugasan (Minimasi)
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:
|
Assignee
|
Rudi
|
Bobby
|
Islan
|
Rendy
|
|
|
Assigment
|
|||||
|
K3
|
10
|
14
|
6
|
0
|
|
|
Sem
|
22
|
20
|
8
|
0
|
|
|
Som
|
0
|
12
|
0
|
2
|
|
|
Sam
|
0
|
2
|
4
|
12
|
|
Tabel 3.2 Reduced Coast
2. Reduced
Cost Matrik diatas terus dikurangi untuk mendapatkan total opportunity
costmatrik. 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 3.3
sebagai berikut:
|
Assignee
|
Rudi
|
Bobby
|
Islan
|
Rendy
|
|
|
Assigment
|
|||||
|
K3
|
10
|
12
|
6
|
0
|
|
|
Sem
|
22
|
18
|
8
|
0
|
|
|
Som
|
0
|
10
|
0
|
2
|
|
|
Sam
|
0
|
0
|
4
|
12
|
|
Tabel 3.3 Matriks total oppornity
cost
3. 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.
|
assignee
|
Rudi
|
Bobby
|
Islan
|
Rendy
|
|
|
assigment
|
|||||
|
K3
|
4
|
6
|
0
|
0
|
|
|
Sem
|
22
|
18
|
8
|
0
|
|
|
Som
|
0
|
10
|
0
|
2
|
|
|
Sam
|
0
|
0
|
4
|
12
|
|
Tabel 3.4 Test Optimalisasi
4. 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:
|
assignee
|
Rudi
|
Bobby
|
Islan
|
Rendy
|
|
|
assigment
|
|||||
|
K3
|
50
|
54
|
46
|
40
|
|
|
Sem
|
58
|
56
|
44
|
 36 |
|
|
Som
|
36
|
48
|
36
|
38
|
|
|
Sam
|
42
|
44
|
46
|
54
|
|
|
assignee
|
Rudi
|
Bobby
|
Islan
|
Rendy
|
|
|
assigment
|
|||||
|
K3
|
4
|
6
|
0
|
0
|
|
|
Sem
|
22
|
18
|
8
|
0
|
|
|
Som
|
0
|
10
|
0
|
2
|
|
|
Sam
|
0
|
0
|
4
|
12
|
|
Tabel 3.5 Jadwal Penugasan
Optimal
|
assignee
|
Nilai
|
|
assigment
|
|
|
Islan sebagai K3
|
46
|
|
Rendy sebagai SEM
|
36
|
|
Rudi sebagai SOM
|
36
|
|
Bobby sebagai SAM
|
44
|
BAB IV
PENUTUP
4.1 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.
Dari
hasil perhitungan diperoleh hasil untuk Islan yang menduduki Pekerjaan sebagai
K3 dengan Nilai 46, Rendy yang menduduki Pekerjaan sebagai SEM dengan Nilai 36,
Rudi yang menduduki Pekerjaan sebagai
SOM dengan Nilai 36, dan Bobby yang menduduki Pekerjaan sebagai SAM dengan
Nilai 34.
