19
solusi yang
diperoleh
dalam
pemrograman
linear
integer
mempun:yai lingkat
kcsalahan
yang t angat kecil, sehingga solusi
yang
dihnsilkan dapat dikatakan cukup
optimal.
2.8. AUgoritma Branch and Bound
AJgoritmBranch and Bound (B&B Algorithm) pcrtama
kali
dikcmba:1gkan olch
A
Land dan G.
Doig
pada
lahun
1960 unlllk
masalah
pcmrograman
linear
integer
mumi
dan
r:ampuran.
Kenmdian
pada
tahun
1965, E.
Bclas
mer.gembangkar,.
algo1itr:1a
ta.Libahan
tmLUk
memecahkan
masalah
pemrograman linear
integer
dcngan
menggunakan
variabei
0
dan
l.
Proses
branching
untuk
fungsi
tujuan
mak:simum
terus
mcnerqs .dilakukan
sampai
solusi
yang
mcndekati
hita:c1gan bulat
dihasilkan. Nilai
Z
yang diperoieh
dalam
hilangan
·oulat
mcnjadi
batas
bawab
(/01Yer
bound). N:Jai
Z
yang
kernudian
d1peroleh
balk
berUpa
bilangan
bu1_at
atau pecahan,
yang
nilainya
lebih kecil
daripada htJtas
bawah
tidak
digunakan.
Proses
branrhinJ?
dilakukan
sampai
dipero!eh
nilai
Z
y8.ng
lebili bes?x
dari
batas
hawah.
Jika
diperoleh
nilai
Z
yang
lebih
besar
dari batas
bawah,
rnakCJ
nilai Z
tersebut
menjad-T_
balas
ba\vah
yang
ba.-u
dan
batas
bawah
yc.ng
lama
dihapus.
Jika
sudah
tidak
diperoleh
nilai Z
yang
lebih
besar dari batas bawah,
maka
batas
bawah
yang ada
menjadi
solusi yang
optimal.
Un
uk
fungsi
tujuan
minimum,
Pro es
branching
yang
dilakukan
hampir
sama
dengan
proses branching
untuk
fungsi tujuan
maksimum.
PcrbeJaannya
untuk
fungsi
tujua:i
mi;UJr.um,
menggunakan batas
atas
(upper bound).
 |