DIVA GRESIK

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