PERTEMUAN X
PROGRAM LINEAR
Persoalan Transportasi
Membahas masalah pendistribusian suatu
komoditas atau produk dari sejumlah sumber
(origin) kepada sejumlah tujuan (destination,
demand), dengan tujuan meminimumkan
biaya yang akan terjadi.
Alokasi produk ini harus diatur sedemikian
rupa karena terdapat perbedaan biaya-biaya
alokasi dari satu sumber atau beberapa
sumber ke tempat tujuan yang berbeda.
Tujuan dari model transportasi adalah
menentukan jumlah yang harus dikirimkan
dari setiap sumber ke setiap tujuan
sedemikian rupa sehingga biaya
Ciri-ciri khusus persoalan
transportasi
Terdapat sejumlah sumber dan sejumlah
tujuan tertentu.
Kuantitas komoditas atau barang yang
didistribusikan dari setiap sumber dan
yang diminta oleh setiap tujuan, besarnya
tertentu.
Komoditas yang dikirim atau diangkut dari
suatu sumber ke suatu tujuan, besarnya
sesuai dengan permintaan dan atau
kapasitas sumber.
Biaya yang dibutuhkan untuk
memindahkan suatu komoditas dari suatu
sumber ke suatu tujuan, besarnya tertentu.
Contoh model transportasi:
Formulasi model transportasi:
Fungsi tujuan : Min Z
=
Fungsi pembatas
:
Xij > 0 untuk seluruh i
dan j
Xij = banyak unit barang yang diangkut dari
asal i ke tujuan j.
Cij =Biaya pengangkutan satu unit barang dari
Contoh Tabel masalah Transportasi:
Keseimbangan Model Transportasi:
Suatu model transportasi dikatakan
seimbang bila jumlah total supply
(sumber) sama dengan jumlah total
demand (tujuan), dituliskan :
Hal ini diperlukan karena dalam persoalan
transportasi akan diperoleh solusi feasible
(solusi layak), jika terpenuhi jumlah total
supply (sumber) sama dengan jumlah
total demand (tujuan).
Langkah-langkah Pemecahan Masalah Transportasi
a) Menentukan pemecahan awal yang layak.
Metode North West Corner (NWC),
Metode pendekatan Vogel (Vogel Approximation
Methods atau VAM),
Metode Inspeksi.
b) Menentukan biaya “kesempatan” (opprtunity)
yang diberikan dengan sel kosong. Jika biaya
“kesempatan” dari semua sel “tidak negatif”, maka
solusi optimal telah diperoleh.
c) Tentukan variabel keluar diantara variabel-
variabel basis yang ada, kemudian hitung solusi
yang baru. Kembali ke langkah b) dan c) sampai
Metode North West Corner (NWC)
Mulai dari pojok kiri atas kemudian bergerak
kekanan atau kebawah sesuai dengan
permintaan dan kapasitas produksi yang
sesuai.
Besar alokasi ini akan mencukupi salah satu
baik kolom maupun baris sehingga jika
terpenuhi salh satunya maka alokasi
berikutnya bergerak ke bawah atau ke kanan
berdasarkan permintaan atau kapasitas
yang belum terpenuhi.
langkah berikutnya sesuai dengan langkah
Contoh:
Sebuah perusahaan Negara berkepentingan
mengangkut produk barang dari empat pabrik ke lima
pasar pasar. Kapasitas supply keempat pabrik,
permintaan pada ke lima pasar dan biaya transport
per unit adalah sebagai berikut :
DESTINATION
Kapasit
ORIGIN as
pabrik
12 4 9 5 9
100
8 1 6 6 7
90
1 12 4 7 7
70
10 15 6 9 1
90
Demand
Contoh Masalah Transportasi Menggunakan NWC
DESTINATION
Kapasit
ORIGIN as
2pabrik
8 2 0
0 12 0 4 9 5 9 6 0
100
3 6 0
0
8 0 1 0 6 6 7
4 90
3 4 0
1 12 4 7 7 0
0 0 7 70
2 0
10 15 6 9 7 1 0
0 0 90
Demand
(perminta 350
an)
Total biaya pengiriman Menggunakan NWC
Metode Inspeksi
Alokasi pertama dibuat terhadap sel yang
berkaitan dengan biaya pengangkutan
termurah dengan melihat persyaratan
kapasitas produk dan permintaan tempat
tujuan.
memilih nilai minimum antara kapasitas
produksi dan permintaan tempat tujuan.
kemudian beralih ke sel termurah berikutnya
sesuai dengan langkah pertama dan kedua.
Contoh
MulaiMasalah Transportasi Menggunakan Metode
dengan alokasi sel termurah:
Inspeksi
Sel termurah terletak pada sel , , dan
Alokasikan nilai minimum antara kapasitas dan
permintaan
Baris atau kolom berwarna merah merupakan nilai
minimum
DESTINATION
Kapasita
ORIGIN
s pabrik
12 4 9 5 9
100
8 5 1 6 6 7
90 4
0 0
7 1 12 4 7 7
70
0 0
10 15 6 9 7 1
90 2
0
Demand 1 0
0
(permintaa 0 350
n) 0
Sel termurah berikutnya terletak pada sel yaitu 5
Alokasikan nilai minimum antara kapasitas dan
permintaan
Baris atau kolom berwarna merah merupakan nilai
minimum
DESTINATION
Kapasita
ORIGIN
s pabrik
12 4 9 5 9
6 100 4
0 0
8 1 6 6 7
40
50
1 12 4 7 7
0
70
10 15 6 9 70 1
20
Demand
(permintaa 350
n) 0
Sel termurah berikutnya terletak pada sel dan yaitu 6
Alokasikan nilai minimum antara kapasitas dan
permintaan
Baris atau kolom berwarna merah merupakan nilai
minimum
DESTINATION
Kapasita
ORIGIN
s pabrik
12 4 9 5 9
40
60
8 1 6 6 7
4 40
50 0
0
1 12 4 7 7
0
70
10 15 6 9 70 1
2 20
0
Demand 0
5
(permintaa 0 3 350
n) 0
Masih terdapat pemintaan barang yang belum
terpenuhi yaitu dan sedangkan barang pada masih
ada yang belum teralokasikan.
Kekurangan permintaan dan akan dipenuhi oleh
DESTINATION
Kapasita
ORIGIN
s pabrik
12 4 9 5 9 3
1 3 0 40 0
0 60
0
8 1 6 6 7
0
50 40
1 12 4 7 7
0
70
10 15 6 9 1
0
20 70
Demand
(permintaa 3 350
n) 0 0
Permintaan barang telah terpenuhi semuanya.
Sehingga diperoleh tabel transportasi dengan metode
Inspeksi
DESTINATION
Kapasita
ORIGIN
s pabrik
12 4 9 5 9
0
10 30 60
8 1 6 6 7
0
50 40
1 12 4 7 7
0
70
10 15 6 9 1
0
20 70
Demand
(permintaa 350
n)
Besar biaya transportasi dengan metode inspeksi
10(12)30(9)60(5)50(1)40(6)70(1)20(6)
Metode VAM (Vogel Aproximation
Method)
[Link] VAM didasarkan atas beda kolom dan beda
baris untuk membedakan antara dua ongkos termurah
dalam satu kolom atau baris.
2. Setiap perbedaan dianggap sebagai “penalti”
karena menggunakan route termurah.
3. Pilih beda kolom atau beda baris (pinalti) tertinggi,
jika nilai pada baris atau kolom sama maka pilih yang
dapat memindahkan barang paling banyak
4. Hapus baris atau kolom yang sudah terpenuhi
alokasi barang, kemudian lanjutkan dengan langkah
yang sama.
Contoh Masalah Transportasi Menggunakan VAM
DESTINATION
Kapasit
ORIGIN as
pabrik
12 4 9 5 9
100
8 1 6 6 7
90
1 12 4 7 7
70
10 15 6 9 1
90
Demand
(perminta 350
an)
DESTINATION
Bed
Kap
a
asita
Bari
s
s
pabr
(Pin
ik
alti)
12 4 9 5 9
100 1
7 8 1 6 6 7
0 900 5
1 12 4 7 7
70 3
1
0
10 15 6 9 1
90 5
(perm
intaa 350
n)
Beda
DESTINATION
Kapas Beda
itas Baris
pabri (Pina
k lti)
12 4 9 5 9
100 1
8 1 6 6 7
90 5
10 15 6 9 7 1
90 2 5
0 0
(permi
0 280
ntaan)
Beda
kolom
2 3 0 1 6
(Pinalti
)
DESTINATION
Bed
Kap
a
asita
Bari
s
s
pabr
(Pin
ik
alti)
12 5 4 9 5 4
0 1000 1
8 1 6 6
90 5
10 15 6 9
0 20 3
(perm
intaa 210
n)
Beda
kolom
2 3 0 1
(Pinal
DESTINATION
Bed
Kap
a
asita
Bari
s
s
pabr
(Pin
6 ik 4
0 0 alti)
12 9 5
100 4
8 6 6
40 0
10 6 9
0 20 3
(perm
intaa 160
n)
Beda
kolom
2 0 1
(Pinal
DESTINATION
Bed
Kap
a
asita
Bari
s
s
pabr
(Pin
ik
alti)
12 9
40 3
8 2 6
0 400 2
10 6
7 20 4
0
(perm
intaa 100
n)
Beda
kolom
2 0
(Pinal
DESTINATION
Bed
Kap
a
asita
Bari
s
s
pabr
(Pin
ik
alti)
1 12 9 3
0 40 0 3
8 6
0
40 2
(perm
intaa 100
n)
Beda
kolom
4 3
(Pinal
ti)
DESTINATION
Kapasita
s pabrik
9
4 40
0
6
3 30
0
(permintaan) 70
DESTINATION
Kapasit
ORIGIN as
pabrik
12 4 9 5 9
60 100
40
8 1 6 6 7
90
10 50 30
1 12 4 7 7
70
70
10 15 6 9 1
70 90
20
Demand
Jumlah Sel yang terisi
(perminta 350
Biaya
an) total pengiriman
metode VAM=
10(8)+70(1)+50(1)+40(9)+30(6)+20(6)+60(5)+70(1)
=1230