model arus jaringan - rudist.files.wordpress.com · topik pembicaraan dibatasi pada 3 macam...

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