Integer Programing with Branching and Bounding

Solve the following integer program
Minimize C = 2 X1 + 3 X2 + 4 X3
Subject to G1 = 2 X1 - 3 X2 + 3 X3 = 7
G2 = -3 X1 + 2 X2 +4 X3 = 5
C disini adalah faktor yang menghasilkan keuntungan itu banyak atau sedikit, sehingga jika yang dikehendaki adalah agar menghasilkan nilai C yang kecil maka semua angka-angka di atas dikalikan dengan minus. Dengan demikian akan terjadi bentuk perumusan baru yakni :


Ini adalah bentuk minimize, sekarang kita akan menentukan nilai X1, X2, dan X3. Metode yang digunakan pertama adalah dengan simplex variable. Dari tabel di atas maka pivot kolom ada di kolom X1 dan pivot baris ada di baris G1, sehingga pivot point terdapat di daerah pertemuan antara kolom X1 dan baris G1 yakni pada nilai -2.


Nilai -2 ini harus dijadikan 1 dan nilai yang lain di kolom X1 harus di jadikan 0 bagaimanapun caranya. Cara yang dipakai adalah dengan menambahkan atau mengurangkan baris G2 dan C ke baris G1. Akan tetapi, jika kita telah menentukan untuk menggunakan perintah tambah, maka semuanya harus memakai tambah dan begitu juga sebaliknya. Baris G1 sekarang diganti nama menjadi baris X1, maka hasil yang didapat adalah :


Dari tabel di atas maka pivot kolom ada di kolom X3 dan pivot baris ada di baris G2, sehingga pivot point terdapat di daerah pertemuan antara kolom X3 dan baris G2 yakni pada nilai 8,5.


Nilai 8,5 ini harus dijadikan 1 dan nilai yang lain di kolom X3 harus di jadikan 0 bagaimanapun caranya. Cara yang dipakai adalah dengan menambahkan atau mengurangkan baris G2 dan C ke baris G1. Dan pada permasalahan ini maka kami menetapkan untuk memakai perintah tambah. Baris G1 sekarang diganti nama menjadi baris X1, berikut adalah contoh perhitungannya :
- Baris C kolom X3 = -1 –((1/8,5) x -8,5) = 0
- Baris X1 kolom X3 = 1,5 – ((-1,5/8,5) x -8,5) = 0
Sehingga hasil yang didapat adalah :


Sekarang kita telah ketahui nilai X1 = 0,76 ; X3 = 1,82
Kita masukkan ke persamaan G1 : 2 X1 – 3 X2 + 3 X3 = 7
: 2 (0,76) – 3 X2 + 3 (1,82) = 7
: 1,52 – 3 X2 + 5,46 = 7
X2 : -0,0067
Sedangkan hasil dari nilai C adalah 8,82.
Sehingga nilai untuk X1, X2, dan X3 secara berurutan adalah 0,76, -0,0067, dan 1,82.


Untuk itu kita optimalkan daerah pada X1 dan X3 :


Dari gambar di atas kita bisa menarik suatu kesimpulan bahwa daerah yang di amati untuk meminimalkan hasil adalah antara 0 – 1 pada koordinat X3. Sehingga batasannya adalah :
a. Solusi pertama
C = 2 X1 + 3 X2 + 4 X3
Subject to G1 = 2 X1 - 3 X2 + 3 X3 = 7
G2 = -3 X1 + 2 X2 +4 X3 = 5
G3 = X3 lebih kecil dari 1






Untuk solusi pertama ini menghasilkan nilai : X1 = 2 X3 = 1 Dan X2 bisa didapat dengan memasukkan nilai X1 dan X2 ke persamaan G1 G1 : 2 X1 – 3 X2 + 3 X3 = 7
: 2 (2) – 3 X2 + 3 (1) = 7
: 4 – 3 X2 + 3 = 7
X2 : 0
Sedangkan hasil yang didapat adalah 8, lebih kecil 0,82 dibanding sebelum diberi batasan.

b. Solusi ke dua C = 2 X1 + 3 X2 + 4 X3
Subject to G1 = 2 X1 - 3 X2 + 3 X3 = 7
G2 = -3 X1 + 2 X2 +4 X3 = 5
G3 = X3 lebih besar dari 0
Ketika memakai batasan G3 : X3 lebih besar dari 0 maka hasil yang didapat sama seperti halnya ketika belum memakai batasan yakni menghasilkan nilai X1 dan X2 sebesar 0,76 dan 1,82. Dan hasil yang didapat pun sama yakni sebesar 8,82.

Dari ke dua solusi yang kami tawarkan di atas, maka jelas bahwa solusi 1 memberikan jawaban yang lebih baik dan memberikan jumlah hasil yang kecil jika dibandingkan tanpa memakai batasan X3 lebih kecil dari 1. Sehingga jika ini adalah suatu produksi, maka untuk meminimalkan hasil sebaiknya kita membuat X1 sebanyak 2 satuan, X2 sebanyak 0, dan X3 sebanyak 1 satuan. Dengan nilai-nilai seperti ini maka hasil yang didapat menjadi :
C = 2 X1 + 3 X2 + 4 X3
= 2 (2) + 3 (0) + 4 (1)
= 8 satuan.