26
Gambar 2.12 Contoh
Data
Gambar di atas dapat dibaca seperti berikut ini :
a) Dari O ke A dapat dilakukan perjalanan maksimum 5 kali setiap hari, sedangkan dari
A
ke O tidak ada perjalanan yang dapat dilakukan.
b) Dari A ke B dapat dilakukan perjalanan sebanyak 1 kali perjalanan, begitu juga dari B
dapat dilakukan perjalanan 1 kali ke A, dan seterusnya.
Dalam hal ini diasumsikan bahwa perjalanan masuk ke suatu node sama dengan
perjalanan keluar dari node itu. Jika kapasitas busur (i,j) adalah cij, maka tingkat aliran
pada busur (i,j) yaitu jumlah aliran dari node i ke node j, adalah bilangan positif yang
tidak lebih besar daripada cij. Dengan demikian, jika tingkat aliran pada busur (i,j)
dinyatakan oleh fij, maka :
Sebenarnya,
persoalan
aliran
maksimum
ini
dapat
diformulasikan
sebagai
persoalan
programa
linier
sehingga
dapat
diselesaikan dengan
metode
simpleks. Akan
tetapi, di sini akan dikemukakan satu prosedur penyelesaian yang lebih efisien, seperti
berikut :
1. Carilah lintasan dari sumber ke tujuan dengan kapasitas aliran positif.
 |