Mata Kuliah Penelitian Operasional II OPERATIONS RESEARCH AN INTRODUCTION SEVENTH EDITION BY HAMDY A. TAHA
BAB 6
Analisis Jaringan Dipresentasikan oleh: Herman R. Suwarman, S.Si
Pendahuluan- Ilustrasi Situasi Aplikasi Analisis Jaringan • •
•
•
Rancangan sambungan pipa gas alam lepas pantai yang menghubungkan sumbernya di Teluk Mexico dengan sebuah titik pengiriman di pantai dengan tujuan meminimumkan biaya pembuatan sambungan pipa tersebut Penentuan rute terdekat yang menghubungkan dua kota dalam sebuah jaringan jalan raya yang ada. Penentuan kapasitas tahunan maksimum dalam jumlah ton jaringan pipa penyaluran batu bara yang menghubungkan tambang batu bara di Wyoming dengan pembangkit tenaga listrik di Houston. (Jaringan pipa batu bara mengirimkan batu bara denganmemompa air melalui pipa yang dirancang khusus dan menghubungakan tambang baru bara dan tujuan yang diinginkan). Penentuan jadwal arus berbiaya minimum dari ladang minyak ke pengilangan minyak dan akhirnya ke pusat-pusat distribusi. Minyak mentah dan produk-produk bensin dapat dikirimkan lewat tanker, pipa, dan/atau truk. Di samping ketersediaan penawaran maksimum di ladang minyak dan persyaratan permintaan minimum di pusat distribusi, batasan atas kapasitas pengilangan dan cara transportasi harus dipertimbangkan.
Algoritma Optimisasi Jaringan • Model Pohon Perentangan Minimal (Minimal spanning Tree) • Algoritma Rute Terdekat (Shortest-route Algorithm) • Algoritma Arus Maksimum (Maximum Flow Algorithm). • Algoritma Jaringan Berkapasitas Biaya Minimum (Minimum-cost capacitated network algorithm) • Algoritma Jalur Kritis (Critical Path Algorithm)
Definisi Jaringan • Sebuah jaringan (network) merupakan sekumpulan node yang dihubungkan oleh busur (arc) atau cabang (branch).
Definisi Jaringan G = (N,A) N = { 1,2,3,4,5} A = {(1,2),(1,3),(2,3),(2,5),(3,4),(3,5),(4,2),(4,5)}
5
3
1
2
4
Definisi Jaringan • Busur (Arc) : dikatakan berorientasi (oriented) atau berarah (directed) jika busur tersebut memungkinkan arus positif dalam satu arah dan arus nol dalam arah yang berlawanan. • Jaringan berarah: jaringan semua busur berarah.
Definisi Jaringan • Jalur (path) merupakan urutan busur-busur tertentu yang menghubungkan dua node tanpa bergantung pada orientasi busur. • Siklus (cycle) : jalur (path) yang membentuk sebuah loop yaitu jika jalur tersebut menghubungkan sebuah node dengan dirinya sendiri. • Jaringan yang berhubungan (connected network) setiap dua node tertentu yang terhubung sedikitnya oleh sebuah jalur (path)
Definisi Jaringan Pohon (Tree) : jaringan yang melibatkan sebagian node.
3
1
2
5
3
1
2
4
Pohon Perentangan (Spanning Tree) : Pohon yang menghubungkan semua node dari jaringan tanpa adanya siklus.
Algoritma Pohon Perentangan Minimal (Minimal Spanning Tree Algorithm) • Contoh aplikasi : pembangunan aspal yang menghubungkan beberapa kota. Jalan antara dua kota bisa jadi melalui satu atau lebih kota-kota yang lainnya. Desain ekonomis yang berdasarkan keterbatasan anggaran membutuhkan langkah minimasi jumlah total jarak (km) jalan yang akan diaspal yang memungkinkan hubungan lalu lintas secara langsung atau tidak langsung di antara kota-kota yang berbeda. Node = Kota Busur = jalan
Algoritma Pohon Perentangan Minimal (Minimal Spanning Tree Algorithm) - Tentukan himpunan node dari jaringan N = {1,2,......,n} - Definisikan = himpunan node yang secara permanen terhubung pada iterasi k
= himpunan node yang belum/akan terhubung secara permanen
Contoh Kasus Minimal Spanning Tree Algorithm Sebuah perusahaan TV kabel Midwest TV Cable Company sedang dalam proses dalam menyediakan jaringan jasa kepada lima wilayah perumahan yang baru dibangun. Kebutuhan perusahaan adalah menentukan hubungan-hubungan yang dapat meminimasi konsumsi kabel dengan jaminan bahwa semua wilayah dapat terhubung (langsung atau tidak langsung)
Jaringan Kabel Midwest TV Cable Company 3 5
2
1
9 6
4
1 3
5
8
5 7
10 4
6
Algoritma Rute Terdekat (Shortest-route Algorithm) • Algoritma Asiklis • Algoritma Siklis (Dijkstra) • Algoritma Floyd Keterangan Baik algoritma asiklik maupun siklis (Dijkstra) merupakan desain algoritma yang menentukan rute terpendek antara node sumber dan node tujuan. Sedangkan algoritma Floyd merupakan algoritma generic karena dapat menentukan rute terpendek pada setiap dua node pada suatu jaringan
Algoritma Rute Terdekat- Asiklis • Jaringan dikatakan bersifat asiklik jika tidak memiliki loop • Algoritma asiklik didasari oleh penggunaan perhitungan rekursif
Algoritma Rute Terdekat- Asiklis
Algoritma Rute Terdekat- Asiklis
Algoritma Rute Terdekat- Asiklis [2,1]
[7,2]
5
2
5 6
2
11
4
10 [0,-]
8
1
7 7
3 4
[4,1]
Keterangan Node 1 (node awal) Node 7 (node akhir) Tidak mempunyai loop
3
6
1
[5,3]
9
[13,5]
Algoritma Rute Terdekat- Asiklis Node j
Perhitungan uj
Label
1
u1 ≡ 0
[0,-]
2
u2 = u1 +d 12 = 0+2 = 2, dari 1
[2,1]
3
u3 = u1 +d13 = 0 + 4, dari 1
[4,1]
u4 = min { u1 + d14, u2+d24,u3+d34} 4
u4 = min { 0+10,2+11,4+3}
[7,3]
U4 = min {10, 13, 7} = 7, dari 3 5
u5 = min {u2+d25, u4+d45}
[7,2]
u5 = min {2+5,7+8} =7, dari 2 6
u6 = min { u3 +d36, u4+d46}
[5,3]
u6 = min {4+1,7+7} = 5, dari 3 7
u7 = min {u5+d57,u6 + d67} u7 = min {7+6,5+9} =13, dari 5
[13,5]
Algoritma Rute Terdekat- Asiklis Rute Optimum diperoleh dimulai dari node 7 dan menelusuri ke belakang dengan informasi label (7)→*13,5+ →(5) →*7,2+ →(2) →*2,1+ →1 Sehingga Rute optimum dari 1 hingga 7 adalah (1) → (2) → (5) → (7)
Algoritma Rute TerdekatSiklis (Dijkstra) • Algoritma Siklis digunakan ketika jaringan mencakup loop yang terarah • Pada algoritma siklis terdapat evaluasi ulang terhadap suatu node
Algoritma Dijkstra (Siklik) – Contoh Kasus 2
15
4 20
100
50 10
1
30 3
600
5
Algoritma Dijkstra (Siklik) – Contoh Kasus
• Iterasi 0
Tentukan label permanen pada node 1, [0,-]
2
15
4 20
100
50 10
[0,-]
1
30 3
600
5
Algoritma Dijkstra (Siklik) – Contoh Kasus
• Iterasi 1
Node 2 dan 3 dapat ditempuh dari node 1 (permanen) menjadi dua label temporer [100,1] dan [30,1].
[100,1](1)
2
15
4 20
100
50 10
[0,-]
1
30
[30,1](1)
3
600
5
Algoritma Dijkstra (Siklik) – Contoh Kasus • Iterasi 1 Node
Label
Status
1
[0,-]
Permanen
2
[100,1]
Temporer
3
[30,1]
Temporer
• u3 = 30, merupakan jarak yang lebih kecil, sehingga node 3 dengan label [30,1]berubah menjadi permanen untuk iterasi berikutnya.
Algoritma Dijkstra (Siklik) – Contoh Kasus
• Iterasi 2
Node 4 dan 5 dapat ditempuh dari node 3
[100,1](1)
2
15
[40,3](2) 4 20
100
50 10
[0,-](1)
1
30
[30,1](1)
3
[90,3](2) 60
5
Algoritma Dijkstra (Siklik) – Contoh Kasus • Iterasi 2 Node
Label
Status
1
[0,-]
Permanen
2
[100,1]
Temporer
3
[30,1]
Permanen
4
[30+10, 3] = [40,3]
Temporer
5
[30+60, 3] = [90,3]
Temporer
• u4 = 40, berubah menjadi permanen untuk iterasi berikutnya.
Algoritma Dijkstra (Siklik) – Contoh Kasus
• Iterasi 3
Node 2 dan 5 dapat ditempuh dari node 4
[55,4](2) [100,1](1)
2
15
[40,3](2) 4 20
100
50 10
[0,-](1)
1
30
[30,1](1)
3
600
[90,4](3) [90,3](2) 5
Algoritma Dijkstra (Siklik) – Contoh Kasus • Iterasi 3 Node
Label
Status
1
[0,-]
Permanen
2
[100,1]
Temporer
3
[30,1]
Permanen
4
[40,3]
Permanen
5
[90,3] atau [40+50, 4] = [90,4]
Temporer
• node 2 dengan label temporer [100,1] pada iterasi 2 berubah ke label [55,4] pada iterasi 3. hal ini menunjukkan rute terpendek telah ditemukan melalui node 4. node 2 menjadi permanen • Pada iterasi 3, node 5 mempunyai dua alternatif label dengan jarak yang sama.
Algoritma Dijkstra (Siklik) – Contoh Kasus • Iterasi 4 hanya node 3 yang dapat dicapai melalui node 2. tetapi node 3 telah memiliki label permanen dan tidak bisa diberikan label baru. Daftar label tetap sama dengan iterasi 3 kecuali label node 2 yang menjadi permanen. node 5 tidak mengarah pada node yang lainnya, sehingga dapat dirubah menjadi permanen, dengan demikian proses berhenti pada iterasi ini.
Algoritma Dijkstra (Siklik) – Contoh Kasus Jalur yang diperoleh dari informasi label (2)→ *55,4+ → (4) → *40,3+ →(3)-> *30,1+ → (1) Sehingga rute terpendek yang diinginkan 1 → 3 → 4 → 2 dengan total jarak 55 satuan jarak.
Algoritma Floyd • Sifatnya lebih general dibanding algoritma Dijkstra karena algoritma Floyd bisa menentukan rute terpendek untuk setiap dua node dalam suatu jaringan (network) • Algoritma Floyd merepresentasikan jaringan n-node sebagai sebuah matriks segiempat dengan n-baris dan n-kolom. • Entri (i, j) dari matriks merupakan jarak dari node i ke j
Algoritma Floyd- triple operation j
dij i
dik
djk k
Gagasan algoritma : mencapai k dari i melalui j dengan jarak terpendek jika keadaan optimal adalah mengganti rute
i→ k
dengan
i→j→k
Algoritma Floyd - Prosedur
Matriks Jarak
Algoritma Floyd - Prosedur
Matriks Sekuens
Algoritma Floyd - Prosedur
Algoritma Floyd - Prosedur
Implementasi Operasi Tripel Kolom j
Baris i
Baris Pivot k
Baris p
Kolom Pivot k
Kolom q
Implementasi Operasi Tripel
Algoritma Floyd – Contoh Kasus
