Model Arus Jaringan Rudi 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
Komponen Jaringan • Jaringan digambarkan sebagai suatu diagram yang terdiri dari 2 komponen, yaitu: – simpul (nodes), biasanya digambarkan dalam bentuk lingkaran – cabang (branches), dalam bentuk garis yang menghubungkan simpul-simpul tersebut. • Simpul (nodes) melambangkan titik-titik persimpangan atau perhentian. Pada umumnya menyatakan lokasi, kota, stasiun, dsb. • Cabang (branches) melambangkan arus dari satu titik ke titik yang lain dalam jaringan tersebut. Pada umumnya menyatakan waktu tempuh, jarak, panjang, dsb.
Contoh Penulisan • Gambar menunjukkan empat simpul, empat cabang. • “Atlanta”, node 1, disebut titik awal (origin), sedangkan yang lain merupakan tujuan (destination) • Cabang di identifikasikan dengan nomor awal dan akhir simpul • 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 (Minimal Spanning 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. 2.
3. 4.
5.
Pilihlah simpul dengan rute langsung tersingkat dari titik awal. Buatlah suatu setelan permanen (Permanent Set) dengan titik awal dan simpul terpilih dalam langkah 1. Permanent Set digunakan untuk menandakan bahwa telah ditemukan rute tersingkat ke simpul-simpul ini. Tentukan seluruh simpul yang berhubungan langsung dengan simpul-simpul setelan permanen. Pilihlah simpul dengan rute (cabang) terpendek dari kumpulan simpul-simpul yang berhubungan langsung dengan simpul-simpul setelan permanen. Ulangi langkah 3 dan 4 sampai seluruh simpul bergabung dengan setelan permanen.
Contoh • Masalah: tentukan rute terpendek dari titik awal 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 terhubung langsung 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
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). 4 32
P
11
D 28 18 B
C
17
17 J
12 Bogor
O
32 19
Jakarta
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 simpul awal untuk bergabung dengan pohon rentang. 3. Pilihlah simpul terdekat yang belum termasuk dalam pohon rentang. 4. Ulangi langkah 3 sampai seluruh simpul telah bergabung dalam pohon rentang.
Definisi dan Contoh Permasalahan • Masalah: Hubungkan semua simpul dalam satu jaringan sehingga total panjang cabang minimum
Pendekatan Solusi • Mulai dari simpul sebarang dalam jaringan dan pilih simpul 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
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.
E
10 7 2 B
4
5
10
1
A
8
1
D
F 3
4
C
7
G
3
Rentang Minimumnya adalah : E B F A
D G
C 30
3. 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
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.
Langkah-langkah penyelesaian adalah : 1. Pilihlah secara arbitrer (sembarang) garis edar dalam jaringan tersebut dari titik awal ke titik tujuan. 2. Sesuaikan kapasitas pada setiap simpul dengan mengurangkan arus maksimal untuk garis edar yang dipilih pada langkah 1. 3. Tambahkan arus maksimal sepanjang garis eadr ke arus berlawanan arah pada setiap simpul. 4. Ulangi langkah 1, 2, dan 3 sampai tidak ada lagi garis edar dengan kapasitas arus yang tersedia.
Contoh : The Scott Tractor Company mengirim bagianbagian 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.
Definisi dan Contoh Permasalahan • Masalah: Maksimumkan jumlah arus barang dari sebuah titik awal ke sebuah tujuan
Pendekatan Solusi • Secara arbitrer, pilih garis edar/jalur manapun sepanjang jaringan dari titik awal ke tujuan dan kirim sebanyak mungkin yang bisa
Pendekatan Solusi • Hitung ulang arus cabang pada kedua arah dan kemudian pilih jalur layak yang lain secara arbitrer dan tentukan arus maksimum sepanjang jalur sampai arus tidak mungkin lagi
Pendekatan Solusi • Lanjutkan
Pendekatan Solusi • Solusi optimal
Contoh : 8
• Tentukan total arus maksimum bahan yang dapat dikirim dari titik awal ke tujuan melalui lintasan sbb.
0 10
A
0
4
4
B 5
Awal
7
D 0
Tujuan
5 0
10
C
Jawab : 0
8
3
A (-22)
7
0
2
0
C
8
D 10 (+22)
8 7
41
B
0
Contoh arus maksimum : Dipunyai suatu jaringan kereta api dari kota A ke kota T. Ingin ditentuakn rute perjalanan kereta api tersebut sedemikian sehingga jumlah total perjalanan kereta api yang dapat dilakukan setiap harinya maksimum, tanpa melanggar batas maksimum perjalanan yang dapat dilakukan pada masingmasing jalan. Diketahui data (informasi) tentang jumlah perjalanan yang dapat dilakukan pada masing-masing rute yang menghubungkan satu stasiun dengan stasiun lainnya, atau dapat dikatakan bahwa data tentang kapsitas aliran pada masing-masing cabang adalah :
3 0
B
1 1
0
5
9 7
0
A
D 2
0
4 5
F
0 T
1 0
4 0 0
0
1
C 4
0
E
6
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
