MATERI 8
MODEL ARUS JARINGAN
Jaringan •
Jaringan adalah suatu susunan garis edar (path) yang menghubungkan berbagai titik
•
Komponen jaringan : simpul ( nodes) dan cabang ( branches) Simpul melambangkan titik persimpangan,
sedang cabang menghubungkan antar simpul
RO/ X / 2
MASALAH RUTE TERPENDEK • • •
Berguna untuk menentukan jarak tersingkat antara titik awal ke beberapa titik tujuan. Metode: Solusi Terpendek (Shortest Path)
Langkah : 1. Pilih simpul dengan rute langsung tersingkat dari titik awal 2. Buatlah suatu setelan permanen dengan titik awal dan simpul terpilih pd langkah 1
3. Tentukan seluruh simpul yang berhubungan langsung dengan simpul simpul setelan permanen 4. Pilihlah rute terpendek dari seluruh simpul yg berhubungan langsung dg simpul simpul setelan permanen. 5. Ulangi langkah 3 dan 4 sampai seluruh simpul bergabung dengan setelan permanen
Contoh soal : The Stagecoach Shipping Company mengangkut jeruk dengan 6 truk dari LA ke enam kota di bagian Barat dan Barat Tengah. Enam rute yang berbeda antara LA, kota kota tujuan serta lamanya waktu dalam jam yg dibutuhkan oleh sebuah truk adalah :
25
2 12
5
16
19
4
35 1
8
14
17
15
14
9 3
22
7
6
2 16 4
35 1 9 3 9 *
16 * 2 16 4
35 1
15 9 3 9
22 6
16 25
2
5
24 *
16
4
35 1
15 9 3 9
22
6
16 25
2
14
24
16
5
19
4 1
17
15 9 3 9
22
6 31 *
7
38 *
16 25
2
14
24
16
19
4 1
5
15
14
9 3 9
7
22
6 31
16
38
2
5 14
24
16
19
4 1 0
43 *
15 9 3 9
7
22
6 31
MASALAH POHON RENTANG MINIMAL (SPANNING TREE) •
Hampir sama dengan Masalah Rute Terpendek, hanya tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjangnya diminimumkan
•
Jaringan yang dihasilkan merentangkan ( menghubungkan ) semua titik dalam jaringan tersebut pada total jarak ( panjang) minimum
The Metro Cable Television Company akan memasang suatu sistem kabel televisi dalam suatu komunitas yang terdiri dari tujuh kota. Masing masing kota harus dihubungkan ke sistem kabel utama. Perusahaan kabel televisi tsb ingin merancang jaringan kabel utama dg cara yang dpt meminimasi total panjang kabel yg hrs dipasang.Jalur yg mungkin tersedia untuk perush. tv kabel tsb dan panjangnya kabel yg dibutuhkan digambarkan sbb :
Langkah • • • •
Pilihlah simpul awal manapun ( biasanya simpul 1 yang terpilih ) Pilihlah simpul yg terdekat dg simpul awal untuk bergabung dg pohon rentang Pilihlah simpul terdekat yg belum termasuk dlm pohon rentang Ulangi langkah 3 sampai seluruh simpul telah tergabung dlm pohon rentang
RO/ X / 17
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 18
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 19
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 20
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 21
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 22
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 23
25
2 12
16
5
4 15
9 3
7
19
35
1
8
14
17 22
14 6
RO/ X / 24
MASALAH ARUS MAKSIMAL
•
Dalam masalah ini, masalah jaringan memiliki kapasitas arus yang terbatas.
•
Permasalahannya : menentukan arus maksimum yang dapat diperoleh melalui sistem tersebut
RO/ X / 25
LANGKAH
1.
Pilih secara sembarang garis edar dalam jaringan tersebut dari titik awal ke titik tujuan
2.
Sesuaikan kapasitas pada setiap simpul dg mengurangkan arus maksimal untuk garis edar yg dipilih dlm langkah 1
3.
Tambahkan arus maksimal sepanjang grs edar ke arus berlawanan arah pd 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 bagian bagian traktor dari Omaha ke St Louis dengan jaringan sistem rel kereta api seperti yang ditunjukkan pada gambar di bawah ini. Namun kontrak membatasi jumlah gerbong kereta api yg dpt dipastikan oleh perusahaan pada setiap cabang selama 1 minggu
Berdasarkan kondisi yang terbatas ini, perusahaan ingin mengetahui jml maksimum gerbong kereta api yg berisi bagian traktor yg dapat dikirim dari Omaha ke St Louis selama satu minggu. Jml gerbong kereta api yg tersedia bagi perusahaan traktor tsb untuk setiap cabang rel ditandai oleh angka pd cabang di sisi kanan setiap sampul yang melambangkan persimpangan rel,
0
6
Masuk
1
2
8 0 3 0
4
2
7
Omaha
0
4 0
3
4
5
0
Keluar
6
5 0
St. Louis
2
3
6
RO/ X / 29
Arus maksimum untuk garis edar 1-2-5-6
4
2
4
4 0
3
6
Masuk 4
0
2
8
1
0
4
2
7
Omaha 0
0 4
4 0
3
4
5
0
Keluar
6
5 0
St. Louis
2
3
6
RO/ X / 30
4
Arus maksimum untuk garis edar 1-4-6
4
0
1
4 0
5
3
2
Masuk 8
0
2
4
4
4
0 2
7
Omaha 0
4 0
3
4
0
4
0
Keluar
6
5 1 0
St. Louis
2
3
6
RO/ X / 31
8
Arus maksimum untuk garis edar 1-3-6
4
0
1
4
0 71
Omaha
5
3
2
Masuk 14
0
2
4
4
0 2
6
4
0
Keluar
6
1
6 0
4 0
3
4
0
0
St. Louis
2
3
6 0
RO/ X / 32
14
Arus maksimum untuk garis edar 1-3-6
4
0
1
4
0
5
3
2
Masuk 15
0
2
4
4
0
1 0
2
Omaha 1
1 2
60
3
1
4
0
Keluar
6
1 0
6
1
4 0
3
4
0
0
St. Louis
0
RO/ X / 33
15
Arus maksimum untuk garis edar 1-3-6
4
0 3
2
Masuk 15
0
2
4
4
1
4
0
Omaha
0
0
2
7
0
1
3
5
4 0
Keluar
6
0
6
1
0
0
3
4
5
0
St. Louis
0
RO/ X / 34
15
