Branch and Bound

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)
	Kemeja	Kaos
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

 -          LP 2

-          LP 3

-          LP 4

-          LP 5

- LP 6

- LP 7

- LP 8

- LP 9

- LP 10

- LP 11

- LP 12

-LP 13

cost volume profit analysis

Analisis Cost Volume Profit

a.      Pengertian Analisis Cost Volume Profit

Menurut Hansen & Mowen (2005:274) ”Analisis biaya-volume-laba (cost-volume-profit analysis) merupakan suatu alat yang sangat berguna untuk perencanaan dan pengambilan keputusan”. Sedangkan menurut Garrison, dkk (2006:322) ”Analisis biaya-volume-laba adalah satu dari beberapa alat yang berguna bagi manajer dalam memberikan perintah”.

Alat ini membantu manajemen suatu perusahaan untuk memahami hubungan timbal balik antara biaya, volume dan laba organisasi dengan memfokuskan pada interaksi antarlima lima elemen berikut: harga jual produk, volume atau tingkat aktivitas, biaya variabel per unit, total biaya tetap, dan bauran produk yang dijual.

Menurut Garrison, dkk (2006:350), ada beberapa asumsi yang mendasari analisis cost volume profit yaitu:     

1. Harga jual konstan. Harga jual produk atau jasa tidak berubah ketika volume berubah.

2. Biaya adalah linear dan dan dapat secara akurat dibagi menjadi elemen variable dan tetap. Elemen variable adalah konstan per unit dan elemen tetap adalah konstan secara total dalam rentang yang relevan.

3. Dalam perusahaan dengan berbagai produk, bauran penjualan adalah konstan.

4. Dalam perusahaan manufaktur, persediaan tidak berubah. Jumlah unit yang diproduksi sama dengan jumlah unit terjual.

b.      Margin Kontribusi

Margin kontribusi menurut Garrison, dkk (2006:324) adalah “jumlah yang tersisa dari pendapatan dikurangi beban variabel”. Margin kontribusi merupakan jumlah yang tersisa untuk menutup biaya tetap dan memberikan keuntungan. Margin kontribusi juga dapat disajikan dalam bentuk persentase. Hansen & Mowen (2005:280) menyatakan bahwa rasio margin kontribusi (contribution margin ratio) adalah bagian dari setiap dolar penjualan yang tersedia untuk menutup biaya tetap dan menghasilkan laba. Adapun rumus rasio margin kontribusi adalah:

      Contoh soal :

PT. CLADTEK INTERNATIONAL

Laporan Laba Rugi Kontribusi

Per 2006

Total		Per Unit		Persentase Penjualan
Penjualan (400 unit)	Rp 100.000		Rp 250	100%
Beban variable	60.000		150	60%
Margin kontribusi	40.000		Rp 100	40%
Beban tetap			35.000

Perhitungan rasio margin kontribusi adalah sebagai berikut:

         

c.       Analisis Titik Impas

Menurut Garrison, dkk (2006:325) ”Titik impas adalah tingkat penjualan dimana laba adalah nol”. Jadi dapat dikatakan bahwa titik impas merupakan titik di mana biaya dan pendapatan sama besarnnya sehingga tidak terjadi laba maupun rugi. Analisa terhadap titik impas ini digunakan untuk menentukan tingkat penjualan dan bauran produk yang diperlukan agar semua biaya yang terjadi dalam periode tersebut dapat tertutupi.

Titik impas dapat dihitung dengan menggunakan metode persamaan (equation method) dan metode margin kontribusi (contribution method).

1.      Metode Persamaan

Metode persamaan menggunakan data-data dari laporan laba rugi yang disusun dengan format kontribusi. Format laba rugi dapat disajikan dengan persamaan sebagai berikut:

Laba = (Penjualan – Beban Variabel) - Beban Tetap

Persamaan tersebut dapat diubah menjadi:

Penjualan = Beban Variabel + Beban Tetap + Laba

Contoh soal :

PT. CLADTEK INTERNATIONAL

Laporan Laba Rugi Kontribusi

Per 2006

Total		Per Unit		Persentase Penjualan
Penjualan (400 unit)	Rp 100.000		Rp 250	100%
Beban variable	60.000		150	60%
Margin kontribusi	40.000		Rp 100	40%
Beban tetap			35.000
Laba besih			Rp 5.000

Penjualan = Beban Variabel + Beban Tetap + Laba

X = 0,6X + Rp 35.000 + Rp 0

                    0,4X = Rp 35.000

                    X = Rp 87.500

di mana:

X = Total penjualan

          0,6 = Rasio beban variabel (beban variabel + penjualan)         

           Rp 35.000 = Total beban tetap

          Titik impas dalam unit yang terjual adalah sebagai berikut:

          Rp 87.500/Rp 250 per unit = 350 unit.

2.      Metode Margin Kontribusi

Metode margin kontribusi pada dasarnya hanyalah versi jalan pintas dari metode persamaan yang telah dijelaskan. Pendekatan ini memusatkan pada ide bahwa setiap unit yang terjual memberikan margin kontribusi tertentu yang dapat digunakan untuk menutupi biaya tetap. Untuk menentukan berapa unit yang harus dijual untuk mencapai titik impas, total biaya tetap dibagi dengan margin kontribusi per unit.

Dalam contoh di atas, perhitungan titik impas dengan mengguanakan metode margin kontribusi adalah sebagai berikut:

d.      Analisis Target Laba

Target laba juga dapat dihitung dengan menggunakan metode persamaan (equation method) dan metode margin kontribusi (contribution method).

Berdasarkan contoh sebelumnya, misalkan target laba yang ingin dicapai perusahaan adalah Rp 40.000. Maka jumlah penjualan total yang harus dicapai adalah :

                          

Jadi target laba dapat dicapai dengan menjual 750 unit per bulan, yang berarti dalam total penjualan berjumlah Rp 187.500 (Rp 250 per unit x 750 unit).