Penyelesaian masalah arus biaya minimum dengan algoritma out-of-kilter

Abstract

Permasalahan arus biaya mininum dalam jaringan memegang peranan penting di antara model-model optimasi jaringan lainnya, dikarenakan permasalahan tersebut dapat digunakan pada banyak penerapan. Algoritma out-of-kilter merupakan salah satu metode untuk menyelesaikan permasalahan arus biaya minimum dalam jaringan yang dikembangkan oleh D.R. Fulkerson (1961) yang dibangun khusus untuk menyelesaikan permasalahan dalam jaringan. Penentuan kondisi keoptimalan dalam algoritma ini diturunkan berdasarkan kondisi keoptimalan Kuhn-Tucker. Busur-busur dalam jaringan yang memenuhi kondisi Kuhn-Tucker disebut in-kilter (busur dalam keadaan optimal), jika tidak disebut out-of-kilter. Untuk busur dalam keadaan out-of-kilter diberikan suatu bilangan yang disebut bilangan kilter, yang mengukur posisi busur tersebut dari keadaan optimal. Secara garis besar algoritma dibagi menjadi dua tahap, yaitu: tahap primal dan tahap dual. Dalam tahap primal, pertama kali ditentukan busur out-of-kilter yang akan diperbaiki, kemudian dilakukan perubahan aliran dalam jaringan. Untuk menjamin bahwa perubahan aliran tersebut tidak mengubah aliran konservasi, maka perubahan aliran hanya dilakukan terhadap busur-busur dalam suatu cycle. Proses pembentukan cycle dilakukan dengan menggunakan metode pelabelan. Keadaan dengan cycle yang mengandung busur out-of-kilter yang akan diperbaiki berhasil dibentuk dinamakan breakthrough. Apabila cycle tidak dapat dibentuk, dinamakan nonbreakthrough. Jika terjadi nonbreakhirough, perubahan aliran dalam tahap primal dihentikan dan dilanjutkan ke tahap dual. Algoritma akan berakhir dengan kesimpulan solusi optimal telah tercapai jika dalam tahap primal semua busurnya berada dalam keadaan in-kilter, atau dengan kesimpulan permasalahan arus biaya minimum tidak memiliki solusi fisibel. Kekonvergenan dari algoritma out-of-kilter, dijamin berdasarkan sifat kemonotonan tak naik dari barisan bilangan kiter dalam keseluruhan tahap dari algoritma.