trisa dini: 2012

ALGORITMA BRANCH AND BOUND

Metode Branch And Bound diusulakan pertama kali oleh A.H.Land dan A.G.Doig pada tahun 1960. Sebenarnya metode ini dibuat untuk pemrograman linier (linier programming) baik pemrograman linier murni maupun pemrograman campuran. Namun kenyataanya metode ini mampu menyelesaikan permasalahan seperti TSP dan beberapa masalah lain. Pada dasarnya, metode ini merupakan prosedur enumerasi yang efisien untuk memeriksa semua solusi layak yang mungkin. Metode ini menggunakan pohon pencarian (Search Tree), setiap simpul di pohon merupakan representasi dari sejumlah kemungkinan solusi dari TSP. Metode ini hanya dapat digunakan untuk masalah optimasi saja (optimazion problem).

Algoritma Branchand Bound untuk ILP (integer linier programing)

Misalkan diberikan suatu masalah pemrograman bilangan bulat sebagai berikut:

Maksimasi Z = cx

dengan pembatas :

Ax = b

x ≥ 0

xj bilangan bulat untuk j € I

dimana I adalah himpunan variabel bilangan bulat , maka langkah-langkah yang harus dilakukan untuk menyelesaikan masalah tersebut adalah :

· Langkah pertama adalah memecahkan masalah ILP sebagai LP dengan mengabaikan pembatas bilangan bulat (bounding). Kemudian misalkan masalah LP dinyatakan sebagai LP-1 yang mempunyai nilai optimal dari fungsi tujuan Z1.

Ø PL-1

Maksimasi Z = cx

dengan pembatas

Ax = b

x ≥ 0

jika solusi optimal dari LP-1 mengandung beberapa variabel bilangan bulat yang mempunyai nilai pecahan, maka solusi optimal bilangan bulat untuk ILP belum diperoleh dan Z1 menjadi batas atas (upper bound) dari nilai maksimum Z untuk ILP.

· Langkah berikutnya adalah mempartisi daerah layak dari LP-1 dengan mencabangkan (branching) salah satu variabel bilangan bulat yang nilainya pecahan.

Misalkan variabel xj dipilih untuk dicabangkan dengan nilai pecahan βj dalam LP-1. Kemudian dibuat dua masalah pemrograman linier baru, LP-2 dan LP-3 dengan memasukkan masing-masing pembatas baru xj ≤ [β] dan xj ≥ [β]+1 dan selesaikan kedua permasalahan hingga diperoleh x1,x2,dan z yang baru dari masalah tersebut :

Ø PL-2

Maksimasi Z = cx

dengan pembatas

Ax = b

xj ≤ [β]

x ≥ 0

Ø PL-3

Maksimasi Z = cx

dengan pembatas

Ax = b

xj ≥ [β]+1

x ≥ 0

· Lakukan poin dua hingga hingga semua node dalam kondisi fathomed. Fathoming suatu node (masalah LP) terjadi jika:

a. Solusi optimal LP merupakan bilangan bulat (tidak terdapat lagi bilangan pecahan). dan nilainya lebih besar dari nilai solusi optimal sebelumnya yang semua variabelnya adalah bilangan bulat (jika ada)

b. Masalah LP adalah tak layak (terjadi ketika salah satu atau kedua variabel masih mempunyai nilai pecahan, namun z nya lebih kecil daripada z sebelumnya)

c. Nilai optimal Z dari masalah LP tidak lebih baik daripada batas bawah (lower bound) saat ini.

Contoh kasus yang diselesaikan dengan metode branch and bound :

v Deskripsi masalah

Sebuah home-industry tekstil “NUYS COLLECTION” membuat dua macam produk tekstil yang sering digunakan masyarakat dewasa ini, yaitu kemeja dan kaos. Dalam home-industry tersebut, kemeja dan kaos harus melalui 4 workstation agar dapat menjadi produk jadi, yaitu:

Ø Workstation 1 : pemotongan kain dan pembuatan pola

Ø Workstation 2 : penjahitan

Ø Workstation 3 : pressing dan pemeriksaan (quality control)

Ø Workstation 4 : pengemasan

Pemilik home-industry tersebut memiliki 4 operator dan masing-masing operator menangani 1 workstation. Pemilik mengalokasikan waktu kerja per hari sebanyak 10 jam yang dimulai dari pukul 08.00 hingga pukul 18.00. Sistem kerja yang diterapkan pada home industry tersebut merupakan sistem kerja seri, yang artinya proses kerja tersebut dilakukan secara berurutan yang dimulai dari workstation 1 dan berakhir di workstation 4. Pemilik menerapkan waktu kerja per shift, yang dimaksudkan bahwa workstation 1 akan mendapatkan shift pertama, workstation 2 akan mendapatkan shift kedua, dan seterusnya. Pemilik menetapkan shift per hari untuk 4 workstation seperti dibawah ini :

Ø Shift 1 (Workstation 1) : pukul 08.00-09.30

Ø Shift 2 (Workstation 2) : pukul 09.30-13.00

Ø Shift 3 (Workstation 3) : pukul 13.00-16.00

Ø Shift 4 (Workstation 4) : pukul 16.00-18.00

Kapasitas produksi untuk kemeja dan kaos per harinya dalam home-industry tersebut adalah 200 buah dan 120 buah. Produk kemeja dan kaos tersebut memiliki waktu proses per produk yang berbeda-beda disetiap workstation seperti yang tertera pada Tabel 3.1.

Tabel 3.1.

Workstation	Waktu yang dibutuhkan (menit)		Waktu tersedia per shift (menit)
Workstation	Kemeja	Kaos	Waktu tersedia per shift (menit)
1	0,45	0,5	90
2	1,05	0,45	210
3	0,9	0,45	180
4	0,6	0,5	120

Pemilik menetapkan harga jual kemeja sebesar Rp.35000 dan kaos sebesar Rp.40000. Pemilik akan mengambil profit sebesar 45% dari harga jual kemeja dan 50% dari harga jual kaos, sehingga keuntungan yang didapat sebesar Rp.15750 untuk satu kemeja dan sebesar Rp.20000 untuk satu kaos. Berapa kemeja dan kaos yang harus diproduksi setiap harinya agar home-industry tekstil tersebut memperoleh keuntungan yang optimal?

v Model matematika

Definisi :

X₁ = Jumlah Produksi Kemeja

X₂ = Jumlah Produksi

Fungsi Tujuan :

Memaksimasikan Z = 15750 X₁ + 20000 X₂

Pembatas :

0.45 X₁ + 0.5 X₂ ≤ 90

1.05 X₁ + 0.45 X₂ ≤ 210

0.9 X₁ + 0.45 X₂ ≤ 180

0.6 X₁ + 0.5 X₂ ≤ 120

X₁ ≤ 200

X₂ ≤ 120

X₁ , X₂ ≥ 0

v Penyelesaian menggunakan metode branch and bound

Jadi, berdasarkan data yang telah diperoleh dari studi lapangan Home Industry teksil “NUYS COLLECTION” bahwa jumlah optimum yang harus diproduksi oleh perusahaan tersebut adalah kemeja sebanyak 70 kemeja dan jumlah kaos sebanyak 117 kaos dengan total keuntungan maksimal sebesar Rp3.442.500.

v Rincian hasil Branch and Bound Setiap Percabangan

- LP 1