Pemrograman Integer dengan Fungsi Objektif Linear Sepotong- Sepotong

Abstract

Integer Linear Programming (ILP) tidak dapat digunakan untuk menyelesaikan permasalahan yang mengandung fungsi objektif linear sepotong-sepotong, karena pada dasarnya fungsi linear sepotong-sepotong bukan merupakan fungsi linear. Tulisan ini memberikan suatu metode untuk menyatakan fungsi linear sepotong-sepotong sebagai fungsi linear, sehingga masalah ILP dengan fungsi objektif linear sepotong-sepotong dapat dinyatakan sebagai ILP dalam bentuk standar. Hal ini dapat dilakukan dengan dua langkah, langkah pertama adalah merubah fungsi objektif linear sepotong-sepotong ( f(x) ) menjadi z1f(b1)+z2f(b2)+...+ znf(bn), dimana , , ..., 1 2 b b bn merupakan break point. Kemudian langkah kedua menambahkan kendala-kendala baru sedemikian sehingga formula pada langkah satu dapat berfungsi.