Model Jaringan • • • • • • • • • • •
Sebuah jaringan terdiri dari sekelompok simpul (node) yang dihubungkan dengan busur (arc). Suatu busur dapat dialiri arus/diberikan bobot dalam jumlah tertentu Contoh: jaringan transportasi: simpul mewakili kota, busur mewakili jalan raya, arus/bobot mewakili jarak Umumnya, arus memiliki jumlah yang terbatas Sebuah busur dikatakan berarah apabila busur tersebut memungkinkan arus positif pada satu arah, dan nol pada arah sebaliknya Jaringan yang berarah adalah jaringan dengan semua busur yang berarah Jalur adalah urutan busur-busur yang menghubungkan 2 simpul Loop adalah jalur yang berakhir pada simpul semula Loop yang berarah adalah loop yang dibentuk oleh busur-busur yang berarah Jaringan yang terhubung adalah sebuah jaringan di mana setiap 2 simpul dihubungkan dengan suatu jalur Pohon adalah suatu jaringan terhubung yang tidak memiliki loop Dalam kuliah ini dibahas 3 jenis model jaringan yaitu: 1. Masalah pohon rentangan minimal 2. Masalah rute terpendek 3. Masalah arus maksimal
Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
Masalah Pohon Perentangan Minimal (Minimum Spanning Tree) Sebuah jaringan TV Kabel sedang merencanakan pembangunan jaringan kabel dari stasiun pusat di kota (1) menuju ke lima kota lainnya, menurut diagram jarak di bawah ini. Tentukan jaringan kabel yang harus dibangun untuk menghubungkan keenam kota tersebut, dengan syarat panjang kabel yang digunakan seminimal mungkin
Algoritma: 1. Tentukan simpul awal jaringan. Hubungkan ke simpul yang terdekat 2. Kategorikan simpul yang sudah terhubung ke dalam himpunan (sebut saja) C, dan simpul yang belum terhubung ke dalam himpunan C’ 3. Pilih sebuah simpul dari himpunan C’ yang memiliki jarak terdekat (bobot terkecil) terhadap salah satu anggota himpunan C 4. Pindahkan simpul yang terpilih tersebut ke himpunan C 5. Kembali ke langkah 3, sampai himpunan C’ kosong
Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
Iterasi C C' 1 {1,2} {3,4,5,6} 2 {1,2,5} {3,4,6} 3 {1,2,4,5} {3,6} 4 {1,2,4,5,6} {3} 5 {1,2,3,4,5,6}
Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
Masalah Rute Terdekat (Jalur Terpendek) Seseorang akan bepergian dari kota u ke kota v. Diberikan diagram jarak antarkota berikut (dalam puluhan mil) : 4
x 4
3 6
u
a 2
y
z
b
3
v
1
4
2
3
2
5
3 c
Rute manakah yang harus ia pilih agar jarak tempuhnya minimal?
Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
Algoritma Jalur Terpendek 1. Buat tabel jarak u ux = 4 uy = 6 uz = 2
x xy = 3 xa = 4
y yb = 2 yc = 1
z zy = 2 zc = 5
a ab = 2 av = 3
b bv = 3
c cv = 3
v
2. Mulai dari kolom u. Beri harga 0. Pada kolom ini pilih jarak/busur terkecil/terdekat, yaitu uz=2. Lingkari uz. Semua busur yang berakhir di z dihapus (dalam hal ini tidak ada). Beri nilai 2 untuk kolom z u (0) ux = 4 uy = 6 uz = 2
x xy = 3 xa = 4
y yb = 2 yc = 1
z (2) zy = 2 zc = 5
a ab = 2 av = 3
b bv = 3
c cv = 3
v
3. Dari kolom yang sudah diberi nilai, cari busur lain yang belum dilingkari, yang nilainya paling kecil jika dijumlahkan dengan nilai kolom. Dalam hal ini ada 2 pilihan yaitu ux=4 dan zy=2 (lingkari keduanya). Beri nilai kolom x=0+4=4 dan y=2+2=4. Hapus semua busur yang menuju x dan y u (0) ux = 4 uy = 6 uz = 2
x (4) xy = 3 xa = 4
y (4) yb = 2 yc = 1
z (2) zy = 2 zc = 5
a ab = 2 av = 3
b bv = 3
c cv = 3
v
4. Ulangi langkah ke 3 seterusnya sampai semua kolom memiliki nilai. Berikut adalah posisi posisi akhir tabel setelah mengulangi langkah ke 3 beberapa kali: u (0) ux = 4 uy = 6 uz = 2
x (4) xy = 3 xa = 4
y (4) yb = 2 yc = 1
z (2) zy = 2 zc = 5
a (8) ab = 2 av = 3
b (6) bv = 3
c(5) cv = 3
Setelah itu lakukan penelusuran terbalik mulai dari simpul akhir (v), sehingga diperoleh: v c y z u Ini adalah rute terpendek dari u ke v dengan jarak = 8
Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
v(8)
Masalah Arus Maksimal • • • •
Tujuan: mengatur alur/rute perjalanan objek (produk, orang, dsb) dari tempat asal ke tempat tujuan sedemikian sehingga volume objek yang dialirkan adalah maksimum, berdasarkan kondisi jaringan yang tersedia.. Dalam model jaringan, tempat digambarkan sebagai simpul, dan jalan digambarkan sebagai busur. Simpul asal disebut sumber, dan simpul tujuan disebut muara. Antara sumber dan muara terdapat simpul lain yang disebut simpul perantara. Diasumsikan bahwa simpul perantara tidak dapat menjadi tempat menyimpan objek (hanya untuk tempat transit). Contoh: tentukan aliran maksimal dari a ke d!
Algoritma: 1. Tentukan satu jalur dari sumber ke muara yang dapat membawa aliran barang yang positif. Jika tidak ada, langsung ke langkah 4. Tentukan aliran maksimum jalur tersebut Pada contoh dapat dipilih jalur ad, dengan aliran maksimum 8 2. Perbaharui data-data pada jaringan. Kapasitas busur pengirim dikurangi dengan aliran maksimum yang melalui busur tersebut, dan kapasitas busur yang berlawanan arah ditambah dengan aliran maksimum yang melalui busur tersebut. Pada contoh, kapasitas busur ad menjadi 8 – 8 = 0, dan kapasitas busur da menjadi 0 + 8 = 8. 3. Kembali ke langkah 1 4. Aliran maksimum adalah akumulasi barang yang diterima di muara melalui masing-masing rute yang ada. Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
Langkah penyelesaian:
Jalur ad, aliran maksimal = 8
Jalur acbd, aliran maksimal = 4
Sumber: Pengantar Teori dan Algoritma Graf, Buku Paket UG
Ahmad Sabri, MSi, Riset Operasional 2, Universitas Gunadarma
