Penerapan Algoritma Branch and Bound

Nama : Yohanes Rozi Astino

NPM : 19372020P

Kelas : IF 20 C

https://teknokrat.ac.id/

https://ftik.teknokrat.ac.id/

Pengertian Metode Branch and Bound

            Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

            Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

·         Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi.

·         Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala)..

Langkah – Langkah Metode Branch and Bound

      Langkah-langkah metode Branch dan Bound dapat dilakukan seperti berikut :

1.        Selesaikan LP dengan metode simpleks biasa

2.        Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi optimum bulat telah tercapai.

3.        Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu.

4.        Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.

Berikut ini adalah contoh journal yang mengimplementasi penggunaan algoritma Branch and Bound:

full Document : download