Recent post
Archive for 2019
BAB I
PENDAHULUAN
PENDAHULUAN
1.1 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 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
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 adalahMinimum (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 :
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
|
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
diatas sebagai berikut:
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
