Network Model [PDF]

Citation preview

Network Model Merita Bernik



• Jaringan adalah suatu susunan garis edar yang terhubung pada berbagai titik di mana suatu barang bergerak • Network models terkenal karena menyajikan suatu gambaran sistem dan banyak sistem yang dengan mudah digambarkan dalam bentuk jaringan



Komponen-komponen Jaringan • Simpul (nodes): melambangkan titik-titik persimpangan. Simpul dilambangkan dengan lingkaran. Umumnya mengambarkan suatu kota, persimpangan, stasiun • Cabang (branches): menghubungkan simpulsimpul tersebut dan mencerminkan arus satu titik ke titik lain dalam jaringan. Cabang dilambangkan dengan garis. Umumnya menggambarkan jalan, yang hubungkan kota, jalan kereta apai, rute udara.



Penyelesaian dengan Network Model • Rute Terpendek • Spanning Tree • Arus Maksimal



Rute Terpendek • Menentukan jarak tersingkat antara titik awal dan beberapa titik tujuan • Prosedurnya: ▫ Pilihlah simpul dengan rute langsung tersingkir dari titik awal ▫ Buatlah suatu setelan permanen dengan titik awal dan simpul terpilih dalam langkah 1 ▫ Tentukan seluruh simpul yang berhubungan langsung dengan simpul-simpul setelan permanen ▫ Pilihlah simpul dengan rute terpendek dari kumpulan simpulsimpulyang berhubungan langsung dengan simpul-simpul setelan permenen



Contoh Soal Suatu perusahaan mengangkat jeruk dengan enam truk dari Los Angeles keenam kota di bagian Barat dan Barat Tengah. Rutenya seperti pada gambar berikut



Rute Pengiriman dari LA



Solusi Rute Terpendek • Setelan permanen adalah rute tersingkat Setelan permanen



Cabang



Waktu



1



1-2



16



1-4



35



1-3



9*



• Berdasarkan tabel diatas setelan permanennya adalah 1-3



Setelan permanen



Cabang



Waktu



1,3



1-2



16*



1-4



35



3-4



24



3-6



31



• Setelan permenennya adalah 1-2



Setelan permanen



Cabang



Waktu



1,2,3



1-4



35



2-4



28



2-5



41



3-4



24*



3-6



31



• Setelan permanenya 3-4 • Untuk waktu dijumlahkan dari rute yang sebelumnya



Setelan permanen



Cabang



Waktu



1,2,3,4



2-5



41



3-6



31*



4-5



38



4-7



43



4-6



41



• Setelan permanennya adalah 3-6



Setelan permanen



Cabang



Waktu



1,2,3,4,6



2-5



41



4-5



38*



4-7



43



6-7



45



• Setelan permanennya adalah 4-5



Setelan permanen



Cabang



Waktu



1,2,3,4,5,6



4-7



43*



6-7



45



5-7



46



• Setelan permanennya adalah 4-7



Tabel solusi akhir Dari 1 ke



Rute



Total Jam



2



1-2



16



3



1-3



9



4



1-3-4



24



5



1-3-4-5



38



6



1-3-6



31



7



1-3-4-7



43



Jalur terpendek



Spanning Tree Minimal • Kita dapat memulai dari simpul manapun dalam jaringan tersebut. • Kita memulai dari simpul pertama. • Prosedurnya: ▫ Pilihlah simpul awal manapun (biasanya simpul pertama) ▫ Pilihlah simpul yang terdekat dengan simpul awal untuk bergabung dengan pohon rentang ▫ Pilihlah simpul terdekat yang belum termasuk pohon rentang, dan ulangi langkah-langkahnya



Contoh Soal • 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 TV tersebut ingin merancang jaringan kabel utama dengan cara yang dapat meminimalisasi total panjang kabel yang harus dipasang. Jalur yang mungkin tersedia untukperusahaan TV kabel tsb dan panjangnya kabel yang dibutuhkan untuk setiap jalur seperti yang terlihat dalam gambar.



Solusi pohon rentang minimal



Kesimpulan • Jumlah minimal kabel televisi untuk menghubungkan tujuh kota tersebut sepanjang 72000 kaki. • Pohon rentang yang sama juga dapat diperoleh dengan memulai proses ini pada salah satu enam simpul selain simpul 1.



Soal 1 • Di bawah ini skema jaringan yang memeperlihatkan jarak antara titik (dalam mil), tentukan rute terdekat dari simpul 1 ke titik-titik yang lain



Skema Jaringan



Soal 2 • Seorang pengembang sedang merencanakan sebuah kawasan pemukiman yang meliputi; rumah petak,rumah tunggal,townhouse,komplek apartemen, area belanja, pusat penitipan anak dan arela bermainnya, ruang pertemuan, dan sekolah. Pengembangan tersebut ingin membangun jaringan jaln yang menghubungkan kesepuluh fasilitas tersebut. Gambar berikut memperlihatkan jalur-jalur yang mungkin yang dapat menghubungkan fasilitas tadi. Tentukan jaringan minimal dari jaringan tersebut dan hitung berapa jumlah panjang jalan yang diperlukan.



Skema Jaringan



Masalah Arus Maksimum • Tujuannya untuk memaksimalisasi total jumlah arus dari satu titik awal ke satu tujuan • Masalah arus ini dapat mencakup: arus air, gas, atau minyak melalui suatu jaringan pipa, arus formulir melalui suatu sistem pemprosesan, arus lalu lintas melalui jaringan jalan raya, atau arus produk melalui sistem lini produksi. Berdasarkan kondisi-kondisi ini pengambilan keputusan ingin menentukan arus maksimal yang dapat diperoleh melalui sistem tersebut



• Prosedur: ▫ Pilihlah secara arbitrer garis edar dalam jaringan tersebut dari titik awal ke titik tujuan ▫ Sesuaikan kapasitas pada setiap simpul dengan mengurangkan arus maksimal untuk garis edar yang dipilih dalam langkah 1 ▫ Tambahkan arus maksimal sepanjang garis edar ke arus berlawanan arah pada setiap simpul ▫ Ulangi langkah-langkah sebelumnya sampai tidak ada lagi garis edar dengan kapasitas arus yang tersedia



Contoh Soal • The scott tractor company mengirim bagianbagian traktor dari Ohama ke st Louis dengan kereta api. Namun kontrak membatasi jumlah gerbong kereta yang dapat dipastikan oleh perusahaan pada setiap cabang selama satu minggu.



Skema jaringan



Pendekatan Solusi Arus Maksimal



Garis edar maksimal 1-4-6



Garis edar maksimal 1-3-6



Arus maksimal garis edar 1-3-4-6



Arus maksimal untuj jaringan rel kereta



Kesimpulan • Berdasarkan jaringan jalur di atas maka gerbang yang dipergunakan sebanyak 15