Download - 1 Transportation Model Klp12
Transportation Model
Riset Operasional D
Jurusan Teknik Informatika – ITS 2014
Contoh Transportation Problem
TUJUANASAL
Transportation Model
Ada m sumber dan n tujuan, ai jumlah unit yang tersedia pada tiap sumber dan akan dikirim tujuan. bj merupakan permintaan dari tiap tujuan. cij merupakan biaya transportasi per unit yang dikirim. Model Matematik untuk transportasi sbb :
m
i
n
jijijxcx
1 10
0
,....,2,1;
,....,2,1;
1
1
ij
m
iij
n
jiij
x
njbjx
miax
Obyektif
Pembatas
Kesetimbangan Model Transportasi
• Pernyataan ini berarti bahwa jumlah yang disuplai dari sumber harus sama dengan jumlah permintaan pada tujuan.
• Pada kenyataannya bahwa jumlah yang disuplai tidak sama dengan permintaannya, dapat lebih besar atau lebih kecil. Kondisi disebut tidak setimbang.
• Kondisi tidak setimbang harus dibuat setimbang dengan menambahkan sumber atau tujuan yang bersifat dummy
• Jika suplai demand, tambahkan tujuan dummy untuk menerima sejumlah ai - bj. Jika demand suplai, tambahkan sumber dummy untuk mensuplai sejumlah bj - ai.
m
ii
m
i
n
jij
n
j
m
iij
n
jj axxb
11 11 11
Teknik Transportasi(Lanjutan)
Biaya dari i ke j
Cara Penyelesaian :
Dengan Tabulasi
SUMBER
T U J U A N
1
2
3
1 2 3 4
b1
b2
b3
Jumlah dari i ke j
a1 a2 a3 a4
Kapasitas
Teknik Transportasi(Metoda Penyelesaian)
• Mendapatkan Solusi Awal• Northwest Corner (NWCR)• Least Cost• Vogel Approximation (VAM)
• Mendapatkan Solusi Optimal (Akhir)• Multiplier (UV Method)
Mendapatkan Solusi Awal
• Ada Tiga Cara yang dapat digunakan yang tujuannya adalah untuk memperoleh variabel basis (dalam metoda simplex membentuk matrix satuan).
• Variabel-variabel basis ini merupakan solusi awal untuk mendapat solusi akhir yang kondisinya feasibel dan optimal.
• Pada penyelesaian awal ini bisa saja kondisi sudah feasibel dan optimal, tapi untuk menyatakan hal tersebut harus diuji terlebih dulu.
Mendapatkan Solusi AwalMenggunakan Northwest Corner
• Metoda Northwest Corner (NWCR) merupakan metoda yang pengisian sel pada tabel penyelesaian masalah transportasi dimulai dari pojok kiri atas.
• Kemudian dilanjutkan pada sel sebelah kanan atau bawah bergantung pada kapasitas yang tersedia.
• Pengisian sel berakhir pada sel pojok kanan bawah.• Sel-sel yang terisi merupakan variabel basis yang
jumlahnya adalah : m + n –1 (m = jumlah lokasi sumber, n = jumlah lokasi tujuan).
Contoh: Pengisian Dengan NWCR
Sebuah perusahaan mempunyai tiga lokasi pabrik yaitu : A, B, C. untuk membuat produknya. Produk yang dibuat ini akan didistribusikan ke empat lokasi pasar, yaitu : P1, P2, P3, P4. Kapasitas dari masing-masing pabriknya dan permintaan dari masing-masing pasar terlihat pada tabel.1 dan biaya angkut per-unit produk ada pada tabel.2
Pabrik Kapasitas Pasar Permintaan
A 100 P1 50B 150 P2 125C 75 P3 100
P4 50
Ke
Dari
P a s a rP1 P2 P3 P4
Pabrik
A 10 15 5 20
B 15 5 10 5
C 25 10 5 15
Untuk penyelesaiannya dibuat tabel transportasi sbb :
Contoh: Pengisian Dengan NWCR
1015
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
50 5050
75
75 7575
25
25 5050
Total Biaya Distribusi = 50 * 10 + 50 * 15 + 75 * 5 + 75 * 10 + 25 * 5 + 50 * 15= 3250
Contoh: Pengisian Dengan Least-Cost
1015
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
125
25
100
25
25
25 5050
Total Biaya Distribusi = 100 * 5 + 125 * 5 + 25 * 5 + 50 * 25 + 25 * 15= 2875
Contoh: Pengisian Dengan VAM
1015
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
Penalti :
Penalti :
5 05 10
5
0
10100
10 5 10
50
5
0
10 5
10
1575
50 50
Contoh: Pengisian Dengan VAM
1015
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
100
50
75
50 50
Total Biaya Distribusi = 100 * 5 + 50 * 15 + 50 * 5 + 50 * 5 + 75 * 10= 2500
Mendapatkan Solusi Akhir1. Berawal dari hasil untuk medapatkan solusi awal yang
diperoleh menggunakan NWCR, LC, dan VAM dapat ditetapkan variabel-variabel yang termasuk basis.
2. Jumlah variabel basis yang dapat digunakan untuk melanjutkan ketahapan mencari solusi akhir adalah m + n – 1
3. Bila jumlah variabel basisnya kurang dari m + n –1, harus ditambahkan variabel basis dengan meletakan nilai 0 pada variabel non basis dengan nilai biaya paling kecil.
4. Setelah jumlah variabel basis sesuai dengan syarat, maka dapat dilanjutkan dengan menggunakan salah satu metoda (Stepping Stone atau Multiplier).
100
Contoh hasil solusi awal yang jumlah Variabel basisnya kurang dari m + n - 1
1015
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
50
75
50 50
Pada tabel diatas ada 5 variabel basis, sehingga kurang satu dari m + n – 1, oleh karena itu perlu ditambahkan 1 variabel dengan meletakan nilai 0 di kotak yang mempunyai ‘cost’ paling kecil
0
Solusi Akhir Dengan Metoda Multiplier (UV)
1. Metoda Multiplier atau UV merupakan salah satu metoda untuk mendapatkan solusi akhir yang feasible dan optimal dari permasalahan transportasi.
2. Metoda ini dapat digunakan bila variabel basis sudah ditetapkan (menggunakan metoda NWCR, Least Cost atau VAM).
3. Apabila variabel basis telah ditetapkan, kemudian ditentukan nilai Ui untuk baris dan Vj untuk kolom.
i = 1 … m dan j = 1… n
4. Tetapkan terlebih dulu salah satu nilai Ui atau Vj sebesar 0
Solusi Akhir Dengan Metoda Multiplier (UV)5. Nilai Ui dan Vj lainnya ditetapkan berdasarkan rumus berikut :
Ui + Vj = Cij
Cij = merupakan nilai ‘cost’
dari kotak variabel basis
6. Setelah semua nilai Ui dan Vj diperoleh, kemudian menetapkan nilai untuk variabel non basis berdasarkan rumus :Cij – Ui – Vj
Cij = merupakan nilai ‘cost’ pada
dari kotak variabel non basis
7. Bila nilai pada kotak variabel non basis ada yang negatif berarti kondisi belum optimal, kemudian pilih nilai variabel non basis yang paling negatif.
Solusi Akhir Dengan Metoda Multiplier (UV)
8. Berawal dari kotak variabel non basis, buat suatu loop tertutup. Loop dapat searah jarum jam atau berlawanan.
9. Tetapkan tanda + atau – bergantian sesuai dengan kotak yang dilalui loop. Berawal pada kotak variabel non basis dengan tanda +.
10. Kotak yang bertanda + berarti sejumlah unit ditambahkan pada kotak tersebut. Besarnya unit yang ditambahkan adalah sama dengan nilai terkecil pada kotak yang mempunyai tanda negatif.
11. Kotak variabel basis yang tidak dilalui loop, nilainya tetap.
12. Ulangi langkah 4 sampai 11, bila masih terdapat nilai variabel non basis yang masih negatif
Solusi Akhir Dengan Metoda Multipler (UV)
V1= V2= V3= V4=
U1=
U2=
U3=
0
10 15
-10
20
-15
15
10
15
15 5 20
5 10 5
25 10 5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
50 50
75 75
25 50
-15 5
0 10
25 10
Loop : (A,P3) (B,P3) (B,P2) (A,P2) (A,P3)
+ - + -
Iterasi I
10
15
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
V1= V2= V3= V4=
U1=
U3=
U2=
50
25125
25 50
500
10 5
5
Iterasi II0
0
15
15 5
-5 -15
10 10
Total Biaya
2500
Loop : (B,P4) (C,P4) (C,P3) (B,P3) (B,P4) + - + -
0
Kondisi Feasibel, belum Optimal
Iterasi III
10
15
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
V1= V2= V3= V4=
U1=
U3=
U2=
50
25125
2550
500
10 5
-10
15
0
15
Total Biaya
22500 5
15 15
15 -5
Loop : (C,P2) (B,P2) (B,P4) (C,P4) (C,P2) + - + -
Kondisi Feasibel, belum Optimal
Iterasi IV
10
15
15
5 20
5 10
5
25
10
5 15
A
B
C
P1 P2 P3 P4
75
150
100
50 125
100
50 325
V1= V2= V3= V4=
U1=
U3=
U2=
50
50100
50
500
10 5
-5
10
0
15
Total Biaya
2000
25
5 5
10 10
15 0
Kondisi Feasibel dan Optimal