LP
harus
dijadikan
bilangan
bulat
dan
lebih
besar
dari
nol
(integer)
dengan
cara
menaikan atau menurunkan bilangan tersebut.
Membuat
suatu
bilangan
menjadi
integer dapat dilakukan dengan cara coba-
coba
(trial
and
error)
Hasil
pecahan yang
diperoleh
dapat
dinaikan
atau diturunkan,
tetapi
harus
memenuhi
pembatas
dan
mencapai
tujuan.
Cara
ini tidak
efisien
untuk
variabel yang banyak, karena akan memakan waktu yang lama.
Cara lain untuk mengintegerkan bilangan adalah dengan teknik branch and
bound (B&B) Prinsip-prinsip dari teknik branch and bound adalah:
•
mengurangi ruang solusi dengan menghilangkan cabang yang tidak fisibel
•
perlu
menambahkan
fungsi
pembatas.
Pembatas
ini
dipakai
hanya
sampai
bila
sudah diketahui cabang tersebut tidak fisibel lagi, kemudian diganti dengan fungsi
pembatas yang baru .
Langkah-langkah algoritma B&B dengan mengasumsikan masalah maksimasi:
1. Ukur/batasi.
Pilih
LPi
sebagai
bagian
masalah
berikutnya
untuk
diteliti.
Pecahkan LPi dan coba ukur bagian masalah itu dengan menggunakan kondisi
yang sesuai.
2. Percabangan.
Pilih
salah
satu
variabel
Xj
yang
nilai
optimumnya
Xj*
dalam
pemecahan
LPi
tidak
memenuhi
batasan integer.
Singkirkan bidang
[Xj*]<Xj<[Xj*]+1
dengan
membuat
dua bagian
masalah
LP
yang
berkaitan
dengan dua batasan yang tidak dapat dipenuhi secara bersamaan ini.
Xj = [Xj*] dan
Xj = [Xj*]+1
 |