Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
ISSN 2085-7829
Penyelesaian Masalah Transshipment Menggunakan Vogels’s Approximation Method (VAM) Transshipment Problem Solving Using Vogels’s Approximation Method (VAM)
Syaripuddin Program Studi Statistika FMIPA Universitas Mulawarman Abstract This study aims to discuss these cases and the transshipment problem will be solved using the VAM and the Microsoft Excel Solver. Based on a discussion of the results it can be concluded that the initial steps used to solve the transshipment problem is to arrange transportation in advance a tabel consisting of the source column, connecting the city and destination city. The next tabel is solved using the method of transportation VAM. In the cases discussed in this study, it is gaining attention is the determination of allocations in the cii = 0. Because the determination of allocations in the cii can have an impact on the final solution. Keywords : Transshipment problems, transportation problems, method of VAM
Latar Belakang Pada masa perang dunia II, angkatan perang Inggris membentuk suatu team yang terdiri dari ilmuwan untuk mempelajari persoalanpersoalan strategi dan teknik sehubungan dengan serangan-serangan yang dilancarkan terhadap negaranya. Selanjutnya ilmu yang lahir dari team ilmuawan Inggris itu merupakan cikal bakal ilmu opreration research. Setelah perang dunia II berahir, operatons research berkembang pesat di Amerika dan sampai sekarang telah banyak digunakan di hampir seluruh kegiatan, baik di perguruan tinggi, konsulatan, rumah sakit, perencanaan kota, maupun pada kegiatan-kegiatan bisnis. Masalah transshipment adalah kasus khusus dari masalah transportasi yang merupakan bagian dari ilmu opreation research. Sedanglan masalah transpotasi adalah suatu metode yang digunakan untuk mengatur distribusi dari sumbersumber yang menyediakan produk yang sama atau sejenis ke tempat tujuan secara optimal. Distribusi dilakukan sedemikain sehingga permintaan dari beberapa tempat tujuan dapat dipenuhi dari beberapa tempat asal yang masing-masing dapat memiliki permintaan dan kapasitas yang berbeda. Masalah transshipment yang merupakan bentuk khusus dari masalah transportasi menpunyai ciri bahwa adalah cara pengiriman barang dari tempat permintaan tidak dapat dilakukan secara langsung. Barang yang diangkut harus mengalami dua atau lebih cara pengangkutan. Misalnya seorang penjual eceran tidak dapat memperoleh barang langsung dari pabrik tetapi harus melalui agen daerah, bahkan seorang agen daerah harus mendapatkan barang dari agen pusat. Jadi proses pengangkutan barang dari tempat produksi ke
Program Studi Statistika FMIPA Universitas Mulawarman
tempat permintaan harus melalui semacam agen terlebih dahulu. Salah satu metode yang digunakan untuk menyelesaikan masalah transshipment adalah Vogel’s Approximation Method (VAM). Metode ini lebih sederhana dan lebih cepat mengatur alokasi dari beberapa sumber ke tujuan dibandingkan metode lain seperti metode stepping stone dan modified distibution method (MODI). Pada pembahasan ini pula akan digunakan solver microsoft Excel untuk menyelesaikan masalah transshipment yang akan digunakan sebagai pembanding dari hasil yang diperoleh menggunakan VAM. Pada penelitian ini akan dibahas contoh kasus metode transshipment dan akan diselesaikan menggunakan VAM. Hasil dari penyelesaian contoh kasus tersebut yang akan menjadi kesimpulan dari penelitian ini. Tinjauan Pustaka Persoalan transportasi membahas masalah pendistribusian suatu komoditas atau produk dari sejumlah sumber kepada sejumlah tujuan dengan maksud meminimumkan ongkos pengangkutan yang terjadi. Ciri-ciri khusus masalah transportasi adalah 1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu. 2. Kuantitas komoditas atau barang yang didistribusikan dari setiap sumber dan yang diminta oleh setiap tujuan besarnya tertentu 3. Komoditas yang dikirim atau diangkut dari suatu sumber ke suatu tujaun besarnya sesuai dengan permintaan dan atau kapasitas sumber.
1
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
ISSN 2085-7829
4.
Ongkos Pengangkutan komoditas dari suatu sumber ke suatu sumber tujuan besarnya tertentu. Formulasi program linier dari masalah transportasi ditulis sebagai berikut : Minimumkan z
m
Model transshipment adalah model transportasi yang memungkinkan dilakukan pengiriman barang dengan cara tidak lansung, dimana barang dari suatu sumber dapat berada pada sumber lain sebelum mencapai tujuan akhirnya. Jadi pada masalah transshipment ini suatu sumber dapat berperan sebagai tujuan dan sebaliknya suatu tujuan dapat berperan sebagai sumber. Dalam model ini setiap sumber maupun tujuan dipandang sebagai titik potensial bagi demand maupun supply. Oleh karena itu untuk menjamin bahwa tiap titik potensial tersebut mampu menampung total barang di samping jumlah barang yang ada di titik tersebut maka perlu ditambahkan kepada titik-titk itu kuantitas supply dan demandnya masing-masing sebesar B.
n
c
ij x ij
i 1 j 1
Berdasarkan Pembatas : n
x
ij
ai , i 1,2,..., m
j 1 n
x
ij
b j , j 1,2,..., n
i 1
xij 0, i, j
B
Sebagai ilustarasi: Jika ada dua sumber dan tiga tujuan (m=2 dan n=3). Maka formulasinya berbentuk Minimumkan
Berdasarkan Pembatas: Pembatas Sumber
1
x13
2
x23
c14 x14
c23
Bentuk umum tabel yang digunakan untuk masalah transportasi jika ada dua sumber dan tiga tujuan (m=2 dan n=3) adalah :
x13 : c13 x14 : c14 x15 : c15
c24 x24
c11 x25
6
x36 : c36 3
x37 : c37 x38 : c38
b1
1
x46 : c46 x56 : c56 x47 : c47
4
x23 : c23 x24 : c24 x25 : c25
c15 x15
Tabel-3: Biaya Satuan Pengangkutan dari Kota Penghubung ke Kota Tujuan 6 7 8 c36 c37 c38 3 x36 x37 x38 c46 c47 c48 4 x46 x47 x48 c56 c57 c58 5 x56 x57 x58
Tabel-1: Transpotasi Dua Sumber Dengan Tiga Tujuan Tujuan 1 2 3 c11 c12 c13 1 x11 x12 x13 Sumber x21 c21 c22 c23 2 x22 x23
2
i
j 1
c13
x11 x21 b1 x12 x22 b2 x13 x23 b3
1
b
Sebagai ilustarasi: Jika pada alur pengiriman barang terdapat dua sumber, tiga pengubung dan tujuan seperti terlihat pada tabel-2, tabel-3 dan gambar-1 berikut :
dan Pembatas Tujuan
1
n
Tabel-2 : Biaya Satuan Pengangkutan dari Kota Asal ke Kota Penghubung 3 4 5
x11 x12 x13 a1 x21 x22 x23 a2
a2
ai
i 1
z c11x11 c12 x12 c13x13 c21x21 c22 x22 c23x23
a1
m
7
b2
1
x57 : c57 5
x48 : c48
1
x58 : c58 8
b3
Formulasi untuk masalah diatas ditulis sbb: Minimumkan Gambar-1: Alur Pengiriman, Persediaan dan Kebutuhan Barang dan Biaya Satuan 1
2
Program Studi Statistika FMIPA Universitas Mulawarman
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
ISSN 2085-7829
x13 x23 x36 x37 x38 0
z c13x13 c14 x14 c15 x15 c23x23 c24 x24
x14 x24 x46 x47 x48 0 x15 x25 x56 x57 x58 0
c25x25 c23x23 c24 x24 c25 x25 c36 x36 c37 x37 c38 x38 c46 x46 c47 x47 c48 x48
xij 0
Berdasarkan Pembatas:
x13 x14 x15 a1 x23 x24 x25 a2 x36 x46 x56 b1
Tabel yang digunakan untuk masalah transshipment ádalah tabel masalah transportasi dengan menggabung tabel-2 dan tabel-3 dan memberikan biaya yang cukup besar (M) kepada semua yang tidak mempunyai jalar transportasi, sehingga pada masalah diatas diperoleh tabel transportasi sbb:
x37 x47 x57 b2 x38 x48 x58 b3
Tabel 4: Transpotasi Dua Sumber, Tiga Penghubung dan Tiga Tujuan Penghubung 3 4 5 6 c13 Sumber
1
x13
2
x23
c14 x14
M x34
4
x44
5
x53
x45 M x54 B
B
B
Metodologi Penelitian Proses VAM dapat diringkas sebagai berikut: 1. Hitung penalty untuk setiap baris dan kolom. Penalty untuk setiap baris ke-i dihitung dengan mengurangkan nilai cij terkecil pada baris tersebut dengan nilai cij satu tingkat lebih besar pada baris yang sama. 2. Penalty kolom diperoleh dengan cara yang sama. Biaya-biaya ini adalah penalty karena tidak memilih kotak dengan biaya minimum. 3. Pilih baris atau kolom dengan penalty (jika terdapat nilai kembar maka pilih secara sembarang). Alokasikan sebanyak mungkin kekotak dengan nilai cij minimum pada baris atau kolom yang dipilih. 4. Hilangkan semua baris dan kolom dimana penawaran dan permintaan telah dihabiskan.
Program Studi Statistika FMIPA Universitas Mulawarman
5.
B
c57 x57
b1
c48 x48
c56 x56
B
c47 x47
0 x55
c38 x38
c46 x46
a2
c37 x37
M x45
M Permintaan
x36
0
M x28
c36
x35
M
a1
M x27
M
M x18
M x26
Kapasitas
8
M x17
c25 X25
0 Penghubung
X16
c24 x24
x33
M
x15
c23
3
c15
Tujuan 7
c58 x58
b2
B b3
Jika semua penawaran dan permintaan belum dipenuhi, kembali kelangkah pertama dan hitung kembali penalty yang baru.
Hasil dan Pembahasan Kasus: Sebuah perusahaan penjual motor memiliki 600 motor yang berada di Kota-1 sebanyak 300 buah dan di Kota-2 300 buah. Motor tersebut akan dipakai di 6 kota yaitu Kota-6 sebanyak 200 buah, Kota-7 sebanyak 100 buah dan Kota-8 sebanyak 300 buah. Karena kondisi jalan, pengangkutan tidak dapat langsung dari kota asal ke kota tujuan dan harus melalui kota penghubung yaitu Kota-3, Kota4 dan Kota-5. Alur pengiriman barang dan biaya pengangkutan sebuah alat berat terlihat pada gambar-1 dan tabel berikut
3
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
ISSN 2085-7829
6
x36 : 6 300
x13 : 16
1
x14 : 10 x15 : c15
1
300
3
x56 : 5
x38 : 10
x47 : 11
4
x23 : 15 x24 : 14
2
1
x46 : 7
x37 : 8
200
7
100
1
x57 : 5
x25 : 17
x48 : 11
5 1
x58 : 12 8
300
Gambar-2: Alur Pengiriman, Persediaan dan Kebutuhan Barang dan Biaya Satuan 1
Tabel-5 : Biaya Satuan Pengangkutan dari Kota Asal ke Kota Penghubung 3 4 5 16 1
x13
10
Untuk menyelesaikan masalah transhipmen ini, pada setiap kota penghubung harus disediakan barang (motor) dummy yang besarnya sama dengan jumlah kapasitas produk atau persediaan barang. Tabel transportasi dibuat dengan menggabung tabel-5 dan tabel-6 dan memberikan biaya yang cukup besar (M) kepada semua yang tidak mempunyai jalur transportasi sehingga pada masalah diatas diperoleh tabel berikut :
12
x14
x15
15 14 17 2 x23 x24 x25 Tabel-6 : Biaya Satuan Pengangkutan dari Kota Penghubung ke Kota Tujuan 6 7 8 6 8 10 3 x36 x37 x38 7 11 11 4 x46 x47 x48 4 5 12 5 x56 x57 x58
Tabel 7: Transpotasi Dua Sumber, Tiga Penghubung dan Tiga Tujuan Kota Penghubung Kota Tujuan 3 4 5 6 7 16 Kota Sumber
1
x13
10 x14
15 2
x23
14 x24
0 Kota Penghubung
3
x33
4
x44
M
5
4
x25
x34 0
x53 600
7
x56 200
x28
11
600 11
x48 5
x57 100
300 10
x38
x47 4
300 M
8 x37
x46 0
x55 600
x27
x36
M x18
M
6
M
M x54 600
x26
x45
M x17
M
M x35
x45
M X16
17
M
M Permintaan
12 x15
Kapasitas
8
600 12
x58 300
600
Program Studi Statistika FMIPA Universitas Mulawarman
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
ISSN 2085-7829
Supaya masalah diatas dapat diselesaikan maka dimisalkan nilai M=1000. Sehingga diperoleh tabel baru sbb : Tabel 8 : Transpotasi Alur Pengiriman dan Kebutuhan Barang dan Biaya Satuan Kota Penghubung Kota Tujuan 3 4 5 6 7 8 16 Kota Sumber
1
x13
2
x23
3
x33
10
15
14
4
x44
5
x53
17
1000
x45
1000
1000
x45
x54
x55
Perhitungan penalty-1 Perhitungan penalty kolom : Penalty untuk kolom-1 adalah 15 .Ini diperoleh dengan mengurangkan nilai c23=15 terkecil pada kolom-1 dengan nilai c33=0 satu tingkat lebih besar pada kolom yang sama. Dengan cara yang sama diperoleh penalty untuk kolom-2 adalah 10, penalty untuk kolom-3 adalah 12, penalty untuk kolom-4 adalah 2, penalty untuk kolom-5 adalah 3 dan penalty untuk kolom-6 adalah 1. Perhitungan penalty baris : Penalty untuk baris1 adalah 2 .Ini diperoleh dengan mengurangkan nilai c12=10 terkecil pada baris-1 dengan nilai c13=10 satu tingkat lebih besar pada baris yang sama. Dengan cara yang sama diperoleh penalty untuk baris-2 adalah 1, penalty untuk baris-3 adalah 6, penalty untuk baris-4 adalah 7 dan penalty untuk kolom-5 adalah 4.
Program Studi Statistika FMIPA Universitas Mulawarman
10 x38 11
x47
x48
600
5
12
x57
990 986 2 7 1
600
11
4
1. Penyelesaian Menggunakan VAM Berikut ini adalah tabel hasil perhitungan menggunakan metode VAM: Tabel-9 : Biaya Satuan cij dan penalty baris dan kolom 3 4 5 6 7 8 JML 1 16 10 12 1000 1000 1000 300 2 2 2 15 14 17 1000 1000 1000 300 1 3 3 0 1000 1000 6 8 10 600 6 2 4 1000 0 1000 7 11 11 600 7 7 5 1000 1000 0 4 5 12 600 4 4 JML 600 600 600 200 100 300 15 10 12 2 3 1 10 12 2 3 1 10 2 3 1 14 2 3 1 1000 2 3 1 2 3 1 2 3 2 2 2
300
8
7
x56
1000 x28
x37
x46
300
1000
6
0
1000 x18
x27
x36 1000
1000
1000 x17
x26
x35 0
1000
X16
x25
x34 1000
1000
x15
x24 0
Kota Penghubung
12
x14
986 2 7 1
Kapasitas
x58
2 7 1
2 4 1
600
2
2
1
1
Penentuan penalty terbesar : Pilih baris atau kolom dengan penalty terbesar (jika terdapat nilai kembar, pilih secara sembarang dan diperoleh penalty terbesar adalah kolom-1 adalah 15. Alokasikan sebanyak mungkin kekotak dengan nilai cij minimum pada baris atau kolom yang dipilih diperoleh c33=0. Dalam kasus transhipmen cii selalu bernilai 0 sehingga mengalokasikan sebanyak mungkin nilai di c ii akan berdampak pada solusi akhir sehingga perlu kehati-hatian. Pada kasus ini alokasi dialihkan ke c23=15 sebanyak x23=300. Perhitungan penalty-2 Perhitungan penalty kolom : Penalty untuk kolom-2 adalah 10, penalty untuk kolom-3 adalah 12, penalty untuk kolom-4 adalah 2, penalty untuk kolom-5 adalah 3 dan penalty untuk kolom-6 adalah 1.
5
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
Perhitungan penalty baris : Penalty untuk baris1 adalah 2, penalty untuk baris-2 adalah 3, penalty untuk baris-3 adalah 2, penalty untuk baris-4 adalah 7 dan penalty untuk kolom-5 adalah 4.
ISSN 2085-7829
Tabel-11: Biaya Satuan cii dan Alokasi xii
Penentuan penalty terbesar : Pilih baris atau kolom dengan penalty terbesar (jika terdapat nilai kembar, pilih secara sembarang dan diperoleh penalty terbesar adalah kolom-2 adalah 12. Alokasikan sebanyak mungkin kekotak dengan nilai cij minimum pada baris atau kolom yang dipilih diperoleh c44=0. Dalam kasus transhipmen cii selalu bernilai 0 sehingga mengalokasikan sebanyak mungkin nilai di c ii akan berdampak pada solusi akhir sehingga perlu kehati-hatian. Pada kasus ini alokasi dialihkan ke c15=12 sebanyak x15=300. Perhitungan dilanjukan sampai semua alokasi terpenuhi. Selengkapnya alokasi dapat dilihat pada tabel berikut : Tabel-10: Alokasi Optimal 3 4 1 0 2 300 0 3 300 4 600 5 JML 600 600
xij yang memberikan nilai 5 300
6
7
8
300 300 600
0 200 200
100 100
JML 300 300 600 600 600
Gambar-3: Solver Biaya Satuan cii dan Alokasi xii Tabel-12: Biaya Satuan cii dan Alokasi xii yang optimal
300
Diketahui bahwa : Kota Sumber adalah Kota-1 dan Kota-2 Kota Penghubung adalah kota-3, Kota-4 dan Kota-5 Kota Tujuan adalah Kota-6, Kota-7 dan Kota-8 Dari tabel-8 dapat disimpulkan bahwa : 1. Kota-1 sebagai kota sumber mengirim sebanyak 300 buah motor ke Kota-5 sebagai kota penghubung dan Kota-5 mendistribusikan 200 buah motor ke Kota-6 dan sisanya 100 buah motor didistribusikan ke Kota-7 sebagai kota tujuan. 2. Kota-2 sebagai kota sumber mengirim sebanyak 300 buah motor ke Kota-3 sebagai kota penghubung dan Kota-3 mendistribusikan 300 buah motor ke Kota-8. 3. Total Biaya yang dikeluarkan adalah : Z=300*12+300*15+300*10+200*4+100*5=12400
2. 6
Penyelesaian Menggunakan Solver Ms.Excel
Dari tabel diatas dapat disimpulkan bahwa : 1. Kota-1 sebagai kota sumber mengirim sebanyak 300 buah motor ke Kota-5 sebagai kota penghubung dan Kota-5 mendistribusikan 200 buah motor ke Kota-6 dan sisanya 100 buah motor didistribusikan ke Kota-7 sebagai kota tujuan. 2. Kota-2 sebagai kota sumber mengirim sebanyak 300 buah motor ke Kota-3 sebagai kota penghubung dan Kota-3 mendistribusikan 300 buah motor ke Kota-8. 3. Total Biaya yang dikeluarkan adalah : Z=300*12+300*15+300*10+200*4+100*5=12400 Program Studi Statistika FMIPA Universitas Mulawarman
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
ISSN 2085-7829
Kesimpulan 1. Langkah awal yang digunakan untuk menyelesaikan masalah transshipment adalah menyusun tabel transportasi terlebih dahulu yang terdiri kota sumber, kota penghubung dan kota tujuan dimana kota yang tidak terhubung di berikan nilai cij=M (bilangan yang besar). Selanjutnya tabel transpotasi tersebut diselesaikan menggunakan metode VAM. 2. Pada kasus yang dibahas di penelitian ini, hal yang mendapat perhatian adalah penentuan alokasi pada nilai cii=0. Karena penentuan alokasi pada nilai cii bisa berdampak pada solusi akhir. Daftar Pustaka Zulfikarijah, Fien. 2008. Pemodelan dalam Riset Operasi. Bandung: Institut Teknologi Bandung. Anton, Howard. 1987. Aljabar Linier Elementer. Jakarta: Erlangga. Rao, S.S. 1987. Optimization Theory and Application. San Diego, USA: Dept. of Mechanical Engg. Supranto, J. 1983. Riset Operasi. Edisi Revisi. Jakarta : Bina Rupa Aksara
Program Studi Statistika FMIPA Universitas Mulawarman
7
Jurnal EKSPONENSIAL Volume 3, Nomor 1, Mei 2012
8
ISSN 2085-7829
Program Studi Statistika FMIPA Universitas Mulawarman