BAB III
PENUGASAN
TUJUAN PRAKTIKUM PENUGASAN
- Memahami permasalahan penugasan dalam dunia nyata dan mampu merumuskannya.
- Memahami bagaimana mencari solusi/menyelesaikan permasalahan penugasan
- Memahami permasalahan penugasan dalam dunia nyata dan mampu merumuskannya.
- 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 berbeda-beda 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 | 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 :
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:
| 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 |
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 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 |
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 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.
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 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 |
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 |
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 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 3.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 | 3 | 2 | 1 | 0 |
Untuk langkah kedua dan seterusnya sama dengan masalah minimisasi.
- PERMASALAHAN
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
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, 26, 22, 29
bagai mana seharusnya manager tersebut memberikan tugas pemasaran tersebut sebagai keuntungan yang di peroleh maksimal.
- 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 |
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 |
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 |
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.
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,- | |
Penyelesaian Dengan Menggunakan Software WinQSB
- Buka program WinQSB dan pilih menu network modeling.
- Buka file|new problem sampai muncul kotak dialog pada Gambar berikut:
- Buka program WinQSB dan pilih menu network modeling.
Gambar 3.8. Kotak dialog problem specification
- Kemudian isi data sesuai Gambar 3.8 dan klik OK
- Kemudian akan mucul tabel penginputan data seperti pada Gambar 3.9 dan ketikkan data yang telah didapatkan pada tabel tersebut (lihat Gambar 3.9)
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
Karyawan a memasarkan blouse dengan biaya Rp. 54
Karyawan b memasarkan Jas dengan biaya Rp.45
Karyawan c memasarkan Rock dengan biaya Rp.41
Karyawan d memasarkan Kemeja dengan biaya Rp.28
Dummy memasarkan Celana dengan biaya Rp.0
Sehingga total keuntungan maksimal yang di peroleh adalah Rp. 168,-
- 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:
Karyawan a memasarkan blouse dengan biaya Rp. 54
Karyawan b memasarkan Jas dengan biaya Rp.45
Karyawan c memasarkan Rock dengan biaya Rp.41
Karyawan d memasarkan Kemeja dengan biaya Rp.28
Dummy memasarkan Celana dengan biaya Rp.0
Sehingga total keuntungan maksimal yang di peroleh adalah Rp. 168,-
Tidak ada komentar:
Posting Komentar