Metode Branch and Bound pertama kali diperkenalkan oleh Land dan Doig (1960). Ide dasarnya adalah untuk membagi daerah solusi fisibel menjadi daerah solusi fisibel yang lebih kecil. Ini merupakan prosedur sederhana yang menetapkan batasan yang lebih tinggi dan rendah menjadi solusi saat menyelesaikan sub masalah secara sistematis. Kemudian metode ini dimodifikasi oleh Dakin (1965) dan dengan sukses menerapkannya di dalam kitab undang- undang hukum dagang banyak orang dalam memecahkan persoalan program integer.
Metode Branch and Bound adalah metode umum untuk mencari solusi optimal dari berbagai permasalahan optimasi. Pendekatan Branch and Bound didasarkan pada prinsip bahwa himpunan total solusi layak dapat dipartisi menjadi subset yang lebih kecil dari solusi. Subset yang lebih kecil ini kemudian dapat dievaluasi secara sistematis sampai solusi terbaik ditemukan.
Metode ini sering digunakan untuk menyelesaikan suatu masalah program integer karena hasil yang diperoleh dalam penyelesaian optimal lebih teliti dan lebih baik dari kedua metode lainnya. Kelemahan pokok metode ini adalah prosedur untuk mencapai hasil optimal sangat panjang. Prosedur penyelesaian masalah maksimasi program integer dengan metode Branch and Bound adalah sebagai berikut :
1. Langkah 1 : penyelesaian optimal dengan metode program linier biasa.
Masalah yang dihadapi diselesaikan terlebih dahulu menggunakan metode program linier biasa (menggunakan metode grafik atau metode simpleks) sampai diperoleh hasil yang optimal.
2. Langkah 2 : pemeriksaan penyelesaian optimal.
Hasil optimal pada langkah 1 diperiksa apakah variabel keputusan yang diperoleh bernilai integer (bilangan bulat) atau pecahan. Apabila ternyata nilai semua variabel keputusan tersebut merupakan bilangan bulat positif (nonnegative integer), maka penyelesaian optimal telah dicapai. Apabila tidak, maka proses iterasi dilanjutkan.
3. Langkah 3 : penyusunan sub masalah (branching).
Apabila penyelesaian optimal belum tercapai, maka masalah tersebut dimodifikasikan ke dalam dua sub masalah (branching) dengan memasukkan kendala baru ke masing-masing sub masalah tersebut. Variabel kendala baru tersebut harus bersifat saling pengecualian (mutually exclusive constraints) sehingga memenuhi persyaratan penyelesaian integer.
4. Langkah 4 : penentuan nilai batas (bounding).
Hasil optimal yang diperoleh dengan metode program linier biasa (non integer) merupakan nilai batas atas (upper bound) bagi setiap sub masalah. Sedangkan hasil optimal dengan penyelesaian integer merupakan nilai batas bawah (lower bound) bagi masing-masing sub masalah. Selanjutnya, apabila sub masalah yang memiliki batas atas yang lebih rendah dari batas bawah yang berlaku, maka sub masalah tersebut tidak perlu dianalisi lagi. Apabila dalam penyelesaian integer menghasilkan hasil yang sama atau lebih baik daripada nilai batas atas dari setiap masalah, maka penyelesaian optimal integer telah tercapai. Apabila tidak, maka sub masalah yang memiliki nilai batas atas yang terbaik dipilih selanjutnya menjadi sub masalah baru. Proses iterasi ini kembali kepada langkah 2, sehingga demikian seterusnya (Sitorus, 1997).
Artikel keren lainnya:
Belum ada tanggapan untuk "Metode Branch and Bound (Pencabangan dan Pembatasan) "
Post a Comment