Model Jaringan Apa itu Model Jaringan? Perhatikan situasi berikut: 1. Disain jaringan pipa gas alam yang menghubungkan Arun Aceh dengan tangki penampungan Pertamina di salah satu kota dengan tujuan minimisasi biaya pemasangan pipa. 2. penentuan rute terpendek yang menghubungkan dua kota pada jaringan jalan yang sudah ada. 3. penentuan kapasitas maksimum tahunan (dalam ton) jaringan pipa coal slurry yang menghubungkan pertambangan dengan daerah pusat pembangkit energi. 4. penentuan jadwal aliran biaya-minimum dari pertambangan ke kilang pemurnia dan akhirnya ke pusat pendistribusian minyak.
Jaringan adalah himpunan simpul yang dihubungkan oleh garis atau kurva. Notasi standar jaringan G : G = (N,A). Predecessor adalah aktivitas yang mendahului suatu aktivitas tertentu. Successor adalah aktivitas yang mengikuti suatu aktivitas tertentu.
Algoritma Minimum Spanning Tree.
Asumsikan himpunan C sebagai himpunan simpul yang terhubung dan C sebagai himpunan simpul yang tidak terhubung.
Solusi Awal : C = { } dan C beranggotakan semua simpul.
Pilih sembarang simpul sebagai titik awal, maka C sekarang memiliki satu anggota dan C berkurang satu.
Hubungkan simpul itu dengan simpul terdekat. C bertambah satu dan C berkurang satu.
Hubungkan salah satu dari kedua simpul yang ada pada C dengan simpul terdekat, maka C bertambah satu lagi dan C berkurang satu.
Demikian seterusnya sampai C ={ } dan setiap simpul sudah terhubung.
Fitri Yulianti, SP. MSi. Gunadarma University
Contoh : Seorang petugas lapangan di The National Park Service setiap hari harus berkendaraan menggunakan mobil untuk memantau empat lokasi yang ada di taman. Setiap area harus dia kunjungi sekali, berangkat dari dan berakhir di pintu masuk. Area-area tersebut beserta jarak jalan yang sudah dibangun ( dalam mil) antara satu area dengan area lainnya ditunjukkan tabel di bawah.
Pintu
air terjun
Masuk Pintu Masuk
Batu
Sunset
The
Raksasa
Point
Meadow
-
7.1
19.5
19.1
25.7
Air Terjun
7.1
-
8.3
16.2
13.2
Batu Raksasa
19.5
8.3
-
18.1
5.2
Sunset Point
19.1
16.2
18.1
-
17.2
The Meadow
25.7
13.2
5.2
17.2
-
Penyelesaian : Jaringan dari kasus di atas adalah:
18.1
25.7 19.2
SP
PM 16.2
7.1 19.5
17.2
AT
13.2
8.3 5.2
BR
TM
Solusi Awal : C = { PM}
C = {AT, BR, SP, TM}
Iterasi 1 : C = {PM, AT}
C = {BR, SP, TM}, Total jarak = 7.1
Iterasi 2 : C = {PM, AT, BR}
Iterasi 3 : C = {PM, AT, BR, TM}
Iterasi 4 : C = {PM, AT, BR, TM, SP}
C ={SP, TM}, Total jarak = 15.4 C = { SP}, Total jarak = 20.6 C ={ }, Total jarak = 36.8
Fitri Yulianti, SP. MSi. Gunadarma University
Solusi Optimum : SP
PM 16.2
7.1
AT
8.3
5.2
BR
TM
Rute Terpendek. Acyclic Jaringan asiklik kalau tidak memuat loop. Algoritma :
Berikan uj = jarak terpendek dari simpul 1 ke simpul j, maka u 1 = 0.
Hitung uj untuk j=2, 3, ... secara rekursif dengan rumus berikut:
u j min u i d ij i
ui = jarak terpendek u i ke simpul yang langsung mendahului. dij = jarak antara simpul j dengan semua predecessor i. Label [d,n] dimana d adalah total jarak dari simpul awal dan n adalah predecessor langsung. Contoh :
5
2 2
5
11
8
10
1
6
4
7
7
9
3
4
3
1
Tentukan rute terpendek!!!
Fitri Yulianti, SP. MSi. Gunadarma University
6
Penyelesaian :
Simpul j Perhitungan uj
Label
1
u1 = 0
[0, -]
2
u2 = u 1 +d 12 = 0+2 = 2, dari 1
[2, 1]
3
u3 = u 1 +d 13 = 0+4 = 4, dari 1
[4, 1]
4
u4 = min {u1 +d14 , u2 +d24 , u3 +d34 }= min {0+10, 2+11, 4+3} = 7, dari 3
[7, 3]
5
u5 = min { u2 +d25 , u4 +d45 }= min {2+5, 7+8} = 7, dari 2
[7, 2]
6
u6 = min {u 3 +d 36 , u4 +d46 }= min {4+1, 7+1} = 5, dari 3
[5, 3]
7
u7 = min {u 5 +d 57 , u6 +d67 }= min {7+6, 5+9} = 13, dari 5
[13, 5]
Siklik Jaringan siklik memuat loop
Algoritma Dijkstra digunakan.
Algoritma siklik menggunakan 2 label, yaitu label sementara dan label permanen. 5
2 2
5
11 10
1
6
8
7 4
7
7
9
3
4
3
1
6
Iterasi 0 : simpul 1 diberi label pemanen [0, -]. Iterasi 1 : simpul 2 label sementara [2, 1], simpul 3 label sementara [4, 1] dan simpul 4 label sementara [10, 1]
min [2, 1] maka simpul 2 diberi label
permanen. Iterasi 2 : dari simpul 2 (simpul terakhir dengan label permanen)
simpul 3 dapat
label sementara lagi [2+7, 2], simpul 5 label sementara [2+5, 2].
Dari [4, 1],
[10, 1], [9, 2] dan [7, 2] minimum adalah [4, 1], maka [4, 1] menjadi label permanen.
Fitri Yulianti, SP. MSi. Gunadarma University
Iterasi 3 : label sementara berikutnya bertambah dengan [7, 3] simpul 4 dan [5, 3] simpul 6. Label [5, 3] menjadi permanen. Iterasi 4 : [14, 6] menjadi label sementara. Sehingga label sementara sekarang menjadi [10, 1], [7, 2], [9, 2], [7, 3], [14, 6]. Label [7, 3] menjadi label permanen. Iterasi 5 : label [15, 4] menjadi label sementara, sehingga label sementara menjadi [7, 2], [9, 2], [14, 6], [15, 4]. Label [7, 2] menjadi label permanen. Iterasi 6 : label sementara bertambah dengan [13, 5], sehingga menjadi [9, 2], [14, 6], [15, 4], [13, 5]
Iterasi Label sementara
Label permanen
Simpul
0.
-
[0, -]
1
1.
[2, 1], [4, 1], [10, 1]
[2, 1]
2
2.
[4, 1], [10, 1], [7, 2], [9, 2]
[4, 1]
3
3.
[10, 1], [7, 2], [9, 2], [7, 3], [5, 3]
[5, 3]
6
4.
[10, 1], [7, 2], [9, 2], [7, 3], [14, 6]
[7, 3]
4
5.
[7, 2], [9, 2], [14, 6], [15, 4]
[7, 2]
5
6.
[10, 1], [9, 2], [14, 6], [15, 4], [13, 5]
[13, 5]
7
Maka rute terpendek dari simpul 1 ke simpul 7 adalah : 1 dari simpul 1 menuju 6 adalah : 1
3
2
5
7,
6, demikian seterusnya.
Aliran Maksimum Digunakan untuk jaringan yang mempunyai kapasitas terbatas. Jaringan tidak berarah dalam arti aliran dimulai dari simpul sumber dan berakhir pada simpul tujuan. Arkus (i,j) mungkin mempunyai 2 arah kapasitas, dari i ke j atau dari j ke i.
Ide dasar algoritma : mencari jalur yang menghubungkan sumber dan tujuan sedemikian sehingga kapasitas arkus pada jalur adalah positif.
Contoh kasus : Fitri Yulianti, SP. MSi. Gunadarma University
Pendistribusian minyak dari 3 lokasi kilang pemurnian ke 2 terminal penampungan. Minyak dipompa dari kilang ke terminal menggunakan 3 pompa dengan bentuk jaringan seperti yang ditunjukkan gambar di bawah.
Kapasitas kilang pemurnian masing-
masingnya diperkirakan 200,000, 250,000 dan 300,000 bbl per hari. Permintaan pada kedua terminal diketahui 400,000 dan 450,000 bbl per hari.
Permintaan pada kedua
terminal yang tidak dapat dipenuhi dari ketiga kilang pemurnain akan disuplai dari tempat lain. Hitunglah kapasitas aliran setiap hari yang melalui masing-masing pompa tersebut!!
pemurnian
Stasiun pompa
terminal
20
1
10
4
7
10
10 50
2
50
20
20
6 20
30 30
5
8
15
3
Penyelesaian :
Iterasi –1: 1
(20, 0)
(10,0)
4 (10,0)
(10, 0) (50,0)
2
(50,0)
(20,0)
6
(20,0)
(30,0)
5 3
7
(30,0)
(15,0)
Fitri Yulianti, SP. MSi. Gunadarma University
C*=50 (20,0)
8
Iterasi-2: 1
(20, 0)
(10,0)
7
4 (10,0)
(10, 0)
(0,50)
C*=50+20 =70
(20,0) (0,50)
2
6
(20,0)
5 3
(20,0)
(30,0)
8
(30,0)
(15,0)
Iterasi-3: 1
(0, 20)
(10,0)
7
4 (10,0)
(10, 0) (0,50)
2
C*=70+20 =90
6 (20,0)
(30,0)
(20,0)
(10,20)
5 3
(0,50)
(0,20)
8
(15,0)
Iterasi-4: 1
(0, 20)
(10,0)
4 (10,0)
(10, 0) (0,50)
2
(0,50)
(0,20)
6
(0,20)
5 3
7
(10,20 ) (10,20)
(15,0)
Iterasi-5:
Fitri Yulianti, SP. MSi. Gunadarma University
(0,20)
C*=90+10 =100 8
(0, 20)
1
(10,0)
4 (10,0)
(10, 0) (0,50)
2
7 (0,50)
(0,20)
6
(0,20)
(10,20 ) (0,30)
5
(0,20)
C*=100+10 =110 8
(5,10)
3
Solusi optimal : 1
(0, 20) (0,10)
4
7
(10,0) (0,50)
(0, 10) (0,50)
2
(0,20)
6 (0,20)
(0,20)
(10,20 )
5 3
(0,30)
8
(5,10)
Jumlah yang dipompa dari pompa 4 adalah 30 bbl, pompa 5 sebesar 50 bbl dan pompa 6 sebesar 70 bbl. Aliran maksimum (c*) = 110 bbl.
Fitri Yulianti, SP. MSi. Gunadarma University
