Analisis Model Jaringan
Tehnik Pendekatan
• Tehnik Minimal-Spanning Tree • Tehnik Maximal-flow • Tehnik Shortest-route
MINIMAL-SPANNING TREE Salah satu tehnik yang menghubungkan simpul dengan jarak yang minimum
Langkah-langkah : • Pilih salah satu simpul secara sembarang • Hubungkan simpul ini dengan simpul lain dengan jarak yang terdekat
Kasus 1 Sebuah perusahaan konstruksi sedang membangun proyek perumahan mewah di Pantai Losari. Pemilik perusahaan harus menentukan cara yang paling murah untuk menyediakan air dan sumber lisrik ke setiap rumah. Jaringan rumah terlihat dalam jaringan berikut. Ada delapan rumah dengan masing-masing jarak dalam seratus meter.
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
Pilih secara sembarang
3
2 3
5 3
4 7
5 7
1
2
2 3 3
2
8 1
5 6 4
6
Teluk
MAXIMAL-FLOW TECHNIQUE Mencari aliran yang paling besar yang dapat melalui jaringan. Tehnik ini biasanya digunakan untuk menentukan volume material yang dapat mengalir dalam sebuah jaringan. Contoh berapa banyak kendaraan maksimum yang dapat berjalan dalam sebuah jalan raya.
Contoh Kasus : Seorang perencana jalan ingin menentukan berapa maksimum kendaraan yang mengalir dalam kota dari Barat ke Timur seperti jaringan berikut ini.
Langkah-langkah • Ambil salah satu jalur dari awal (sumber) ke akhir (sink) • Tentukan arah dengan kapasitas arus terkecil sebut C. Nilai C ini merupakan kapasitas maksimum tambahan yang dapat dialokasikan dalam rute tersebut. • Untuk setiap simpul dari alur, kurangi kapasitas arus dari sumber ke tujuan dengan nilai C dan tambahkan untuk arah kebalikan • Ulangi langkah diatas sampai penambahan tidak dapat dilakukan.
Contoh Kasus :
Seorang perencana jalan ingin menentukan berapa maksimum kendaraan yang mengalir dalam kota dari Barat ke Timur seperti jaringan berikut ini (1 unit = 100 kendaraan). 2 1 2 1
2 1
6 0
Titik Timur
3 Titik Barat
1 2
0 1 4 1 1
10
0
3
1
6 5
3 2
Berapa jumlah maksimum kendaraan yang dapat mengalir dari Barat ke Timur?
Pilih salah satu alur dari sumber ke tujuan secara sembarang, mis 1-2-6. Tentukan kapasitas terkecil dari jalur. Tentukan nilai C > 2 = 200 kendaraan
Tambah 2
2 1 2
Iterasi 1
Alur lama
2 6
3
Kurangi 2
1 3 2 0
1 1
4
6
Alur baru
Perhatikan alur baru mencerminkan kapasitas baru relatif pada tahapan ini. Jumlah arus dari setiap simpul menunjukkan dua faktor. Faktor pertama, adalah arus yang bisa berasal dari simpul tsb. Faktor kedua adalah arus yang dapat dikurangi dari simpul tsb.
Ulangi proses untuk jalur lain -> 1, 2, 4, 6 Nilai C adalah 1 -> 100 kendaraan
Iterasi 2
Tambah 1
3 2 1
1 6
1 1
1 1 4
Kurangi 1
Jaringan Baru
0 4 2 0
4 2
0 1 2
0 2 4 0 1
10
0
3 3 2
1
6 5
6 0
Ulangi jalur lain : 1, 3, 5, 6
Iterasi 3 : akhir
Kapasitas minimum dari alur ini adalah 2 = 200 kendaraan
6 0 Kurangi 2
1 10
1 0
3 2 Tambah 2
6 5
Jaringan Baru
0 4 2 0
4 2
6 2
0 1 2
0 2 4 0 1
8
2
3
3
4 5
3 0
Total arus (kenderaan/jam) = 200 + 100 + 200 = 500 kendaraan
Shortest-Route Tehnik yang meminimumkan jarak dalam sebuah jaringan
Langkah-langkah :
1. Tentukan simpul terdekat dari pusat jaraingan 2. Temukan simpul terdekpa selanjutnya dari pusat jaringan. Tuliskan jarakk dalam kotak di simpulnya. Dalam beberapa kasus, beberapa alur harus diperiksa untuk mendapat simpul yang terdekat. 3. Ulangi proses sehingga mencakup seluruh jaringan
Kasus 200 2
4
100
100
Pabrik
100
50
1
6
150
200 100 40 3
5
Gudang
Iterasi 1 100
200 2
4
100
100
Pabrik
100
50
1
6
150
200 100 40 3
5
Gudang
Iterasi 2 100
200 2
4
100
100
Pabrik
100
50
1
6
150
200 100 40 3 150
5
Gudang
Iterasi 3 100
200 2
4
100
100
Pabrik
100
50
1
6
150
200 100 40 3
5
150
190
Gudang
Iterasi 4 100
200 2
4
100
100
290
Pabrik
100
50
1
6
150
200 100 40 3
5
150
190
Gudang
Latihan 1 Prabawa adalah pemilik budidaya kuda terbesar di Indonesia. Dia berencana untuk menginstal sistem pengairan untuk kandang kuda. Lokasi fasilitas dan jarak antar lokasi diberikan dalam jaringan berikut. Prabawa hendak menentukan cara yang murah untuk mendistribusikan air ke setiap fasilitas. Apa rekomendasi anda.
5
2
12
10
13 10
18 1
8
19
8
6
15 3 12
12
10 18
4
7
14
Latihan 2 Sebuah perusahaan kimia berencana membangun pabrik baru untuk memproduksi bahan bakar disel baru. Gambar berikut menunjukkan jaringan dari pusat pengolahan utama berikut aliran bahan bakar (dalam ribuan gallon). Manajemen bermaksud menentukan jumlah bahan bakar maksimum yang dapat mengalir dalam pabrik dari simpul 1 sampai 7 3
4 0
2
3
7
8 5
5
1
8
8 5
5
6 3 3
3
0
0
1
6
7
4
4 1
4
6
6
7 0
Latihan 3 Jaringan berikut menunjukkan jalan raya dan kota disekitar Kota Impian. Seorang pengusaha helm sepeda harus mengirimkan produknya ke distributor di kota Bojong Soang dari kota asalnya Sukamiskin, Apa rekomendasi anda
90
6
100
2
10 7
100
13 90
100
100
Suka Miskin 90
1
11
90 90
3
16
14
105 110
90
350
Bojong Soang
4
12 100
8
100
9
90
90
100 15
5 200
Soal menggunakan QM3 1. Sebuah perusahaan real estate bermaksud meminimumkan total kabel yang harus disediakan untuk instalasi listrik di sebuah kompleks perumahan sehingga biaya pembangunan bisa lebih murah. Jaringan perumahan dapat dilihat dalam gambar Jaringan 1 berikut. Setiap rumah telah diberi nomor dan jarak antar rumah juga telah disediakan. Apa yang akan saudara rekomendasikan. 2. Kota Cimahi bermaksud membuat jalan satu arah. Jaringan jalan dapat dilihat dalam jaringan 2. Berapa maksimum kendaraan yang per jam yang dapat berjalan dari bagian TImur ke Barat. Rute mana yang saudara rekomendasikan.
3. Perusahaan pengangkutan Baragajul Jaya mendapat pekerjaan memindahkan barang perkantoran dari kantor lama ke kantor baru. Jaringan jalan dapat dilihat dalam gambar 3. Apa rekomendasi anda.
Jaringan 1: instalasi listrik 3
7
3 1
1
6
2
4
5
12
8
4 14
3
2
7
3
5 5
7 6
9
6
13
6 4
4 4
2
5
5
3
7 10
11 3
Jaringan 2 : Jaringan Jalan 2 2
2 5
2
2
0
1
7
2
2
2 3
0
2 2
2
4 0
1
6 0 1
3
8 0
1
5
4 4
Jaringan 3 : Rute Pindah
7 2
120 100
100 50
1
50
5
3
100
10
13
130
100 Kantor Lama
60
70 8
40
200
20
100
100
40
11 100 4
50
6 100
100 9
12
Kantor Baru
