BAB 2 LANDASAN TEORI 2.1
Model Transportasi Menurut Mulyono (2004, p114) persoalan transportasi membahas masalah pendistribusian suatu komoditas atau prouk dari sejumlah sumber (supply) kepada sejumlah tujuan (destination, demand) dengan tujuan meminimumkan ongkos pengangkutan yang terjadi. Ciri-ciri khusus persoalan transportasi ini 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. Barang yang dikirim atau diangkut dari suatu sumber ke suatu tujuan, besarnya sesuai dengan permintaan dan kapasitas sumber. 4. Ongkos pengangkutan komoditas dari suatu sumber ke suau tujuan, besarnya tertentu. Secara diagramatik, model transportasi dapat digambarkan sebagai berikut: Misalkan ada m buah sumber dan n buah tujuan.
5
Sumber
Tujuan
a
b
i=1
X 11
j=1
X 12 . . . .
X 1n
i=2
j=2
X 21 X 22
. . . . . . . . . .
j=3
. . . .
. . . .
X 2n
j=n i=3
X 31
X 32 . . . .
X 3n Gambar 2.1 Model Transportasi Dimana,
Masing-masing sumber mempunyai kapasitas ai , i = 1, 2, 3, ..., m.
Masing-masing tujuan membutuhkan komoditas sebanyak b j , j = 1, 2, 3, ..., n.
6
Jumlah satuan (unit) yang dikirimkan dari sumber i ke tujuan j adalah sebanyak
X ij
Ongkos pengiriman per unit dari sumber i ke tujuan j adalah C ij .
Dengan demikian perumusan matematisnya adalah sebagai berikut: m
Meminimumkan:
z=
n
∑∑ C i =1 j =1
ij
n
∑X
Berdasarkan pembatas:
j =1
ij
= ai , i = 1,2,3,..., m
ij
= bi , j = 1,2,3,..., n
m
∑X i =1
X ij
X ij ≥ 0 untuk seluruh i dan j.
Sebagai ilustrasi, jika ada 2 buah sumber dan 3 tujuan (m=2, n=3)
b1 C 11, X 11
a1 C , 12 X
12
21 ,X
C 21 C 13 , X
b2
13
X 22 C 22,
a2 C23, X
23
b3
Gambar 2.2 Ilustrasi Model Transportasi 2 Sumber 3 Tujuan
7
Perumusan matematis: Meminimumkan: z = C11 X 11 + C12 X 12 + C13 X 13 + C 21 X 21 + C 22 X 22 + C 23 X 23
Berdasarkan pembatas: X 11 + X 12 + X 13 = a1
pembatas sumber
X 21 + X 22 + X 23 = a 2 X 11 + X 21 = b1 X 12 + X 22 = b2
pembatas tujuan
X 13 + X 23 = b3
Sedangkan matriks berupa tabel dari persamaan tersebut dapat dilihat pada gambar berikut: tujuan 1 sumber (i)
1 C11 X11
2
2 C12 X12
C21
3 Supply C13 a1
X13 C22
C23
a2 X21 X22 X23 b1 b3 b3 demand Gambar 2.3 Matriks Transportasi dalam Tabel 2.2
Model Transshipment
Suatu perluasan dari rumusan transportasi adalah masalah transshipment (pemindahan), dimana setiap sumber dan tujuan dapat juga menjadi titik perantara pengiriman dari sumber-sumber atau tujuan-tujuan lain. Berikut adalah diagram contoh model transshipment.
8
Sumber (i)
Biaya Demand (bal)
Supply (bal) (70) (70)
Pulo Gadung
Tanggerang
(40)
(40) (17)
(60) (80)
(27)
(45)
(80)
Kebayoran
Bekasi
(100)
(36)
(20)
(20)
(50)
(35) (50)
Pasar Boplo
Ciputat
(60)
Gambar 2.4 Contoh Persoalan Transshipment Dalam model ini setiap sumber maupun tujuan dipandang sebagai titik-titik potensial bagi demand maupun supply. Oleh karena itu, untuk menjamin bahwa tiap titik potensial tersebut mampu manampung total barang di samping jumlah barang yang telah ada pada titik-titik itu kuantitas supply dan demand-nya masingm
m
i =1
j =1
masing sebesar B. B ≥ ∑ ai = ∑ b j dari pemodelan transportasi. Dengan demikian, bila ada persoalan transportasi sebagai berikut: Tabel 2.1 Contoh Persoalan Transportasi T1 S1 S2
T2
T3
10
20
30
20
50
40
Demand 100
100
9
100
Supply
100 200
Maka pemodelan transshipment-nya adalah: Tabel 2.2 Contoh Persoalan Transshipment S1
S2
T1
S1 S2
T2
T3
10
20
30
20
50
40
Supply
100 + B 200 + B
T1
B
T2
B
T3
B
Demand
B
B
100 + B 100 + B 100 + B
Model diatas baru lengkap apabila ongkos per unit pengangkut untuk barisbaris-baris dan kolom-kolom yang lainnya telah ditetapkan. Dalam hal ini perlu diingat bahwa ongkos per unit pada elemen-elemen diagonal adalah nol. 2.3
Metode Northwest-Corner
Metode Northwest-Corner digunakan untuk menentukan solusi awal. Langkah-langkahnya adalah sebagai berikut: Mulai dari pojok barat laut tabel dan alokasikan sebanyak mungkin pada X 11 tanpa menyimpang dari kendala penawaran atau permintaan (artinya X 11 ditetapkan sama dengan yang terkecil di antara nilai supply dan demand) X 11 = min(a1 , b1 ) , jika b1 < a1 maka X 11 = b1 ; jika b1 > a1 maka X 11 = a1 . Kalau X 11 = b1 , maka yang mendapat giliran untuk dialokasikan adalah X 12 sebesar min(a1 − b1 , b2 ) ; kalau X 11 = a1 (atau b1 > a1 ), maka selanjutnya yang mendapat
10
X 12 sebesar min(b1 − a1 , a 2 ) . Demikian
giliran untuk dialokasikan adalah seterusnya. Contoh:
Tabel 2.3 Tabel Hasil Perhitungan Metode Northwest-Corner T1 S1
10 5
T3
T4
Supply
0
20
11
7
9
20
10 12
S2
5
15
0
S3 Demand
T2
5
14
5 16
15
15
18 5 10
15 25 5
a1 = 15; b1 = 5 ⎯ ⎯→ X 11 = min(15,5) = 5 a1 − b1 = 10; b2 = 15 ⎯ ⎯→ X 12 = min(10,15) = 10
Langkah
selanjutnya
adalah
mengisi
b2
sampai
penuh
dengan
mengalokasikan sebesar 5 pada X 22 , yaitu jumlah kekurangan yang terjadi dalam pemenuhan kebutuhan pada b2 . Dengan melanjutkan prosedur di atas, maka akan diperoleh berturut-turut: X 23 = 15, X 24 = 5 dan X 34 = 5, yang bersama-sama dengan X 11 , X 12 , dan X 22
membentuk solusi layak basis awal Z = 410. 2.4
Metode Least Cost
Metode Least Cost atau ongkos terkecil berusaha mencapai tujuan minimisasi biaya dengan alokasi sistematik kepada kotak-kotak sesuai dengan besarnya biaya transpor per unit.
11
Prosedur metode ini adalah: 1. Plih variabel X ij (kotak) dengan biaya transpor ( C ij ) terkecil dan alokasikan sebanyak mungkin. Untuk C ij terkecil, X ij = minumum ( Supply i , Demand j ). Ini akan menghabiskan baris i atau kolom j. 2. Dari kotak-kotak sisanya yang layak (yaitu yang tidak terisi atau tidak terhilangkan), pilih nilai C ij terkecil dan alokasikan sebanyak mungkin. 3. Lanjutkan proses ini sampai semua penawaran dan permintaan terpenuhi. Contoh: Tabel 2.4 Tabel Hasil Perhitungan Metode Least Cost T1 10
S1
Demand
T3
T4
Supply
0
20
11
7
9
20
15 12
S2 S3
T2
15 0
14
10 16
18
5 5
15
15
15 25 5
10
Dengan mengambil contoh diatas, C12 = C 31 = 0 adalah ongkos terkecil dari keseluruhan tabel. Maka X 12 dan X 31 mendapat prioritas pengalokasikan pertama kali. Jumlah unit yang dialokasikan masing-masing adalah
X 12
= min
( Supply1, Demand 2 ) = 15. dan X 31 = min ( Supply 3, Demand1 ) = 5. Selanjutnya lihat ongkos terkecil berikutnya, yaitu C 22 = 7. Tetapi, karena tujuan kedua ( Demand 2 ) telah terisi penuh, maka lihat ongkos terkecil berikutnya, diperoleh C 23 = 9. Alokasikan X 23 = min ( Supply 2, Demand 3 ) = min (25,15) = 15. Dengan
12
menjalankan prosedur di atas, diperolah X 24 =10. Maka X 12 , X 31 , X 23 dan X 24 bersama-sama membentuk solusi layak basis awal Z = 335. 2.5
Metode Pendekatan Vogel
Metode Pendekatan Vogel atau Vogel’s Approximation Method (VAM) melakukan alokasi dalam suatu cara yang akan meminimumkan penalty (opportunity cost) dalam memilih kotak yang salah untuk suatu alokasi. Proses Metode Pendekatan Vogel dapat diringkas sebagai berikut: 1. Hitung penalty untuk tiap kolom dan baris dengan jalan mengurangkan elemen ongkos terkecil dari yang kedua terkecil. 2. Selidiki kolom atau baris dengan penalty terbesar. Alokasikan sebanyak mungkin pada variabel dengan ongkos terkecil, sesuaikan supply dan demand, kemudian tandai kolom atau baris yang sudah terpenuhi. Kalau ada 2 buah kolom atau baris yang sudah terpenuhi secara simultan, pilih salah satu untuk ditandai, sehingga supply atau demand sama dengan nol, tidak akan terbawa lagi dalam perhitungan penalty pada iterasi berikutnya. 3. Bila tinggal 1 kolom atau baris yang belum ditandai, stop iterasi. Bila tinggal 1 kolom atau baris dengan supply atau demand positif yang belum ditandai, tentukan variabel basis pada kolom atau baris dengan cara ongkos terkecil (least cost). Bila semua baris dan kolom yang belum ditandai mempunyai supply dan demand sama dengan nol, tentukan variabel-variabel basis yang berharga nol
dengan cara ongkos terkecil, kemudian stop.
13
Jika syarat-syarat diatas tidak terjadi, hitung kembali penalty untuk baris atau kolom yang belum ditandai. Kembali ke nomor 2. Contoh:
S1
Tabel 2.5 Tabel Perhitungan Iterasi Pertama Vogel Penalty T2 T3 T4 T1 Supply Baris 10 0 20 11 15 10
S2 S3 Demand Penalty Kolom
12
7
9
20
0
14
16
18
5
15
15
10
10
7
7
7
25
2
5
14
Kerena baris ketiga memiliki penalty terbesar (=14) dan karena C 31 = 0 merupakan ongkos terkecil di dalam barisnya, maka dialokasikan X 31 = 5. Dengan demikian, baris 3 dan kolom 1 sudah terpenuhi secara simultan. Dalam hal ini bisa dipilih baris 3 atau kolom 1 yang akan ditandai. Misalkan dipilih kolom 1 untuk ditandai, maka sisa supply untuk baris 3 menjadi 0. Tabel baru menjadi:
14
S1
Tabel 2.6 Tabel Perhitungan Iterasi Kedua Vogel Sisa Penalty T2 T3 T4 T1 Supply Baris 10 0 20 11 15 11
S2 S3
12
7
9
20
0
14
16
18
5
Sisa Demand Penalty Kolom
0
15
15
10
-
7
11
9
25
2
0
-
Selanjutnya ulangi kembali perhitungan penalty. Dapat dilihat bahwa baris 1 dan kolom 3 mempunyai penalty yang sama (=11) sehingga kembali dapat dipilih salah satu untuk ditandai. Misalkan dipilih kolom 3 untuk ditandai, maka alokasikan X 23 =15. Sisa supply untuk baris 2 sekarang menjadi 10.
S1
Tabel 2.7 Tabel Perhitungan Iterasi Ketiga Vogel Sisa Penalty T1 T2 T3 T4 Supply Baris 10 0 20 11 15 11 12
S2 S3 Sisa Demand Penalty Kolom
7
9
20
16
18
15 0
14
5 0
15
0
10
-
7
-
9
10
13
0
-
Dengan menghitung penalty yang baru diperoleh penalty terbesar untuk baris 2 (=13) sehingga alokasikan X 22 = 10. Kemudian tandai baris 2.
15
Tabel 2.8 Tabel Perhitungan Iterasi Keempat Vogel Sisa T1 T2 T3 T4 Supply 10 0 20 11 S1 15 12
S2 S3 Sisa Demand
7 10
9
20
16
18
15
0
14
5 0
5
0
0 0
10
Supply yang masih tersedia adalah 15 (baris 1), sedangkan demand yang
belum terpenuhi adalah kolom 2 sebanyak 5 dan kolom 4 sebanyak 10. Karena tidak ada pilihan lain, maka alokasikan X 12 = 5 dan X 14 =10 dengan metode least cost. Pengisian tabel selesai dengan solusi layak basis awal Z = 315: X 12 = 5, X 14 = 10, X 22 = 10, X 23 = 15, dan X 31 = 5.
Tabel 2.9 Hasil Akhir Alokasi dengan Metode Pendekatan Vogel T1
2.6
0
T4 20
5
Supply
11 10
12
S2
Demand
T3
10
S1
S3
T2
7 10
0
9
20
16
18
15 14
5 5
15
15
10
Metode Pendekatan Russell
Berikut adalah prosedur Metode Pendekatan Russell:
16
15 25 5
1. Untuk setiap baris Supply i yang masih menjadi pertimbangan atau belum terisi, tentukanlah u i yang merupakan biaya per unit ( C ij ) terbesar yang masih ada dalam baris tersebut. 2. Untuk setiap kolom Demand j yang masih menjadi pertimbangan atau belum terisi, tentukanlah v j yang merupakan biaya per unit ( C ij ) terbesar yang masih ada dalam kolom tersebut. 3. Untuk setiap variabel X ij yang sebelumnya belum dipilih dalam baris-baris dan kolom-kolom ini, hitunglah Δ ij = C ij − u i − v j . 4. Pilih variabel yang mempunyai nilai negatif (mutlak) terbesar dari Δ ij (kalau ada yang sama pilih secara arbitrer). Lanjutkan proses ini mulai dari nomor 1 lagi sampai tidak ditemukan nilai negatif (mutlak) terbesar dari Δ ij . Contoh: Tabel 2.10 Contoh Soal untuk Metode Pendekatan Russell T1 S1 S2 S3 Demand
T2
T3
T4
Supply
10
0
20
11
12
7
9
20
0
14
16
18
5
15
15
15 25 5
10
Hasil perhitungan iterasi pertama contoh soal dihitung secara berurutan dapat dilihat pada Tabel 2.11 dibawah ini.
17
u1
u2
u3
20
20
18
Tabel 2.11 Hasil Iterasi Pertama Russell Δ ij v1 v2 v3 v4 12
14
20
20
Alokasi
Δ 11 = -22 Δ 12 = -34 *
X 12 = 15
Δ 13 = -20 Δ 14 = -29 Δ 21 = -20 Δ 22 = -27
Δ 23 = -31 Δ 24 = -20
Δ 31 = -30 Δ 32 = -18 Δ 33 = -22 Δ 34 = -20
Dari tabel 2.11 dapat dilihat nilai Δ ij negatif terbesar ada pada Δ 12 sehingga alokasi sebanyak mungkin pada X 12 = min( Supply1 , Demand 2 ) = 15 sebagai variabel dasar (alokasi) pertama. Karena telah memenuhi Supply1 dan Demand 2 maka baris 1 dan kolom 2 tidak menjadi pertimbangan lebih lanjut. Hasil-hasil perhitungan iterasi berikutnya termasuk urutan variabel-variabel dasar (alokasi-alokasi), diperlihatkan dalam Tabel 2.12.
18
Tabel 2.12 Hasil Perhitungan Semua Iterasi Russell Iterasi
u1
u2
u3
v1
v2
v3
v4
Δ ij terkecil
Alokasi
1
20
20
18
12
14 20
20
Δ 12 = -34
X 12 = 15
2
-
20
18
12
-
16
20
Δ 31 = -30
X 31 = 5
3
-
20
-
-
-
9
20
Δ 23 = -20
X 23 = 15
4
-
20
-
-
-
-
20
Δ 24 = -20
X 24 = 20
Alokasi secara penuh hasil perhitungan metode pendekatan Russell dengan solusi basis awal Z = 335 : X 12 , X 31 , X 23 , dan X 24 disajikan dalam Tabel 2.13. Tabel 2.13 Hasil Akhir Alokasi Metode Pendekatan Russell T1 10
S1
Demand 2.7
T3
T4
Supply
0
20
11
7
9
20
15 12
S2 S3
T2
15 0
14
10 16
18
5 5
15
15
15 25 5
10
Metode Multiplier
Setelah solusi layak dasar awal diperoleh dari masalah transportasi, langkah berikutnya adalah menekan kebawah biaya transpor dengan memasukkan variable nonbasi (yaitu alokasi barang ke kotak kosong ke dalam solusi). Proses evaluasi variable nonbasis yang memungkinkan terjadinya perbaikan solusi dan kemudian mengalokasikan kembali dinamakan Metode multiplier. Cara ini dikembangkan berdasarkan teori dualitas. Untuk tiap basis i dari tabel transformasi dikenal suatu
19
multiplier u i , dan untuk kolom j disebut multiplier V j sehingga untuk tiap variabel
basis X ij didapat persamaan: u i + v j + C ij . Dari persamaan di atas dapat dihitung beberapa penurunan ongkos sebagai berikut:
transportasi per unit untuk tiap variabel nonbasis X ij C ij = X ij − u i − v j .
Sebagai contoh ada solusi awal yang telah didapat dari Metode NortwestCorner
Tabel 2.14 Solusi Awal Hasil Perhitungan Metode Nortwest-Corner T1 S1
T3
10 5
T4
Supply
0
20
11
7
9
20
10 12
S2
5
15
0
S3 Demand
T2
5
14 15
Basis awal: X 11 : u1 + v1 = C11 = 10 X 12 : u1 + v 2 = C12 = 0 X 22 : u 2 + v 2 = C 22 = 7
X 23 : u 2 + v3 = C 23 = 9 X 24 : u 2 + v 4 = C 24 = 20
X 34 : u 3 + v 4 = C 34 = 18
20
5 16
15
18 5 10
15 25 5
Dengan menentukan u i = 0 , maka harga-harga multiplier yang lain dapat dicari sebagai berikut: u1 + v1 = 10 Æ v1 = 10 u1 + v 2 = 0 Æ v 2 = 0 u 2 + v2 = 7 Æ u 2 = 7
u 2 + v3 = 9 Æ v 3 = 2 u 2 + v 4 = 20 Æ v 4 = 13
u 3 + v 4 = 18 Æ u 3 = 5
Tabel 2.15 Perhitungan Iterasi Pertama Multiplier v1 = 10
ui = 0 u2 = 7
u3 = 5
10 •
v3 = 2
v2 = 0
0 •
12 -5
+18
•
-15 5
20
7
0
v 4 = 13
-2 9
• 14
+9 15
11 20 •
16 +9 15
18 • 10
Untuk menentukan entering variable, alokasi yang sudah terpenuhi (disimbolkan dengan •) tidak diperhitungkan : C 21 =C 21 −v1 − u 2 = −5 C 31 =C 31 −v3 − u1 = −15 C13 =C 13 −v1 − u 3 = 18 C14 =C 14 −v1 − u 4 = −2 C 32 =C 32 −v3 − u 2 = 9
21
C 33 =C 33 −v3 − u 3 = 9 Entering variable adalah X 31 karena memberikan penurunan ongkos per unit yang terbesar, yaitu sebanyak 15 satuan ongkos per unit. Dengan demikian, dapat dibuat sebuah loop yang berawal dan berakhir pada variabel X 31 . Tabel 2.16 Tabel Closed-Loop Iterasi Pertama T1 5
-
12 5 +
Demand
dan
+
Supply
0
20
11
7
9
20
15
-
10
S3
T4
10 +
S2
-
T3
10
S1
Tanda
T2
14
5+ 16
X 31
18 5-
5
15
15
15 25 5
10
menyatakan bahwa variabel yang bersangkutan (pada
masing-masing kotak) akan bertambah atau berkurang besarnya sebagai akibat perpindahan kolom dan perpindahan baris. Leaving variable dipilih dari variabel-varibel sudut loop yang bertanda
-
.
Pada contoh di atas, di mana X 31 telah terpilih sebagai entering variable, caloncalon leaving variable-nya adalah X 11 , X 22 , dan X 34 . Dari calon-calon ini, pilihlah salah satu yang nilainya paling kecil. Pada contoh diatas kebetulan ketiganya bernilai sama (=5) sehingga bisa dipilih salah satu untuk dijadikan leaving variable. Misalkan X 34 dipilih sebagai leaving variable, maka nilai X 31 naik 5 dan nilai-nilai variabel basis yang di sudut loop juga berubah (bertambah atau berkurang 5 sesuai dengan tanda
22
+
atau
-
).
Solusi baru ini adalah seperti pada tabel berikut dengan ongkos transportasi sebesar: (0 x 10) + (15 x 0) + (0 x 7) + (15 x 9) + (10 x 20) + (5 x 0) = 335. Tabel 2.17 Hasil Iterasi Pertama Setelah Perputaran Nilai Pada Closed-Loop T1 S1
Demand
T3
10 0
T4
Supply
0
20
11
7
9
20
15 12
S2 S3
T2
0
15
10
14
10 16
15 25
18
5 5
15
15
5
10
Bandingkan dengan solusi awal pada Tabel 2.4 yang ongkos transportasinya adalah = 410. Selisih ongkos transportasi (410 – 335 = 75) sama dengan hasil perkalian antara: jumlah unit yang ditambahkan pada X 31 x penurunan ongkos per unit Ù (5) x (15). Perhatikan, angka 0 pada X 11 dan X 22 adalah variabel basis yang berharga 0. Jadi, tidak boleh dihilangkan karena ia tidak sama dengan kotak-kotak lain yang tidak ada angkanya (variabel nonbasis). Sampai tahap ini masih harus memeriksa, barangkali nilai fungsi tujuan masih bisa diperbaiki. Untuk itu lakukanlah kembali langkah-langkah yang sudah dikerjakan sebelumnya, dengan mengunakan Tabel 2.17 sebagai solusi awal (pengganti Tabel 2.14). Sehingga didapat: Variabel nonbasis
Perubahan ongkos per unit
X 13
C13 = +18
X 14
C14 = −2
23
X 21
C 21 = −5
X 32
C 32 = +24
X 33
C 33 = +24
X 34
C 34 = +15
Dengan demikian dipilih X 21 sebagai entering variable. Tabel 2.18 Tabel Perhitungan Iterasi Kedua Multiplier T1 S1 S2
T2
T3
10 -
0
0 15
S3
X 21
20
11
9
20
+
12 +
Toko4 Supply
7 0
-
10
15
10
14
16
18
5
Demand
5
15
15
15 25 5
10
Tabel 2.19 Tabel Perhitungan Iterasi Ketiga Multiplier T1
T2 10
S1
0 -
S2 S3 Demand
T3
X 14 7
+
10
0
9 15
14
10
-
16
15
15
15
+
20 18
5 5
Supply 11
20
15
12 0
T4
25 5
10
Pada loop yang berasal dan berakhir pada X 21 ini, leaving variable-nya ada dua, yaitu X 11 dan X 22 . Karena keduanya berharga 0, bisa dipilih salah satu untuk dijadikan leaving variable. Misalkan X 11 adalah leaving variable, maka X 21 = 0
24
dengan ongkos transportasi tetap 335. Karena itu, dicoba membuat loop dari variabel nonbasis yang lain, yang juga dapat menurunkan ongkos transportasi per unit (yaitu
C11 = +5; C 32 = +19; C13 = +18; C 33 = +19 ;
X 14 ). Maka didapat:
; C34 = +10; C14 = −2 . Dari Tabel 2.10 terlihat bahwa leaving variable adalah X 24 sehingga X 14 = 10; X 22 = 10; dan X 12 = 5. Solusi optimal adalah : Tabel 2.20 Tabel Hasil Akhir Perhitungan dengan Metode Multiplier T1 10
S1 S2 S3 Demand
T2
T3
T4
Supply
0
20
11
7
9
20
16
18
5 12 0
10
15
10 5 5
14 15
15
15 25 5
10
Dengan ongkos transportasi Z = 315. 2.8
Pengetahuan Dasar Algoritma
Dalam konteks matematika dan ilmu komputer, algoritma adalah sebuah prosedur (Suatu himpunan instruksi yang terdeskripsi dengan jelas beserta dengan urutan pengerjaannya) untuk menyelesaikan suatu tugas, dengan diberikan suatu kondisi awal, dan akan berhenti pada kondisi akhir yang telah diketahui. Secara informal, konsep dari algoritma diilustrasikan dengan contoh sebuah resep. Konsep algoritma berawal pada penggabungan urutan-urutan prosedur menjadi satu untuk menyelesaikan permasalahan matematik, seperti mencari faktor
25
persekutuan terbesar dari dua bilangan. Konsep tersebut diresmikan pada tahun 1936 melalui Mesin Turing Alan Turing, dan kalkulus lambda Alonzo Church, yang pada akhirnya membentuk fondasi ilmu komputer. Kebanyakan algoritma dapat diimplementasikan secara langsung ke dalam bahasa pemrograman, algoritma lainnya setidaknya dapat disimulasikan secara teoritis oleh program komputer. 2.8.1 Sejarah Singkat Algoritma
Kata algoritma berasal dari nama seorang matematikawan Persia abad ke-9 Abu Abdullah Muhammad bin Musa al-Khwarizmi. Kata algoritma pada awalnya hanya merupakan istilah yang diperuntukkan aturan-aturan dalam melakukan operasi aritmatik menggunakan bilangan Hindu-Arab, namun pada evolusinya melalui terjemahan eropa latin nama al-Khwarizmi diterjemahkan menjadi algorithm pada abad 18. Definisnya pun mengalami pengembangan sehingga dapat berarti semua prosedur untuk menyelesaikan suatu masalah atau untuk melakukan suatu tugas. Pertama kali suatu algoritma ditulis untuk komputer berjudul Ada Byron’s notes on the analitycal engine pada tahun 1842, di mana nama Ada Byron diterima secara luas sebagai programmer pertama di dunia. Namun, karena Charles Babbage tidak pernah menyelesaikan analytical engine-nya, algoritma tersebut pun tidak pernah diimplementasikan. 2.8.2 Pseudocode
Algoritma adalah kumpulan langkah-langkah untuk melakukan perhitungan. Kebanyakan algoritma akan diimplementasikan sebagai program komputer. Algoritma dapat ditulis dalam notasi apapun termasuk dalam Bahasa Inggris untuk 26
tujuan dokumentasi dan penelitian. Namun suatu cara yang lebih disukai untuk menulis algoritma adalah dengan menulisnya dalam bentuk pseudocode. Notasi pseudocode dapat menghindari ambiguitas dalam bahasa, dan juga dapat diterjemahkan ke dalam bahasa pemrograman secara langsung. Salah satu contoh dari algoritma yang paling sederhana adalah untuk menemukan bilangan yang paling besar dari suatu daftar bilangan tidak terurut, yang apabila ditulis dalam Bahasa Inggris adalah sebagai berikut: 1. Let us assume the first item is largest. 2. Look at each of the remaining items in the list and make the following adjustment.
If it is larger than the largest item we gathered so far, make a note of it.
3. The latest noted item is the largest in the list when the process is complete. Algoritma di atas apabila ditulis menjadi pseudocode menjadi seperti berikut di bawah ini: Algorithm LargestNumber Input: A non-empty list of numbers L. Output: The largest number in the list L. largest ← L0 for each item in the list L≥1, do if the item > largest, then largest ← the item return largest
Gambar 2.5 Gambar Pseudocode Mencari Nilai Terbesar 2.8.3 Analisis Algoritma
Pada prakteknya, kebanyakan orang yang mengimplementasikan algoritma ingin mengetahui seberapa banyak sumber daya tertentu yang diperlukan untuk algoritma tersebut. Sumber daya yang dimaksud di sini adalah storage (besar memori komputer) dan waktu. Beberapa metode telah dikembangkan untuk
27
memberikan jawaban yang bersifat kuantitatif untuk pertanyaan di atas; misalnya, algoritma pencarian bilangan terbesar seperti yang pernah disebut sebelumnya memerlukan waktu O(n), menggunakan notasi big O, dengan n sebagai jumlah bilangan yang terdapat pada daftar. Pada setiap satuan waktu, algoritma di atas hanya perlu menyimpan 2 nilai: bilangan terbesar yang telah ditemukan sampai saat tersebut, dan posisi sekarang pada daftar. Oleh karena itu, algoritma tersebut dikatakan memerlukan storage O(1). Algoritma yang berbeda mungkin dapat menyelesaikan tugas yang sama dengan kumpulan instruksi yang berbeda, yang dapat berakibat pada perbedaan waktu dan/atau storage yang diperlukan. Waktu proses (computing time) suatu algoritma, dapat dibedakan mejadi dua hal, yaitu: 1. Apriori analysis, yaitu analisis untuk mendapatkan waktu proses dalam bentuk fungsi matematik, yang disebut sebagai fungsi batas waktu proses. Analisis ini dilakukan sebelum algoritma tersebut diproses dengan suatu komputer. Fungsi waktu ini sering disimbolkan dengan notasi Big O. 2. Aposteriortesting, yaitu analisis untuk mendapatkan waktu proses aktual suatu algoritma. Hasil perhitungan waktu didapat pada saat algoritma diproses pada suatu komputer. 2.8.4 Notasi Big O
Dalam membandingkan kecepatan proses algoritma selanjutnya, penulis menggunakan notasi Big O karena notasi ini paling luas digunakan di dunia komputer dibanding notasi-notasi lainnya.
28
Notasi Big O merupakan suatu notasi matematika untuk menjelaskan batas atas dari magnitude suatu fungsi dalam fungsi yang lebih sederhana. Dalam dunia ilmu komputer, notasi ini sering digunakan dalam analisis kompleksitas algoritma. Notasi Big O pertama kali diperkenalkan pakar teori bilangan Jerman, Paul Bachman tahun 1894, pada bukunya yang berjudul Analytische Zahlentheorie edisi kedua. Notasi tersebut kemudian dipopulerkan oleh pakar teori bilangan Jerman lainnya, Edmund Landau, dan oleh karena itu, terkadang disebut sebagai symbol Landau. Notasi Big O sangat berguna saat menganalisis efisiensi suatu algoritma. Sebagai contoh, waktu (atau jumlah langkah) yang diperlukan oleh suatu algoritma untuk menyelesaikan tugas dengan ukuran n adalah T(n) = 4n2-2n+2. Untuk n yang besar, hasil perhitungan n2 menjadi dominan, sehingga perhitungan yang lain dapat diabaikan (misalnya saat n=500, 4n2 1000 kali lebih besar dari 2n, sehingga mengabaikan 2n+2 tidak akan membawa efek yang besar pada tujuan utama pada umumnya). Kemudian koefisien pada polinomial pun dapat dihilangkan dengan alasan yang sama, sehingga dengan notasi big O, dapat disimpulkan: T (n) ∈ O(n 2 ) bahwa algoritma di atas memiliki kompleksitas waktu dengan orde O(n 2 ) . Untuk membandingkan kompleksitas algoritma yang satu dengan yang lain, dapat digunakan tabel jenis kompleksitas di bawah, yang diurutkan berdasarkan kompleksitas yang paling baik ke yang paling buruk.
29
Notasi
Tabel 2.21 Tabel Jenis Kompleksitas Nama
O(1)
Konstan
O(log * n)
Logaritma iterative
O(log n)
Logaritmik
O([log n]c)
Polilogaritmik
O(n)
Linier
O(n log n)
Linierithmik, loglinier, quasilinier or supralinier
O(n2)
Kuadratik
O(nc), c > 1
Polinomial (kadang disebut algebraic)
O(cn)
Eksponensial (kadang disebut geometric)
O(n!)
Faktorial, kombinatorial
O(nn)
-
30
