## INTEGER PROGRAMMING DENGAN PENDEKATAN METODE BRANCH AND BOUND GUNA MENGOPTIMALKAN JUMLAH PRODUK DENGAN KEUNTUNGAN MAKSIMAL
“ Studi Kasus pada Perusahaan Furniture PT. PUTRA JEPARA ”

## Adnan Sauddin
Jurusan Matematika, Fakultas Sains dan Teknologi, UINAM Adnan.sauddin@uin-alauddin.ac.id
Wahyuni Abidin
Prodi Matematika, FST-UINAM Kiki Sumarni Mahasiswa Jurusan Matematika UIN Alauddin Makassar
Info:
Jurnal MSA Vol. 3 No. 1
Edisi: Januari – Juni 2015 Artikel No.: 7 Halaman: 45 - 52 ISSN: 2355-083X Prodi Matematika UINAM

## ABSTRAK
This paper discussed about optimization of the number of products with maximum profit. PT. Putera Jepara is a company that produces furniture products with finishing processes. Problems in a furniture company usually requires an integer solution to be realistic. The method used to optimize the number of products with maximum profit was the integer programming that included methods such as Branch and Bound. Branch and Bound method is the optimal solution of linear programming which resulted in the decision variables numbers. This study aimed to analyze the amount of products, which were manufactured by PT. Putera Jepara as the furniture company with a maximum cost-owned company within the available time per month. A large number and types of products that can  provide optimum gain (maximum) with a branch method is to produce as much as 2 units of wardrobe, 46 sets of dining table, 2 units of cupboard and 1 unit of chair.
Kata Kunci: Simplex method, branch and cut method

## 1. PENDAHULUAN
Persaingan dunia usaha dalam mempengaruhi pandangan pelanggan merupakan hal yang penting untuk dapat survive dalam mengikuti irama bisnis yang terus berkembang. Salah satu factor penting dan utama untuk dapat survive adalah kualitas produk atau  layanan yang dihasilkan. kualitas produk dapat diperoleh dengan melakukan serangkaian kegiatan produksi secara efektif dari sisi pemanfaat seluruh sumber daya yang dimiliki dan hal tersebut dapat berpengaruh pada efisien penggunaan sumber daya keuangan.
Rangkaian kegiatan untuk mendapatkan kombinasi penggunaan sumber daya yang sesuai dengan kebutuhan produk dilakukan dengan cara memilih kombinasi sumber daya yang menghasilkan hasil yang optimal. Langkah demikian dikenal dengan proses optimasi, yaitu serangkaian kegiatan dalam mencari penyelesaian terbaik. Penyelesaian terbaik tidak selalu indentik dengan keuntungan yang paling tinggi akan tetapi cenderung pada
memaksimumkan keuntungan, atau tidak selalu berkaitan dengan biaya terkecil. Terdapat tiga hal penting dalam proses optimasi, yaitu tujuan, alternative keputusan dan sumber daya yang terbatas.
Dalam ilmu matematika, optimasi proses dilakukan dengan bantuan teori linear programing. Akan tetapi kebanyakan hasil yang diperoleh memberikan nilai yang memuat angka decimal, nilai tersebut sulit untuk diterapkan pada suatu permasalah jumlah produk yang dihasilkan, seperti produksi elektronik, Furnitur, dll, dimana produk yang seperti ini, sebagaimana dimaklumi selalu genap-atau utuh-sebuah meja;sebuah computer,  atau dikenal dengan bilangan bulat (integer) dalam ilmu matematika.
Salah satu alternative penyelesaian optimasi yang menghasilkan solusi integer adalah integer programming. Merupakan suatu pemodelan matematis yang memungkinkan menghasilkan solusi bulat. Salah satu metode yang dikenal adalah Brand and Bound. Pada artikel ini akan membahas bagaimana menentukan solusi
Jurnal MSA Vol. 3 No. 1 Ed. Jan-Juni 2015
optimum dari suatu perusahaan meuble dengan menggunakan metode Branch and Bound dengan tujuan menentukan jumlah setiap produk yang layak.

## 2. TINJAUAN PUSTAKA Program Linear
Model merupakan suatu penyederhanaan dari permasalahan yang kompleks menjadi lebih sederhana. Ada beberapa klasifikasi model dalam riset operasi, yaitu model ikonik, model analog dan model matematik. Adapun tahapan dalam riset operasi yaitu:
1. Merumuskan masalah Hal ini menggambarkan permasalahan yang sedang dihadapi perusahaan. Dalam perumusan masalah ditentukan variabel keputusan (apa yang dapat dikendalikan perusahaan melalui sumber daya yang ada), tujuan (menentukan dari variabel keputusan yang ada, apakah akan memaksimumkan laba, meminimumkan biaya, dan lain-lain), dan kendala (pembatas-pembatas yang dihadapi perusahaan untuk mencapai ntujuan tersebut, misalnya mesin, tenaga kerja, bahan baku dan lain-lain).
2. Membentuk model matematis Dari permasalahan yang ada dibuat dalam model matematis untuk membuat permasalahan lebih jelas dan dimengerti dalam mengetahui hubungan yang saling terkait.
3. Mencari penyelesaian masalah Dari alat analisis yang ada pada riset operasi dipilih alat mana yang digunakan untuk memecahkan masalah tersebut.
4. Menguji Model Merupakan proses pengecekan apakah model tersebut telah mencerminkan dari apa yang diwakili. Model ini digunakan sebagai dasar pengujian validitas dengan membandingkan hasil masa lampau dengan hasil masa kini dan harus memberikan hasil yang sama.
Metode analisis yang paling bagus untuk menyelesaikan persoalan alokasi sumber ialah metode program linier. Pokok pikiran yang utama dalam menggunakan program linier ialah merumuskan masalah dengan jelas dengan menggunakan sejumlah informasi yang tersedia. Sesudah masalah terumuskan dengan baik, maka
langkah berikut ialah menerjemahkan masalah ini ke dalam bentuk model matematika, yang terang mempunyai cara pemecahan yang lebih mudah dan rapi guna menemukan jawaban terhadap masalah yang dihadapi.
Pemrograman linier menggunakan model matematika untuk menggambarkan suatu masalah. Sifat linier di sini berarti semua fungsi matematika harus berupa fungsi linier.  Kata pemrograman di sini bukan berarti program komputer, melainkan perencanaan. Pemrograman linier meliputi perencanaan aktivitas untuk mendapatkan hasil maksimal, yaitu sebuah hasil yang mencapai tujuan terbaik (menurut model matematika) di antara semua kemungkinan alternatif yang ada.
Dalam membangun model akan menggunakan karakteristik-karakteristik yang biasa digunakan persoalan programan linier, yaitu:

## a. Variabel Keputusan
Variabel  keputusan adalah variabel yang menguraikan secara lengkap keputusan- keputusan yang akan dibuat. Variabel keputusan dituliskan dengan, 𝑥𝑥 𝑗𝑗 , 𝑗𝑗 = 1, 2, … , 𝑛𝑛 . .
b. Fungsi tujuan
Fungsi tujuan merupakan fungsi dari variabel keputusan yang akan dimaksimumkan (untuk pendapatan atau keuntungan) atau diminimumkan (untuk ongkos).
c. Pembatas/Fungsi kendala Pembatas merupakan kendala yang dihadapi sehingga kita tidak bisa menentukan harga- harga variabel keputusan secara sembarang.
d. Pembatas tanda Pembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusannya diasumsikan hanya berharga non-negative atau variabel keputusan tersebut boleh berharga positif, dan nol.
Bentuk umum fungsi linier; 𝑍𝑍 = ∑ 𝑐𝑐 𝑗𝑗 𝑥𝑥 𝑗𝑗 𝑛𝑛 𝑗𝑗=1 ; 𝑥𝑥 𝑗𝑗 , 𝑗𝑗 = 1,2, … , 𝑛𝑛 Dengan batasan;
∑ 𝑎𝑎 𝑖𝑖𝑗𝑗 𝑥𝑥 𝑗𝑗 𝑛𝑛 𝑗𝑗=1 ≥≤ 𝑏𝑏 𝑖𝑖 , untuk 𝑖𝑖 = 1,2,3, … , 𝑛𝑛 .

## Metode Simpleks
Metode simpleks ialah suatu metode yang secara matematis dimulai dari suatu pemecahan dasar yang fisibel ke pemecahan dasar yang fisibel (feasible) lainnya dan ini dilakukan berulang-ulang (dengan junlah ulangan yang terbatas) sehingga akhirnya tercapai suatu pemecahan dasar yang optimum dan pada setiap step menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih besar (lebih kecil) atau sama dari step-step sebelumnya.  Metode simpleks merupakan bagian dari linier programming yang digunakan sebagai alat untuk memecahkan permasalahan yang menyangkut dua variabel keputusan atau lebih. Metode ini menggunakan pendekatan tabel yang dinamakan tabel simpleks.

## Pemrograman Integer
Model pemrograman Integer ( Integer Programming) untuk menghasilkan penyelesaian optimal bilangan bulat, pada dasarnya ini juga merupakan analisis pasca optimal pemrograman linear. Penerapan model ini berangkat dari penyelesaian optimal sebuah kasus pemrograman linear yang menghasilkan bilangan pecahan. Teknik Integer programming untuk menghasilkan nilai variabel keputusan bulat yang akan dibahas adalah metode branch and cut.
Metode Branch Cabang ( Branch) adalah sebuah metode untuk menghasilkan penyelesaian optimal pemrograman linear yang menghasilkan variabel-variabel keputusan bilangan bulat. Metode branch sering membuat penyelesaian kasus-kasus pemrograman linear yang memiliki lebih dari dua variabel keputusan menjadi rumit, berbelit-belit, dan tidak efisien sehingga sering kali pendekatan pembulatan lebih disenangi.
Langkah  -  langkah metode branch and bound untuk  masalah maksimasi, dapat dilakukan seperti berikut :
1. Selesaikan LP dengan metode simpleks biasa.
2. Bounding. Pilih LP i sebagai sub problem untuk di bulatkan. selesaikan untuk LP i dan usahakan fathom
Keadaan fathom terpenuhi jika salah satu kondisi ini dipenuhi :
a) Subproblem menghasilkan solusi integer layak permasalahan ILP.
b) Subproblem tidak dapat menghasilkan solusi yang lebih baik dari solusi batas bawah terbaik yang ada (z) permasalahan ILP yang ada.
i. Jika LP i fathomed, perbaharui batas bawah z jika solusi ILP lebih baik. Jika tidak, pilih subproblem yang baru dan ulangi langkah 1. Jika semua subproblem sudah diselidiki, stop. Solusi optimum ILP adalah z batas bawah terakhir, jika ada. ii. Jika LP i belum fathomed, teruskan ke langkah 2.
3. Branching  (pencabangan). Pilih satu variabel 𝑥𝑥 𝑗𝑗 yang nilai optimumnya tidak memeuhi batasan integer. dengan membuat dua subproblem LP yang sesuai dengan 2 pembatas: [ ] * j j x x ≤ dan [ ] 1 * + ≥ j j x x
4. Kembali ke langkah awal jika masih bernilai pecahan.

## 3. METODE PENELITIAN
Jenis penelitian yang digunakan dalam penelitian ini adalah penelitian. Sumber data yang digunakan dalam penelitian ini merupakan data primer dan skunder. Objek penelitian tersebut adalah Perusahaan Furniture PT.PUTRA JEPARA. Variabel penelitian adalah Variabel keputusan banyaknya produksi yang diproduksi seperti lemari pajangan ( 𝑥𝑥 1 ), meja makan ( 𝑥𝑥 2 ), lemari jam ( 𝑥𝑥 3 ), dan kursi tamu ( 𝑥𝑥 4 ).

## Prosedur Penelitian
Untuk mneyelesaikan permasalahan yang ada, maka prosedur penelitian yang akan dilakukan adalah sebagai berikut :
1. Mengumpulkan data proses dan produksi pada PT. Putra Jepara.
2. Membuat model matematis yang sesuai.
Fungsi Tujuan:
𝑀𝑀𝑎𝑎𝑀𝑀𝑀𝑀𝑖𝑖𝑀𝑀𝑀𝑀𝑀𝑀 , 𝑍𝑍 = ∑ 𝑐𝑐 𝑗𝑗 𝑥𝑥 𝑗𝑗 𝑛𝑛 𝑗𝑗=1 ; 𝑥𝑥 𝑗𝑗 , 𝑗𝑗 = 1,2, … , 𝑛𝑛 Dengan Kendala :
∑ 𝑎𝑎 𝑖𝑖𝑗𝑗 𝑥𝑥 𝑗𝑗 𝑛𝑛 𝑗𝑗=1 ≥≤ 𝑏𝑏 𝑖𝑖 , untuk 𝑖𝑖 = 1,2,3, … , 𝑛𝑛
3. Menghitung nilai optimasi dan variabel – variabel model.
4. Mengoptimalkan hasil dengan metode branch and bound dengan langkah-langkah :
a) Selesaikan LP dengan metode simpleks biasa.
b) Bounding. Pilih LP i sebagai sub problem untuk di bulatkan. selesaikan untuk LP i dan usahakan fathom.
(1) Fathom dipenuhi jika salah satu kondisi ini dipenuhi :
• Subproblem menghasilkan solusi integer layak permasalahan ILP.
• Subproblem tidak dapat menghasilkan solusi yang lebih baik dari solusi batas bawah terbaik yang ada (z) permasalahan ILP yang ada.
(2) Jika LP i fathomed, perbaharui batas bawah z jika solusi ILP lebih baik.
Jika tidak, pilih subproblem yang baru dan ulangi langkah 1. Jika semua subproblem sudah diselidiki, stop.
Solusi optimum ILP adalah z batas bawah terakhir, jika ada.
c) Jika LP i belum fathomed, teruskan ke langkah 2.
d) Branching (pencabangan). Pilih satu variabel 𝑥𝑥 𝑗𝑗 yang nilai optimumnya tidak memeuhi batasan integer. dengan membuat dua subproblem LP yang sesuai dengan 2 pembatas:
[ ] * j j x x ≤ dan [ ] 1 * + ≥ j j x x Kembali ke langkah awal jika masih bernilai pecahan.
e) Membuat kesimpulan.

## 4. HASIL DAN PEMBAHASAN
Hasil
1. Pengumpulan Data Proses dan Produksi
Mulai dari Proses Finishing yang dilakukan perusahaan, data harga produk mentah, banyaknya jumlah pesanan produk mentah, data pemakaian dan jumlah biaya bahan baku yang dikeluarkan, waktu penyelesaian finishing/produk, upah tenaga kerja, dan menghitung laba setiap produk yang diproduksi. Data yang diperoleh dapat di lihat pada Tabel di bawah ini berturut-turut sebagai berikut:
Tabel 4.1 Harga Produk Mentah
Berdasarkan Tabel 4.1 di atas, Perusahaan tersebut telah memesan rata-rata produk yang mencakupi biaya yang dimiliki. Banyaknya jumlah rata-rata produk yang telah dipesan oleh perusahaan dari Jawa dapat dilihat Tabel 4.2 sebagai berikut:
Tabel 4.2 Data Jumlah Pesanan Produk Mentah
Beberapa produk furniture menghendaki suatu finishing yang kompleks, yang akan membutuhkan bahan sederhana untuk finishing seperti dempul, amplas, cat, melamine clear dan tinner.  Karena hanya 4 produk saja maka perusahaan menyediakan dengan maksimum selama sebulan sebanyak 60 kg dempul, 100
meter amplas, 200 liter sending, 200 liter melamine clear, 125 liter Tinner A, dan 125 liter Tinner super. Untuk bahan 1 kg dempul seharga Rp. 20.000, 1 meter amplas Rp. 11.000, 1 liter sending Rp. 30.000, 1 liter melamine clear Rp. 30.000, Tinner A/liter Rp. 11.000, dan Tinner Super/liter  Rp.14.000. Maka untuk anggaran bahan setiap produk yang digunakan seperti pada Tabel 4.2 berikut.

## Tabel 4.3 Data Pemakaian Dan Jumlah Biaya
Bahan Baku Yang Dikeluarkan
Produksi barang di PT. Putra Jepara dilaksanakan pada hari Senin hingga Sabtu. Dalam penelitian ini yang menjadi kendala adalah jam kerja karyawan bagian produksi. Rata-rata jumlah hari kerja yang efektif bagian produksi pada PT. Putra jepara dalam satu bulan adalah 27 hari kerja. Untuk 1 hari jam kerja adalah 8 jam, sehingga dalam 1 bulan membutuhkan waktu 216 jam. Adapun jumlah waktu penyelesaian produk dapat dilihat pada Tabel 4.4 berikut:
Tabel 4.4 Waktu Penyelesaian Finishing/Produk
Pada Tabel 4.4 di atas, khusus untuk produk meja makan dikerjakan oleh tenaga kerja yang berbeda. PT. Putra Jepara memiliki 8 tenaga kerja yang mampu melakukan proses finishing. Akan tetapi pimpinan perusahaan furniture/mebel mengkhususkan 7 orang tenaga kerja untuk menyelesaikan proses finishing pada meja makan setiap bulan karena jumlah produk mentah lebih banyak dibanding produk lain. Penyelesaian 1 set meja makan dilakukan lebih
cepat yaitu selama 4 jam karena pekerja lebih fokus cepat penyelesaiannya untuk meja makan. sistem penerimaan upah tenaga kerja yaitu setiap tenaga kerja berikan upah tergantung dari berapa banyaknya produk yang telah diselesaikan dapat dilihat pada Tabel 4.5 di bawah ini:

## Tabel 4.5 Upah Tenaga Kerja
Untuk mendapatkan model matematis yang disebutkan fungsi tujuan, dapat dihitung dengan mengetahui banyaknya keuntungan yang diperoleh setiap produk yang diproduksi perusahaan jepara dengan rumus sebagai berikut:
Keuntungan :
Harga jual produk – ( Upah Tenaga kerja + biaya  bahan    produk  + harga beli barang mentah)
Tabel 4.6 . Data Laba Dari Setiap Produk Yang Di Produksi
Pada Tabel 4.6 merupakan laba setiap produk, yang dapat diidentifikasi sebagai fungsi tujuan untuk diformulasikan dalam simbol matematis.
2. Model Matematis Yang sesuai a. Fungsi tujuan
Maksimum, 𝑧𝑧 = 2.353.000 𝑥𝑥 1 + 2.088.000 𝑥𝑥 2
+ 1.453.000 𝑥𝑥 3 + 3.447.000 𝑥𝑥 4 b. Fungsi Kendala i. 32 𝑥𝑥 1 + 32 𝑥𝑥 3 + 24 𝑥𝑥 4 ≤ 216
ii. 4 𝑥𝑥 2 ≤ 216 iii. 𝑥𝑥 1 ≤ 2 iv. 𝑥𝑥 2 ≤ 50 v. 𝑥𝑥 3 ≤ 3 vi. 𝑥𝑥 4 ≤ 1 vii. 𝑥𝑥 1 + 𝑥𝑥 2 + 0.5 𝑥𝑥 3 + 2 𝑥𝑥 4 ≤ 60 viii. 2 𝑥𝑥 1 + 2 𝑥𝑥 2 + 𝑥𝑥 3 + 2 𝑥𝑥 4 ≤ 100 ix. 3 𝑥𝑥 1 + 2 𝑥𝑥 2 + 2 𝑥𝑥 3 + 3 𝑥𝑥 4 ≤ 200 x. 3 𝑥𝑥 1 + 2 𝑥𝑥 2 + 𝑥𝑥 3 + 2 𝑥𝑥 4 ≤ 200 xi. 3 𝑥𝑥 1 + 2 𝑥𝑥 2 + 2 𝑥𝑥 3 + 3 𝑥𝑥 4 ≤ 125 xii. 3 𝑥𝑥 1 + 2 𝑥𝑥 2 + 𝑥𝑥 3 + 2 𝑥𝑥 4 ≤ 125 𝑥𝑥 1 , 𝑥𝑥 2 , 𝑥𝑥 3 , 𝑥𝑥 4 ≥ 0

## 3. Menghitung Nilai Optimasi dan Variabel- variabel Model dengan Metode Simpleks
Maksimum, 𝑧𝑧 = 2.353.000 𝑥𝑥 1 + 2.088.000 𝑥𝑥 2 + 1.453.000 𝑥𝑥 3 + 3.447.000 𝑥𝑥 4 + 𝑀𝑀 1 + 𝑀𝑀 2 + 𝑀𝑀 3 + 𝑀𝑀 4 + 𝑀𝑀 5 + 𝑀𝑀 6 + 𝑀𝑀 7 + 𝑀𝑀 8 + 𝑀𝑀 9 + 𝑀𝑀 10 + 𝑀𝑀 11 + 𝑀𝑀 12 4.

## Hasil Dengan Langkah-langkah Metode
Branch and Cut
Gambar 4.1. Metode Branch
Dari Gambar 4.1  di  atas  merupakan awal percabangan dari metode simpleks. Seperti yang kita lihat bahwa dari percabangan diatas masih ada yang bernilai pecahan dan terlihat tidak realistis jika sebuah produk dapat di jual dalam keadaan setengah jadi. Sehingga dapat dilakukan kembali langkah-langkah metode branch and bound yang akan dicabangkan ulang dengan pembatas baru yaitu 𝑥𝑥 1 ≤ 1 dan 𝑥𝑥 1 ≥ 2 . Setelah
dilakukan metode branch and bound maka hasilnya dapat di lihat pada gambar di bawah ini:
Gambar 4.2 Lanjutan percabangan Metode
branch and bound
Pada Gambar 4.2 terlihat bahwa pada LP 7 masih terlihat hasil produk Meja Makan bernilai pecahan untuk itu kita berharap bahwa pembatasan yang akan kita lanjutkan pada percabagan selanjutnya menemukan hasil produk yang optimal sehingga percabangan dan pembatasan dapat kita ketahui keuntungan yang lebih besar. Oleh karena itu, lakukan iterasi dengan menggunakan tabel simpleks selanjutnya. Setelah melakukan iterasi menggunakan tabel simpleks dapat kita lihat hasil akhir percabangan dan pembatasan pada Gambar 4.3 dibawah ini

## Gambar 4.3 Hasil akhir percabangan metode branch and bound
Maka  besarnya keuntungan produk dengan metode branch and bound pada percabangan
𝑥𝑥 1 = 2 ; 𝑥𝑥 2 = 45 ; 𝑥𝑥 3 = 3 ; 𝑥𝑥 4 = 1 ;
𝑍𝑍 1 = 106452
𝑥𝑥 2 ≤ 45 𝑥𝑥 2 46 𝑥𝑥 1 = 1.5 ; 𝑥𝑥 2 = 46; 𝑥𝑥 3 = 3 ; 𝑥𝑥 4 = 1 ; 𝑍𝑍 2 = 107363.5
𝑥𝑥 1 = 2 ; 𝑥𝑥 2 = 45.5 𝑥𝑥 3 = 3 ; 𝑥𝑥 4 = 1 ; 𝑍𝑍 0 = 107496
𝑥𝑥 1 = 2 ; 𝑥𝑥 2 = 𝑥𝑥 1 = 1.5 ; 𝑥𝑥 2 = 𝑥𝑥 1 = 2 ; 𝑥𝑥 2 = 45 5
𝑥𝑥 1 = 1 ; 𝑥𝑥 2 = 46 5 3 𝑥𝑥 1 = 2 ; 𝑥𝑥 2 = 46;
𝑥𝑥 1 = 1 ; 𝑥𝑥 2 = 46 ; 𝑥𝑥 1 = 0.5 ; 𝑥𝑥 2 = 47;
𝑥𝑥 1 = 0 ; 𝑥𝑥 2 = 𝑥𝑥 1 = 1 ; 𝑥𝑥 2 = 47;
𝑥𝑥 1 = 0 ; 𝑥𝑥 2 = 47; 𝑥𝑥 3 = 3 ; 𝑥𝑥 4 = 1 ; 𝑥𝑥 1 = 0 ; 𝑥𝑥 2 = 48; 𝑥𝑥 3 = 2 ; 𝑥𝑥 4 = 1 ; 𝑍𝑍 10 = 106557 𝑥𝑥 1 = 0 ; 𝑥𝑥 2 = 47.5 ; 𝑥𝑥 3 = 3 ; 𝑥𝑥 4 = 1 ;
terakhir adalah sebesar Rp. 106.557.000,-, dengan memproduksi/finishing sebanyak 48 set meja makan, 2 unit lemari jam dan 1 unit kursi tamu serta untuk lemari pakaian tidak ada yang dapat di produksi, ini mengakibatkan bahwa ini kurang optimal untuk dijadikan patokan sebagai keuntungan perusahaan.
Adapun hasil yang lebih optimal dengan keuntungan maksimalnya yaitu pada metode branch and bound yang memiliki keuntungan lebih besar yaitu pada percabangan di awal batasan adalah sebanyak Rp. 107.087.000,-, dengan memproduksi/finishing sebanyak 2 unit lemari pakaian, 46 set meja makan, 2 unit lemari jam dan 1 unit kursi tamu

## 5. PEMBAHASAN
Berdasarkan hasil perhitungan matematis dari model yang telah diberikan, dengan menggunakan Metode Simpleks diperoleh hasil 2 unit lemari pakaian, 45.5 set meja makan, dan 3 unit lemari jam, serta 1 set kursi tamu yang memberikan nilai 𝑍𝑍 sebesar Rp. 107.496.000,-. Untuk jelasnya dapat dilihat pada Tabel 4.12 berikut.
Tabel 4.12 Hasil Olahan Metode Simpleks Produk Banyaknya Yang Diproduksi Lemari Pakaian Meja Makan
Lemari Jam Kursi Tamu 2 45.5
3 1
Secara rasional, hasil tersebut sebagaimana yang di tujukan pada Tabel 4.12 dengan memproduksi 45.5 set meja makan Nampak bahwa hasil tersebut tidak rasional, dengan demikian perlu dilakukan perhitungan ulang dengan menggunakan Integer Programming untuk menghasilkan hasil yang rasional, dalam hal ini digunakan metode branch and cut . Dari hasil perhitungan diperoleh 2 unit lemari pakaian, 46 set meja makan, 2 unit lemari jam dan 1 set kursi tamu yang memberikan nilai 𝑍𝑍 sebesar Rp.
107.087.000,-. Untuk jelasnya dapat dilihat dari Tabel 4.38 berikut:
Tabel 4.38 Hasil Olahan bounding/batasan awal Metode Branch and bound
Produk Banyaknya Yang Diproduksi Keuntungan Lemari Pakaian Meja Makan Lemari Jam Kursi Tamu 2
46 2 1 Rp.
107.087.000
Sedangkan Untuk Hasil perhitungan pada bounding/batasan akhir memang diperoleh hasil yang cukup optimal karena tidak ada lagi produk yang dihasilkan setengah jadi atau bernilai pecahan/desimal sehingga untuk produk lemari pakaian tidak dapat dikerjakan/diproduksi, sebanyak 48 set meja makan, 2 unit lemari jam dan 1 unit kursi tamu dengan keuntungan sebesar Rp. 106.557.000,- Untuk lebih jelas dapat dilihat pada Tabel 4.54 berikut.
Tabel 4.54 Hasil Olahan Metode Bound
Produk Banyaknya Yang Diproduksi
Keuntungan
Lemari Pakaian Meja Makan Lemari Jam Kursi Tamu 0 48 2 1 Rp. 106.557.000,-
Jadi, dari hasil perhitungan menggunakan Metode branch and bound pada Tabel 4.38 dan Tabel 4.54 kita dapat menarik kesimpulan bahwa batasan/bounding yang dilakukan di awal lebih menguntungkan di bandingkan pada saat melakukan percabangan hingga batasan sudah tidak ada yang bernilai pecahan. Maka untuk kasus pada perusahaan Furniture PT. Putra

## Jurnal MSA Vol. 3 No. 1 Ed. Jan-Juni 2015
Jepara metode branch and bound merupakan metode yang satu kesatuan yang dapat dilakukan percabangan dan membatasi setiap masalah maksimasi untuk menghasilkan variabel integer yang lebih maksimal dan optimal.

## 1. KESIMPULAN
Berdasarkan  hasil penelitian dan pembahasan yang telah dilakukan pada PT. Putra Jepara dengan menggunakan pendekatan metode branch and bound, hasil penyelesaian optimal yaitu metode branch and bound dengan keuntungan sebesar Rp. 107.087.000,-/bulan ketika perusahaan mampu menyelesaikan finishing/bulan sebanyak lemari pakaian 2 unit, 46 set meja makan, 2 unit lemari jam, dan 1 unit kursi tamu

## DAFTAR PUSTAKA
Ernawati. “Analisis Perubahan Koefisien Fungsi Tujuan Secara Simpleks Pada Masalah Program Linear Bilangan Bulat”. Skripsi . Yogyakarta: Fak. Matematika dan Ilmu Pengetahuan Alam  Universitas Negeri Yogyakarta,2010.http://eprints.uny.ac.id/17 28/1/ERNAWATI_06305141050.pdf(12 januari 2015).
Nico, dkk. “Aplikasi Metode Cutting Plane Dalam Optimasi Jumlah Produksi Tahunan PT.XYZ”. Jurnal. http://jurnal.usu.ac.id/index.php/smatematika/arti cle/view/5871/pdf  (12 januari 2015).
Nursalam. Strategi Pembelajaran Matematika. Makassar: AU-Press, 2013.
Hillier, Frederick S. dan Gerald J. Lieberman.
Introduction To Operation Research Eighth Edition .  Terj. Parama Kartika Dewa, dkk., Operations Research- Penelitian Operasional . Yogyakarta: Andi, 2008.
Rahman, Hairur. Indahnya Matematika dalam Al-Qur’an . Malang: UIN-Malang Press,
2007.
Rangkuti, Aidawayati. 7 Model Riset Operasi & Aplikasinya . Surabaya: Brilian Internasional, 2013.
Shihab, M Quraish. Tafsir al-Misbah (Pesan, Kesan dan Keserasian al-Qur’an), vol: 8. Jakarta: Lentera Hati, 2002
, M Quraish. Tafsir al-Misbah (Pesan, Kesan dan Keserasian al-Qur’an), vol: 14. Jakarta: Lentera Hati, 2002.
Siagian, P. Penelitian Operasional Teori dan Praktek . Jakarta: UI-Press, 1987.
Siswanto. Operation Research Jilid 1. Jakarta: Erlangga., 2006.
. Operation Research Jilid 2. Jakarta: Erlangga., 2007.
Supranto, J. Linear Programming. (Jakarta: Universitas Indonesia, 1983).
, J. Riset Operasi Untuk Pengambilan Keputusan Edisi Revisi . Jakarta: UI- Press, 2006.
, J. Riset Operasi Untuk Pengambilan Keputusan Edisi Revisi . Jakarta: PT.Raja Grafindo Persada, 2013).
Taha, Hamdy A. Riset Operasi Suatu Pengantar Edisi kelima jilid 1. Jakarta: Binarupa Aksara, 1996.
Utami, Arum Tri. ”Penerapan Model Integer Linear Programming (Metode Branch and Bound dan Cutting Plane) ”. Skripsi. Yograkarta: Fak.Sains Dan Teknologi Universitas Islam Negeri Sunan Kalijaga,
2013.
http://digilib.uin- suka.ac.id/12104/1/BAB%20I,%20V,%2 0DAFTAR%20PUSTAKA.pdf (12 Januari 2015).
Weber, Jean E. Analisis Matematik Penerapan Bisnis dan Ekonomi Edisi Keempat Jilid
2. Jakarta: Erlangga, 1999).
Wijaya, Andi. Pengantar Riset Operasi (Tujuan, Pengertian dan langkah-langkah pengerjaan, contoh serta latihan soal) . Jakarata: Mitra Wacana Media, 2011.
Yuwono, Bambang. Bahan Kuliah Riset Operasional . http://nurfajria.staff. gunadarma.ac.id/Downloads/files/31242/ RISET+OPERASIONAL.pdf (11 Januari 2015).