Terdapat beberapa metode untuk menghasilkan batasan-batasan khusus yang akan memaksa pemecahan optimum dari masalah program linier yang dilonggarkan untuk bergerak kearah pemecahan integer yang diinginkan. Salah satunya yang umum digunakan adalah metode Branch and Bound.
Metode Branch and Bound (cabang dan batas) adalah salah satu metode untuk menghasilkan penyelesaian optimal program linier yang menghasilkan variable-variable 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 variable keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru.
Langkah-langkah penyelesaian masalah program linier menggunakan metode cabang batas, yaitu :
-
Metode ini diawali dengan metode simpleks sampai terdapat penyelesaian optimal. Kemudian untuk basis
variabel yang nilainya real dirubah menjadi integer
yang batasnya
. Tetapi karena range tersebut tidak memberikan penyelesaian integer, maka konsekuensinya nilai integer
harus memenuhi salah satu syarat dibawah ini:
atau
-
Kemudian persoalan pemrograman linear yang awal dengan kendala tambahan
atau
diselesaikan sampai diperoleh keadaan optimum. Dengan demikian setiap
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.
-
Nilai
yang integer lalu dimasukkan ke dalam basis sampai semua variabel basis yang diinginkan menjadi integer, setiap
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 nlai variable basis yang integer dan memberikan penyelesaian optimum yang fisibel.