23
Selesaikan pl,dengan
menggunakan s2.tu dmi
liga
kond.isi
s
bagai berikut:
a.
Nilai
optimal
Z
dari
pli
tL
ak
dapat
menghasilkan
nitai
tujuan
yang
lcbih
bcsar
dari
baLas bawah yang sekarang.
b.
Pltmenghasilkan solusi inleger
yangfeasible dan lebih besar Jari
batas bawah yang
sekarang.
c.
PL
tidak
rnempunyai
solusi
yangfeasihle.
Maka sclanjutnya akan muncLtl
dua kcadaan yai:u :
a.
Jika
plt
dibandingkan
da.ll.
solusi
yang
lebih
baik
ditemukan,
maka
perbahami
(update)
batas
bawah. .Tika semua
submasalah
teiah
dibandingkan,
hentikan, so)usi
pemrograman
linear
mteger
ada
dal_am
batas
bawah
yang
sekarang.
Dcngan
kata
lain, tentu...\an i =
i
+
I, dan uiangi
langkah
l.
b.
Jika p1
1
tidak dibmldingkan, ianjutkan ke
iangkah 2
u11tuk proses
branching.
Langkah
2
:
{Branching). Pilih satu
dari variabel integer Xb
dimana nilai optimal
JV
dalam solusi
piitidak. integer. Balasi daerah solusi :
[Xj]<.<j<[Xj]+l
dcngan
mcmbuat
dua submasalah
yang seS'..lai
unluk :
Xf
,;[.<]
]
dan
x;
?[
x; ]
+
I
Temukan
i-
i
+
l, dan
uiangi
langkah
1.
Langkah- hmgkah
di
atas
ditcrapkan untuk problem
ma.'><simisasi.
lJntuk
problem
minimisasi, kita
mengganti
batas bawah
menjadi
batas atas (upper
bound)
dengan
menentukan
nilai '/
awa1
'-
+
·-.
 |