dalamAnallslsKuantltatif Pokok-pokokPemrogramanMetodeCabang-batas
Pokok-pokok PemrogramanMetode Cabang-batasdalam Analisis Kuantitatif Ir. Drs.\[ae/u'lung*
Abstract Broncfi.4oundtecfuiqwk tfu nsst simpbttutfud h quantitatiaeana[ysisoppficatiotts in round ftnearprogrannning(inugerprogrmning), flesidestfu possiiifrry to utifize tfu metfiot n oifur oppfiron* sttcft-asassgimentpro6{ems.'tfikartbtc {iscussestfu 6asbprogrCIrnniag co[cfor tfie algoritfunof tfioseauopro6(mu.
Pendahuluan alammenyelesaikansoalpenugasanadasuatualgoritmayang sering digunakan yaitu sederetanlangkahHungarian : 1. Kurangi setiapkolom dari nilai terkecilnya. 2. Kurangi setiapbaris dari nilai terkecilnya. 3. Tarik garis pada setiapbaris/kolom denganmemprioritaskan baris/kolom yang mengandungnilai-nilai nol terbanyak. 4. Jikajumlah garis = ukuran matriks ( n ), maka solusioptimal tercapai dan bisa dilakukan alokasi,jika tidalq lakukan langkahberikutnya. .
r
5. Jikajumlah garis < n , kurangi setiapelemenyang tidak tergaris dengan elemen terkecil yang tidak tergariq yang tergaris sekali tidak ikut dikurangi, yang tergarisdua kali justeru ditarnbahkan. Perhatikan bahwa matriks harus berbentuk bujursangkar.Jika perlu tambahkankolom/baris yang elemennyanol semua(dummy\agar berbentukbujursangkarberukuran n x n.
StafPengajarTetap Fakultas TeknikUKRIDA,dansaatini sedang mengikuti Sarjana ProgramPasca Ilmu Komputerdi Universitaslndonesia.
Meditek
13
*
dalamAnallsls Pokok-pokokPemrogramanMetodeCabang-batas KuanUtatlf 6. Kembali ke langkah 3, sampaidapat dilakukan pengalokasian. Catatan : Untuk fungsi tujuan maksimum semuaelemennyadikalikan harga negatif, sedangkancaranyasama. Supayamemahamipenggunaanlangkah-langkahdi atas,makadisajikan contoh sebagaiberikut : Suatu perusahaanyang menghasilkanprodukconsuma goodsmemiliki 5 pramuniaga(A, B, C, D dan E) yang ditugaskanke wilayah \,2,3, 4, dan 5. Kelima pramuniaga bertugas ke satu area pemasaran.Setiap pramuniaga akan memerlukan biaya untuk pemasaranseperti teqgambardalam tabel berikut ini : Area Pemasar:iln ke a0
cl
H
Dari A B C D E
2
1
3
4
5
7
1,1,
10
759811 9
12
85469 73695 467511 Gambar 1
Penyelesaiandimulai denganmengambilnilai terkecildari setiapkolom sebagaielemenpengurangdi kolomnya,sehinggaakan didapat: Area Pemasaran
c! 0!
F E
ke
1
z
3
4
5
Dari A B C D E
3 5 4 3 0
2 9 2 0 3
5 3 0 2 3
3 6 1 4 0
6 5 4 0 6
Gambar 2
14
Meditek
+
pokok-pokokPemrogramanMetodeCabang-batas dalamAnallslr Kuantltatlf Kemudian diambil nilai terkecil dari setiap baris sebagai elemen pengurangdi barisnya. Area Pemasatan
G'
o0 G
tr
tr
ke
1
2
3
4
5
Dari A B C D E
1 2 4 3 0
0 6 2 0 3
3 0 0 2 3
1
4
3
z
4
0
0
6
Gambar 3 Karenajumlah garishanyaempatmaka diambil nilai terkecil yangtidak dilalui garis (nilai 1), kurangi yang tidak terkenagaris,yang terkenasekali tidak dikurangi dan yang terkenadua kali ditambahkannilai ini (nilai 1). Area Pemasatan
00
G t-
Er
ke
1
2
3
Dari A B C D E
0 1 3 3 0
0 6 2 1
0 0 3
4
4
4
2 0 4 0
5
3 1 3 0 6
Gambar 4
Alokasi diambil denganprioritas baris yang hanyamemPunyaisatunol terlebih dahulu, dalam hal ini 83 dan D5 kemudiandiambil C4 atauE1 atau A2 terlebih dahulu. Dengan demikian solusi optimal didapatkan sebagai berikut: A harusditugaskanke area2(A-2),8-3,C-4,D-5,dan E-1(supaya biaya seminimalmungkin).
Meditek
15
dalamAnallsls Pokok-pokokPemrograman MetodeCabang-batas Kuantitatlf
Metode Cabangbatas Metode ini dimulai dengan membentuk batas atas (uVpa-bounil) ZV = + o. Terdapat 5 ! = 120 kemungkinan dari perjalanan yang layak (feasble)bagi kelima pramuniaga tadi. Kemudian kita membentuk batas bawah (Iouterbound),yaitu dengan mengambil nilai terkecil dari setiap kolom dan dijumlahkanZt= 4+3+4+5+5= 21 (lihat Gambar1). Kita buat iterasi pertama berdasarkan urutan batas bawah dengan dimulai dari urutan awal :
z
=
7 + 3 + 4 + 5 + 5 = 2 4 ( t i d a k l a y a k/ T L ) A-1
= B-1
9 +3+4+5+5=%(lL) B-1
c-1
= _8 +3+6+5+5=27(fL) c-1
A-1
z Z
z
=
Z
= _4, +3+4+6+5=22(fL) E-1
D-1 E-1
7 +5+4+5+9=30OL) D-1
Ternyata dari Zt = 21,tanPamemperhatikanadanyaPenggunaanbaris yang samatidak dapat dibuat penyelesaianyang layak. Hasilnya dapat dibuat menjadi diagram pohon (Gambar 5) sebagai berikut: Iterasi Pertama dari Teknik Cabang batas
24 (tid^k layak) 26 (tidaklayak) jawab layak
@rr(tidak zt= 2l
@ro
(Tidak hyak)
layak)
(tidaklayak) (tidak layak)
Gambar 5
16
Meditek
+
Pokok-pokokPemrogramanMetodeCabang-batas dalamAnallslsKuantltatif Padaiterasi yang kedua kita mulai lagi denganmembuatZg yang baru (sebelumnyadipilih a o) yaitu denganmenghindarkanpenggunaanelemen pada baris yang sama,dan dengansyaratZrs Zubaru. Z
Z u7
Z
= I-A-1,B-2
r,A-t,c-z
LA-l,D-z
I-A-I,E-Z
7 + 12 +4+5+5=33(Layak/L) A_1 B_2
= 7 A-1 -
Z + nl
=
+
5 c_2
3 D_z
7 + 6 E-z A_1
+6+S+S=28(IL)
+
+4+5+9=2BCIL)
+4+6+5=28(tL)
Juga ki ta pi lih batasbawah yang b aruZt(sebel u mny a 21 dan ti d ak Iayalg karena adanya penggunaan elemen pada baris yang sama) dengan menggunakanacuanbatasatasyang layak yaitu mengkombinasikandua elemenpertama,sertamenghindarkanpenggunaanelemenpadabarisyang sama. 7 'tgl.
9 + 5 +4+5+5=28(L) B-1 A_2
' a-z
9 + S +6+5+5=30(TL) B-1 B_2
LB-L,C-Z Z
Z
=
9 + 3 +4+5+9=30(IL) B- r D_2
=
9 + 6 +4+6+5=30(tL) E-2 B_1
LB-.,D-'
LB-1,E-2
Karenabatasbawah yang baru adalah 28 dan merupakan jawab layak serta lebih kecil dari batas atas (28 < 33) maka 28 akan menjadi batas atas yang baru. Terdapat24 penyelesaianyang layak yang bukan merupakan jawabnya termasuk A-1, B-2 ; A-1, C-2 ; A-1,D-2 ; dan A-1, E-2. Sekarang akan dicari jalan lain dimulai dari C-1.
Meditek
17
dalamAnallsls Pemrograman MetodeCabang-batas Pokok-pokok Kuantltatlf Z Z
= 8 + 5 +6+5+5=29(IL) LC-L,A-Z c_l A-2 =8 LC-1,B.-2
+
72+6+5+5=35(fl.) B-2
c_l
=
8 c-l
+
LC-I,D-? 7 'LC-L-E-2 '
8 c_l
+ 6 +6+8+5=33OL) E_2
Z
3 +7+5+10=33(IL) D_2
*
Dengan memperhatikan batas bawah dan batas atas yang tidak layak maka kombinasi jalan di atasdiabaikan.Lebih lanjut kita perhatikan,kita tidak melakukan pekerjaanpada D-1 dan kombinasi tugas dua karena akan menghasilkan batas bawah yang terbaik sebesar30 dan tidak layak. Langsung saja kita lakukan pekerjaan pada E-l dan kombinasi tugas dua yaitu: = Z__. LF.I, A-2
4
+
tr-t
5
+4+6+5=U(lL)
A-2
= Z-_,_^ LB1.' B-2
4 + 72+4+5+5=31(IL) E-1 B-z
Z__, _^ = LF-l.C-2 '
4 + 5 +6+8+5=28(II-) E_l C_2
Zrur.o-, '
=
4 E-r
+
3
+4+6+9=260Jr)
D-z
Dalam kombinasi di atas terdapat dua penugasanyang mempunyai hargadi bawah batasatasyutn (?tldan26di bawah 28).Sudahtentu Z dan Zi tidak langsungmenjadi batasataskarenatidak layak.
18
Meditek
Pokok'pokokPemrogramanMetodecabang-batardalamAnallelr Kuaniltafif Iterasi kedua ini dapat dilihat pada diagram pohon di bawah ini (gam_ bar 6). Iterasi kedua metode cabang-batas OS
)
28CrL)
OC D
28 (fL)
Or
28Cr-)
28(L)
oA
9 c
a0@-)
33-A 33&l ze(TL) Xs
36Cn-)
oc a3cn) D 33Cn-)
@o @) 6.nugasan2) z4(n-) _OA
o<.Si ;;&l -O
D
z6(TL)
1 Gambar 6 Sekarangkita mempunyai dua penugasanyang Zt < Zu = 2g yaitu :
Z Z
t*r, o-, LF-I,D-2
= vL =)fi
untuk iterasi y.angketig"_Ftu-gunakan kombinasi dua jalan di atas , dengan kombinasi tugas 3. Kombinasi E-1, A-2 dengan tugas 3 dapat dibuat: = Z LE I,A-2,8-3
Meditek
4 + 5 +7+6+5=27(L) E_l A_2 B_3
19
Pokok-pokok Pemrograman MetodeCabang-batas dalamAnallsle Kuantltatlf Z
=
4
LE.L,A-Z,C-3 E_1
Z
= 4
LF-I,A-Z,D-3 E-l
+ 5 +4+9+5=Z7W) A_2 C-3
+ 5 +6+6+9=30(n") A_2
= Z7 adalah jawab layalq maka dapat kita Karena 4yyA-2,L-3 tentukan sebagaibatas atasyang baru menggantikan yang lama (28). Untuk kombinasi E-7,D-2 dengantugas3 dapat dibuat: *
= 4 + 2 +9+6+9=30(IL) Z LE.I,D-Z"L-3 E-1 D-2 A-3 = 4 + 2 +7+6+9=28(IL) Z LF-I,D-2,8-3 E-l D-Z B_3 = 4 + 3 +4+8+10=29(L) Z LF-I,D-Z,C-3 E-l D-Z C-3 Karena batas atas yang baru adalah 7/ mak,asetiap batas bawah y"ng lebih besar dariZT diabaikan, sehinggadidapat jawab yang layak (E-7, A-2, B-3, C4, dan D-5) yang paling optimal.
20
Meditek
Pokok'pokokPemrogramanMetodeCabang-batas dalamAnailsleKuanfltaflf Iterasi ke tiga metode cabang-batas O:
33(L)
.C)- 28Crr-) C D 28Cr,) o E 28(rL)
c)A a&) 6 c a0Gr.)
33 33&) c
29 (lL)
CTT-)
2) B 27e) O ro gn;(Renugasan ,O 27(tr-) 6 A za ltr:('\ Ct c 30(n-) G\ : ,,,8 31CrLi Oo
\-5c
\5p
2scn-) OA ]o(rrl
26(rL)<83 #t)
Gambar 7
Metode Cabang batas untuk integerptogramming Metode.cabang batasdapat.digunakan juga untuk menyelesaikan persoalanall-integer vogramminr(programlinearbulat semuiya"r, ^ioi-intega yo grammin g (programIi nearbulat sebagian). Sebagai contoh: M a k s i m u mka n Z -8 xr+6 xz denganfungsikendala2xr + Sxzs lZ 8xr +3xzs\Z Xt, X2> 0, Xt,Xz integer
Meditek
21
*
Pokok-pokokPemrogramanMetodeCabang-batardalamAnallslr Kuantltatlf DarijawabanlineardidapatkanX1=2 | a"n xz=2: dengan Zmak= 8.21 * 6. Z!= UsebagaiZu 25
Jikajawab dibulatkan akan didap?t x1 = 2danx2= 2(bulatkan ke bawah untuk soal maksimum, bulatkan ke atas untuk soal minimum) sehingga Z = 8.2 + 6.2 = 28 sebagu Zt. Sebutanini akan berbalik untuk soal minimum.
Zu=34 zL=23
Xts 2
=34
tl
l0
_)
1qg
Xt.3
zrL
(11,4
z.2t Z.rl trl, rl ) -) [mekslmunl Y*. g
Gambar 8 Hasil intega optimal adalah Z = 30 yaitu untuk X1= 3 dan Xz='1. Padacontoh lain : MinimumkarrZ = 10 Xr + 5 Xz denganfungsi kendala
3 Xr + 6Xz . 12 3 X r +X z " 9 Xt ,Xz. O Xr, Xz integer
22
Meditek
Pokok-pokokPemrogramanMetodeCabang-batardalamAnallslr Kuantltaul Dari jawablineardidapatkanXr=2!, Z 6ir.= 19' 2
!+
*r=
3
dengan
5' I = 31 sebagaiZl-
/;11= 19.3 + 5. 1 = 35 (untuk soalminimumkan dilakukan pembulatan ke atas)
Xts 2
XL=2,8 X2 = 0,6
zt=31 Zv=35 =31
Xr.3 15 -11= [0,9f -)2. {9 11,01 - 3l [Z.8iOCI-rZ [mlnlmuml = 3 5 Z
Z= 40 Z =35
Gambar9 Didapatkan hasil integeryang optimal adalahZ = 35 yaitu untuk X p 2dan X2 = 3 atauX t= 3dan Xz= 1
Penutup Pada dasarnya metode cabang batas'dapat diringkaskan sebagai berikut : . Langkah inisialisasl, dimulai dengan sekumpulan himpunan penyelesaianpada pengertian (termasuk penyelesaiantidak layak yang tidak dapatdieliminasi)hanya"himpunan tinggal",buat Z = +o.
Meditek
23
Pokok-pokokPemrogramanMetodeCabang'batasdalamAnallsls Kuantltatlf . Langkah cahang, untuk setiap himpunan yang baru mengandung batasbawahZl-pada harga dari fungsi sasaranuntuk penyelesaian dalam himpunan. . Langkah pengukuraz,untuk setiaphimpunan yang baru, di luar dari pengertianuntuk:
" zL> zv " Himpunan yang ditemukanmengandungpenyelesaiantak layak " Penyelesaianlayak yang tepatdalamhimpunandapatdiidentifikasi jik^ZL < Zu kemudiansimpan sehubungandenganfungsisasaran, penyelesaianini sebagaipenyelesaian"berkewajiban"dan kembali ke kondisi 1 untuk himpunanyang sisa Aturan berhenti,hentikanprosedurketika tidak adalagi himpunan yang sisa,dan penyelesaianyang sekarangadalahpenyelesaianyang optimal. Penggunaan Metode cabang batas dalam integeryogramming dengan denganpembulatandi sekitarnilai optimal yang tidakbulat, cabang-cabang tidakbulat dijadikan Zu untuk persoalanmaksimal,dan optimal yang nilai Zl untuk persoalanminimal. Sedangkanuntuk Zt persoalanmaksimal digunakan pembulatan ke bawah, danZv persoalanminimal digunakanpembulatanke atas. Cabang-cabangyang terbentuk dengan pembulatan dari nilai-nilai xr dan xz terdapat dalam daerahyang layak. Hasilnya baik xt , xz haruslah bulat dan memenuhi kriteria persoalan.
Kesimpulan 1. Metode cabang batas dapat mempercepatpengerjaanpersoalan penugasan,dan mudah untuk memeriksanya. 2. Dalam integeryogramming, metode ini jauh lebih sederhanauntuk dipahami dibandingkan metode lainnya (Cutting plane atau ailditiaezeroone).Persoalandengan banyak variabel akan menghasilkanpercabangan yangbanyak juga.
24
Meditek
Pokokpokok PemrogramanMetodeCabang-batardalamAnallsl: Kuantltatlf
Kepustakaan ilrcisions, 1. Bierman, Bonini, Hausman., Quantitatiueanalysbfor Business 7th edition,Irwin Topan1985 2. Garfinkel, Robert and GeorgeL Nemhau*r,lnteger Programming,John Wlley & Son,Inc,New yorkll/L 3. Markland, Robert 8., Topbsk ManagetnentSciene,Jotrn- Wlley & Son, New York 1979 4. Taha,Hamdy A., Oryratbn Rewrch an inffiuctbn,4th edition Macmillan Publishing Company,New York 1987. 5. Zionts 5., Linearand lntegr Programming,Englewood Cliffs, Prentice Hall Inc, NewYork 1974.
Meditek
25
+
