Erick Edward. S: Riset Operasi " Metode Penugasan"

Riset Operasi " Metode Penugasan"

Diposting oleh Erick Edward Ploren Sitorus

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. MetodeHungarian 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

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

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

http://arisbudi.staff.gunadarma.ac.id

http://elearning.gunadarma.ac.id/docmodul/pengantar_riset_operasional/bab6-masalah_penugasan.pdf

http://kiayati.staff.gunadarma.ac.id

http://indriastuti90.blogspot.co.id/2011/06/makalah-masalah-penugasan.html

http://matematikakuadrat.blogspot.co.id/2008/11/masalah-penugasan-untuk-kasus-maksimasi.html