model arus jaringan - rudist.files.wordpress.com · topik pembicaraan dibatasi pada 3 macam...
TRANSCRIPT
Model Arus JaringanRudi Susanto
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 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.Pada umumnya menyatakan waktu tempuh, jarak,panjang, dsb.
Komponen Jaringan
Contoh Penulisan• Gambar menunjukkan empat simpul, empat cabang.
• “Atlanta”, node 1, disebut titik awal (origin), sedangkanyang lain merupakan tujuan (destination)
• Cabang di identifikasikan dengan nomor awal dan akhirsimpul
• Nilai pada setiap cabang bisa berarti jarak, waktu, biaya, dll
Topik pembicaraan dibatasi pada 3 macam
persoalan, yaitu:
• Masalah Rute Terpendek (Shortest Route)
• Masalah Rentang Pohon Minimum (MinimalSpanning Tree)
• Masalah Aliran Maksimum (Maximal Flow)
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. Pilihlah simpul dengan rute langsung tersingkat dari titikawal.
2. Buatlah suatu setelan permanen (Permanent Set) dengantitik awal dan simpul terpilih dalam langkah 1. Permanent Setdigunakan untuk menandakan bahwa telah ditemukan rutetersingkat ke simpul-simpul ini.
3. Tentukan seluruh simpul yang berhubungan langsung dengansimpul-simpul setelan permanen.
4. Pilihlah simpul dengan rute (cabang) terpendek darikumpulan simpul-simpul yang berhubungan langsung dengansimpul-simpul setelan permanen.
5. Ulangi langkah 3 dan 4 sampai seluruh simpul bergabungdengan setelan permanen.
Contoh
• Masalah: tentukan rute terpendek dari titikawal ke semua tujuan
Definisi dari Contoh Permasalahan
Pendekatan Solusi
Tentukan rute terpendek awal dari titik awal(node 1) ke tujuan terdekat node (3)
Pendekatan Solusi
Tentukan semua simpul yang terhubunglangsung ke setelan permanen (permanent set).
Pendekatan Solusi
Definisi ulang permanent set.
Pendekatan Solusi
Lanjutan
Pendekatan Solusi
Lanjutan
Pendekatan Solusi
Lanjutan
Pendekatan Solusi
Optimal Solution
Pendekatan Solusi
Ringkasan Solusi
19
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 }.
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.
Langkah-langkah penyelesaian adalah :
1. Pilihlah simpul awal manapun.
2. Pilihlah simpul yangterdekat dengan simpulawal untuk bergabung dengan pohonrentang.
3. Pilihlah simpul terdekat yang belumtermasuk dalam pohon rentang.
4. Ulangi langkah 3 sampai seluruh simpultelah bergabung dalam pohon rentang.
Definisi dan Contoh Permasalahan
• Masalah: Hubungkan semua simpul dalam satujaringan sehingga total panjang cabang minimum
Pendekatan Solusi
• Mulai dari simpul sebarang dalam jaringan dan pilihsimpul terdekat untuk menggabungkan rentang pohon
Pendekatan Solusi
• Pilih simpul terdekat yang sedang tidak ada pada area pohon rentang
Pendekatan Solusi
• Lanjutkan
Pendekatan Solusi
• Lanjutkan
Pendekatan Solusi
• Lanjutkan
Pendekatan Solusi
• Optimal Solusi
30
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 :
3. Masalah Arus Maksimum (Maximal
Flow):
• Masalah aliran maksimum merupakanmasalah jaringan dimana cabang-cabangjaringan tersebut memiliki kapasitas arus yang terbatas.
• Tujuan dari masalah arus maksimum adalahmemaksimumkan total jumlah arus dari satutitik awal ke satu tujuan
Masalah arus maksimum dapat
mencakup:
• arus (aliran) air, gas, atau minyak melalui suatujaringan pipa,
• arus formulir melalui suatu sistem pemrosesandalam kantor pemerintah,
• arus lalu lintas melalui jaringan jalan raya,
• arus produk melalui suatu sistem lini produksi,
• dll.
Dalam kondisi tersebut, pengambil keputusan inginmenentukan arus maksimum yang dapat diperoleh melalui
sistem tersebut.
Langkah-langkah penyelesaian adalah :
1. Pilihlah secara arbitrer (sembarang) garis edar dalamjaringan tersebut dari titik awal ke titik tujuan.
2. Sesuaikan kapasitas pada setiap simpul denganmengurangkan arus maksimal untuk garis edar yangdipilih pada langkah 1.
3. Tambahkan arus maksimal sepanjang garis eadr ke arusberlawanan arah pada setiap simpul.
4. Ulangi langkah 1, 2, dan 3 sampai tidak ada lagi garisedar dengan kapasitas arus yang tersedia.
Contoh :The Scott Tractor Company mengirim bagian-bagian traktor dari Omaha ke St Louis dengankereta api. Namun, kontrak membatasi jumlahgerbong kereta yang dapat dipastikan olehperusahaan pada setiap cabang selama satuminggu.
Definisi dan Contoh Permasalahan
• Masalah: Maksimumkan jumlah arus barangdari sebuah titik awal ke sebuah tujuan
Pendekatan Solusi
• Secara arbitrer, pilih garis edar/jalur manapunsepanjang jaringan dari titik awal ke tujuan dan kirimsebanyak mungkin yang bisa
Pendekatan Solusi
• Hitung ulang arus cabang pada kedua arah dan kemudian pilihjalur layak yang lain secara arbitrer dan tentukan arus maksimumsepanjang jalur sampai arus tidak mungkin lagi
Pendekatan Solusi
• Lanjutkan
Pendekatan Solusi
• Solusi optimal
41
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 :
Contoh arus maksimum :
Dipunyai suatu jaringan kereta api dari kota A ke kota T. Inginditentuakn rute perjalanan kereta api tersebut sedemikiansehingga jumlah total perjalanan kereta api yang dapatdilakukan setiap harinya maksimum, tanpa melanggar batasmaksimum perjalanan yang dapat dilakukan pada masing-masing jalan.
Diketahui data (informasi) tentang jumlah perjalanan yangdapat dilakukan pada masing-masing rute yangmenghubungkan satu stasiun dengan stasiun lainnya, ataudapat dikatakan bahwa data tentang kapsitas aliran padamasing-masing cabang adalah :
1
1
6
0
09
4 0
0
5
4 0
2
0
1
1
3
0
4
0
7
5
A
B
C
D F
E
T
0
0
Gambar di atas dibaca sebagai berikut : Dari A ke B dapat dilakukan maksimum 5 kali perjalanan setiap hari, sedangkan dari B
ke A tidak ada perjalanan kereta api yang dapat dilakukan. Dari B ke D maksimum 1 kali perjalanan, begitu juga dari D ke B dapat dilakukan
maksimum 1 kali perjalanan setiap hari.
Source
• Taylor W. Bernard. 2004. Management Science Eight Edition. Prentice Hall : New Jersey