MODEL TRANSPORTASI - I

MATAKULIAH RISET OPERASIONAL

Pertemuan Ke-7

Riani Lubis
Program Studi Teknik Informatika
Universitas Komputer Indonesia

1
 PENGANTA
R
⚫ Terdapat bermacam-macam network model.
⚫ Network :
⚫ Suatu sistem saluran-saluran yang menghubungkan titik-
titik yang berlainan.
⚫ Susunan titik (node) dan garis yang menghubungkan node-
node.
⚫ Contoh network : jaringan rel kereta api, sistem saluran pipa,
jaringan jalan raya, jaringan penerbangan dll.
⚫ Banyak masalah jaringan dapat dirumuskan sebagai masalah
PL & solusinya diperoleh dengan menggunakan metode
simpleks.
⚫ Salah satu teknik lain yang lebih efisien daripada metode
simpleks adalah metode transportasi, karena masalah
transportasi adalah salah satu contoh dari model jaringan
yang memiliki ciri-ciri yang sama.
2
 Persoalan Transpotasi (1)

⚫ Persoalan transportasi terpusat pada pemilihan rute dalam

jaringan distribusi produk antara pusat industri dan distribusi
gudang atau antara distribusi gudang regional dan distribusi
pengeluaran lokal.

⚫ Pada umumnya, masalah transportasi berhubungan dengan

distribusi suatu produk tunggal dari beberapa sumber,
dengan penawaran terbatas, menuju beberapa tujuan, dengan
permintaan tertentu, pada biaya transpor minimum. Karena
ada satu macam barang, suatu tempat tujuan dapat
memenuhi permintaannya dari satu atau lebih sumber.

3
 Persoalan Transpotasi (2)
⚫ Persoalan transportasi merupakan persoalan linier khusus
yang disebut persoalan aliran network.

⚫ Asumsi dasar model transportasi adalah bahwa biaya

transpor pada suatu rute tertentu proporsional dengan
banyaknya unit yang dikirimkan.

⚫ Tujuan dari model transportasi adalah merencanakan

pengiriman dari sumber-sumber ke tujuan sedemikian rupa
untuk meminimumkan total biaya transportasi, dengan
kendala-kendala :
⚫ Setiap permintaan tujuan terpenuhi
⚫ Sumber tidak mungkin mengirim komoditas
lebih besar dari kapasitasnya.
4
 Contoh

5
 Misal sebuah perusahaan pengalengan mempunyai 3
pabrik pengalengan (sumber) yang harus melakukan distribusi
ke 4 gudang (tujuan). Setiap pabrik memiliki kapasitas produksi
tertentu dan setiap gudang memiliki jumlah permintaan tertentu
terhadap produk tersebut. Biaya transpor per unit dari masing-
masing pabrik ke
masing-masing gudang berbeda-beda. Masalah yang
timbul adalah menentukan jumlah barang yang harus
dikirim dari masing-masing pabrik ke masing-masing
gudang dengan tujuan meminimumkan biaya transpor.

6
 ⚫ Suatumodel transportasi dikatakan seimbang (balanced
progam), jika total jumlah antara penawaran (supply) dan
permintaan (demand) sama :

⚫ Dan dikatakan tidak seimbang (unbalanced program), jika

kapasitas sumber lebih besar dari kapasitas tujuan atau
sebaliknya :

7
 Perumusan Model Transportasi
Fungsi Tujuan
Minimumkan :

Fungsi Balanced program Unbalanced program

Pembatas

Xij ≥ 0 untuk semua i dan j

i = 1, 2, ....., m
j = 1, 2, ....., n
8
 Jika ada 2 buah sumber & 3 tujuan (m = 2, n = 3), maka :

SUMBER TUJUAN

D1

S1

D2

S2

D3

9
F. Tujuan :
Minimumkan

Z = C11X11 + C12X12 + C13X13 + C21X21 + C22X22 + C23X23

F. Pembatas :

X11 + X12 + X13 = S1 Persamaan

pembatas
X21 + X22 + X23 = S 2 “Sumber”
= D1 Persamaan
X11 + X21
= D2 pembatas
“Tujuan”
X12 + X22 =D
X13 + X23
3 ≥ 0
Xij

10
 Sm

11
 Contoh :
Sebuah perusahaan Negara berkepentingan mengangkut pupuk
dari tiga pabrik ke tiga pasar. Kapasitas supply ketiga pabrik,
permintaan pada ketiga pasar dan biaya transpor per unit adalah
sebagai berikut :

PASAR
PENAWARAN
1 2 3

1 8 5 6 120
PABRIK 2 15 10 12 80
3 3 9 10 80
PERMINTAAN 150 70 60 280

12
13
14
 Langkah Pemecahan Masalah
Transportasi :
1. Menentukan solusi fisibel awal dengan menggunakan ketiga
metoda berikut :
a. North West Corner Rule (NWCR) / Pokia-Pokaba
b. Least Cost Value (LCV) / Ongkos Terkecil
c. Vogel Approximation Method (VAM)

2. Pilih salah satu hasil solusi fisibel awal yang mempunyai nilai
solusi fisibel terkecil.

3. Menentukan apakah metoda yang terpilih pada langkah 1 sudah

optimum atau belum, dengan cara menentukan entering
variabel. Jika ada perubahan, maka lanjutkan ke langkah 4. Tapi
jika tidak ada, maka STOP (berhenti).
15
 4. Menentukan leaving dari langkah 3 dan
menghitung variabel kembali fisibel yang baru,
kemudian kembali
nilaike langkah
solusi 3.

Untuk langkah 3 dan langkah 4, dapat menggunakan salah satu

metode di bawah ini :
a. Stepping Stone Method
b. Multiplier Method

16
 Metode North West Corner Rule

⚫ Menentukan distribusi dari pojok kiri atas ke pojok kanan

bawah tanpa memperhatikan besarnya biaya.

⚫ Prosedurnya :
1. Mulai pada pojok kiri atas tabel dan
alokasikan sebanyak mungkin pada X11 tanpa
kendala penawaran
menyimpang dari atau permintaan (artinya
X11
ditetapkan sama dengan yang terkecil diantara
nilai S1 dan D1 atau min(Si,Dj)

17
 2. Ini akan menghabiskan penawaran pada sumber 1 dan
atau permintaan pada tujuan 1. Akibatnya, tidak ada lagi
barang yang dapat dialokasikan ke kolom atau baris yang
telah dihabiskan dan kemudian baris atau kolom itu
dihilangkan. Kemudian alokasikan sebanyak mungkin ke
kotak di dekatnya pada baris atau pindahlah secara
diagonal ke kotak berikutnya.

3. Lanjutkan dengan cara yang sama sampai semua

penawaran telah dihabiskan dan keperluan permintaan
telah dipenuhi.

18
 120

30 50

20 60

19
 Caranya :
⚫ Sebanyak mungkin dialokasikan ke X11 sesuai
aturan
dengan bahwa X adalah yang minimum diantara
[120,150], berarti X1111 = 120. Ini menghabiskan penawaran
pabrik 1 dan akibatnya, pada langkah selanjutnya baris 1
dihilangkan.
⚫ Karena X11 = 120, maka permintaan pada tujuan 1 belum
terpenuhi sebanyak 30. Kotak di dekatnya,
X21
dialikasikan sebanyak mngkin sesuai dengan X21 = min
[30,80] = 30. Ini menghilangkan kolom 1 pada
langkah selanjutnya.
⚫ Kemudian X22 = min [50,70] = 50, yang
menghilangkan baris 2.
⚫ X32 = min [20,80] = 20
⚫ X33 = min [60,60] = 60

20
 Solusi fisibel awal dengan 5 variabel basis & 4 variabel
non-basis sbb :
Variabel Basis : Variabel Nonbasis :
X11 = 120 X12 = 0
X21 = 30 X13 = 0
X22 = 50 X23 = 0
X32 = 20 X31 = 0
X33 = 60
Maka total biaya transpor adalah :
Z = 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23 + 3X31 + 9X32 +
10X33
= (8x120) + (15x30) + (10x50) + (9x20) + (10x60)
= 2690
21
 Metode Least Cost Value
⚫ Mencapai tujuan minimasi biaya dengan alokasi sistematik
pada kotak-kotak sesuai dengan besarnya biaya transpor per
unit.
⚫ Prosedurnya :
1. Pilih variabel Xij (kotak) dengan biaya transpor (Cij)
terkecil dan alokasikan sebanyak mungkin. Untuk Cij
terkecil, = minimum [Si, Dj]. Ini akan
Xij
menghabiskan baris i atau kolom j.
2. Dari kotak-kotak sisanya yang layak (yaitu yang tidak
terisi atau tidak dihilangkan), pilih nilai Cij terkecil dan
alokasikan sebanyak mungkin.
3. Lanjutkan proses ini sampai semua penawaran dan
permintaan terpenuhi.

22
 70 50

70 10

80

23
 Caranya :
⚫ Langkah pertama dalam metode LCV adalah menyarankan
alokasi X31 karena C31 = 3 adalah kotak dengan biaya
minimum. Jumlah yang dialokasikan
adalah = min [150,80] = 80. Karena alokasi
X31
menghabiskan inipenawaran sumber 3 sehingga baris 3
dihapus, dan maupun tak layak lagi. Juga,
X32 X33
permintaan sebanyak 150 pada tujuan 1 dikurangi
80 sehingga sekarang permintaannya tinggal 70.

⚫ Alokasi kotak selanjutnya dipilih dari 6 kotak sisanya, Cij

terkecil adalah C12 = 5 dan X12 = min [70,120] = 70.

24
 ⚫ Alokasi kotak sisanya dibuat dengan cara yang sama.

⚫ Jika terdapat nilai Cij terkecil yang sama (kembar), pilih

diantara kotak itu secara sembarang. Karena ini hanya
merupakan solusi awal yang tidak berpengaruh terhadap solusi
optimum, kecuali mungkin memerlukan iterasi yang lebih
banyak untuk mencapainya.

25
 Solusi fisibel awal dengan 5 variabel basis & 4 variabel
non-basis sbb :
Variabel Basis : Variabel Nonbasis :
X12 = 70 X11 = 0
X13 = 50 X22 = 0
X21 = 70 X32 = 0
X23 = 10 X33 = 0
X31 = 80
Maka total biaya transpor adalah :
Z = 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23 + 3X31 + 9X32 +
10X33
= (5x70) + (6x50) + (15x70) + (12x10) + (3x80)
= 2060
26
 Metode Aproksimasi Vogel
⚫ VAM hampir selalu memberikan suatu solusi awal yang lebih
baik dibanding metode NWCR dan seringkali lebih baik
daripada metode LCV.

⚫ Pada
beberapa kasus, solusi awal yang diperoleh memalui
VAM akan menjadi optimum.

⚫ VAM melakukan alokasi dalam suatu cara yang akan

meminimumkan penalty (opportunity cost) dalam memilih
kotak yang salah untuk suatu alokasi.

27
 Prosedurnya
1. Hitung opportunity cost untuk setiap baris dan kolom.
Opportunity cost untuk setiap baris i dihitung dengan
mengurangkan nilai Cij terkecil pada baris itu dari nilai Cij satu
tingkat lebih besar pada baris yang sama. Opportunity cost
kolom diperoleh dengan cara yang serupa. Biaya-biaya ini
adalah penalty karena tidak memilih kotak dengan biaya
minimum.

2. Pilih baris atau kolom dengan opportunity cost terbesar (jika

terdapat nilai kembar, pilih secara sembarang). Alokasikan
sebanyak mungkin ke kotak dengan nilai Cij minimum pada
baris atau kolom yang dipilih.
Untuk terkecil. Xij = minimum [Si , Dj]. Artinya
Cij
penalty terbesar dihindari.

28
 3. Sesuaikan penawaran dan permintaan untuk
menunjukkan alokasi yang sudah dilakukan. Hilangkan semua
baris dan kolom dimana penawaran dan permintaan telah
dihabiskan.

4. Jika semua penawaran dan permintaan belum dipenuhi,

kembali ke langkah 1 dan hitung lahi opportunity cost yang
baru. Jika semua penawaran dan permintaan, solusi awal telah
diperoleh.

29
 Penalty Cost (Baris)

6–5=1

12 – 10 = 2

80 9–3=6

Dipilih
Penalty
Penalty
8–3=5 terbesar
Cost 9–5=4 10 – 6 = 4
(Kolom)

30
 Penalty Cost (Baris)

70 50 1 1 1
II

70 10 2
III 2 2

80 6
– –

Penalty I 4 4
5 Cost
(Kolom) II 7 5 6

31 III – 5 6
 Caranya :
⚫ Langkah pertama dalam metode VAM adalah menghitung
opportunity cost (penalty cost) untuk iterasi ke-1 yang
dilakukan pada setiap baris dan kolom. Setelah itu dipilih
opportunity cost yang terbesar.

⚫ Karena sumber 3 memiliki nilai opportunity cost terbesar

maka disarankan alokasi X31 karena C31 = 3 adalah kotak
dengan biaya minimum jika dibandingkan dengan C32 dan C33.
Jumlah yang dialokasikan adalah X31 = min [150,80] = 80.
Karena alokasi ini menghabiskan penawaran sumber 3
sehingga baris 3 dihapus, dan X32
maupun tak diperhitungkan lagi pada iterasi
X33
berikutnya. Juga, permintaan sebanyak 150 pada tujuan
1 dikurangi 80 sehingga sekarang permintaannya tinggal 70.

32
 ⚫ Pada iterasi ke-2, lakukan perhitungan opportunity cost
dengan mengabaikan kotak yang telah terisi (X31) ataupun
yang tidak akan diperhitungkan lagi (X32, X33). Karena pada
iterasi ke-2, kolom tujuan 1 yang memiliki
opportunity cost terbesar maka disarankan
mengalokasikan ke kotak X11 karena C31 =
alokasi 8sebesardengan
X31 = min [70,120] = 70.

⚫ Lakukan iterasi tersebut berulang-ulang

sampai permintaan terpenuhi semua.

33
 Solusi fisible awal dengan 5 variabel basis & 4 variabel
non-basis sbb :
Variabel Basis : Variabel Nonbasis :
X11 = 70 X12 = 0
X13 = 50 X21 = 0
X22 = 70 X32 = 0
X23 = 10 X33 = 0
X31 = 80
Maka total biaya transpor adalah :
Z = 8X11 + 5X12 + 6X13 + 15X21 + 10X22 + 12X23 + 3X31 + 9X32 +
10X33
= (8x70) + (6x50) + (10x70) + (12x10) + (3x80)
= 1920
34
 ⚫ Beedasarkan hasil pencarian solusi awal dengan ketiga metoda
di atas, diperoleh kesimpulan bahwa biaya awal terkecil adalah
1920 yang diperoleh dari hasil pencarian dengan metoda VAM.
⚫ Tetapi apakah solusi ini merupakan solusi optimum atau
bukan, belum diketahui. Karena harus dilanjutkan ke langkah
2 untuk mencari solusi optimum.
⚫ Setelah solusi layak dasar awal diperoleh, kemudian dilakukan
perbaikan untuk mencapai solusi optimum.

⚫ Pencarian solusi optimum dapat dilakukan dengan

menggunakan metoda stepping stone atau metoda
multiplier.

35
 Contoh 1 Kasus Transportasi Unbalance
Fungsi Tujuan :
Minimalkan Z = 8X11 + 5X12 + 6X13+ 15X21 + 10X22 +
12X23 + 3X31 + 9X32 + 10X33
Fungsi Pembatas :
X11 + X12 + X13 = 120
X21 + X22 + X23 = 80
X31 + X32 + X33 = 80
X11 + X21 + X31 ≤ 150 Menunjukkan bahwa semua unit yang
tersedia akan dikirimkan, namun satu/lebih
X12 + X22 + X32 ≤ 70 kendala permintaan tidak akan terpenuhi

X13 + X23 + X33 ≤ 90

Xij ≥ 0
36
 Pencarian Solusi
⚫ Dalam pencarian solusinya dapat menggunakan tabel
transportasi seperti biasa, atau dapat ditambahkan sumber hayal
(dummy) yang memiliki biaya transportasi nol per unit untuk
setiap tujuan karena sesungguhnya kotak dummy analog dengan
variabel slack yang nilai kontribusinya dalam fungsi tujuan
sama dengan nol.

⚫ Dalam pencarian solusi dengan metode Least-Cost, kotak- kotak

dummy dapat diabaikan dan alokasi dibuat sesuai dengan biaya
minimum, setelah alokasi dilakukan. Kelebihannya dialokasikan
ke variabel dummy yang sesuai.

37
 ⚫ Dalam pencarian solusi dengan metode VAM, nilai Cij
dummy digunakan sebagai biaya kolom terkecil ketika
dilakukan perhitungan opportunity cost.

⚫ Dalam
metode stepping stone dan multifier, kotak-kotak
dummy diperlakukan seperti kotak-kotak yang lain.

38
 Tabel Transportasi Tanpa Dummy :

39
 Tabel Transportasi dengan Dummy :

40
 Pencarian Solusi Awal dengan Metode NWCR :

41
Z=
 Pencarian Solusi Awal dengan Metode NWCR :

42 Z=
 Pencarian Solusi Awal dengan Metode Least Cost :

43 Z=
 Pencarian Solusi Awal dengan Metode Least Cost :

44 Z=
 Pencarian Solusi Awal dengan Metode VAM :

45 Z=
 Pencarian Solusi Awal dengan Metode VAM :

46 Z=
 Contoh 2 Kasus Transportasi Unbalance
Fungsi Tujuan :
Minimalkan Z = 8X11 + 5X12 + 6X13+ 15X21 + 10X22 +
12X23 + 3X31 + 9X32 + 10X33
Fungsi Pembatas :
X11 + X12 + X13 ≤ 120
X21 + X22 + X23 ≤ 80
X31 + X32 + X33 ≤ 80
X11 + X21 + X31 = 100
X12 + X22 + X32 = 70
X13 + X23 + X33 = 90
Xij ≥ 0
47
 Tabel Transportasi Tanpa Dummy :

48
 Tabel Transportasi dengan Dummy :

49
 Pencarian Solusi Awal dengan Metode NWCR :

50 Z=
 Pencarian Solusi Awal dengan Metode NWCR :

51 Z=
 Pencarian Solusi Awal dengan Metode Least Cost :

52 Z=
 Pencarian Solusi Awal dengan Metode Least Cost :

53 Z=
 Pencarian Solusi Awal dengan Metode VAM:

54 Z=
 Pencarian Solusi Awal dengan Metode VAM:

55 Z=