MAXIMUM FLOW Mei 27, 2008
Posted by dickyrahardi in manajemen.add a comment
Oleh : Dicky Rahardiantoro
Dalam masalah rute terpendek (shortest route) dapat dipecahkan masalah rute perjalanan terpendek untuk memindahkan barang-barang dari kantor lama ke kantor baru. Dalam masalah pohon rentang minimum (minimal spanning tree) telah dipecahkan contoh permasalahan panjang kabel listrik terpendek yang dapat mensuplai kebutuhan listrik tiap ruangan.
Pada masalah-masalah tersebut tidak dijumpai adanya perhitungan tentang kapasitas suatu cabang yang terbatas pada jumlah tertentu. Padahal terdapat masalah-masalah jaringan dimana cabang-cabang suatu jaringan tersebut memiliki kapasitas arus yang terbatas. Sebagai contoh, debit arus air antar saluran air, masing-masing cabang dalam jaringan saluran air tentunya memiliki debit maksimum, bilamana debit maksimum tersebut dilanggar akan menyebabkan terjadinya luapan air di salah satu atau beberapa cabang. Contoh lain, arus lalu lintas pada beberapa badan jalan, arus lalu lintas maksimum perlu dihitung untuk menghindari kemacetan jalan.
Artikel selengkapnya dapat dilihat di dickyrahardi.com
MINIMAL SPANNING TREE Mei 27, 2008
Posted by dickyrahardi in manajemen.add a comment
Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.
Masalah pohon rentang minimum serupa dengan masalah rute terpendek (shortest route), kecuali bahwa tujuannya adalah untuk menghubungkan seluruh simpul dalam jaringan sehingga total panjang cabang tersebut diminimisasi. Jaringan yang dihasilkan merentangkan (menghubungkan) semua titikdalam jaringan tersebut pada total jarak (panjang) minimum.
Langkah-langkah dari pohon rentang minimum adalah :
- pilih secara arbitrer sebuah node dalam jaringan
- hubungkan node tersebut dengan node terdekat yang dapat meminimalkan total jarak
- perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung
- ulangi langkah ketiga sampai seluruh node dapat terhubung
Sebagai contoh, gedung Istec Corporation yang baru memiliki beberapa ruangan dan tiap ruangan membutuhkan 1 lubang aliran listrik (atau biasa disebut sebagai steker). Teknisi listrik akan menyalurkan listrik dari ruang bagian depan sampai keseluruh ruangan dengan total panjang kabel yang seefisien mungkin….
Shortest Path Problems Mei 27, 2008
Posted by dickyrahardi in manajemen.add a comment
oleh : Dicky Rahardiantoro
Jaringan (Network) adalah suatu susunan garis edar (path) yang menghubungkan berbagai titik, di mana satu barang atau lebih bergerak dari satu titik ke titik lain atau setiap orang akrab dengan berbegai jaringan seperti system jalan tol, jaringan telepon, jaringan rel kereta api, dan jaringan televisi.
Network model sangatlah aplikatif untuk diterapkan ke banyak permasalahan pengambilan keputusan yang dapat dimodelkan sebagai model optimasi jaringan dan penyelesaian problem yang efisien dan efektif.
Jaringan diilustrasikan sebagai diagram yang terdiri dari dua komponen penting : simpul (nodes) dan cabang (branches). Simpul melambangkan titik-titik persimpangan. Cabang menghubungkan simpul-simpul tersebut dan mencerminkan arus satu titik ke titik lain dalam jaringan tersebut. Simpul-simpul dalam diagram jaringan dilambangkan dengan lingkaran dan cabang dilambangkan dengan garis yang menghubungkan simpul-simpul tersebut.
Jaringan yang ditunjukkan pada gambar di atas memiiki empat simpul dan empat cabang. Simpul yang melambangkan Atlanta disebut sebagai titik awal (origin) dan tiga simpul sisanya dapat merupakan tujuan, tergantung dariapa yang ingin kita tentukan dari jaringan tersebut. Nilai-nilai yang tertera pada tiap cabang dapat menunjukkan tentang informasi jarak, lamanya waktu, atau biaya yang diberikan pada masing-masing cabang.
Pada prinsipnya, tujuan dari pemodelan jaringan adalah untuk memperoleh solusi jarak terpendek, waktu tersingkat dan biaya terendah di antara titik-titik dalam jaringan.
MASALAH RUTE TERPENDEK
Masalah rute terpendek (Shortest Path Problems) berguna untuk menentukan jarak tersingkat antara titik awal dan beberapa titik tujuan. Sebagai contoh, sebuah perusahaan jasa pengangkutan barang disewa untuk memindahkan furnitur dan perlengkapan kantor milik Istec Corporation ke markas besarnya yang baru. Untuk memindahkan barang-barang tersebut, perusahaan jasa yang disewa dapat melalui beberapa jalur antar kota sebagaimana yang digambarkan pada diagram jaringan berikut ini…….
