BAB IV Penugasan dan Transshipment 1. Penugasan Masalah penugasan bermula dari penempatan para pekerja pada bidang yang tersedia agar biaya yang ditanggung pemberi tugas/perusahaan dapat diminimalkan. Jika dalam hal ini, pekerja dianggap sebagai sumber dan pekerjaan dianggap sebagai tujuan, sehingga masalah penugasan akan sama dengan masalah transportasi, dimana banyaknya sumber dan banyaknya tujuan adalah sama, setiap sumber hanya menghasilkan satu demikian pula setiap tujuan hanya memerlukan satu. a. Menyelesaikan Masalah Penugasan dengan Algoritma Hungaria Untuk lebih mudah memahami, marilah kita perhatikan contoh masalah berikut: Sebuah perusahaan yang berada di tiga kota yaitu Banjarmasin, Solo, dan Denpasar memerlukan tenaga ahli untuk menyelesaikan pekerjaan tertentu. Ketiga ahli itu berada di Jakarta, Surabaya, dan Ujung Pandang. Biaya ketiga orang ahli tersebut adalah seperti Tabel 2.6.a. Tabel 2.6.a. Tujuan Banjarmasin Solo Denpasar Jakarta 30 36 40 Surabaya 20 25 29 Ujung Pandang 27 24 22 Untuk menyelesaikan masalah ini akan digunakan sebuah metode yang disebut dengan Metode Hongaria, Langkah-langkah menyelesaikan masalah penugasan dengan algoritma Hungaria adalah sebagai berikut: 108 109Cara menentukan total biaya minimum adalah dengan mengurangkan setiap baris dengan bilangan terkecil dari baris itu sendiri, sehingga kita peroleh tabel berikut: 0 6 10 0 5 9 5 2 0 Selanjutnya dikurangi dengan bilangan terkecil menurut kolom-kolomnya, sehingga diperoleh tabel berikut: 0 4 10 0 3 9 5 0 0 Selanjutnya dibuat garis sesedikit mungkin menurut baris atau kolom sehingga menutup semua bilangan nol (0). Bilamana jumlah garis masih lebih kecil dari banyaknya baris atau kolom, maka belum dapat disusun tabel optimalnya. Dalam hal diatas diperlukan dua garis, sehingga harus dilakukan langkah berikutnya yaitu: Mengurangi semua bilangan yang tidak tertutup garis dengan bilangan terkecil, dan menambahkan bilangan tersebut kepada persilangan garis penutup. Pada masalah diatas, diperoleh tabel berikut: 0 1 7 0 0 6 8 0 0 Dari tabel di atas, bagaimanapun caranya mencoret bilangan nol, paling sedikit diperlukan tiga buah garis. Langkah selanjutnya memilih sel nol untuk setiap baris atau kolom. Caranya ialah ada dua yaitu menurut baris atau menurut kolom. Pilih sel yang baris/kolom yang bilangan nolnya hanya satu (paling sedikit) Buang baris dan kolom pada sel yang terpilih. Lakukan terus sampai selesai. 110Dari tabel diatas misalnya kita lakukan pada baris, maka sel pada baris 1 kolom 1 adalah set pertama yang dipilih, jadi baris 1 dan kolom 1 dibuang (diabaikan) 0 * 1 7 0 0 * 6 8 0 0 * Setelah kita lakukan proses diatas, maka sel yang terpilih adalah sel (1,1), (2,2), dan (3,3). Sehingga total biaya minimal yang diperlukan adalah 30 + 25 + 22 = 77. Dimana Banjarmasin mendatangkan ahli dari Jakarta, Solo mendatangkan ahli dari Surabaya, dan Denpasar mendatangkan ahli dari Ujung Pandang. Masalah penugasan ini juga dapat digunakan untuk masalah maksimum, yaitu dengan mengubah sedikit masalah maksimum ke minimum. Untuk lebih mudahnya kita ambil contoh berikut: Sebuah Perusahaan akan memberi tugas kepada tiga orang ( A, B, C) untuk menduduki jabatan tertentu (X,Y, Z). Keuntungan dari ketiga orang pada ketiga jabatan tersebut sebagai berikut: Jabatan X Y Z A 20 26 30 Pekerja B 10 15 19 C 17 14 12 Langkah pertama adalah membuat tabel regrete, yaitu tabel karena tidak mengambil tindakan terbaik. Cara membuat adalah dengan mengurangkan setiap sel dengan bilangan terbesar tiap barisnya. Langkah ini menghasilkan tabel berikut: 10 4 0 9 4 0 0 3 5 111 Selanjutnya kita lakukan langkah-langkah seperti pekerjaan minimum, sehingga kita peroleh tabel berikut: 6 0 0 4 0 0 0 3 9 Penugasan optimal dicapai pada Pekerja A pada jabatan Z, Pekerja 6 0 0 * B pada jabatan Y, Pekerja C pada jabatan X, dengan keuntungan = 30 4 0 * 0 + 15 + 17 = 62 0 * 3 9 Atau Pekerja A pada jabatan Y, Pekerja 6 0 * 0 B pada jabatan Z, Pekerja C pada jabatan X, dengan keuntungan = 26 4 0 0 * + 19 + 17 = 62 0 * 3 9 Tabel Pekerja dan Jabatan Jabatan X Y Z A 20 26 30 Pekerja B 10 15 19 C 17 14 12 b. Menyelesaikan Masalah Penugasan dengan Program Komputer i. Program Lindo untuk Menyelesaikan Masalah Penugasan Dengan komputer (program Lindo) juga dapat digunakan untuk menyelesaikan masalah penugasan ini yaitu seperti permasalahan pada transportasi. Program perhitungan dipersilahkan kepada pembaca sebagai latihan. 112 MAX 20 AX + 26 AY + 30 AZ + 10 BX + 15 BY + 19 BZ + 17 CX + 14 CY + 12 CZ SUBJECT TO 2) AX + AY + AZ = 1 3) BX + BY + BZ = 1 4) CX + CY + CZ = 1 5) AX + BX + CX = 1 6) AY + BY + CY = 1 7) AZ + BZ + CZ = 1 END Hasil perhitungan dengan Lindo diperoleh sebaga berikut: LP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1) 62.00000 VARIABLE VALUE REDUCED COST AX 0.000000 9.000000 AY 0.000000 0.000000 AZ 1.000000 0.000000 BX 0.000000 8.000000 BY 1.000000 0.000000 BZ 0.000000 0.000000 CX 1.000000 0.000000 CY 0.000000 0.000000 CZ 0.000000 6.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 -11.000000 4) 0.000000 -12.000000 5) 0.000000 29.000000 6) 0.000000 26.000000 7) 0.000000 30.000000 LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 62.00000 VARIABLE VALUE REDUCED COST BX 0.000000 0.000000 BY 0.000000 0.000000 BZ 1.000000 0.000000 CX 1.000000 0.000000 CY 0.000000 8.000000 CZ 0.000000 14.000000 AX 0.000000 1.000000 AY 1.000000 0.000000 AZ 0.000000 0.000000 113 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 5.000000 4) 0.000000 9.000000 5) 0.000000 21.000000 6) 0.000000 10.000000 7) 0.000000 17.000000 NO. ITERATIONS= 3 ii. Program Solver untuk Menyelesaikan Masalah Penugasan Diselesaikan dengan Solver, maka kita buat tabel dan hasilnya sebagai berikut. Seperti pada penyelesaian masalah transportasi, masalah Penugasan dikerjakan dengan memulai mengisi nilai awal = 0. sehingga tabel awalnya sebagai berikut Setelah solver dijalankan dengan mengisi / memilih seperti gambar berikut. 114Selanjutnya dengan memilih Solve, maka akan diperoleh hasil seperti berikut. Dari hasil ini dapat disimpulkan bahwa Pendapatan optimun terjadi apabila A ditempatkan pada jabatan Z, B pada jabatan Y dan C pada jabatan X. Dengan pendapatan sebesar 62. Soal-soal 1. Suatu perusahaan memerukan 4 orang untuk 4 pekerjaan, sebut saja pekerjaan P, Q, R, dan S. Pekerjaan-pekerjaan itu akan diisi oleh 4 calon, yaitu: A1, A2, A3, dan A4. Prediksi pendapatan tiap bulan yang diperoleh apabila pekerjaan diserahkan kepada pekerja tersebut adalah seperti Tabel 3 berikut: Tabel 3. Prediksi pendapatan dari Pekerjaan Pekerjaan Kode Pelamar A1 A2 A3 A4 P 100 120 85 100 Q 70 110 70 80 R 95 110 90 90 S 90 115 80 100 115Gaji yang diminta tiap bulan dari pekerja tersebut adalah seperti Tabel 4 berikut: Tabel 4. Data permintaan gaji pelamar Pekerjaan Kode Pelamar A1 A2 A3 A4 Gaji 50 60 50 45 Berikan penyelesaian tentang posisi pekerjaan para pekerja tersebut agar pendapatan perusahaan maksimum. 2. Sebuah Kantor akan mengangkat empat Kepala SubBagian (Kasubag) dari empat orang, yaitu Keuangan, Rumah Tangga, Pelayanan Masyarakat, dan Kerja Sama. Keempat calon adalah A1, A1, A3, dan A4. Dari keempat orang tersebut mengajukan anggaran seperti terlihat pada Tabel 4 berikut: Tabel 4. Usulan dana berkenaan jabatan Jabatan Calon Pejabat Kasubag A1 A2 A3 A4 Keuangan 100 90 90 100 Rumah Tangga 70 65 85 90 Pelayanan Masyarakat 80 70 70 90 Kerja Sama 75 65 80 95 Tentukan posisi jabatan masing-masing agar biaya pengelolaan pekerjaan minimal. Adakah posisi lain yang sama-sama menguntungkan?. 3. Untuk melayani transportasi Anak Sekolah/Pegawai Kantor, sebuah perusahaan kereta api listrik akan membeli empat buah lokomotif yang akan ditempatkan pada tiga tempat yang menyebar dalam kota itu, yaitu tempat I, II, dan III, masing-masing sebuah lokomotif kecuali tempat III sebanyak dua buah lokomotif. Lokomotif-lokomotif itu akan melayani perjalanan dari kota asal menuju tempat tujuan di pagi hari, dan pulang di siang hari. Jarak antara tempat asal dan tempat tujuan terlihat pada Tabel 2 berikut: 116Tabel 2. Jarak antara tempat asal dengan tempat tujuan. Tempat tujuan A B C D I 13 35 42 9 II 6 61 18 30 III 15 10 5 9 Tentukan jaringan rel kereta api, agar total panjang rel minimum. 4. Suatu perusahaan memerlukan 5 orang untuk 5 pekerjaan, sebut saja pekerjaan P, pekerjaan Q, pekerjaan R, pekerjaan S, dan pekerjaan T. Untuk memenuhi pekerjaan itu, perusahaan membuka lowongan kerja, dan ternyata yang melamar ada 7 orang, kemudian diberi kode: A1, A2, ..., A7. Prediksi pendapatan tiap bulan yang diperoleh apabila pekerjaan diserahkan kepada pelamar adalah seperti Tabel 2 berikut: Tabel 2. Prediksi pendapatan dari Pekerjaan Pekerjaan Kode Pelamar A1 A2 A3 A4 A5 A6 A7 P 100 120 85 100 90 130 90 Q 70 110 70 80 100 120 90 R 95 110 90 90 60 140 100 S 90 115 80 100 80 150 80 T 70 100 80 75 100 120 75 Para pelamar disuruh mengajukan gaji yang diminta setiap bulannya. Hasil permintaan gaji pelamar adalah seperti Tabel 3 berikut: Tabel 3. Data permintaan gaji pelamar Pekerjaan Kode Pelamar A1 A2 A3 A4 A5 A6 A7 Gaji 50 60 50 45 45 60 35 Tentukan 5 calon yang harus diterima agar keuntungan perusahaan maksimum. 1172. Transshipment Transshipment adalah masalah transportasi tetapi untuk mengirim barang dari tempat produksi ke tempat permintaan tidak dapat dilakukan secara langsung. Barang yang diangkut harus mengalami dua atau lebih cara pengangkutan. Misalnya Seorang petani tidak dapat m emperoleh pupuk dari Pabrik langsung, tetapi harus melalui agen daerah, bahkan agen daerah harus memalui agen pusat baru dari Pabrik. Jadi proses penangkutan barang dari tempat produksi ke tempat permintaan harus melalui semacam agen terlebih dahulu. Sebagai contoh perhatikan masalah transshipment berikut. Sebuah Perusahaan Alat Berat Arifin memiliki 14 alat berat yang berada di Jakarta sebanyak 6 buah dan di Surabaya 8 buah. Alat berat tersebut akan dipakai di 6 kota, yaitu Tasikmalaya 2 buah, Cirebon 1 buah, Jogja 4 buah, Solo 4 buah, Madiun 3 buah, dan Jember 2 buah. Karena kondisi jalan, pengangkutan tidak dapat langsung dari kota asal ke kota tujuan dan harus melalui kota Transit yaitu Kota Bandung, Kota Semarang, dan Kota Malang. Alur pengiriman barang dan Biaya pengangkutan sebuah alat berat terlihat pada Gambar 1 dan tabel berikut. Tabel Biaya Satuan Pengangkutan dari Kota Asal ke Kota Transit BDG SMG MALANG JKT 10 15 25 SBY 20 15 10 Tabel Biaya Satuan Pengangkutan Kota Transit ke Tempat Tujuan TASIK CRB JOGJA SOLO MADIUN JEMBER BDG 10 15 SMG 15 10 10 MALANG 20 15 10 10 118 Gambar 1. Alur Pengiriman Barang, Perasediaan Barang, Kebutuhan Barang, dan Biaya Satuan Pengangkutan Masalah. Tentukan sistem Transshipment agar biaya pengiriman barang minimum. Penyelesaian. Untuk menyelesaikan masalah transshipment ini, pada setiap kota transit harus dibuat atau disediakan barang (alat) dummy yang besarnya sama dengan jumlah semua kapasitas produk atau persediaan barang. Tabel Transportasi dibuat dengan menggabung kedua tabel tersebut dan memberikan biaya yang cukup besar (M) kepada semua yang tidak mempunyai jalur transportasi, sehingga pada masalah diatas diperoleh tabel transportasi sebagai berikut.