mata kuliah penelitian operasional ii analisis jaringan · (jaringan pipa batu bara ... setiap dua...
TRANSCRIPT
Mata Kuliah Penelitian Operasional IIOPERATIONS RESEARCH
AN INTRODUCTION SEVENTH EDITION
BYHAMDY 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 menghubungkansumbernya di Teluk Mexico dengan sebuah titik pengiriman di pantai dengantujuan meminimumkan biaya pembuatan sambungan pipa tersebut
• Penentuan rute terdekat yang menghubungkan dua kota dalam sebuah jaringanjalan raya yang ada.
• Penentuan kapasitas tahunan maksimum dalam jumlah ton jaringan pipapenyaluran batu bara yang menghubungkan tambang batu bara di Wyomingdengan pembangkit tenaga listrik di Houston. (Jaringan pipa batu baramengirimkan batu bara denganmemompa air melalui pipa yang dirancang khususdan menghubungakan tambang baru bara dan tujuan yang diinginkan).
• Penentuan jadwal arus berbiaya minimum dari ladang minyak ke pengilanganminyak dan akhirnya ke pusat-pusat distribusi. Minyak mentah dan produk-produkbensin dapat dikirimkan lewat tanker, pipa, dan/atau truk. Di samping ketersediaanpenawaran maksimum di ladang minyak dan persyaratan permintaan minimum dipusat distribusi, batasan atas kapasitas pengilangan dan cara transportasi harusdipertimbangkan.
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
1 3
4
5
2
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)}
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
1 3
2
1 3
4
5
2
Pohon (Tree) : jaringan yang melibatkan sebagian node.
Pohon Perentangan (SpanningTree) : Pohon yangmenghubungkan semua nodedari jaringan tanpa adanyasiklus.
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 = KotaBusur = jalan
Algoritma Pohon Perentangan Minimal (Minimal Spanning Tree Algorithm)
- Tentukan himpunan node dari jaringanN = {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 TVCable Company sedang dalam proses dalammenyediakan jaringan jasa kepada limawilayah perumahan yang baru dibangun.Kebutuhan perusahaan adalah menentukanhubungan-hubungan yang dapat meminimasikonsumsi kabel dengan jaminan bahwa semuawilayah dapat terhubung (langsung atau tidaklangsung)
Algoritma Rute Terdekat (Shortest-route Algorithm)
• Algoritma Asiklis• Algoritma Siklis (Dijkstra)• Algoritma Floyd
KeteranganBaik algoritma asiklik maupun siklis (Dijkstra)merupakan desain algoritma yang menentukan ruteterpendek antara node sumber dan node tujuan.Sedangkan algoritma Floyd merupakan algoritmageneric karena dapat menentukan rute terpendek padasetiap 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
[2,1] [7,2]
5
6
2 11 8
10
[0,-] [13,5]
7
3
4 9
1
[4,1] [5,3]
1
2
3 6
4
5
7
KeteranganNode 1 (node awal)Node 7 (node akhir)Tidak mempunyai loop
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]
4
u4 = min { u1 + d14, u2+d24,u3+d34}
[7,3]u4 = min { 0+10,2+11,4+3}
U4 = min {10, 13, 7} = 7, dari 3
5u5 = min {u2+d25, u4+d45}
[7,2]u5 = min {2+5,7+8} =7, dari 2
6u6 = min { u3 +d36, u4+d46}
[5,3]u6 = min {4+1,7+7} = 5, dari 3
7u7 = min {u5+d57,u6 + d67}
[13,5]u7 = min {7+6,5+9} =13, dari 5
Algoritma Rute Terdekat- Asiklis
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 Terdekat-Siklis (Dijkstra)
• Algoritma Siklis digunakan ketika jaringan mencakup loop yang terarah
• Pada algoritma siklis terdapat evaluasi ulang terhadap suatu node
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 0Tentukan label permanen pada node 1, [0,-]
1
2
3
4
5
100
30
20
15
10
50
600[0,-]
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 1Node 2 dan 3 dapat ditempuh dari node 1 (permanen) menjadi dua label temporer
[100,1] dan [30,1].
1
2
3
4
5
100
30
20
15
10
50
600[0,-]
[30,1](1)
[100,1](1)
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 1
• u3 = 30, merupakan jarak yang lebih kecil, sehingga node 3 dengan label [30,1]berubah menjadi permanen untuk iterasi berikutnya.
Node Label Status
1 [0,-] Permanen
2 [100,1] Temporer
3 [30,1] Temporer
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 2Node 4 dan 5 dapat ditempuh dari node 3
1
2
3
4
5
100
30
20
15
10
50
60[0,-](1)
[30,1](1)
[100,1](1)
[40,3](2)
[90,3](2)
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 2
• u4 = 40, berubah menjadi permanen untuk iterasi berikutnya.
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
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 3Node 2 dan 5 dapat ditempuh dari node 4
1
2
3
4
5
100
30
20
15
10
50
600[0,-](1)
[30,1](1)
[100,1](1)
[40,3](2)
[90,3](2)
[90,4](3)
[55,4](2)
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 3
• 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.
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
Algoritma Dijkstra (Siklik) –Contoh Kasus
• Iterasi 4
hanya node 3 yang dapat dicapai melalui node 2.tetapi node 3 telah memiliki label permanen dantidak bisa diberikan label baru. Daftar label tetapsama dengan iterasi 3 kecuali label node 2 yangmenjadi 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
Gagasan algoritma : mencapai k dari i melalui j dengan jarak terpendek jika
i
j
k
dij
dik
djk
keadaan optimal adalah mengganti rute
i→ k dengan i → j → k