Riset Operasi
Edit Rusnita, S.T., [Link]
Metode
Transportasi
North West Corner dan Vogel’s Method Approximation
Model Transportasi
Suatu metode yang digunakan untuk mengatur
distribusi dari sumber-sumber yang menyediakan
produk yang sama, ke tempat-tempat yang
membutuhkan secara optimal
Pendahuluan
Model Transportasi merupakan salah satu persoalan linear
programming yang mempunyai karakteristik khusus.
Kekhususannya adalah bahwa pada umumnya persoalan
membutuhkan sejumlah pembatas dan variable yang sangat
banyak, sehingga penyelesaian dengan metode simplek akan
relatif rumit. Karakteristik khusus lain adalah bahwa pada
umumnya koefisien aij dalam pembatas-pembatasnya
berharga nol, dan sedikit koefisien yang berharga bukan nol
muncul dalam suatu pola tertentu.
Pendahuluan
Pada umumnya model transportasi berkaitan dengan masalah
pendistribusian suatu produk dari sejumlah sumber (misal pabrik)
kesejumlah tujuan (misal daerah pemasaran). Model ini juga dapat
digunakan untuk memecahkan masalah-masalah yang berkaitan
dengan analisis lokasi, perencanaan dan penjadwalkan produksi,
penjadwalan tenaga kerja dan sebagainya.
Asumsi dasar model transportasi adalah bahwa biaya transportasi
disuatu rute tertentu adalah proporsional dengan banyaknya unit yang
dikirim. Definisi unit yang dikirim tergantung pada jenis produk yang
diangkut, yang penting satuan permintaan suatu produk harus
konsisten.
Formulasi dan Bentuk Umum
Model transportasi pada dasarnya merupakan sebuah model linear
programming, tetapi mengingat strukturnya yang khusus
memungkinkan pengembangan suatu prosedur pemecahan yang lebih
efisien. Gb. berikut memperlihatkan sebuah model transportasi suatu
jaringan dengan m sumber dan n tujuan yang diwakili oleh node
(simpul). Rute pengiriman produk dari suatu sumber ke suatu tujuan
diwakili oleh suatu busur. Jumlah penawaran pada suatu sumber i
adalah ai dan jumlah permintaan pada tujuan j adalah bj. Biaya per
unit dari sumber i ke tujuan j adalah cij. Model ini dapat digambarkan
sebagai berikut
sumber tujuan
a1 1 c11,x11
1 b1
b2
a2 2 2
n bn
cmn,xmn
am m
unit penawaran unit permintaan
Formulasi dan Bentuk Umum
Model linier Programming yang menggambarkan masalah transportasi
secara umum dapat diformulasikan sebagai berikut :
Minimumkan Z
Dengan kendala:
Formulasi dan Bentuk Umum
Kelompok pembatas pertama mengharuskan jumlah pengiriman dari
sebuah sumber tidak dapat melebihi penawarannya, sedangkan
kelompok pembatas kedua mengharuskan jumlah pengiriman ke
sebuah tujuan harus dapat memenuhi permintaannya.
Formulasi dan Bentuk Umum
Dalam kehidupan nyata seringkali jumlah penawaran tidak sama
dengan jumlah permintaan. Tetapi sebuah model transportasi dapat
selalu berimbang. Pengimbangan ini selain berguna dalam pemodelan
situasi praktis tertentu adalah penting untuk pengembangan sebuah
metode penyelesaian yang sepenuhnya memanfaatkan struktur khusus
dari model transportasi. Berdasarkan model di atas dapat dibuat tabel
linear programming berikut :
Formulasi dan Bentuk Umum
Berdasarkan tabel diatas terlihat bahwa semua koefisien teknologi
berharga nol atau satu. Hal ini merupakan karakter khusus model
transportasi. Karena sifatnya yang khusus tersebut, maka dapat
dikembangkan suatu prosedur yang lebih efisien yang disebut dengan
teknik transportasi. Bentuk umum tabel transportasi adalah sebagai
berikut :
Metode Penyelesaian
Dari masalah yang telah disajikan dalam bentuk tabel, dapat diselesaikan dengan
beberapa metode. Ada 8 metode solusi awal dan 2 metode solusi optimum. Metode
solusi awal meliputi :
• Row Minimum Method
• Modified Row Minimum Method
• Coloumn Minimum Method
• Modified Coloumn Minimum Method
• Matrix Minimum Method
• North West Corner Method
• Russel Approximation Method
• Vogel Approximation Method
Metode solusi optimum meliputi :
• Stepping Stone Method
• Modified Distribution Method.
Flow Chart Algoritma Transportasi
Contoh
Suatu perusahaan yang mempunyai 3 buah
pabrik di W, H, P. Perusahaan
menghadapi masalah alokasi hasil
produksinya dari pabrik-pabrik tersebut
ke gudang-gudang penjualan di A, B, C
Data Kapasitan dan Kebutuhan/Bulan
Kapasitas produksi tiap
Pabrik Kebutuhan tiap bulan
bulan
W 90 ton 50 ton
H 60 ton 110 ton
P 50 ton 40 ton
Jumlah 200 ton 200 ton
Data Biaya Pengangkutan
Biaya tiap ton (dalam ribuan Rp)
Dari
Ke gudang A Ke gudang B Ke gudang C
Pabrik W 20 5 8
Pabrik
15 20 10
H
Pabrik
25 10 19
P
Penyusunan Tabel Alokasi
● Aturan
1. jumlah kebutuhan tiap-tiap gudang diletakkan pada baris
terakhir
2. kapasitas tiap pabrik pada kolom terakhir
3. biaya pengangkutan diletakkan pada segi empat kecil
Contoh
Ke Kapasitas
Gudang A Gudang B Gudang C Pabrik
Dari
Pabrik 20 5 8
X11 X12 X13 90
W
Pabrik 15 20 10
X21 X22 X23 60
H
Pabrik 25 10 19
X31 X32 X33 50
P
Kebutuhan
50 110 40 200
Gudang
Penggunaan Linear Programming dalam Metode Transportasi
Minimumkan Z = 20XWA + 15XHA + 25XPA + 5XWB + 20XHB + 10XPB +
8XWC + 10XHC + 19XPC
Batasan
XWA + XWB + XWC = 90 XWA + XHA + XPA = 50
XHA + XHB + XHC = 60 XWB + XHB + XPB = 110
XPA + XPB + XPC = 50 XWC + XHC + XPC = 40
Prosedur Alokasi
Pedoman Sudut Barat Laut (Northwest Corner Rute)
1. Mulai dari sudut kiri atas dari X11 dialokasikan sejumlah maksimum produk
dengan melihat kapasitas pabrik dan kebutuhan gudang
2. Kemudian setelah itu, bila Xij merupakan kotak terakhir yang dipilih
dilanjutkan dengan mengalokasikan pada Xi,j+1 bila i mempunyai kapasitas
yang tersisa
3. Bila tidak, alokasikan ke Xi+1,j, dan seterusnya sehingga semua kebutuhan
telah terpenuhi
Tabel Alokasi Tahap Pertama
Ke Gudang A Gudang B Gudang C
Kapasitas
Dari Pabrik
Pabrik 20 5 8
50 40 90
W
Pabrik 15 20 10
60 60
H
Pabrik 25 10 19
10 40 50
P
Kebutuhan 110 40 200
Gudang 50
Prosedur Alokasi
Metode Vogel’s Approximation
1. Susunlah kebutuhan, kapasitas masing-masing sumber, dan biaya
pengangkutan ke dalam matrik
2. Carilah perbedaan dari dua biaya terkecil (dalam nilai absolut), yaitu biaya
terkecil dan terkecil kedua untuk tiap baris dan kolom pada matrik (Cij)
3. Pilihlah 1 nilai perbedaan-perbedaan yang terbesar di antara semua nilai
perbedaan pada kolom dan baris
4. Isilah pada salah satu segi empat yang termasuk dalam kolom atau baris
terpilih, yaitu pada segi empat yang biayanya terendah di antara segi empat
lain pada kolom/baris itu. Isiannya sebanyak mungkin yang bisa dilakukan
Feasible Solution Mula-Mula dari Metode VAM
Gudang Perbedaan
Kapasitas
A B C baris
W 20 5 8 90 3
Pabrik H 15 20 10 60 5
P 25 10 19 50 9
Kebutuhan 50 110 40 Pilihan XPB = 50
Perbedaan Kolom 5 5 2 Hilangkan baris P
P mempunyai perbedaan baris/kolom terbesar
dan B mempunyai biaya angkut terkecil
Gudang Perbedaan
Kapasitas
A B C baris
W 20 5 8 90 3
Pabrik H 15 20 10 60 5
Kebutuhan 50 60 40 Pilihan XWB = 60
Perbedaan Kolom 5 15 2 Hilangkan kolom B
Kebutuhan Gd B menjadi
B mempunyai 60 krn
perbedaan telah diisi
baris/kolom
kapasitas
terbesar pabrik
dan WP=50 (dihilangkan)
mempunyai biaya
angkut terkecil
Gudang Perbedaan
Kapasitas
A B C baris
W 20 8 30 12
Pabrik H 15 10 60 5
Kebutuhan 50 40 Pilihan XWC = 30
Perbedaan Kolom 5 2 Hilangkan baris W
Kapasitas Pabrik W
W mempunyai menjadi 30
perbedaan krn telah
baris/kolom
diangkut ke pabrik
terbesar dan B=60 (dihilangkan)
C mempunyai biaya angkut
terkecil
Gudang Perbedaan
Kapasitas
A B C baris
W
Pabrik H 15 10 60 5
Kebutuhan 50 10 Pilihan XHA = 50
Perbedaan Kolom Pilihan XHC = 10
Kebutuhan gudang C menjadi 10 krn
telah diisi pabrik W=30 (dihilangkan)
H mempunyai perbedaan baris/kolom
terbesar dan C mempunyai biaya angkut
terkecil
Ke Gudang Gudang Gudang Kapasitas
Dari A B C Pabrik
Pabrik 20 5 8
60 30 90
W
Pabrik 15 20 10
50 10 60
H
Pabrik 25 10 19
50 50
P
Kebutuhan
Gudang
50 110 40 200
Setelah terisi semua, maka biaya transportasinya yang harus dibayar adalah
60(Rp 5,-) + 30(Rp 8,-) + 50(Rp 15,-) + 50(Rp 15,-) + 10(Rp 10,-) + 50(Rp 10,-) = Rp
1.890,-
Latihan Soal
PT. Siman memiliki 3 lokasi berbeda (I, II, III) dengan kapasitas106, 132 dan127.
PPT Siman memiliki tiga distribution channels (A, B , C) dengan permintaan
sebesar 122,152 and 91 untuk masing-masing.
Selesaikan dengan metode NWC dan VAM
Biaya produksi di tiga perusahaan sama, delivery cost nya adalah:
Plant A B C
1 2 3 4
2 6 12 8
3 4 7 10