Apr 15 2012

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 X\sb{j}\sp{*} variabel yang nilainya real dirubah menjadi integer  X\sb{j} yang batasnya X\sb{j}\sp{*} \leq X\sb{j} \leq X\sb{j}\sp{*}+1. Tetapi karena range tersebut tidak memberikan penyelesaian integer, maka konsekuensinya nilai integer X\sb{j} harus memenuhi salah satu syarat dibawah ini: X\sb{j} \geq X\sb{j}\sp{*} atau X\sb{j} \leq X\sb{j}\sp{*}+1
  2. Kemudian persoalan pemrograman linear yang awal dengan kendala tambahan X\sb{j} \geq X\sb{j}\sp{*} atau X\sb{j} \leq X\sb{j}\sp{*}+1  diselesaikan sampai diperoleh keadaan optimum. Dengan demikian setiap X\sb{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\sb{j} yang integer lalu dimasukkan ke dalam basis sampai semua variabel basis yang diinginkan menjadi integer, setiap X\sb{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 nlai variable basis yang integer dan memberikan penyelesaian optimum yang fisibel.

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Gravatar
Logo WordPress.com

You are commenting using your WordPress.com account. ( Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. ( Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. ( Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. ( Logout / Ubah )

Batal

Connecting to %s