model arus jaringan - gunadarma...
TRANSCRIPT
![Page 1: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/1.jpg)
MODEL ARUS JARINGAN
![Page 2: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/2.jpg)
• 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 tanpamemperhatikan arah aliran sisi (arc).
• Path yang menghubungan node dengan dirinya = cycle (siklus)
• Network terhubung = setiap dua nodeberbeda dihubungkan oleh paling sedikit satupath.
• Tree=jaringan terhubung yg merupakan subset darijaringan tanpa cycle (sikluc)
• Spanning tree= tree yg menghubungkan
DEFINISI
![Page 3: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/3.jpg)
1
2
Tree
3
![Page 4: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/4.jpg)
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.
![Page 5: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/5.jpg)
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
![Page 6: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/6.jpg)
Jaringan digambarkan sebagai suatu diagram yangterdiri dari 2 komponen, yaitu:
simpul (nodes), biasanya digambarkan dalambentuk lingkaran
cabang (branches), dalam bentuk garis yangmenghubungkan simpul-simpul tersebut.
Simpul (nodes) melambangkan titik-titikpersimpangan atau perhentian. Pada umumnyamenyatakan lokasi, kota, stasiun, dsb.
Cabang (branches) melambangkan arus dari satutitik ke titik yang lain dalam jaringan tersebut. Padaumumnya menyatakan waktu tempuh, jarak, panjang,dsb.
![Page 7: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/7.jpg)
Topik pembicaraan dibatasi pada 3
macam persoalan, yaitu:
1) Masalah Rute Terpendek (ShortestRoute)
2) Masalah Rentang Pohon Minimum(Minimal Spanning Tree)
3) Masalah Aliran Maksimum (MaximalFlow)
![Page 8: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/8.jpg)
1. Masalah Rute Terpendek
(Shortest Route) :
Masalah rute terpendek berguna untuk menentukan jarak tersingkat antara titik
awal (sumber) dengan beberapa titik tujuan
![Page 9: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/9.jpg)
Langkah-langkah penyelesaian
adalah :
1. Pilihlah simpul dengan rute langsung tersingkat dari titikawal.
2. Buatlah suatu setelan permanen (Permanent Set)dengan titik awal dan simpul terpilih dalam langkah 1.Permanent Set digunakan untuk menandakan bahwatelah ditemukan rute tersingkat ke simpul-simpul ini.
3. Tentukan seluruh simpul yang berhubungan langsungdengan simpul-simpul setelan permanen.
4. Pilihlah simpul dengan rute (cabang) terpendek darikumpulan simpul-simpul yang berhubungan langsungdengan simpul-simpul setelan permanen.
5. Ulangi langkah 3 dan 4 sampai seluruh simpulbergabung dengan setelan permanen.
![Page 10: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/10.jpg)
10
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).
Bogor Jakarta
B
P
D
C
O
J
28
4
17
11
17
32
12
32
18
Route dengan
waktu tempuh
terpendek
{ BD, DP, PJ }.
![Page 11: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/11.jpg)
Seseorang akan bepergian dari kota u ke kota v.
Diberikan diagram jarak antarkota berikut (dalam
puluhan mil) :
x4
4 3
a
2 3
u 6 y 2b 3 v
12
4
z5 3
c
Rute manakah yang harus ia pilih agar jarak
tempuhnya minimal?
Contoh :
![Page 12: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/12.jpg)
JAWABAN:
Setelah itu lakukan penelusuran terbalik mulai
dari simpul akhir (v), sehingga diperoleh:
v c y z u = 10
![Page 13: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/13.jpg)
Latihan
Tentukan minimal spanning tree dari jaringan
berikut:
SE
2000
LA
DE
1300DA
CH NY
DC
11001300
1000
2000
2600
1400780 900
800
200
![Page 14: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/14.jpg)
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.
![Page 15: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/15.jpg)
Definisi Spanning tree : Untuk suatu jaringan dengan n node, spanning tree adalah sekumpulan dari n-1 busur (arc) yang menghubungkan semuanode dalam jaringan dan tidak mengandungloop Definisi Minimum Spanning Tree:Minimum spanning tree adalah spanning tree dengan panjang minimum dalam suatujaringan
Masalah Rentang Pohon Minimum
(Minimal Spanning Tree)
![Page 16: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/16.jpg)
Langkah-langkah penyelesaian
adalah :
1. Pilihlah simpul awal manapun.
2. Pilihlah simpul yang terdekat dengansimpul awal untuk bergabung denganpohon rentang.
3. Pilihlah simpul terdekat yang belumtermasuk dalam pohon rentang.
4. Ulangi langkah 3 sampai seluruh simpultelah bergabung dalam pohon rentang.
![Page 17: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/17.jpg)
Gambaran
1
3
22
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 adalahminimum spanning tree
4 7
12
![Page 18: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/18.jpg)
Algoritma
Untuk menemukan spanning tree dapat digunakanalgoritma 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 denganhimpunan yang telah terhubungkan (connected set),
Algoritma selesai jika semua node telahterhubungkan dan terdapat n -1 arc yang masukdalam himpunan arc yang terhubungkan(connected arc)
18
![Page 19: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/19.jpg)
Midwest TV Company dalam
proses
kabel ke
menyediakan jaringan
wilayahlima
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).
![Page 20: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/20.jpg)
• N={1,2,3,4,5,6}
•
1
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}.
Jaraknya = 3
• C4={1,2,5,4} dan C4={3,6}.
Jaraknya = 4
• C5={1,2,5,4,6} dan C5={3}.
Jaraknya = 3
1
2
3
5
6
3 mil
4
5
Alternate links
• 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
4
3
5
Minimal spanning tree
![Page 21: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/21.jpg)
Contoh :
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.
A
E
D
B
C
F
G
8
3
5
3
7
7
12
10
4
1
4
10
B
E
D
C
A
F
G
Rentang Minimumnya
adalah :
![Page 22: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/22.jpg)
Contoh
Kota Vancouver berencana mengembangkan
sistem transportasi kereta api baru.
Sistem tersebut harus menghubungkan 8 pusat-
pusat perumahan dan komersial.
Distrik Metropolitan Transit perlu memilih set garis
yang akan menghubungkan semua pusat dengan
total biaya minimum.
![Page 23: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/23.jpg)
23
PusatPerbelanjaan
Loop
2 6
4
7
8
Bagian Barat
Bagian Utara
Universitas
PusatBisnis
BagianTimur
Bagian Selatan
PusatKota
50
34
35
39
45
41
Biaya Total = $236 juta
REPRESENTASIJARINGAN
5
1
3
![Page 24: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/24.jpg)
24
PusatPerbelanjaan
4
7
8
Bagian Barat
Bagian Utara
Universitas
Pusat Bisnis
BagianTimur
Bagian Selatan
PusatKota
50
34
35
39
45
41
Biaya Total= $236 juta
OPTIMAL SOLUTIONNETWORKREPRESENTATION 53
1
62
![Page 25: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/25.jpg)
Topik pembicaraan dibatasi pada 3
macam persoalan, yaitu:
1) Masalah Rute Terpendek (ShortestRoute)
2) Masalah Rentang Pohon Minimum(Minimal Spanning Tree)
3) Masalah Aliran Maksimum(Maximal Flow)
![Page 26: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/26.jpg)
Masalah Arus Maksimum
(Maximal Flow):
Masalah aliran maksimum merupakan masalah jaringan dimana cabang-cabang jaringan tersebut memiliki kapasitas arus yang terbatas.
Tujuan dari masalah arus maksimum adalah memaksimumkan total jumlah arus dari satu titik awal ke satu tujuan
![Page 27: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/27.jpg)
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.
![Page 28: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/28.jpg)
Langkah-langkah penyelesaian
adalah :
1. Pilihlah secara arbitrer (sembarang) garis edardalamjaringan tersebut dari titik awal ke titik tujuan.
2. Sesuaikan kapasitas pada setiap simpuldengan mengurangkan arus maksimal untuk garisedar yang dipilih pada langkah 1.
3. Tambahkan arus maksimal sepanjang garis edar kearus berlawanan arah pada setiap simpul.
4. Ulangi langkah 1, 2, dan 3 sampai tidak ada lagigarisedar dengan kapasitas arus yang tersedia.
![Page 29: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/29.jpg)
The Scott Tractor Company mengirim bagian-bagian 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.
Contoh :
![Page 30: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/30.jpg)
Definisi dan ContohPermasalahan
• Masalah: Maksimumkan jumlah arus barangdari sebuah titik awal ke sebuah tujuan
![Page 31: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/31.jpg)
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.
![Page 32: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/32.jpg)
Pendekatan Solusi• Secara arbitrer, pilih garis edar/jalur manapun
sepanjang jaringan dari titik awal ke tujuan dan kirimsebanyak mungkin yang bisa
Augmenting path 1 2 5 6 min {6,8,4} =4
![Page 33: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/33.jpg)
Pendekatan Solusi• Hitung ulang arus cabang pada kedua arah dan kemudian
pilih jalur layak yang lain secara arbitrer dan tentukanarus maksimum sepanjang jalur sampai arus tidakmungkin lagi
Augmenting path 1 4 6 min {4,5} =4
![Page 34: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/34.jpg)
Pendekatan Solusi
• Lanjutkan
Augmenting path 1 3 6 min {7,6} =6
![Page 35: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/35.jpg)
Pendekatan Solusi
• Solusi optimal
Augmenting path 1 3 4 6 min {1,2,,1} =1
![Page 36: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/36.jpg)
Contoh :
Tentukan total arus maksimum bahan yang dapat dikirim dari titik awal ke tujuan melalui lintasan sbb.
A DB
C
8
7
0
10
4
5
410
05
0
0Awal Tujuan
A DB
C
0
0
7
0
0
2
83
78
8
10(-22) (+22)
Jawab :
![Page 37: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/37.jpg)
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.
![Page 38: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/38.jpg)
Permasalahan yang muncul yaitu:
1. Buatlah jalur kereta, agar banyaknya lintasan maksimum.
![Page 39: MODEL ARUS JARINGAN - Gunadarma Universityadydaryanto.staff.gunadarma.ac.id/Downloads/files/53454/06.+MODEL... · memperhatikan arah aliran sisi ... Midwest TV Company dalam proses](https://reader034.vdokumen.com/reader034/viewer/2022052119/5c86b34f09d3f2815e8c9184/html5/thumbnails/39.jpg)