MODEL ARUS JARINGAN
DEFINISI • • • • • • • •
Jaringan (network) = (N, A); N=node, A=arc = sisi=busur. Arc (sisi) terarah mempunyai arah. Jaringan terarah mempunyai semua sisi yang terarah. Path (lintasan) = sekumpulan arc yang berbeda yang menghubungkan dua node melalui node yang lain tanpa memperhatikan arah aliran sisi (arc). Path yang menghubungan node dengan dirinya = cycle (siklus) Network terhubung = setiap dua node berbeda dihubungkan oleh paling sedikit satu path. Tree=jaringan terhubung yg merupakan subset dari jaringan tanpa cycle (sikluc) Spanning tree= tree yg menghubungkan
1
3
2 Tree
Pengertian Jaringan
Jaringan adalah suatu susunan garis edar (path) yang terhubung pada berbagai titik, dimana satu atau beberapa barang bergerak dari satu titik ke titik lain (Taylor, 2005) Contoh : sistem jalan tol, jaringan telepon, jaringan rel kereta api, jaringan televisi, dsb.
Pada dasarnya model arus jaringan juga merupakan pengembangan dari model transportasi atau distribusi yang berkaitan dengan pemindahan / pengiriman komoditas dari suatu sumber ke suatu tujuan dengan ongkos transportasi minimum.
Pada perkembangannya ternyata model transportasi ini dapat juga digambarkan dan diselesaikan dalam suatu bentuk jaringan
Jaringan digambarkan sebagai suatu diagram yang terdiri dari 2 komponen, yaitu: simpul (nodes), biasanya digambarkan dalam bentuk lingkaran cabang (branches), dalam bentuk garis yang menghubungkan simpul-simpul tersebut. Simpul (nodes) melambangkan titik-titik persimpangan atau perhentian. Pada umumnya menyatakan lokasi, kota, stasiun, dsb. Cabang (branches) melambangkan arus dari satu titik ke titik yang lain dalam jaringan tersebut. Pada umumnya menyatakan waktu tempuh, jarak, panjang, dsb.
Topik pembicaraan dibatasi pada 3 macam persoalan, yaitu: 1)
2)
3)
Masalah Route) Masalah (Minimal Masalah Flow)
Rute
Terpendek
Rentang
(Shortest
Pohon Minimum Spanning Tree) Aliran Maksimum (Maximal
1. Masalah Rute Terpendek (Shortest Route) : Masalah rute terpendek berguna untuk menentukan jarak tersingkat antara titik awal (sumber) dengan beberapa titik tujuan
Langkah-langkah penyelesaian adalah : 1.
2.
3.
4.
5.
Pilihlah simpul dengan rute langsung tersingkat dari titik awal. Buatlah suatu setelan permanen (Permanent Set) dengan titik awal dan simpul terpilih dalam langkah 1. Permanent Set digunakan untuk menandakan bahwa telah ditemukan rute tersingkat ke simpul-simpul ini. Tentukan seluruh simpul yang berhubungan langsung dengan simpul-simpul setelan permanen. Pilihlah simpul dengan rute (cabang) terpendek dari kumpulan simpul-simpul yang berhubungan langsung dengan simpul-simpul setelan permanen. Ulangi langkah 3 dan 4 sampai seluruh simpul bergabung dengan setelan permanen.
Contoh :
Seseorang yang tinggal di Bogor dan bekerja di Jakarta dapat melalui berbagai route seperti tergambar pada jaringan di bawah. Angka menunjukkan waktu yang dibutuhkan untuk menempuh route tersebut (dalam menit). 4 32
P D
11
28 B
18
C
17
17
J
12 Bogor
O
32 10
Jakarta
Route dengan waktu tempuh terpendek { BD, DP, PJ }.
Contoh : 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 2
y
z
3
v
1
4
2
b
3
5
c
3
Rute manakah yang harus ia pilih agar jarak tempuhnya minimal?
JAWABAN: Setelah itu lakukan penelusuran terbalik mulai dari simpul akhir (v), sehingga diperoleh: v c y z u = 10
Latihan Tentukan minimal spanning tree dari jaringan berikut: SE 2000 1100
1300 1000
DE
CH
800
NY
2000 LA
200 2600 1400
780
DC
900 DA
1300
2. Masalah Rentang Pohon Minimum (Minimal Spanning Tree)
Masalah rentang pohon minimum sebenarnya serupa dengan masalah rute terpendek, dimana perbedaannya adalah:
Tujuan masalah rute terpendek adalah menentukan rute terpendek antara titik awal dan simpul tujuan dalam jaringan tersebut. Tujuan dari masalah rentang pohon minimum adalah menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang dapat diminimumkan.
Jaringan yang dihasilkan merentangkan (menghubungkan) semua titik dalam jaringan tersebut pada total jarak (panjang) minimum.
Masalah Rentang Pohon Minimum (Minimal Spanning Tree) Definisi Spanning tree : Untuk suatu jaringan dengan n node, spanning tree adalah sekumpulan dari n-1 busur (arc) yang menghubungkan semua node dalam jaringan dan tidak mengandung loop Definisi Minimum Spanning Tree: Minimum spanning tree adalah spanning tree dengan panjang minimum dalam suatu jaringan
Langkah-langkah penyelesaian adalah : 1. 2.
3.
4.
Pilihlah simpul awal manapun. Pilihlah simpul yang terdekat dengan simpul awal untuk bergabung dengan pohon rentang. Pilihlah simpul terdekat yang belum termasuk dalam pohon rentang. Ulangi langkah 3 sampai seluruh simpul telah bergabung dalam pohon rentang.
Gambaran 12 1
4
2
7 3
Perhatikan Contoh jaringan di samping. Terdapat 3 spanning tree, yaitu: 1. Arc (1,2) dan (2,3) 2. Arc (1,2) dan (1,3) 3. Arc (1,3) dan (2,3) Spanning tree ketiga adalah minimum spanning tree
Algoritma
Untuk menemukan spanning tree dapat digunakan algoritma berikut: Mulailah dengan memilih busur (arc) terkecil (terpendek) dan membuat himpunan arc yang terhubungkan Pada setiap iterasi tambahkan arc terkecil yang belum terpilih yang memiliki koneksi dengan himpunan yang telah terhubungkan (connected set), Algoritma selesai jika semua node telah terhubungkan dan terdapat n -1 arc yang masuk dalam himpunan arc yang terhubungkan(connected arc) 18
Midwest TV Company dalam proses menyediakan jaringan kabel ke lima wilayah pengembangan perumahan baru. Gambar di bawah adalah jaringan TV yang mungkin yang menghubungkan ke lima wilayah tersebut. Kabel diukur dalam mil yang ditunjukkan oleh setiap arc (sisi).
• N={1,2,3,4,5,6} • C1={1} (sebarang node juga dapat digunakan untuk memulai); C1={2,3,4,5,6}. • C2={1,2} dan C2={3,4,5,6}. Jaraknya = 1 • C3={1,2,5} dan C3={3,4,6}. 1 Jaraknya = 3 • C4={1,2,5,4} dan C4={3,6}. 1 Jaraknya = 4 • C5={1,2,5,4,6} dan C5={3}. Jaraknya = 3 • C6={1,2,5,4,6,3} dan C6={ }=. Jaraknya = 5 • Jadi kabel minimum (terpendek) yang diperlukan adalah 1+3+4+3+5=16 mil
2 3 mil 4
5 Alternate links
5
3 6 5 3 4 Minimal spanning tree
E
10
Contoh :
7
2
Berikut ini adalah jaringan yang mungkin dihubungkan oleh PT. TELKOMNUS antar beberapa kota, di mana angka yang tercantum pada cabang adalah total biaya dalam milyar rupiah.
B
4
5
10
1
A
8
1 D
C
F
3
4
7
G
3
Rentang Minimumnya adalah : B
A
F D
C
E
G
Contoh
Kota Vancouver berencana mengembangkan sistem transportasi kereta api baru. Sistem tersebut harus menghubungkan 8 pusatpusat perumahan dan komersial. Distrik Metropolitan Transit perlu memilih set garis yang akan menghubungkan semua pusat dengan total biaya minimum.
REPRESENTASI JARINGAN 3 Bagian Utara 34
Bagian Barat
Universitas
50 Pusat Bisnis 4
5
39
Loop
45
1
8
35 Pusat 2 Kota
41
6
Pusat Perbelanjaan
Bagian Timur
Biaya Total = $236 juta 7
Bagian Selatan 23
OPTIMAL SOLUTION NETWORK REPRESENTATION3 Bagian Utara
34
Universitas
50
5
Pusat Bisnis 39 4
Bagian Barat
45
1
8
35 Pusat 2 Kota
41
6
Pusat Perbelanjaan
Bagian Timur
Biaya Total= $236 juta 7
Bagian Selatan 24
Topik pembicaraan dibatasi pada 3 macam persoalan, yaitu: 1)
2)
3)
Masalah Rute Terpendek (Shortest Route) Masalah Rentang Pohon Minimum (Minimal Spanning Tree) Masalah Aliran Maksimum (Maximal Flow)
Masalah Arus Maksimum (Maximal Flow):
Masalah aliran maksimum merupakan masalah jaringan dimana cabangcabang jaringan tersebut memiliki kapasitas arus yang terbatas. Tujuan dari masalah arus maksimum adalah memaksimumkan total jumlah arus dari satu titik awal ke satu tujuan
Masalah arus maksimum dapat mencakup: • arus (aliran) air, gas, atau minyak melalui suatu jaringan pipa, • arus formulir melalui suatu sistem pemrosesan dalam kantor pemerintah, • arus lalu lintas melalui jaringan jalan raya, • arus produk melalui suatu sistem lini produksi, • dll. Dalam kondisi tersebut, pengambil keputusan ingin menentukan arus maksimum yang dapat diperoleh melalui sistem tersebut.
Langkah-langkah penyelesaian adalah : 1. Pilihlah secara arbitrer (sembarang) garis edar dalam jaringan tersebut dari titik awal ke titik tujuan. 2. Sesuaikan kapasitas pada setiap simpul dengan mengurangkan arus maksimal untuk garis edar yang dipilih pada langkah 1. 3. Tambahkan arus maksimal sepanjang garis edar ke arus berlawanan arah pada setiap simpul. 4. Ulangi langkah 1, 2, dan 3 sampai tidak ada lagi garis edar dengan kapasitas arus yang tersedia.
Contoh : The Scott Tractor Company mengirim bagianbagian traktor dari Omaha ke St Louis dengan kereta api. Namun, kontrak membatasi jumlah gerbong kereta yang dapat dipastikan oleh perusahaan pada setiap cabang selama satu minggu.
Definisi dan Contoh Permasalahan
• Masalah: Maksimumkan jumlah arus barang dari sebuah titik awal ke sebuah tujuan
Algoritma masalah aliran maksimum adalah sebagai berikut:
Algoritma masalah aliran maksimum adalah sebagai berikut: a. Identifikasi (kenali) augmenting path yang mempunyai kapasitas sisa positif. b. Sebut kapasitas sisa c* dari augmenting path, yaitu minimum dari kapasitas setiap jalur (arc) yang dilalui. c. Kurangkan dengan c* pada setiap awal jalur kapasitas sisa, dan tambahkan c* pada arah yang berlawanan. Selanjutnya kembali ke langkah a.
Pendekatan Solusi • Secara arbitrer, pilih garis edar/jalur manapun sepanjang jaringan dari titik awal ke tujuan dan kirim sebanyak mungkin yang bisa Augmenting path 1 2 5 6
min {6,8,4} =4
Pendekatan Solusi • Hitung ulang arus cabang pada kedua arah dan kemudian pilih jalur layak yang lain secara arbitrer dan tentukan arus maksimum sepanjang jalur sampai arus tidak mungkin lagi Augmenting path 1 4 6
min {4,5} =4
Pendekatan Solusi • Lanjutkan
Augmenting path 1 3 6
min {7,6} =6
Pendekatan Solusi • Solusi optimal
Augmenting path 1 3 4 6
min {1,2,,1} =1
Contoh :
8
0 10
A Awal
Tentukan total arus maksimum bahan yang dapat dikirim dari titik awal ke tujuan melalui lintasan sbb.
0
4
4
B 5
7 0
D 0
Tujuan
5 10
C
Jawab : 0
8 3
A (-22)
7
B
0
2
0 7
D 10 (+22)
8 C
8
0
Permasalahan yang muncul yaitu: 1. Lewat jalur mana dari O menuju ke T sehingga diperoleh jarak terpendek, berapa jaraknya. 2. Buatlah jaringan air yang menghubungkan semua tempat peristirahatan agar panjang pipa yang digunakan minimum.
Permasalahan yang muncul yaitu: 1. Buatlah jalur kereta, agar banyaknya lintasan maksimum.
