Tuesday, May 27, 2008
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.
Sebelum menjelaskan ke pemecahan masalah, maka perlu dijelaskan terlebih dahulu arti dari angka-angka yang terdapat pada tiap cabang. Cabang yang menghubungkan antara node-1 dengan node-2 memuat angka 2 dan 0, maksudnya adalah :
- arus maksimal kendaraan yang dapat melintasi jalan dari node-1 ke node-2 adalah 200 mobil per jam
- arus dari node-2 ke node-1 adalah 0 mobil per jam, artinya tidak ada arus dari node-2 ke node-1 (arus hanya searah dari node-1 ke node-2)
- Pilihlah secara arbitrer garis edar dalam jaringan tersebut dari titik awal ke tujuan
- Sesuaikan kapasitas pada setiap node dengan mengurangkan arus maksimal untuk garis edar yang dipilih pada langkah pertama
- Tambahkan arus maksimal sepanjang garis edar ke arus berlawanan arah pada setiap node
- Ulangi langkah 1,2 dan 3 sampai tidak ada lagi garis edar dengan kapasitas arus yang tersedia
Berikut ini adalah penerapan langkah-langkah penyelesaian arus maksimal untuk menjawab permasalahan arus maksimal dari mess karyawan Istec Corporation ke kantor barunya.
Arus maksimal dari node-1 ke node-8 yang melewati garis edar 1-2-5-7-8 adalah sebesar 2 atau 200 mobil per jam. Tiap arus menuju ke node-8 dikurangi 2 dan arus yang berlawanan ditambah 2, sehingga menghasilkan hasil sebagai berikut.
Hasil di atas memperlihatkan bahwa tidak ada lagi jalan yang dapat ditempuh melalui node-1 ke node-2, karena arus maksimumnya adalah nol (0). Secara arbitrer diambil garis edar 1-3-6-8. Arus maksimum pada garis edar ini adalah 2 atau 200 mobil per jam, sehingga total arus maksimum yang dapat masuk adalah sebesar 4 atau 400 mobil per jam.
Jalur lain atau garis edar lain yang masih memungkinkan untuk dilewati adalah jalur 1-4-6-8 dan 1-4-8 dengan arus maksimum masing-masing jalur adalah 1 atau 100 mobil per jam, sehingga meningkatkan total arus maksimum yang dapat masuk sebesar 5 atau 500 mobil per jam.
Pada langkah ini tidak ada lagi jalur atau garis edar yang dapat menghubungkan arus dari node-1 ke node-8. Agar lebih jelasnya diagram jaringan disajikan dengan tanda-tanda panah berikut :
Karena tidak ada lagi arus yang dapat mengalir dari node-1 ke node-8, maka proses iterasi telah mencapai penyelesaian optimun. Dari sini dapat diambil kesimpulan bahwa arus maksimum yang menghubungkan antara lokasi mess karyawan dengan kantor baru adalah sebesar 5 atau 500 mobil per jam dengan rincian sebagai berikut :
| Jalur | Maksimum Arus Mobil |
| 1 – 2 – 5 – 7 – 8 | 200 |
| 1 – 3 – 6 – 8 | 200 |
| 1 – 4 – 8 | 100 |
| Total | 500 |
Labels: manajemen
Pohon rentang minimum (minimal spanning tree) adalah teknik mencari jalan penghubung yang dapat menghubungkan semua titik dalam jaringan secara bersamaan sampai diperoleh jarak minimum.
- 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
Karena node-1 adalah ruangan terdepan yang menjadi sumber aliran listrik utama, maka node-1 akan dijadikan sebagai patokan dalam jaringan. Node yang paling dekat dengan node-1 adalah node dengan jarak 2 meter, sehingga kita hubungkan node 1 dengan node-3.
Kemudian kita lihat node-node terdekat yang belum terhubung dengan node 1 dan 3, yaitu node 7, 6 dan 2. Yang terdekat dengan node 3 adalah node 7 dengan jarak 3 meter. Kemudian node 3 dan node 7 dapat dihubungkan.
Node yang belum terhubung terdekat dengan node 1, 3 dan 7 adalah node 6 dengan panjang 2 meter.
Node yang belum terhubung dan dekat dengan node 1,3,7 dan 6 adalah 5 dan 2. Node 5 dapat terhubung dengan node 6 dengan jarak 3 meter, sedangkan node 3 dapat dihubungkan dengan node-1 dengan jarak 3 meter.
Sisa node yang belum terhubung adalah node 8, 4 dan 9. Node 4 dapat dihubungkan dengan node 5 dengan jarak 3 meter, dan untuk mencapai node 9 total jarak terdekat lebih pendek jika ditempuh dari node 8 ke 9 dari pada melalui node 4.
Karena seluruh node telah terhubung atau telah terkait dalam satu jaringan, maka solusi di atas telah optimum. Jadi teknisi listrik dapat memulai merentangkan kabelnya dengan menghubungkan node 1 – 2, 1 – 3, 3 – 7, 6 – 7, 5 – 6, 4 – 5, 6 – 8, 8 – 9
Labels: manajemen
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.
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.
MASALAH RUTE TERPENDEK
Agar perjalanan lebih efisien, maka jalur manakah yang jarak tempuhnya lebih pendek ?
Shorthes Route Algorithm
Langkah-1, berilah node-1 label permanen [0,S]. Angka pertama pada permanen label tersebut menunjukkan jarak antar node, sedangkan angka kedua menunjukkan nomer node sebelumnya. Node-1 tidak memiliki node pendahulu (node sebelumnya) sehingga label S menunjukkan bahwa ia adalah node awal.
Langkah-3, identifikasi seluruh node dengan tentatif label yang menunjukkan jarak paling kecil dengan node sebelumnya. Katakanlah node tersebut sebagai node-k, maka ubahlah tentatif label pada node-k tersebut menjadi permanen label dengan menggunakan simbol [ , ]. Jika semua node telah memiliki permanen label maka beralihlah ke langkah ke-5
Node 3 dan 6 adalah node yang dapat dicapai langsung dari node-4 yang telah memiliki permanen label. Total jarak node 4 ke node 3 adalah sebesar 60 dan total jarak node 4 ke node 6 adalah 140, sehingga node 6 diberi tentatif label (140,4) dan node 3 diberi tambahan 1 tentatif label (60,4).
Untuk mencapai node-2 hanya terdapat satu jalur yaitu melalui node 1 sehingga tentatif label pada node-2 dapat diubah menjadi permanen label [100,1].
Lakukan proses tersebut sampai seluruh node memiliki tentatif label dan seluruh tentatif label dapat berubah menjadi permanen label. Pada iterasi akhir diperoleh hasil sebagai berikut :
Hasil tersebut menunjukkan bahwa untuk mencapai node-13 jarak terpendeknya adalah melalui node-10, 7, 5, 3, 1. Artinya perjalanan dari node-1 (kantor lama) ke node-13 (kantor baru) hendaknya dapat melalui rute 1 – 3 – 5 – 7 – 10 – 13 dengan jarak total sebesar 430 miles.
Labels: manajemen












