20
Bcrikut
ini
mcmpakan
contoh
soal
dari
pcmrograman
linear
integer
menggunakan
algo:ritma
Branch and
Bound
:
Comtoh- soal 2.8.
Maksimumk:m Z- 5
X
1
+
4
X2
Dengan
kendafa :
Xr +
X,
<5
lOX!
T
GXJ S45
).;."1,
X2
'2:.0
Dengan mctodc simpleks, diperoleh solusi optimal
yaitu
:
x,=3,75 ;Xi=
1,2s
Ka.rena
so1usi
optimal
dengan
metode
simpleks
bukan benJpa
bilangan
bulat
(integer), maka dilanjutkan dengan algoritma Bmnch
and Bound_
Pertan:;a-
tama
k:ta
piiih
satu
dan
bilangan
integer
dimana
soiusi
optimal
Galmn
pcmrogra..."'llan linear
be::upa nilai
desimal.
Misalkan
kita
pilih X1
-
3,75_ Kita
pisahkan
daerah
3,75
dengan
rnembaginya
menjadi
3
<
X1 <
4.
Solusi
dalam
pemrograman
Iinear
se!anjutnya dibagi
menjadi
dna ruang yailu:
Ruang PU
Ruang PLO
+
(X1 .,;J)
R-u.ang PL2 =
Ruang PLO-t-
(X1 ;;::4)
Keterangan :
PLl =
Pemrograman
Linear
1
PL2 =
Pcm.rograrmm Linear
2
PLO.....,
Pemrograman Linear
yang la.TTia
 |