PERBANDINGAN ANTARA PENDEKATAN BRANCH AND BOUND DAN PEMROGRAMAN LINEAR z DENGAN SEBUAHCONTOH KASUS OPTIMASI Retno Maharesi Fakultas Ilmu Komputer, Universitas Gunadarma. Jl.Margonda Raya 100, Depok 16424 Abstrak Pendekatan solusi dari suatu masalah optimisasi Diskrit atau Kombinatorik dapat diperolelt dengan menggunakan metode Branch & Bound secara langsung pada permasalahan atou amtformulasikan problem ke bentukpemrograman linear yang solusinya dikhususkan untuk bilangan hilat positif saja (Pemrograman Integer). Dapat tidaknya solusi optimal dari suatu -permasalahan optimisasi Diskrit atau Kombinatorik untuk diperoleh, bergantung pada kejelian seseorang dalant nelihat ada-tidaknya potensi dari penggunaan metode Branch & Bound ata,u menemukanformulasi Pemrograman Linear untuk masalahyang bersangkutan.Pada tulisan ini, akan diuraikan bagaimana nendapatkan solusi dengan metodeBranch & Bound secara efektif danjuga jikc digunakan Fonnulasi Pemrograman Linear untuk solusi Integer. Untuk mal<sudtersebut, di sini akan digunakan salah satu antoh permasalahan optimisasi kombinatorik. Permasalahan tersebut adalah ntengenai pndistribusian n = 5job pada m =3 mesin,dengan tiap job dapat diproses di sernuamesin dan mesinnesin tersebut dapat dioperasikan secara pararel sehingga total waktu penyelesaian ninimunt. *lanjutnya solusi yang diperoleh dengan menggunakandua metode ini akan dibandingkan. Sehingga furdasarkan pembahasan pada contoh kasus ini dapat diperoleh pengertian yang berguna dalant senyelesaikanpernrasalahan optimisasiDiskrit atau Kombinatorik lain secara lebih efektif. Kata kunci: branch and bound, optimisasi dislvit, optimisasi kombinatorik, pemrograntan integer, Fnrograman linear, solusi optimum, distribusijob, penyelesaian efektif. t.
Pendahuluan
Algorithma Branch and Bound adalah suatu metode pendekatan untuk mendapatkan solusi masalahoptimisasi diskrit dan kombinatorik. Masalah optimisasi Dislsit jika nilai variabel keputusan mrupakan himpunan yang beranggotakannilai-nilai diskrit. Pemrograman Lrteger adalah termasuk .lalam masalah optimisasi Diskrit karenanilai dari variabel-variabel keputusannyamerupakananggota trirnpunanbilangan bulat (integer). Sedangkanmasalah optimisasi kombinatorik berhubungandengan Denentuankombinasi optimum dari sejumlah alternatif kombinasi dari sekumpulan obyek. Menurut sratu referensi sebagianbesar dari masalahoptimisasi kombinatorik dapat diformulasikan ke masalah Pernrograman Integer. Problem utama pada metode penyelesaianmasalah kombinatorik dengan tanpa menggunakan furrulasi pernrogramanLinear terletak pada ketidaktersediaanyakondisi untuk mengecek optimalitas dui solusi feasible yang telah diperoleh. Sebagaimana telah diketahui, metode Simplex yang digrrnakan untuk menyelesaikan suatu masalah pemrograman linear mempunyai kondisi untuk mngecek apakah solusi yang didapat sudah optimal atau belum. Pada suatu proses pengecekan,jika hndisi optimalitas belum dipenuhi maka ia dapat memberikan arah yang dapat menunjukkan kepada nlafu penyelesaianyang optimal melalui sejumlah iterasi yang tertentu banyalcaya.Kondisi optirnalitas peda pemrogramanlinear ini bersifat global, karenajika sebuahsolusi optimal telah diperoleh, maka ia mupakan penyelesaian optimal yang menyeluruh (global). Pada masalah optimisasi dislcrit atau hsmbinatorik, metode Branch and Bound yang digunakan untuk menyelesaikanpermasalahannyatidak P-12
P-13
Antara PendekatanBranch And BoundDan PemrogramanLinear : Scbuah Contoh Kasus Optimasi
i kondisi optimal yang slobal sepertipadametodeSimplex.Sehinggajika sebuahsolusi fiperoleh, maka ia musti dibandingkandengansetiapsolusi pada semuaalternatifkombinasi remastikan bahwa suatu solusi adalahglobal. Padahalbanyaknyaalternatif kombinasi obyek secaraeksponensialterhadapjumlah obyekdalamsuatupermasalahan.. Sebagaicontoh : 1) Pada masalah penetapan 5 job, job 1,2,3,4 dan 5 yang masing-masingnya diproses dengan 3 buah mesin I, II atau IIL Waktu yang diperlukan untuk menyelesaikan pada setiap mesin bervariasi bergantung pada tipe mesinnya. Permasalahannya adalah
total waktu minimum untuk pengerjaan5 job padatiga buah mesin.Di sini persoalannya samahalnya denganmemilih alternatif yang memberikanwaktu tercepatdari 243 altematif. Di pcsoalannyaadalahsamahalnya denganmemilih altematif yang memberikanwaktu tercepatdari efrernatifyang ada atarrlebih jelas lagi : cara untuk menempatkanmesin padajob cara untuk menempatkanmesin padajob cara untuk menempatkanmesin padajob cara untuk menempatkanmesin padajob cara untuk menempatkanmesin padajob
=
(tC,
x
'C,
x
' C,
1= 2= 3= 4: 5=
'C, 'Ct 'Ct 'C, 'Cr .
x
' C,
x
tc,) cara.
yangterdiriatas5item,yaitul,2,3,4, 2)Padamasalahpengurutanprosespengerjaanproduk 5 dimana setiap item harus dike{akan tiga tahapan,I, II dan III secaraberurutan.Waktu yang untuk menyelesaikansetiap tahapanpada setiap mesin bervariasi bergantungpada tipe dan job nya. Permasalahannya adalah menentukan trutan dari tahapan pengerjaan untuk
produk itu sehinggawaktu pengerjaansecarakeseluruhanpaling cepatMasalahini dapat hkan sebagai: Bagaimanamemilih sebuahalternatif urutan dari 5 tahapan kerja.yang wakru tercepat, yang artinya sama dengan bagaimana memilih 1 diantara 5! buah
if urutanjob, ataulebihjelas lagi : carauntuk menempatkansuatujob padaurutan I = knya carauntuk menempatkansuatujob padaurutan2 = cara untuk menempatkan suatu job pada urutan 3 :
hyaknya carauntuk menempatkansuatujob padaurutan4 = lmyaknya carauntuk menempatkansuatujob padaurutan5 = lchingga total kombinasidari urutanyangdihasilkanadalah: 120:
(tC,
x
oC,
x
tC,
x
2Cr
tc, oc, ,C, ,C, tc,
x
tc,)
cara.
Kedua contoh di atas memotivasi untuk lebih mengefektifkan teknik pencarian solusi optimal pendekatan Branch and Bound p4!a suatu tipe masalah kombinatorik dan alternatif hgan tEnggunaan teknik lain yang diharapkan tidak banyak mengkonsumsi waktu, seperti halnya teknik Femrograman Integer. Pada bagian berikut dari tulisan ini akan diperlihatkan bagaimana nenyelesaiakan masalah yang diberikan oleh kedua contoh di atas dengan teknik Pemrograman Linear &u Branch and Bound
(s)
0 lx p + 6 x g + 9 x g+ lx 7 + 9 x g 7 I I x : Z ursou Ip €Fe{ q{e/Y\Ielol
(r)
9 rg + f x 6 y + f rg + Z x 7 + [ x p q I I x : I urseu Ip Biro)tnpl?^\Ielol : Blepua{ depeq:a;
(e)
(z)
IIx =z
ue)ltunlururtrAI :rsslnuuoc
Euz,(laqeuel: lty jlqafqo 1sEurytullu Eundut€ueu{qun ue4eunSrp '0I'6'8'L'9'S'V'E'Z'I - r 4nlun6 =tx e>11f 91 ulsetu1pep€I qof 'il utsetuIp €pB{eplt I gof qlf 0 -!x qole{lf ulseru ?pB I Ip ] 0I '6'8 'L'g: I {nlun 11 I urseuIp epe{epll I qof e>ll0
(r)
_lx
g'V'E'Z' I = r {n}unI ursoru!p spsI qofe>{lfI
8ue,t uollstugtoPlp :trD{lreqteEeqas rx uesrunde>{ rselnurog ueure.6oluad Ip l{€lsssut Jueutl ue4etm8Euatu uulte sele {n1un [aq?lJ€A rueull uuruerSoruredepolel l
L
v
6
8 9 I
ru
I
s
OI 8
t
L
7 L
s
!
il
v
'€
v
z I
I
qof ursetrAI otDQ uop snso4 I'e 9:u t=w Tnlun IaqDJ
'l'z loq4riolous){ueqp s}Bp usEuop s
- u ueP f = trr {nltm snss){uuleun8rp us)F IUI ualqord ueeresale,(uad erec uep rss4snll le8eqag e runrurururqo[enures uesfta?sadq4E/$ Islol ul?ceseFa4aqpdep ffurqas tu npls '' 'oZ'I ursorrrrp ue4ehorppledep qofdeqas ueSuopue?tu€sJeq u qof ' ' '€qof 'Zqof 'Iqo[ n1re,(qof u ueeftaEuedue4rsnqrqsrpqapuetureEeq tue{ urseu ur epede>1 urseru durles epud qof depes ueeftaEuad npp/tr surei teuaEuaur u1ep e{lf trqetallp
ualqord lslugeo
L
7 sn1sn8yZZ- lZ 'ugu1e1'erurepeung sulsJaArun unrrollpnv
(ZmZftrql{6;tr} uatr1alu1 ualsls uuprelnduo;tr's8urpaacor4
rt-d
khcndingan Antara PendekatanBranch And Bound Dan PemrogramanLinear : ScrDgrnSebuahContoh Kasus Optimasi
P-l5
lmai waktu kerja di mesin 3: sII > 5( 1 - x1 - x6 ) + 6(1 - x2 - x7 ) + 8( I - x3 - xg )+ 9(1 - x4 - xg )+7( 1 - xS - xI0 ) x1< I x2<1 x3
'
,
xg
0
(6)
kqelesaian untuk masalahini diperolehdenganmenggunakan programriset operasionalTORA, denganprint m ;ebagaiberikut: l.m=nt solution found at node : 66 Optimalityverified at node : *. OPTIMUM INTEGER SOLUTJON **.* ]trctive value (min) = 7.00000 "urr:.ble Value Obj Coeff Obj Val :"lrrib
..{ E9
'-msrramt .. >r I >r l>r .{,,(r j
-
4r,'niof Sol
l.0000 r.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000 1.0000 0.0000 7.0000 RHS
0.0000 0.0000 35.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.0000
0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 7.0000
Slack(-)/Surplus(+) 1.0000+ 1.0000+ 0.0000+ 0.00000.00001.00001.00001.00001.00001.00000.00000.00001.0000-
'gZ:{L'B7}xeur :{1'r+6+8+9+S} xeur: (€'€'€'€'€'05eSSurqesm€Sqofuepmetqof qof geraq(g'g'€'€'€'0)apoN qof 'm€Zqol'ru€l 'ilIee
(e.€.E.'.€.ob qot,mezsqzoitilTlru;g;'i.9;,tr13+:Jff$; eaaurqas m€rqo!,rtr€€ tresqofu€p 8Z={g'gg}xeut= {S'r+6+8a9ag}xeur : (r'€'€'6'€'% et8urqasI€S qolu"p met qol'Itre€ qol'11IeZ qof 'ilI€tqof q$raq (t't'g'g'€'g) apoN uolresspraqSuqrqrpledepsep 1ptaqq {qun rnpp : apouzpedledzpralSuef e48ue-a18ue apoudeqasepedgrqa.(qorstungIeUN'S qof nelu, 'E'Z qo! nflef 'qof Suerequres {n}un ru{elraqIs/vre 'I utz:8etp epe4 lp uoqod apou rcEeqes s€]s qo[qel?pe (g) e.tuqn8Eunsas apouu€qllrurad 1e,acu '0=9x'IX 0=Lx'T-;1I =0'X'0:6x=iX'0=8x:€X
o=Lx'zx'0 = 9x:IX O+Lr{:TX'0E9)(:IX
IeqEuE^relru Is?Ingulo)
apou lp
oqnc4nftn rsCIlnqDJ t'f pqoJ
: efes (g'g) opou uep 1o18uefuaq8ue,{Sueqec qenq,t Z: e x t x t x E x g ledep'ro1 ru8eqag'Sueqec ueselafuad efueq -iueqec lentuatu lrD1lraqIeqel ue8uap ue4e!:a41p ursaut ne}e eJuces e4eur uuqrunlase{ '1g ludep qof de11aseua:e) :lruIuaq II '1 qcyunf 'w{qellp apou Sueqec eped re8eqasSunrF{lp ledzp uogrseqrp 3ue,{ rrppra} {nlun }llns rur qoluoo eped gradas qof g uep urseu g snsslt:plun efes ueurspq nles ue:{eun8Euaure,(uequeEuap dr43ua1Erscasprmog pue qcu?rg apoteu qalo ue{nlredrp Suud uoqod uurEurp uerequreS8ua6
punogpue qcusr gepolet r ^l .v 2:tlx - z leuqdo leyu ueEuaq
Sqof:III ursel4l tqol'g qof:il ursert
Z qof'I qof; I ursaII nsle 0=0 I x' I -6x' I -8x'6r=1x'6-9tx'g- gx'g=7x .g-6x '1=gx '[=lX leurqdo rsnlos uulluoqtuetu ss]e !p lnolugd '1etu4do Isnlos Jl]€tuellu qenqes !.Ep qlqet ludeprel Iu! ul"p llqun Isq€pe4 'pur4do rsnlos Jqeluetls uoluequeur ledep Euu,( ueqrFd uurppefuau {epq €uere>l'ue8uem4o>1refunduraut rul uru-6o-rd ue8uep qalo:adrp Eue,{ nnlog mog mfn8y ZZ- lT,'e1relef'vrurepuungselrsralrunumgotrpnv ruolsls uepralnduro; 'sEurpaacor4 ftOOZfntf,tg;fl uo[1a1u1
9I - d
SiluurodinganAntara PendekatanBranch And Bound Dan PemrogramanLinear : SebuahContoh Kasus Optimasi
Penyelesaianoptimal dengan metode Branch and Bound secara menyeluruh untuk kasus ini urynr Clakukan denganlangkah-langkahsebagaiberikut: .'Jrnrkan representasi diagram pohon untuk m=3 dan n: 5. Representasi diagram pohon untuk $@b rni adalah : l* Tcmpkan batas atas dari solusi yang nilainya akan digunakan sebagai pembanding dengan solusi node lain. Sebaiknya batas atas ini mempunyai nilai yang mendekati penyelesaian optimal. re *n[n-*:ran3cara memilihnya, dapat dilakukan denganmudah : untuk menggunakansemuamesin, karena pendistribusian semuajob pada setiap mesin akan illigtmekan roul:rangr akumulasi wakfu operasi pada mesin. data pada tabel berikut 2.1 (agar lebih jelas tabel2.l dituliskan kembali sebagaitabel 4.2), jobryEngtr ,mffi ]Eg membutuhkan.wdktupenyelesaianrelatif cepat. Tabel 4.2 Data untuk kasus m = 3 dan n : 5 Mesin Job n I II 1
2 3 4 5
4 2 8 10 5
5 a z a J a
A
5 6 8 9 7
+.nsarkanyang diambil adalah 5)I, 2)I, 4)II, 3)II, l)trI, berarti susunan ini berkorespondensi = max{5,2+5,3 +3\:7. iiqE"n node(0,3,1,2,2,1),sehinggaf1o,r,r,z,z,ry 3 r::nmg nilai F mulai dari node paling pangkal,jika nilai F lebih rendah atau sama dengan 7 lanjutkan k menghitung F pada cabang-cabangturunannya.Jika nilai F lebih besar dari pada 7 berpindahlah -mrn mrn:<menghitung pada node lain yang sederajatdengannode sebelumnya. Berdasarkan langkah-langkah yang diuraikan, maka untuk contoh ini diperoleh solusi optimal gnbal = 7, diperoleh dari node pangkal {0, 1} dan {0,3} yang ditunjukkan oleh tabel berikut: Tabel4.3 . Node panskal yanp memberikansolusi optimal. Node panskal {0,1
{0 .1
(0.1.1.2.2.3) F:7 (0.1 . 1 ) (0,1,1,2)( 0.1.1.2.2)( 0.t.1.2.2.2\ F:10 F :l 1 F=6 F=6 F:6 rc.r.r.2.2.1 Node panekal{0.3}
{0 .3 }
Q.3.r.2.2.3\F:12 (0.3.1) (0,3,1,2)(0,3,t,2,2) (0,3,r,2,2,2) F=10 F:5 F:6 F=5 rc3.r.2.2.rF=7
Sehinggadiperoleh kombinasi: (3, 1,2,2, l), yaifi mesin I mengerjakanjob 2 dan 5, mesin II -reerjakanjob 3 dan 4, mesin Itr mengerjakanjob 1. Atau (1, I,2, 2,3), yaitu mesin I mengerjakan _mt'i dan 2 mesin II mengerjakanjob 3 dan 4, mesin III mengedakanjob 5. Dari penjelasan bagaimana cara mendapatkan solusi optimal untuk contoh ini ada beberapa hal mempengaruhi keefektifan penggunaanmetode ini antaralain adalah : :qmg l. Cara pengkodean dari setiap node pada pembentukan diagram pohon. Pengkodean yang terstruktur secarabaik memudahkandalam pembuatandiagram pohonnya. 2. Pemilihan batas atas yang digunakan sebagai kriteria pembanding terhadap node-node yang akan dihitung nilai fungsi obyektifirya. Karena semakin dekat nilainya ke nilai solusi optimal, maka akan semakin cepat dapat diputuskan untuk memangkas cabang-cabang turunan dari
(rr)
uz. ' ''7+u'1+u= r {nlunU ulsau1pspst qofu>tltt I ursau1pep€rypp I qof erillO
(or)
_lx
u' "' 'i 't'Z' | = I {n}unI ulsaur1pspeI qof e>tlfI
: ln>IlraqrcEeqasuz>llslugaplp8ue.( lx uesnlndal laqsue^ : lnqesral snsq {n}tm ra8alut ueuel8orued rsqnurog 'Sursodtelnq ueEuepqSuerequresu uep tu ue8uap 'u = qof qupunf uep tu = ulsottrqepunf >p1unJ€euITueuerSorured ,rn1n*og uallfesp ue>Ielut tn>IIJog'Iut qotruocqalo uurppfungp rgadss 'ute1uem1nda1[aqeu€An]Bns Iqnuauau unleq uergegur?uarurde8uapI{BlBpee,(un1usqePS 'nlnqep l{!qapa}qeqnlPsruEqlut "Fell-q uaptm8Euau Eps elep 'e,(qeuols8unJ lndur lrunuatu efurseinturog e:pf eEEurqag lrsp tlslldxa {nlmq auek ure€ojd euarel lrsrldxe erecese,{ue1epua1 1s8rm;undneur;rqa,(qo rs8unSuesqnuaduu>lnlJelratu zpe 8ue,t ralnduo4 uu8ord uu4er(ueqeque4UeqradrpnFad unuelq 'lsnueur eJ?ces u?llBselastp lduruq Euert elepue4 ls8unJ {niun npp/r.\ ueerpasJe}a{ lnpns uep Suupurdrp ualuffiunruaul {epl} 'Jesaq BIOlsJaqSuur{)tuo}€utquo{ undneruuesnlnda4 [aq"rJE uaneqrlaur 4z,(uequu>{e?uesIp euaJe) uzurerSorure4 raialut ueEuap urerEord :a1nduro1 ue4ngadrp >p4un ueresalafuad ieEues qelesetu .u1,uJ ({)t{} utul = ulur{:n}I€f '1tcarya1 lsEurgreltu ueSuapleuqdo apou - z urul ne1,gEVZ'"' 'Z'l = { {ryun nfler('rur raEalul ueuerSorurad z ue>iluntulul4 ueuecuadueauap eures Suer(rseluasardarre,{unduraur 't u?p Z 'l Blspue)t qalo uald,aleltp euerurcEeqes eped grp1a.(qo isEury rs€lruruoJ ue4Suepag bue.,( rsnlos ue4edn:eu e8nf 8uu,t '{(t\z '(Z)z '(1)z} xetu I d uu8uap stuss nluaUs} "iqts"ig ri6u p 1s3uryr€lru EueJe) 'apou derlesepud rs8ury tepu ue8urqrq8uadue8uaperuesEue,{rse}uesarder t"r(,rnd*"ut iur .re8a1u1ueue.doruad tselntu:o; sPEd (€) ?lepua{ ue8usp tedues (1) elupue;1 : qBIBpeu€{pn$l?urp Suer(u€urusse) 'rut uelqord uu4rcsalsfuour {nlun uu4eun6ry 8ue,{ epoloru unpe erelus ueeurnsol er{uepe lel{tlsur {nlun uerlqepnruarurut tgedas uestlnuad uu3
(6)
(s) (t)
'0Zrx ''Z'l * '0I '" I {nlun 'l > tx ilI rnsotuIp uFa{ npp^r lvotldepeqrel . I u")rIInuIIull^I z
: lqlreq tuEeqas 11s11du1 IselnuuoC ueuelSo$Iad erecesuotsllnllp ledepeduqnSSunsas I uer8eqepedzpe8ue,(re8alq punog us8l4puuqJad uBBuaO puu qruurg uulu{apued ugp ra3a1u1uutuurSorured lsnlos
'S
'lul e1epepedue8uepue4Sutpueqtp ue>p uq8unu uIeI qap rptd leunldo ue>lnlJaruatu nple^\ qrqal 3uz,t €tu€l ledac qrqel nelg 'S usp V 'E'Z'l leq?F€AuB}run ueuun8Sua4 ue}run rsnlosuopedepueur{$un tur luedes 'ue8ueqecuad Eue,( uurpun8rp eue}lDl uulur.rn3rp1tI! I{oluoc epe4 lequuerrus}run ueqrlrued 'E 'e.{rnunlaqas ru1 qe1a1 eEn[ sele seWqqalorodueurerec uu4selatrp '1eulr1do uelnlaqa{8uu,(seleseleqqalo:adlP}u! qo}uoc teltu ueSuepeuresefiure1ru euerure8eg slrellq Iqnuoueru4eptl Euc{ apoun1uns epu4'qqrdrpqe1a1 Euef su1sselsqlellu IrsP8uu.rn4 7967 snlsnEy ZZ - lZ 'euu:1uf 'ctu-repuungselrsJelrun unuoltpnv (ZOOZUlWt6;) uaf1a1ulualsrs uep ralndruoa 's8urpaacor;
8I-d
Dtendingan Antara PendekatanBranch Antl Bound Dan PemrogramanLinear : SebuahContoh Kasus Optimasi
P-19
0 jika job i tidak ada di mesin II.
I Jikajob i adadi mesinm-l untuki = n(m-2)+1 ,n(m-2)+2,' . ., n(m-i)
(r2)
0 jika job i tidak adadi mesinII. da di mesinm jika x;: 0 untuki= I,2,3,. ' . .n(m-l). = variabel yang {igunakan untuk menampung nilai fungsi obyektif. z=X
n (m -l F l
kendala:
r.fcu kerja mesin 1: > IariX j,
untukj=L, . 2 , . . , n
. ( 13 )
untukj:1 , 2 , . . . , n
(14)
kerja mesin m-l: > I Err'-rijX1+1rn-21n , untukj =1,2, " ',n
( l s)
*eltu kerja mesin2:
>2 az:X3* ,
kerjamesinm: > I{ a,n:(l- I4*nti-rl )}, un t u k j= 1 , 2 ,. . . ,n d a ni: 1 , 2 , . . . , m. untukk= l, 2,. . . , (m-l)n . 0,
(16)
&oryuter untuk masalahPemrogramanInteger yang digunakandi sini tidak menyediakan alternatifoptima,sehinggaterpaksahanyadiperolehsebuahsolusisaja. nf Ui" piha( denganmetodeBranchandBoundsemuasolusi altematif optimal dapatdiperoleh Otomatis, karena prosedur penyelesaiannyamemang mengharuskan unfuk I tffiatis. batas atas yang terpilih sebagai kandidat solusi optimal, merupakan nilai optimum yang =&tingga pada al*rir proses perbandinean yang dilakukan secara skematik (menurut akan dapat memastikan predikat global optimum untuk suatu kandidat diagram) tree Bi
jumlah evaluasinilai fungsi padanodePerbandingansecaraskematikmengakibatkan ;1rrmmenjadi jauh lebih sedikit yang bersangkutan fng h"-r dievaluasi pada tee diagram total node yang adapadatreediagramitu.
'6661' t6I-E8I 'dd' '1ol ,,'3u1taau13ug pwsnpuJ lo TnutnoT puoltDuraruJ .. 'qceorddy punog pue t{cueJg eq1., '666I 'raru6 'g'3 tg] 79-19dd'g'qc tS] '9661 'rar*nl)'qrg 'uo4nz1w17do 7oqo73ot uolpnpo4uJ'rcoq1'A pu?'soelepru4'4'lsroH'X '986I ' Vil -;il'dd '7 '1orr't1uoasaY suotlotadglo slouuy .r'uoqvzlurgdg -ra8alq pue l€lJoleurqtuoC,,'pa{uef.i 'd pue €lJs) 'H tVl ' EEZ-E6I'dd' ZI' tlc'gL6| 'acuarcg luotua8euu;41pueSuueaur8ug lergsnpul t{ sallas IIIH-/t\?rg'cIAI qroA map'tlcootddy rlurqtyoslv paruayo-ratdwoc V :qcnasay suot1otadg ol uolpnporlul 'gL6l 'ftllg 'A'C tg]
'rv- 6E'dd't.
qc '886I '{alu$. uqol :arode8uls 'puZ'Zututwot&ot4 nBaTuJpuo nanT to thoaql'-ralf1rqcg 'y 'SI€- €g€'dd'qc'966I'cul uY :qJJoasay suoqotadg',(ptueg '1'y 'leuoqeuraltqll?H-eclluaJd:e:ode8ug'rr;'uolqnpoJtuJ B{B}snd rBlJuq
tZ] tt] 'L
-:.
'e[es pque Fse r?po{es epuduepr"saq qlqol e,(u$ual3ue,{ eqesnuelnpadtp eEnf rto{apueur 3ue,{ reyu ue8uap rsnlos uep l€plpuol uolledepuaul lnlun undneprvr'rgu.raq rsnlos 1eu4do ueledruaur 1uI IeH 'qepueJJllslarSuef lolel lp apou eped uu4snlndtp ueleruaq8ued 8ue,{ nqerrr leEues rsenlele saso.rduellnfueleu {spq nBlBue4nfuelaru 4uun uesqnde>1 rs8ung ledac qrqal ledep Jrqo,(qo 'rs€nlelorp ue4e Suer( apou-apou r$lelasuaur tu€lep €l:ollq urefugadureru uule surdua eSSurqeg eJscesrur leurqdo rsnlos rclru qe>{epuaut?ue,( telu uBL{IIrued'ueuopad ue4pe[p ledup er(utunlsqas uer8eq eped uzun '1eurr1dorsnlos rslru $e>lepuarue,{urc1tu e88urq u€Dllruepas luru4do Isnlos Lr?p]?prpuB{ reEeqasueleunErp 8ue,{ se}e r{E/y\eqsElEq/ sele s?l?q I€ilu uBlruua;;:l;11;l;srrna.r"p e,(urs8un; repu ue?unlrq8uad sasord uaiquaqrp Euef euuru apou nBlB e,(urs8un; te1ruueSunlrq8ued saso.rd uellnfuelp srueq 8ue,{ epou euetu qsllur-qelruratu urel€p nlucquou ue>p IUI lUadas 'uoqod iue.6erp lenqtuatu {nlun u?{Isa1olulP e,{uesetq8ue,( n14ern 1aqe1ueapo4SuadeJec 'enpa;tr 'uoqod urut8elp usp l?nsrl tseluasa:daruapun8Euaru eduel 63uq qtqal 1ar'a1 lerueqSuau eSSurqag 8ue,( apou rp {Blalrat 8ue,{ Euzqec rp apou a4 4ua8raq qepuarol 1ana1ue8uap Suuqeceped 1e1a1.ra1 uup rsFru grqe,{qo ls8unJ tsenleaa8uau ledep PtrD[L{Bpniuue8uaps{etu ue>Fryllp l€dep 1u11eqe11f Euals{ 'eruego6 e ueD{rurepedeEuep,q'ualqord uep leuots8urg ue8uep nluepetrlselsose te,{undruatu apo>1re8uqosueleun8rp 8ue.,{e13ue u,{ropeqas'n}r ureles 'r33ur} qrqal 8ue.{ Euequcle^el ry upz Suef apo4 upud ledupral rlszd qepuar qrqal 8ueqec la^e[ p epe Suef apou eped apo4 e88utq ueplnuapes Jnpln-qsrel BJ€cas ue{ru1€lrp iedep apou detias eped 'apo4 edn-laq 'laq€l ue}:eqruad Ue>II}SBd: ue:1.lnfuetp 'punog pw rlcueJg apoleuruueunS8uad J^q"q-rnq"1"E.r"* qEIe}aS *1qo-rJ n1"nt rsesruqdo rusl€p rsualod:aq e1e,{u-n1 {Fo}Eurquol e uBDIItuopudu8uaur 'g ue€eq rp do13ua1ue8uepue44niun1lpeueture8eqas3-Jff{5 SZpf 1 t{o}uoc eped tuelqLd uel8uupag au€plrurepedeEuau 'punog pue r{cuelg uzle4apuad ue8uap unllesalaslp ne1a1j!P[{5 {Epp efes ]runuoru Z qoluoc eped ualqord 'qoluoc reEeqag'ntl qB[€sBuIqelo qllrulp uplEunurEue,(punog pue qruerg u4urlapuad uederauad rsuelod lur{llar.u 4n1tm uendurelue{ uolnFadrp }Fropqqtuo{ tsesruqdo qel?setu nlens eped punog pu€ qcu?rg uele4epuad ue4eun88uaru ledup 4rgun uurlEuupag '1r1ns1u8ues3uepe4-8uupe{ntl rwlruruoJ ualsrlnuau {nlun luqspud 'nll uelqold{ruun tensos3u?{ i?eull uelrrerSorurod rsBIruruoJqenqes uu:lnrueuaru eueuleSeq qulep? rur u€qspnrue{ ue>ll€BJusrueru 'nDle/d l{3lo }se}€qlp e1p4 4ers3 Suen: eltqude Inlun uape,{eqrp srueq 8ue,( e8:eq unure5l ue8uap) .reaull ueurur8oruad epoletu ueleunSEuou 'ua1mfuerp ]eEuss (e,(uqus1 :a1nduro4 tuer8o-rd ue8uapurmun sreoas{uo}€urquo{ rsesnugdo qelesetuuerzsalafuade/rrl{eq'efuuolpseqtp Euu,(Isnlos :ap{ere>[snurur snld Hep sudapal 'up1egue4leqrlraduraurefirurnlaqas uerSeq eped ueselafua4
uBlndlulsey 7gg7snlm8y ZZ- lT,'ege1u1'uuuupeungselrsJalrunrunuolrpnv (ZOOZ ruatslsueprelnduo;,1's8urpaaco-r4 flltprlg;) uefi1a1u1
'9 0z-d
