MAXIMUM FLOW

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.

Untuk lebih memahami masalah arus maksimum, kembali kita ambil contoh dari Istec Corporation. Kali ini masalah yang diangkat adalah masalah maximum flow of cars (arus kendaraan maksimum) yang melewati jalan penghubung antara Mess karyawan dengan kantor baru. Jalan penghubung tersebut dapat digambarkan dalam gambar jaringan di bawah ini.


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)

Interpretasi di atas juga dapat diterapkan pada cabang-cabang lain yang menghubungkan antar node. Permasalahannya adalah berapakah arus maksimum dari jalan yang menghubungkan mess karyawan dengan kantor?

Untuk menjawab permasalahan ini, maka diambil langkah-langkah penyelesaian yang dibuat oleh L.R. Ford Jr dan D.R. Fulkerson sebagai berikut :

  1. Pilihlah secara arbitrer garis edar dalam jaringan tersebut dari titik awal ke tujuan
  2. Sesuaikan kapasitas pada setiap node dengan mengurangkan arus maksimal untuk garis edar yang dipilih pada langkah pertama
  3. Tambahkan arus maksimal sepanjang garis edar ke arus berlawanan arah pada setiap node
  4. 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.

Secara arbitrer diambil garis edar 1-2-5-7-8



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.

Karena arus maksimum pada garis edar 1-3-6-8 adalah 2, maka tiap arus menuju node-8 dikurangi 2 dan tiap arus berlawanan ditambah 2.



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.

Secara arbitrer diambil garis edar 1-4-8. Tiap arus menuju node-8 dikurangi 1 dan tiap arus berlawanan ditambah 1.



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

Baca Selengkapnya

MINIMAL SPANNING TREE

oleh : Dicky Rahardiantoro


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 :

  1. pilih secara arbitrer sebuah node dalam jaringan
  2. hubungkan node tersebut dengan node terdekat yang dapat meminimalkan total jarak
  3. perhatikan semua node apakah terdapat node yang belum terhubung, temukan dan hubungkan node terdekat yang belum terhubung
  4. 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. Adapun jarak antar ruangan dapat digambarkan dalam gambar jaringan berikut ini, sedangkan ruang bagian depan digambarkan sebagai node-1.



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

Panjang kabel yang dibutuhkan adalah : 21 meter





Baca Selengkapnya

Shortest Path Problems

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.



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-2, hitunglah tentatif label (d,n) terhadap semua node yang dapat dicapai langsung dari node 1. Label d menunjukkan jarak suatu node dengan node sebelumnya dan n adalah node sebelumnya.

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

Langkah-4, berilah tentatif label (t,k) pada node yang dapat dicapai langsung dari node-k. Label t menunjukkan jarak kumulatif sedangkan k adalah node sebelumnya yang telah memiliki permanen label. Bila suatu node telah memiliki tentatif label maka gunakan tentatif label yang memiliki jarak terpendek

Langkah-5, lakukan langkah-langkah di atas sampai seluruh tetatif label pada tiap node memiliki jarak paling pendek dengan node sebelumnya, sehingga tentatif label tersebut menjadi permanen label

Penerapan Shortest Route Algorithm pada proses pemindahan barang-barang Istec Corporation ke kantor barunya.

Label [0,S] diberikan pada node-1. Node 2, 3 dan 4 adalah node yang dapat dicapai langsung dari node-1. Masing-masing diberi tetatif label (100,1) , (50,1) dan (40,1).

Karena node-4 memiliki jarak paling pendek dari node-1 maka tentatif label node-4 berubah menjadi permanen label [40,1].


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).

Node 3 memiliki 2 tentatif label, yaitu : (50,1) dan (60,4), padahal tiap node hanya boleh memiliki 1 tentatif label. Sehingga tentatif label yang dipilih untuk node-3 adalah (50,1).

Karena tidak ada lagi jalur yang dapat ditempuh menuju node-3 selain dari node-1 dan node-4, maka tentatif label (50,1) sudah menunjukkan jarak terpendek, sehinga tentatif label tersebut dapat diubah menjadi permanen label [50,1].


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].

Node-5 dapat dicapai oleh node-2 dan node-3, sehingga node-5 dapat memiliki tentatif label (200,2) dan (150,3). Tentatif label yang dipilih untuk node-5 adalah (150,3). Karena tidak terdapat lagi suatu node yang dapat mencapai node-5 dengan jarak yang lebih pendek dari 150 maka tentatif label berubah menjadi permanen label [150,3].



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.





Baca Selengkapnya

test code

Baca Selengkapnya