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.
Asal Ahli
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
109 Cara 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.
110 Dari 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
0
0
8
7 *
6
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
Pekerja
X
Y
Z
A
20
26
30
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 6
0
4
0
0
*
0 *
3
Pekerja A pada jabatan Z, Pekerja B pada jabatan Y, Pekerja C pada jabatan X, dengan keuntungan = 30 + 15 + 17 = 62
*
0 9
Atau 6
0
4
0
0
3
9
0
*
*
Pekerja A pada jabatan Y, Pekerja B pada jabatan Z, Pekerja C pada jabatan X, dengan keuntungan = 26 + 19 + 17 = 62
0 *
Tabel Pekerja dan Jabatan Jabatan
Pekerja
X
Y
Z
A
20
26
30
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) VARIABLE AX AY AZ BX BY BZ CX CY CZ ROW 2) 3) 4) 5) 6) 7)
62.00000 VALUE 0.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000
REDUCED COST 9.000000 0.000000 0.000000 8.000000 0.000000 0.000000 0.000000 0.000000 6.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
LP OPTIMUM FOUND AT STEP
DUAL PRICES 0.000000 -11.000000 -12.000000 29.000000 26.000000 30.000000 3
OBJECTIVE FUNCTION VALUE 1) VARIABLE BX BY BZ CX CY CZ AX AY AZ
62.00000 VALUE 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000
REDUCED COST 0.000000 0.000000 0.000000 0.000000 8.000000 14.000000 1.000000 0.000000 0.000000
113
ROW 2) 3) 4) 5) 6) 7)
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
NO. ITERATIONS=
DUAL PRICES 0.000000 5.000000 9.000000 21.000000 10.000000 17.000000
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.
114 Selanjutnya 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
115 Gaji yang diminta tiap bulan dari pekerja tersebut adalah seperti Tabel 4 berikut: Tabel 4. Data permintaan gaji pelamar Pekerjaan
Gaji
Kode Pelamar A1
A2
A3
A4
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:
116 Tabel 2. Jarak antara tempat asal dengan tempat tujuan.
Tempat Asal
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
Gaji
Kode Pelamar A1
A2
A3
A4
A5
A6
A7
50
60
50
45
45
60
35
Tentukan 5 calon yang harus diterima agar keuntungan perusahaan maksimum.
117
2. 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 memperoleh 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 BDG SMG MALANG
10
CRB
JOGJA
SOLO
MADIUN JEMBER
15 15
10
10
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.
119 Tabel Transportasi Gabungan BDG
SMG MALANG TASIK CRB JOGJA SOLO MADIUN JEMBER Kapasitas
JKT
10
15
25
M
M
M
M
M
M
6
SBY
20
15
10
M
M
M
M
M
M
8
BDG
0
M
M
10
15
M
M
M
M
14
SMG
M
0
M
M
15
10
10
M
M
14
MALANG
M
M
0
M
M
20
15
10
10
14
14
14
14
2
1
3
4
2
2
14
Permintaan
Dari tabel ini, maka sistem transportasi dapat dicari, dan akhirnya sistem transshipment dapat ditentukan. i. Program Lingo untuk Menyelesaikan Masalah Transshipment Masalah transshipmen ini apabila diselesaikan dengan Lingo, maka kita memberikan nilai M yang cukup besar, misalnya 1000, maka program Lingo untuk masalah ini adalah sebagai berikut. Model: Sets: Kapasitas/JKT, SBY, BDG, SMG, MLG/:Asal; Permintaan/BDG1, SMG1, MLG1, TASIK, CRB, JOGJA, SOLO, MADIUN, JEMBER/:Demand; Links(Kapasitas,Permintaan):Ship, Cost; Endsets Min=@sum(Links:Ship*Cost); @for(Permintaan(j):@sum(Kapasitas(i):Ship(i,j))>Demand(j)); @for(Kapasitas(i):@sum(Permintaan(j):Ship(i,j))
1000, 1000, 1000, 10, 15,
1000, 1000, 1000, 1000, 10,
1000, 1000, 1000, 1000, 10;
Enddata End
Setelah program kita jalankan dan kita ambil data yang diperlukan, maka akan kita peroleh.
120
Rows=
15 Vars=
Nonzeros=
45 No. integer vars=
149 Constraint nonz=
90(
0
90 are +- 1) Density=0.216
Smallest and largest elements in absolute value= No. < :
5 No. =:
Single cols=
0 No. > :
( all are linear)
1.00000
9, Obj=MIN, GUBs <=
1000.00
9
0
Optimal solution found at step: Objective value:
24 320.0000
Variable
Value
Reduced Cost
SHIP( JKT, BDG1)
3.000000
0.0000000E+00
SHIP( JKT, SMG1)
3.000000
0.0000000E+00
SHIP( JKT, MLG1)
0.0000000E+00
15.00000
SHIP( JKT, TASIK)
0.0000000E+00
980.0000
SHIP( JKT, CRB)
0.0000000E+00
975.0000
SHIP( JKT, JOGJA)
0.0000000E+00
975.0000
SHIP( JKT, SOLO)
0.0000000E+00
975.0000
SHIP( JKT, MADIUN)
0.0000000E+00
980.0000
SHIP( JKT, JEMBER)
0.0000000E+00
980.0000
SHIP( SBY, BDG1)
0.0000000E+00
10.00000
SHIP( SBY, SMG1) SHIP( SBY, MLG1)
4.000000
0.0000000E+00
4.000000
0.0000000E+00
SHIP( SBY, TASIK)
0.0000000E+00
980.0000
SHIP( SBY, CRB)
0.0000000E+00
975.0000
SHIP( SBY, JOGJA)
0.0000000E+00
975.0000
SHIP( SBY, SOLO)
0.0000000E+00
975.0000
SHIP( SBY, MADIUN)
0.0000000E+00
980.0000
SHIP( SBY, JEMBER)
0.0000000E+00
980.0000
SHIP( BDG, BDG1)
11.00000
0.0000000E+00
SHIP( BDG, SMG1)
0.0000000E+00
995.0000
SHIP( BDG, MLG1)
0.0000000E+00
1000.000
SHIP( BDG, TASIK) SHIP( BDG, CRB)
2.000000
0.0000000E+00
1.000000
0.0000000E+00
SHIP( BDG, JOGJA)
0.0000000E+00
985.0000
SHIP( BDG, SOLO)
0.0000000E+00
985.0000
SHIP( BDG, MADIUN)
0.0000000E+00
990.0000
SHIP( BDG, JEMBER)
0.0000000E+00
990.0000
SHIP( SMG, BDG1)
0.0000000E+00
1005.000
SHIP( SMG, SMG1) SHIP( SMG, MLG1)
7.000000 0.0000000E+00
0.0000000E+00 1005.000
121 SHIP( SMG, TASIK)
0.0000000E+00
SHIP( SMG, CRB)
0.0000000E+00
995.0000 5.000000
SHIP( SMG, JOGJA)
3.000000
0.0000000E+00
SHIP( SMG, SOLO)
4.000000
0.0000000E+00
SHIP( SMG, MADIUN)
0.0000000E+00
995.0000
SHIP( SMG, JEMBER)
0.0000000E+00
995.0000
SHIP( MLG, BDG1)
0.0000000E+00
1000.000
SHIP( MLG, SMG1)
0.0000000E+00
995.0000
SHIP( MLG, MLG1)
10.00000
0.0000000E+00
SHIP( MLG, TASIK)
0.0000000E+00
990.0000
SHIP( MLG, CRB)
0.0000000E+00
985.0000
SHIP( MLG, JOGJA)
0.0000000E+00
SHIP( MLG, SOLO)
0.0000000E+00
5.000000 0.0000000E+00
SHIP( MLG, MADIUN)
2.000000
0.0000000E+00
SHIP( MLG, JEMBER)
2.000000
0.0000000E+00
Hasil ini apabila kita pindah kedalam tabel, maka akan kita peroleh tabel berikut. Biaya Trashipment 320.
JKT SBY
BDG
SMG
3
3 4
MLNG
TSIK
CRB JGJA SOLO MDIUN
JBER
Kapasitas 6
4
BDG
8 3
1
SMG
3
4
MALANG Permintaan
2
1
3
4
2
2
2
2
14
Dari tabel ini, dapat disimpulkan bahwa, Dari Jakarta terdapat 6 buah alat berat, 3 buah dikirim ke Bandung, dan 3 buah ke Semarang. Dari Surabaya terdapat 8 buat alat berat, 4 buah dikirim ke Semarang, dan 4 buah dikirim ke Malang. Kota Bandung mendapat kiriman dari Jakarta 3 buah alat berat, dikirim ke Tasikmalaya 2 buah dan dikirim ke Cirebon 1 buah.
122 Kota Semarang mendapat kiriman dari Jakarta 3 buah dan dari Surabaya 4 buah alat berat, dikirim ke Jogja 3 buah dan dikirim ke Solo 4 buah. Kota Malang mendapat kiriman dari Surabaya 4 buah alat berat, dikirim ke Madiun 2 buah dan dikirim ke Jember 2 buah.
ii. Program Solver untuk Menyelesaikan Masalah Transshipment Masalah Transshipment ini apabila dikerjakan dengan Solver, maka kita buat tabel awal sebagai berikut.
Setelah Solver dijalankan dengan mengisi menu solver (Solver Parameter) berikut.
123
Maka akan kita peroleh hasil sebagai berikut.
124 Dari hasil ini, maka kesimpulan dapat diambil sama seperti kesimpulan pada penyelesaian dengan Lingo di atas.
Soal-soal 1. Dua pabrik batu bara terletak di Pontianak dan Balikpapan masing-masing dapat menghasilkan 300 ton setiap bulannya. Sementara Perusahaan yang memerlukan batu bara berada di pulau Jawa, yaitu di 10 kota: Banten, Jakarta, Cirebon, Tegal, Pekalongan, Semarang, Kudus, Surabaya, Malang, dan Banyuwangi. Dari kota-kota tersebut berturut-turut memerlukan bata-bara (dalam ton): 50, 100, 50, 75, 60, 40,40, 50, 30, dan 30. Pengangkutan batu bara dilakukan dengan dua tahap, yaitu dari Pontianak dan Balikpapan ke pelabuhan di Jakarta, Semarang, dan Surabaya menggunakan kapal, Sedangkan dari Pelabuhan ke kota-kota tujuan menggunakan Truk. Biaya Pengangkutan tiap ton batu bara terlihat pada tabel berikut. Biaya Pengiriman batu bara Dengan Kapal Jakarta Semarang Surabaya Pontianak
50
60
70
Balikpapan
80
70
60
Dengan Truk Banten Jakarta
20
Semarang
Jakarta Cirebon Tegal Pklongan Smrang 5
25
30
25
20
Surabaya
15
Kdus
Srbaya
5
10
20
20
15
5
Mlang Bnywngi
15
20
Buatlah sistem transshipment agan biaya pengiriman batu bara minimum.
2. Bagaimana sistem transshipment pada soal no 1 ini bilamana kebutuhan batu bara di Tegal, Surabara, dan Banyuwangi masing-masing naik 25 ton sebulan, sementara kebutuhan di Jakarta turun 25 ton sebulannya.
125 3. Bagaimana sistem transshipment pada contoh soal di atas (tentang alat berat) bilamana jumlah alat berat di Jakarta ada 10 buah, dan di surabaya ada 6 buah.
