PEMROGRAMAN LINEAR INTEGER

Pemrograman linear integer (bilangan bulat) tergolong dalam  pemrograman linear. Pemrograman linear integer ini menjadi linear jika beberapa atau semua variabel tidak dibatasi oleh integer. Program linear integer pada intinya berkaitan dengan dengan pemrograman-pemrograman linear di mana atau semua variabel memiliki nilai-nilai integer.

Banyak persoalan praktis menginginkan nilai varibel yang bulat agar persoalan menjadi realistik. Jumlah orang, mesin-mesin, kendaraan, untuk persoalan praktis tidak akan realistik jika dinyatakan dengan bilangan pecahan. Akan terasa sangat janggal jika dikatakan untuk menyelesaikan pekerjaan tertentu diperlukan  buah mesin dan   orang. Sebaliknya jika dikatakan bahwa pekerjaan itu diperlukan 2 atau 3 buah mesin dan 5 orang akan terasa menjadi realistik dan lebih gampang mengambil keputusan. Pemrograman linear integer menyelesaikan soal alokasi yang nilai variabelnya merupakan integer (bilangan bulat). Pemrograman linear integer berhubungan dengan fungsi yang bernilai integer (Argga, 1985).

Metode Branch and Bound Method (Cabang dan Batas)

Metode Branch and Bound (cabang dan batas) adalah salah satu metode untuk menghasilkan penyelesaian optimal pemrograman linear yang menghasilkan variabel-variabel keputusan bilangan bulat. Sesuai dengan namanya, metode ini membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas dan bawah bagi masing-masing variabel keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru (Siringoringo, 2005).

Langkah-langkah penyelesaian masalah pemrograman linear menggunakan metode cabang batas (Arga, 1985):

1. Metode ini diawali dengan metode simpleks sampai terdapat penyelesaian optimal. Kemudian untuk basis variabel yang nilainya real dirubah menjadi integer x_j yang batasnya . Tetapi karena range tersebut tidak memberikan penyelesaian integer, maka konsekuensinya nilai integer x_j harus memenuhi salah satu syarat dibawah ini:
2. Kemudian persoalan pemrograman linear yang awal dengan kendala tambahan  diselesaikan sampai diperoleh keadaan optimum. Dengan demikian setiap x_j akan menghasilkan dua cabang yang berbeda, dengan nilai basis dan nilai fungsi tujuan optimum yang berbeda. Basis yang sudah integer tetapi menghasilkan nilai fungsi tujuan yang lebih rendah dari basis yang integer di cabang lain, harus dibuang dan cabang tersebut tidak perlu dilanjutkan penyelusurannya.
3. Nilai x_j yang integer lalu dimasukkan ke dalam basis sampai semua variabel basis yang diinginkan menjadi integer, setiap x_j yang baru akan menghasilkan dua cabang yang baru, kecuali cabang yang tidak fisibel. Cabang yang tidak fisibel langsung dapat dibuang.

Dengan cara demikian akan dapat diketahui semua nilai  variabel basis yang integer dan memberikan penyelesaian optimum yang fisibel.

Banyak persoalan seperti capital-budgeting-problem, fixed-charge problem, job-sob scheduling problem, dapat diselesaikan dengan metode pemrograman linear integer nol-satu (Argga, 1985).