Learning Outcomes• Mahasiswa dapat menghitung

pemecahan masalah/kasus model integer programming dengan menggunakan program komputer..

Outline Materi:• Metoda Branch & Bound• Contoh kasus..• Penyusunan program• Demo programming

Metoda Branch dan Bound• Metoda ini merupakan yg lebih efisien dari

metoda sebelumnya dan telah menjadi kode komputer standar untuk Integer Programming.

• Pertama kali diperkenalkan oleh Land dan Doig, kemudian dikembangkan oleh Little.

• Teknik ini dapat diterapkan untuk masalah pure maupun mixed integer programming

Masalah maksimisasi,

Adapun langkah-langkah metoda tsb untuk masalah maksimisasi sbb:

• 1.Selesaikan masalah LP dgn metoda simpleks tanpa pembatasan bil.bulat.

• 2.Teliti solusi optimumnya. Jika var basis yg diharapkan bulat adalah bulat maka solusi optimum bulat telah tercapai. Tetapi jika satu atau lebih var basis yg diharapkan bulat ternyata tdk bulat, lanjutkan ke langkah 3.

3.Nilai solusi pecah yg layak dicabang kan ke dalam sub-sub masalah. Tujuannya adalah utk menghilangkan solusi kontinu yg tidak memenuhi per syaratan bulat dari masalah tsb. Pencabangan dilakukan melalui kendala mutually exclusive yg perlu utk memenuhi persyaratan bulat dgn jaminan tidak ada solusi bulat layak yg tak diikutsertakan.

4.Untuk setiap submasalah, nilai solusi optimum kontinu fungsi tujuan di tetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah. Submasalah yg memiliki batas atas kurang dari batas bawah yg ada tidak diikutsertakan pada analisis lanjutan.Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap submasalah yg dicari. Jika solusi demikian ada, suatu submasalah dengan batas atas terbaik dipilih utk dicabangkan. Kembali ke langkah 3.

Contoh,

Maks z= 3x1 + 5x2Kendala: 2x1 + 4x2 25

X1 8 2x2 10x1,x2 non negatif integer.

Solusi optimum kontinu X1=8, X2=2,25 Dan Z=35,25.Solusi ini adalah batas atas awal. Batas bawah adlh solusi yg dibulatkan ke bawah X1=8, X2=2 dan Z=34.

• Dalam metoda Branch dan Bound di pilih X yg pecah yaitu X2=2,25 dan utk menghilangkan yg pecah diciptakan dua kendala baru yg terdekat dgn 2,25 yakni 2 dan 3. Sehingga diperoleh dua kendala mutually exclusive X2 2 dan X2 3 yg pada uraian berikut disebut bagian A dan bagian B.

• Bagian A :• Maks z=3x1 + 5x2• Kendala 2x1 + 4x2 25• x1 8• 2x2 10 (berlebih)• x2 3• x1,x2 0 • Bagian B :• Maks z=3x1 + 5x2• Kendala 2x1 + 4x2 25• x1 8• 2x2 10• x2 2• x1,x2 0

Bagian A dan B diselesaikan tanpa pembatasan bil.bulat dengan metoda simpleks diperoleh

Bagian A: x1=8; x2=2 dan z=34Bagian B: x1=6,5; x2=3 dan z=34,5• Bagian B, dicabangkan ke dalam sub bagian B1

dan B2. Pertama dengan kendala x1 6 dan X1 7.

• Kedua submasalah dinyatakan sbb:

• Subbagian B1 :• Maks z=3x1 + 5x2• Kendala 2x1 + 4x2 25• x1 8 (berlebih)• 2x2 10 • x2 3• x1 6• x1,x2 0 • Subbagian B2 :• Maks z=3x1 + 5x2• Kendala 2x1 + 4x2 25• x1 8• 2x2 10• x2 3• x 1 7• x1,x2 0

• Subbagian B1:x1=6;x2=3,25;z=34,25• Subbagian B2: tidak layak!• Selanjutnya subbagian B1 kembali di cabangkan

dgn kendala x2 3 & x2 4• Subbagian B1a :• Maks z=3x1 + 5x2• Kendala 2x1 + 4x2 25• 2x2 10 (berlebih)• x2 3• x1 6• x2 3• x1,x2 0

• Subbagian B1b: Maks z=3x1 + 5x2• Kendala 2x1 + 4x2 25• 2x2 10• x2 3 (berlebih)• x1 6• x2 4• x1,x2 0• Subbagian B1a:x1=6;x2=3;z=33• Subbagian B1b: x1=4,5;x2=4;z=33,5• Karena hasil yg diperoleh memiliki batas atas (z=33 dan

z=33,5) yg lebih jelek dibanding solusi hasil bagian A,maka solusi optimal adalah

• x1=8; x2=2; dan z=34 yg dihasilkan oleh bagian A..