BAB II LANDASAN TEORI Adapun landasan teori yang dibutuhkan dalam pembahasan tugas akhir ini di antaranya adalah definisi graf, lintasan terpendek, lintasan terpendek fuzzy, metode rangking fuzzy, algoritma Dijkstra dan algoritma Floyd.
2.1
Graf
Definisi 2.1 (Munir, 2001) Graf ( , ), di tulis dengan notasi
didefinisikan sebagai pasangan himpunan
= ( , ), dimana
dari titik-titik (vertex) dan
adalah himpunan tidak kosong
adalah himpunan sisi (edge) yang menghubungkan
dua buah titik. Gambar 2.1 merupakan contoh graf sederhan.
Gambar 2.1 Graf Sederhana Dengan : V = { , 2.2.
,
,
}, E = {( ,
), (
,
), ( ,
), ( ,
)}
Macam-Macam Graf Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan
atas dua jenis:
2.2.1 Graf Tidak Berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah di sebut graf tak berarah. Gambar 2.2 merupakan contoh graf tidak berarah.
II-1
B
C A
D Gambar 2.2 Graf Tak Berarah
2.2.2 Graf Berarah Graf yang setiap sisinya diberikan orientasi arah disebut graf berarah. Gambar 3 merupakan contoh graf berarah.
Gambar 2. 3 Graf Berarah
2.3
Graf Berbobot
Definisi 2.2 (Munir, 2005) Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot). Bobot pada tiap sisi dapat berbeda-beda tergantung pada masalah yang dimodelkan dengan graf. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah titik komunikasi ke titik komunikasi lain (dalam jaringan komputer), ongkos produksi, dan sebagainya. Gambar 2.4 merupakan contoh graf berbobot.
II-2
Gambar 2.4 Graf Berbobot 2.4
Lintasan Terpendek Persoalan mencari lintasan terpendek di dalam graf merupakan salah satu
persoalan optimasi. Graf
yang digunakan dalam mencari lintasan terpendek
adalah graf berbobot yaitu graf yang setiap sisinya diberikan nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu, dan sebagainya. Lintasan terpendek dengan titik awal s dan titik tujuan t didefinisikan sebagai lintasan terpendek dari s ke t dengan bobot minimum. Sebagai contoh penerapan lintasan terpendek adalah persoalan tukang pos Cina. Persoalan tentang tukang pos Cina pertama kali dikemukakan oleh Mei Ko Kwan, seorang Matematikawan Cina, pada tahun 1962. Persoalan ini adalah persoalan yang banyak dihadapi para tukang pos, yaitu tentang bagaimana seorang tukang pos akan mengantarkan surat-surat yang dibawanya ke alamat-alamat yang ia tuju. Ia harus merencanakan rute perjalanannya agar ia mendapatkan lintasan terpendek dari alamat awal ke alamat akhir dengan semua alamat di kunjungi. Untuk menyelesaikan tukang pos Cina, alamat-alamat yag dituju dapat dinyatakan sebagai titik pada graf, sedangkan jalan yang menghubungkan antar dua buah alamat dinyatakan dengan sisi. Bobot pada sisi menyatakan jarak antar dua buah alamat.
II-3
B
8
D
2
1
A
3
4
F 4
6
8 C
5
2 E
Gambar 2.5 Contoh Graf untuk Persoalan Tukang Pos Cina 2.5
Lintasan Terpendek Fuzzy Masalah pencarian lintasan terpendek sangat umum dan secara luas
dipelajari pada teori graf. Lintasan terpendek bertujuan untuk menemukan lintasan dengan bobot minimum. Pada proses pencarian lintasan, sering kali hanya jarak dari tiap ruas jalan yang digunakan sebagai parameter. Tetapi dalam kenyataannya, biaya, volum jalan, kemacetan, kepadatan jalan dan lain-lain merupakan faktor yang semestinya digunakan sebagai pertimbangan atau parameter dalam menentukan lintasan yang dipilih. Karena, parameter-parameter tersebut mempunyai nilai yang tidak tepat. Oleh karena itu, untuk menangani parameter di atas teori bilangan fuzzy sangat dibutuhkan karena dalam hal ini teori bilangan fuzzy biasanya dinyatakan dalam bentuk besaran, misalnya kurang lebih 10, kira-kira 5 jam, dan sebagainya. Sehingga logika fuzzy digunakan untuk memodelkan multi parameter yang ada pada persoalan lintasan. Sebagai contoh, persoalan tukang pos Cina, alamat-alamat yang di tuju dinyatakan sebagai titik pada graf, sedangkan jalan yang menghubungkan antar dua buah alamat dinyatakan dengan sisi. Bobot pada sisi menyatakan jarak antar dua buah alamat, tetapi dalam lintasan terpendek fuzzy bobot pada sisi menyatakan himpunan bilangan fuzzy segitiga yang menyatakan parameter dari sisi tersebut. Dimana parameternya merupakan parameter yang nilainya bersifat tidak tepat atau fuzzy seperti waktu, kemacetan, kepadatan, biaya, dan lain-lain.
II-4
B
(8, 9, 10)
D (1,3,5)
(3, 5, 7)
(4, 6, 8)
A
(4,7,10)
(4,6,8) (7,9,11)
(5,8,9)
C
F
(2,4,6)
(5,7,9)
E
Gambar 2.6 Contoh Graf untuk Persoalan Tukang Pos Cina dengan Bobot Bilangan Fuzzy 2.6
Bilangan Fuzzy Segitiga
Definisi 2.3 (Susilo, 2006). Bilangan fuzzy segitiga A dinyatakan dengan = (
,
adalah :
,
) adalah himpunan fuzzy A di ( − ) , ( − ) ( − ) , ( − ) 0 , <
=
2.7
( ) yang fungsi keanggotaannya ≤
<
≤
≤
>
Operasi Aritmatika Dasar pada Bilangan Fuzzy Adapun operasi penjumlahan, pengurangan, perkalian, dan pembagian
dalam bilangan fuzzy adalah : Jika maka :
= ( ⨁
1. (
,
,
,
,
) ⨁
) dan ,
,
=
,
= (
, +
merupakan dua bilangan fuzzy segitiga
,
+
,
(2, 5, 9) ⨁ 4, 6, 8 = (2 + 4, 5 + 6, 9 + 8)
+
)
−
)
= (6, 11, 17)
2. (
,
⊝ ,
)⊝
,
,
= (
−
,
−
,
(5, 7, 9) ⊝ 4, 5, 6 = (5 − 4, 7 − 5, 9 − 6) = (1, 2, 3)
II-5
3. ,
⨂ ,
⨂
(
,
(min
,
,
,
,
,
=
,
,
,
,
,
,
,
,
,
,
,
,
,maks
))
(5, 7, 9)⨂(4, 5, 6) = (min (20, 25, 30, 28, 35, 42, 36, 45, 54), maks (20, 25, 30, 28, 35, 42, 36, 45, 54))
= (20, 54) 4. (
/
,
,
)/( ,
,
) = (min ( ,
,
,
,
,
,
,
,
,
,
,
,
,
,
, ))
,
,maks
(5, 7, 9)∕ (4, 5, 6) = (min( , , , , , , , , ), maks ( , , , , , , , , ))
= ( , ) 2.8
Rangking Bilangan Fuzzy Merupakan sebuah metode untuk menbandingkan jumlah bilangan fuzzy
atau peringkat dari bilangan fuzzy. dan adalah dua bilangan fuzzy segitiga.
Misalkan i.
ℜ
ii.
ℜ
2.9
ℜ
ℜ
ℜ
iii.
>
ℜ
<
= ℜ
.
. .
Metode Rangking Fuzzy Metode Rangking fuzzy dikemukakan oleh C. H. Cheng (1998), yang
merupakan jarak antara titik centroid ( , ℜ
=
dengan
(
=
) + (
) dan titik asalnya, yaitu :
)
(
(
)
)
(2.1)
(2.2)
II-6
dan
= 2.10
(
(2.3)
)
Algoritma Dijkstra Algoritma Dijkstra ditemukan oleh Edsger W. Dijkstra yang merupakan
salah satu varian bentuk algoritma popular dalam pemecahan persoalan yang terkait dengan masalah optimasi dan bersifat sederhana. Algoritma ini menyelesaikan masalah mencari sebuah lintasan terpendek (sebuah lintasan yang mempunyai panjang minimum) dari titik s ke titik t dalam graf berbobot pada graf berarah, namun algoritma ini juga benar untuk graf tak berarah. Misalkan G adalah graf berarah berbobot dengan himpunan titik { ,
,…,
} dan lintasan terpendek yang dicari adalah dari
Dijkstra dimulai dari titik
ke
=
. Algoritma
. Sesuai dalam iterasinya, algoritma akan mencari
satu titik yang jumlah bobotnya dari titik 1 terkecil. Titik-titik terpilih dipisahkan dan titik-titik tersebut tidak diperhatikan lagi dalam iterasi berikutnya. Misalkan: ={ ,
,…,
}.
= Himpunan titik-titik lintasan terpendek.
∈ ( ) yang sudah terpilih dalam jalur
= Jumlah bobot lintasan terkecil dari
ℜ = Rangking fuzzy.
1,
∗ 1.
= Bobot dari sisi ( ,
).
= Jumlah bobot lintasan terkecil dari
ke
.
ke
.
Secara formal, algoritma dijkstra untuk mencari lintasan terpendek adalah
sebagai berikut: 1.
= {};
= { ,
,…,
}
2. Untuk i = 2,……,n, lakukan 3. Selama
∉
lakukan:
=
1,
II-7
a. Pilih titik b. Untuk setiap ganti
∈
−
∈
dengan
terkecil. Set
dengan −
>
lakukan : jika +
4. Untuk = 1,2, … , jika
∈
( , ).
maka
∗
1,
Menurut algoritma di atas, lintasan dari titik
=
ke
= .
∪{
+
}
( , ) maka
melalui titik-titik
.
dalam L, dan jumlah bobot lintasan terkecilnya adalah
Sebagai contoh untuk lintasan terpendek menggunakan algoritma dijkstra adalah :
3 4 2 3
5
Gambar 2.7 Contoh Graf Berarah dari
Berdasarkan dari Gambar 2.7 di atas maka akan dicari lintasan terpendek ke .
Penyelesain :
Matriks W untuk menyatakan graf pada Gambar 6 adalah sebagai berikut:
1.
2.
− 4 3 ∞ ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ −
L = {} dan =
,
,
Untuk = 2 : Untuk = 3 :
3.
Untuk = 4 : =
∉
.
2 =
1,2 = 4.
4 =
1,4 = ∞.
3 =
1,3 = 3.
sehingga langkah 3(a) dan 3(b) di lakukan.
3(a) : D(k) terkecil adalah D(3) sehingga L = L ∪
= {} ∪
3
= { 3 }.
=
.
II-8
∈ V–L=
3(b) :
,
,
−
= { ,
{ , } akan diperiksa apakah
>
Untuk j = 2 :
}. Sehingga untuk = +
, .
D(j) = D(2) = 4 ; D(k) + w(k, j) = D(3) + w(3, 2) = 3 + 2 = 5. Oleh karna D(2) < D(3) + W(3, 2), maka D(2) = 4 (nilainya tetap). Untuk j = 4 D(j) = D(4) = ∞ ; D(k) + w(k, j) = D(3) + w(3, 4) = 3 + 5 = 8. Oleh karna D(4) >D(3) + W(3, 4), maka D(4) = 8 (nilainya berubah).
Langkah selanjutnya adalah kembali ke langkah 3. Karena 3(a) dan 3(b) dilakukan. 3(a) : −
= { 2,
3, 4}
−
3
= { ,
}.
=
.
∉
maka langkah
Di antara D(k) ( dengan k = 2, 4) hasil iterasi langkah 3(b), D(k) yang terkecil adalah D(2) sehingga Sekarang, L = L ∪ ∈ V–L=
3(b) :
−
=
= { 3} ∪ ,
= { } akan diperiksa apakah
Untuk j = 4 :
,
2
−
= { 3,
>
,
2 }.
= {
+
}. Sehingga untuk
, .
= D(4) = 8; D(k) + w(k, j) = D(2) + w(2, 4) = 4 + 3 = 7. Oleh karna
D(4) < D(2) + w(2, 4), maka D(4) = 7 (nilainya berubah).
Langkah selanjutnya adalah kembali ke langkah 3. Karena iterasi berhenti. 4.
∈
=
∗ 1.2 = ∗ 1.3 =
∗ 1.4 =
,
,
,
2 = 4.
∗ 1.
=
=
∈
maka
.
3 = 3.
4 = 7.
II-9
Tabel 3.1. Hasil Iterasi Lintasan Terpendek pada Algoritma Dijkstra Indeks k sehingga
L
D(2)
D(3)
D(4)
w(1, 2) = 4
w(1,3) = 3
w(1,4) = ∞
V-L
D(k) minimum { ,
∅
-
{ }
3
,
{ ,
}.
Min (D(2),
}.
D(3)+w(3,2)
Min (D(4), 3 (tetap)
D(3)+w(3,4)
= Min (4,
= Min (∞,
3+2) = 4
3+5) = 8 Min (D(4),
{ ,
2
}
{ }
4 (tetap)
3 (tetap)
D(2)+w(2,4) = Min (8, 4+3) = 7
{ ,
4
,
}.
Panjang lintasan terpendek dari baca mundur sebagai berikut :
adalah 7 dengan jalur yang di
Pada titik terakhir ( ) diperoleh penurunan jarak pada kolom D(4) dari 8 ke 7, itu berarti titik yang terpilih pada baris tersebut ( →
) adalah jalur lintasan ( jalur
).
Pada kolom D(2) tidak terjadi penurunan jarak (dari 4 tetap 4), itu berarti bahwa titik pada indeks k = 3 ( ) bukan jalur lintasan. Jadi, lintasan terpendeknya adalah 2.11
→
→
dengan total panjang = 7.
Algoritma Floyd
II-10
Algoritma Floyd adalah algoritma untuk menghitung lintasan terpendek pada graf berarah. Algoritma Floyd menggunakan dua matrik yaitu matrik
dan
matrik . Matrik
merupakan matrik untuk melihat bobot akhir pada lintasan,
sedangkan matrik
merupakan matrik untuk melihat lintasan yang terpilih.
Matriks ini merepresentasikan bobot dari keseluruhan sisi yang ada pada graf ( , ) dengan
,
dimana i adalah titik awal dan j adalah titik tujuan.
Diberikan beberapa notasi yang akan digunakan dalam algoritma Floyd
yaitu: = jarak dari titik i ke titik j. = suatu titik yang dilewati oleh suatu lintasan dari i ke j yang mempunyai jarak
.
= matriks jarak. = matriks urutan. ℜ
= rangking fuzzy.
1.
Didefinisikan matriks
Langkah-langkah algoritma Floyd adalah sebagai berikut: dan . = ∞.
Jika i dan j tidak terhubung langsung, definisikan 2.
Tetapkan k = 1. a.
Didefinisikan baris k dan kolom k sebagai baris dan kolom pivot.
b.
Untuk setiap , maka
c.
+
pada matriks >
Jika matriks maka matriks
d.
dalam
, maka
, jika
+
di ganti dengan
pada matriks
<
+
tetap.
≠
berubah
dengan k.
Jika k = n, iterasi berhenti.jika k < n, definisikan langkah 1.
, ≠
. Tetapi jika
tetap maka matriks tetap, tetapi jika matriks diubah dengan mengganti
, ≠
=
+ 1, kembali ke
Sebagai contoh untuk lintasan terpendek pada algoritma floyd adalah sebagai berikut : Dengan graf yang sama, maka akan diselesaikan masalah lintasan terpendek dengan algoritma Floyd.
II-11
Penyelesain : Iterasi 1 : 1. Didefinisikan matriks D dan matriks . − 4 3 ∞ ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ − 2.
− = 1 1 1
dan
= 1.
a. Definisikan baris 1 dan kolom 1 dari matrik
2 − 2 2
3 3 − 3
4 4 4 −
sebagai baris dan kolom
pivot. − 4 3 ∞ ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ − b. Untuk setiap
dan
pada matriks , elemen
− = 1 1 1 <
2 − 2 2
+
3 3 − 3
4 4 4 −
maka tidak
ada elemen yang diubah untuk matrik . Maka matriks D tetap pada iterasi berikutnya. c. Tidak ada elemen matriks
yang di ubah dari matrik
mengikuti perubahan pada matriks
Karena perubahan
, maka matrik
tetap
pada iterasi berikutnya. d. Karena k < 4 maka untuk iterasi berikutnya didefinisikan k = 2 dan kembali ke langkah 1.
Iterasi 2 : 1. Didefinisikan matriks
2.
dan matriks
− 4 3 ∞ ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ −
= 2
.
dan
a. Definisikan baris 2 dan kolom 2 dari matrik
− = 1 1 1
2 − 2 2
3 3 − 3
4 4 4 −
sebagai baris dan kolom
pivot.
II-12
− 4 3 ∞ ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ − b. Untuk setiap
− 1 dan = 1 1
pada matriks , elemen
maka elemen
pada matrik
diperoleh matriks
pada iterasi berikutnya.
c. Untuk elemen matriks
matriks
>
+
2 − 2 2
3 3 − 3
4 4 4 −
,∞> 4+ 3
di ubah menjadi 7. Sehingga
di ubah menjadi 2 sehingga di peroleh
pada iterasi berikutnya.
d. Karena k < 4 maka untuk iterasi berikutnya didefinisikan k = 3 dan kembali ke langkah 1.
Iterasi 3 : 1.
2.
Didefinisikan matriks
dan matriks
.
− 4 3 7 ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ −
− 1 dan = 1 1
= 3
a. Definisikan baris 3 dan kolom 3 dari matrik
2 − 2 2
3 3 − 3
2 4 4 −
sebagai baris dan kolom
pivot. − 4 3 7 ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ − a. Untuk setiap
− 1 dan = 1 1
pada matriks , elemen
ada elemen yang diubah untuk matrik . b. Tidak ada elemen
<
+
2 − 2 2
3 3 − 3
2 4 4 −
maka tidak
yang di ubah dari matrik .
c. Karena k < 4 maka untuk iterasi berikutnya didefinisikan k = 4 dan kembali ke langkah 1.
Iterasi 4 : 1. Didefinisikan matriks
dan matriks
.
II-13
2.
− 4 3 7 ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ −
− 1 dan = 1 1
= 4
a. Definisikan baris 4 dan kolom 4 dari matriks
2 − 2 2
3 3 − 3
2 4 4 −
sebagai baris dan
kolom pivot. − 4 3 7 ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ − b. Untuk setiap
− 1 dan = 1 1
pada matriks , elemen
ada elemen yang diubah. c. Tidak ada elemen
<
2 − 2 2
+
3 3 − 3
2 4 4 −
maka tidak
yang di ubah dari matrik .
d. Karena k = n maka iterasi berhenti. − 4 3 7 ∞ − ∞ 3 = ∞ 2 − 5 ∞ ∞ ∞ −
− 1 dan = 1 1
2 − 2 2
3 3 − 3
2 4 4 −
Dari iterasi 4 di dapat hasil akhir untuk lintasan terpendek dari titik 1 ke titik 4 adalah :
= 2
Jadi, lintasan terpendeknya adalah
= 2
→
= 3
→
dengan bobot adalah 7.
II-14
