Beranda > Penelitian operasional > Metode Branch and Bound pada Integer Programming

Metode Branch and Bound pada Integer Programming

Metode ini adalah metode penyelesaian dengan memecah permasalahan non integer untuk mendapatkan solusi optimal integer. Percabangan dilakukan pada angka desimal terbesar. Misalnya X1 = 5,4 dan X2=7,4 maka yang dipilih adalah X2. Oleh karena itu permasalahan terdapat pada X2 dan X2 dipecah menjadi 2 masalah baru, yaitu soal linier programming sebenarnya ditambah pembatas lebih dari sama dengan 8 untuk subproblem 1 dan kurang dari sama dengan 7 untuk subproblem 2. Bila solusi dari keduanya belum integer atau salah sau integer, dipilih nilai Z terbesar untuk masalah maksimasi. Misalnya untuk subproblem 1 nilai X1 = 4,5 dan X2= 8 dengan Z=40,67 sedangkan untuk subproblem 2 nilai X1 = 3 dan X2 = 7 dengan z = 38. Meskipun subproblem 2 memiliki solusi integer namun ia tidak dipilih karena nilai Z untuk subproblem 1 lebih besar dari subproblem 2. Oleh karena itu dipilih X1 pada subproblem 1 untuk dipecahkan menjadi 2 subproblem baru. Begitu seterusnya hingga terdapat solusi optimal.

 

Subproblem yang solusinya tidak akan menghasilkan subproblem yang lebih tinggi nilai Z nya tidak perlu dipecahkan atau disebut fathomed. Kelemahan dari metode ini adalah banyaknya permasalaha yang harus diselesaikan utnuk mendapatkan solusi. Karena dari satu soal saja minimal harus ada 2 percabangan yang diselesaikan, namun bila kondisi belum optimal persoalan baru akan muncul dai pemecahan variabel non integer. Oleh karena itu metode ini cukup memakan banyak waktu dan memerlukan benyak perhitungan.

  1. Yoga
    13 November 2009 pukul 01:12

    metode lainnya mana ne gie????

    ditunggu segera

  2. 25 Maret 2010 pukul 02:21

    buku yang kebanyakan dibuat referensi untuk perkuliahan OR itu karangannya siapa??? kau pakai buku krangannya siapa???

  1. No trackbacks yet.

Tinggalkan Balasan

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

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 )

Connecting to %s

%d blogger menyukai ini: