Metode Branch and Bound

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 :

1. 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
   
2. 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.
   
3. 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.