Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306

## IMPLEMENTASI METODE BRANCH AND BOUND DALAM MENGOPTIMALKAN
JUMLAH PRODUKSI  ROTI ( STUDI KASUS: PABRIK ROTI GARDEN)

## PEMATANG SIANTAR

## IMPLEMENTATION OF BRANCH AND BOUND METHODS IN OPTIMIZING THE AMOUNT OF BREAD PRODUCTION (CASE STUDY: BREAD GARDEN FACTORY) PEMATANGSIANTAR
JESICA RAYANI SINAGA 1 , LOLYTA DAMORA SIMBOLON 2 , DEBORA EXAUDI SIRAIT 3
1 Program Studi Matematika,Universitas HKBP Nommensen Pematangsiantar Jalan Sangnaualuh No.4 Pematangsiantar email: jesicasinaga10@gmail.com 1 2 Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas HKBP Nommensen Pematangsiantar Jalan Sangnaualuh No.4 Pematangsiantar email: lolyta.simbolon@uhnp.ac.id 2 3 Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas HKBP Nommensen Pematangsiantar Jalan Sangnaualuh No.4 Pematangsiantar email: debora.sirait@uhnp.ac.id 3

## Abstrak
Metode branch and bound merupakan salah satu metode  yang digunakan untuk menghasilkan solusi  optimal pemrograman linier, yang akan menghasilkan variabel keputusan bilangan bulat. Metode ini membatasi solusi optimal  yang  akan  menghasilkan  bilangan  pecahan  dengan  membuat  cabang  atas  dan  bawah  untuk  setiap variabel keputusan yang memiliki nilai pecahan, sehingga setiap       pembatasan akan menghasilkan cabang baru. Tujuan dari penelitian ini adalah untuk mengetahui model matematika dari permasalahan pengoptimalan bahan baku  di  Pabrik  Roti  Garden  serta  untuk  mengimplementasikan  metode Branch  and  Bound dalam mengoptimalkan  jumlah  produksi  roti  agar  mendapatkan  keuntungan  yang  maksimal  di  Pabrik  Roti  Garden. Dengan jenis roti yang menjadi variabel keputusan dalam penelitian ini adalah roti Coklat, Srikaya , Kelapa dan Kacang  Hijau.  Dalam  penelitian  ini  peneliti  menggunakan  bantuan software  POM/QM untuk  menyelesaikan masalah program linear. Hasil perhitungan menggunakan langkah- langkah metode branch and bound , diperoleh Hasil  selisih  nilai  keuntungan  penjualan  sebesar  16,64%  atau  Rp.1.418.300,00,  dari  perkiraan  keuntungan perusahaan sebelumnya. Jumlah produksi roti  yang diperoleh dari bahan-bahan  yang tersedia adalah 36.500 roti, dimana  Roti Coklat diproduksi 11.666 roti, Roti Srikaya diproduksi 7.334 roti, Roti Kelapa diproduksi 6.000 roti dan Roti Kacang Hijau diproduksi 12.500 roti dengan keuntungan sebesar Rp. 9.938.300.
Kata kunci : Program Linier, Metode Branch and Bound, Program Integer

## Abstract
The branch and bound method is one of the methods used to produce an optimal solution for linear programming, which  will  produce  an  integer  decision  variable.  This  method  limits  the  optimal  solution  that  will  produce  a fractional number by creating an upper and lower branch for each decision variable that has a fractional value, so that each restriction will produce a new branch. The purpose of this study was to determine the mathematical model of the problem of optimizing raw materials at the Garden Bread Factory and to implement the Branch and Bound method in optimizing the amount of bread production in order to get maximum profit at the Garden Bread Factory. The type of bread that became the decision variable in this study was Chocolate, Srikaya, Coconut and Green Bean bread. In this study, researchers used POM/QM software to solve  linear programming problems. The results of the calculation using the steps of the branch and bound method, the result of the difference in the value of sales profits is 16.64% or Rp. 1,418.300.00, from the previous estimated company profits. The amount of bread production obtained from the available ingredients is 36,500 breads, where Brown Bread is produced 11,666 loaves, Srikaya Bread is produced 7,334 breads, Coconut Bread is produced 6,000 breads and Green Bean Bread is produced 12,500 breads with a profit of Rp. 9,938,300.
Keywords : Linear Program, Branch and Bound Method, Integer Program
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306

## Pendahuluan
Pertumbuhan  dan  perkembangan  industri  di  Indonesia  tergolong  cukup  pesat,  diiringi  dengan  semakin canggihnya teknologi dan luasnya wawasan, tidak dapat dipungkiri bahwa persaingan di dunia industri semakin sengit,  semakin  marak  kawasan-kawasan  industri  modern  sehingga  semakin  banyak  pula  produk  yang dihasilkan di pasaran. Seiring dengan kebutuhan konsumen yang semakin beragam, pelaku industri tentu akan melakukan inovasi terhadap produknya sesuai dengan kebutuhan dan permintaan konsumen [8] . Pelaku industri juga dituntut untuk memiliki suatu kemampuan bersaing agar mampu bertahan di kalangan industry [5] . Strategi- strategi  mulai  digalakkan,  salah  satunya  strategi  perencanaan  produksi.  Dalam  wawancara  peneliti  dengan pemilik pabrik Roti Garden Pematangsiantar, diketahui bahwa pabrik Roti Garden Pematangsiantar mengalami sejumlah kendala dalam perencanaan produksi yang tidak optimal, dimana komposisi dalam penggunaan bahan baku tidak dilakukan pencatatan dan pencatatan stok barang yang kurang maksimal sehingga timbul masalah pengoptimalan jumlah produksi. Selain itu, pembukuan keuangan hanya dilakukan di waktu-waktu tertentu, tidak dilakukan secara rutin sehingga tidak dapat diidentifikasi dengan jelas keuntungan yang diperoleh. Pemrograman linier  adalah  pemecahan  masalah  alokasi  sumber  daya  yang  terbatas  dengan  metode  yang  digunakan  untuk mendapatkan hasil yang optimal dalam model matematika terhadap sejumlah kendala dengan cara menentukan besarnya setiap nilai variabel, sehingga nilai fungsi tujuan menjadi optimum [2] .  Sedangkan pemrograman integer adalah  pemrograman  linier  yang  menggunakan  bilangan  bulat  atau  variabel  dalam  bentuk  bilangan  bulat, variabel  keputusan  harus  bernilai  integer  (variabel  bernilai  bilangan-bilangan  bulat) [4] .  Metode  yang  dapat digunakan untuk mendapatkan solusi dari  permasalahan pemrograman bilangan  bulat adalah metode Branch and Bound (cabang dan batas) [1] . Metode Branch and Bound merupakan salah satu metode yang menghasilkan solusi optimal untuk program linier yang menghasilkan variabel keputusan bilangan bulat [3] . Salah satu cara yang digunakan  untuk  menghasilkan  solusi  yang  optimal  dengan  melakukan  percabangan  secara  terus  menerus sehingga diperoleh solusi dengan hasil bilangan bulat. Metode Branch and Bound digunakan pada permasalahan program integer [7] . Kelebihan metode Branch and Bound adalah sering digunakan untuk menyelesaikan masalah program bilangan bulat karena hasil yang diperoleh dalam solusi optimal lebih akurat dan lebih baik dari metode lainnya [6] .

## Metode Penelitian
Penelitian  ini  dilaksanakan  di  Pabrik  Roti  Garden  Pematangsiantar,  yang  beralamatkan  di  Jalan  Banjar, Kecamatan  Siantar  Barat,  Kota  Pematangsiantar,  Sumatera  Utara.  Penelitian  ini  dilakukan  dengan  cara pengambilan  data  dari  Pabrik  Roti  Garden  Pematangsiantar,  yaitu  data  jumlah  dan  persediaan  bahan  baku, harga jual dan biaya produksi dari 4 jenis roti (Cokelat,Srikaya,Kelapa dan Kacang Hijau). informasi pendukung yang  digunakan  untuk  penelitian  ini  dikumpulkan  dari  buku,  jurnal,  maupun  dokumen-dokumen  lain  yang berkaitan  dengan  topik  pembahasan.  Dalam  penelitian  ini  peneliti  menggunakan  pendekatan  penelitian kuantitatif  asosiatif,  karena  dalam  penelitian  ini,  peneliti  ingin  menggali  lebih  jauh  tingkat  efektivitas  dalam penerapan metode Branch and Bound pada linnier programming dalam pengoptimalan jumlah produksi roti yang berada  pada  pabrik  Roti  Garden  Pematangsiantar.  Langkah-langkah  dalam  pengolahan  data  adalah  sebagai berikut : (a) Memodelkan fungsi tujuan dan fungsi kendala yang ada dalam bentuk program linier, (b) Menghitung nilai variabel-variabel menggunakan metode simpleks , (c) Mencari nilai optimal dengan menggunakan metode Branch and bound dengan bantuan software POM/QM (d) Membuat Kesimpulan.

## Hasil Penelitian dan Pembahasan Hasil Penelitian
Dalam  menyelesaikan  masalah  pengoptimlan  jumlah  produksi  roti  pada  Pabrik  Roti  Garden Pematangsiantar menggunakan metode Branch and bound, data-data yang diperlukan adalah data komposisi bahan  baku  yang  diperlukan  dari  setiap  adonan  jenis  roti,  data  persediaan  bahan  baku,  serta  data  harga
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306
penjualan setiap adonan jenis roti. Data yang diperoleh dari Pabrik Roti Garden Pematangsiantar adalah sebagai berikut:
Tabel 1. Harga Jual Roti dan Biaya Produksi 1 Buah Roti Serta Keuntungan Penjualan Roti
Tabel 2. Tabel komposisi Bahan Baku dan Persediaan Bahan Baku dari 4 Jenis Roti
No Jenis Bahan Baku Produksi Roti Jenis Produksi Roti Persediaaan    Bahan Baku Produksi (gr) Roti Cokelat (gr) Roti Srikaya (gr) Roti Kelapa (gr) Roti Kacang hijau (gr) 1 Tepung Terigu 12 12 12 12 450000 2 Mentega 3 3 3 3 300000 3 Gula pasir 0,8 1,1 1,4 1,2 750000 4 Pengembang 0,01 0,01 0,01 0,01 2500 5 Garam 0,01 0,01 0,01 0,01 14800 6 Cokelat 3 - - - 35000 7 Srikaya - 1,2 - - 30000 8 Kelapa - - 2 - 12000 9 Kacang hijau - - - 2 25000
Sumber : Pabrik Roti Garden Pematangsiantar
Pengolahan data terlebih dahulu dimulai dengan identifikasi Fungsi Tujuan. Maka dengan demikian, akan diambil Fungsi Tujuan sebagai berikut:
𝑥 1 = Roti Coklat
𝑥 2 = Roti Srikaya
𝑥 3 = Roti Kelapa
𝑥 4 =  Roti Kacang Hijau
Dengan fungsi kendala sebagai berikut:
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306
𝑎 1 = Tepung Terigu
𝑎 2 = Mentega
𝑎 3 = Gula Pasir
𝑎 4 = Pengembang
𝑎 5 = Garam
𝑎 6 = Coklat
𝑎 7 = Srikaya
𝑎 8 = Kelapa
𝑎 9 = Kacang Hijau
Dimana 𝑍 =  total  keuntungan  (buah),  dan b i =  jumlah  persediaan  bahan  baku  Maka,  Model  program  linier permasalahan di atas antara lain sebagai berikut: Maksimalkan 𝑍 = total keuntungan (buah) 𝑥 1 + total keuntungan (buah) 𝑥 2 + total keuntungan (buah) 𝑥 3 + total keuntungan 𝑥 4 (buah).
Dengan kendala :
𝑎 11 𝑥 1 + 𝑎 12 𝑥 2 + 𝑎 13 𝑥 3 + 𝑎 14 𝑥 4 ≤ 𝑏 1 𝑎 21 𝑥 1 + 𝑎 22 𝑥 2 + 𝑎 23 𝑥 3 + 𝑎 24 𝑥 4 ≤ 𝑏 2 𝑎 31 𝑥 1 + 𝑎 32 𝑥 2 + 𝑎 33 𝑥 3 + 𝑎 34 𝑥 4 ≤ 𝑏 3 𝑎 42 𝑥 1 + 𝑎 42 𝑥 2 + 𝑎 43 𝑥 3 + 𝑎 44 𝑥 4 ≤ 𝑏 4 𝑎 51 𝑥 1 + 𝑎 52 𝑥 2 + 𝑎 53 𝑥 3 + 𝑎 54 𝑥 4 ≤ 𝑏 5 𝑎 6 𝑥 1 ≤ 𝑏 6 𝑎 7 𝑥 2 ≤ 𝑏 7 𝑎 8 𝑥 3 ≤ 𝑏 8 𝑎 9 𝑥 4 ≤ 𝑏 9

## Pembahasan
Penyelesaian awal dengan metode simpleks Langkah-langkah metode simpleks:
1. Mengubah fungsi tujuan dan kendala
Fungsi Tujuan   : Z – (250 𝑥 1 + 200 𝑥 2 + 280 𝑥 3 + 310 𝑥 4 ) = 0 Fungsi kendala : 12𝑥 1 +  12𝑥 2 +  12𝑥 3 +  12𝑥 4 + 𝑥 5 ≤   250000
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306
3 𝑥 1 +  3 𝑥 2 +    3 𝑥 3 +  3 𝑥 4 + 𝑥 6 ≤ 300000 0,8𝑥 1 + 1,1𝑥 2 +  1,4𝑥 3 +  1,2𝑥 4 + 𝑥 7 ≤   750000
0,01𝑥 1 +  0,01𝑥 2 +  0,01𝑥 3 +  0,01𝑥 4 + 𝑥 8 ≤   2500 0,01𝑥 1 +  0,01𝑥 2 +  0,01𝑥 3 +  0,01𝑥 4 + 𝑥 9 ≤  14800 𝑥 1 +   𝑥 10 =  35000
1,2𝑥 2 +   𝑥 11 = 30000
2𝑥 3 + 𝑥 12 = 12000
2𝑥 4 + 𝑥 13 = 25000
( 𝑥 5 sampai 𝑥 13 merupakan variabel slack . Variabel slack adalah variabel   tambahan yang mewakili persediaan bahan baku yang tidak digunakan).
Model matematika yang telah dibentuk kemudian akan diselesaikan dengan program linier
Tabel 3 . Solusi Masalah
Sehingga  Roti  Coklat  yang  harus  di  produksi  dalam  sehari  adalah    sebanyak  11666,6667  roti,  Roti  Srikaya sebanyak 7333,33 roti, Roti Kelapa sebanyak 6000 roti  dan Roti Kacang Hijau sebanyak 12500. Namun masalah ini belum valid karena solusi yang dibutuhkan adalah  solusi berupa bilangan integer. Dikarenakan Roti Coklat dan Roti Srikaya belum berupa bilangan integer. Selanjutnya akan digunakan metode Branch and Bound agar solusi yang diperoleh berupa bilangan integer .

## Analisis Metode Branch and Bound
Langkah  pertama  yang  dilakukan  adalah  menentukan  batas  atas  (BA)  dan  batas  bawah  (BB).  Hasil  yang diperoleh sebelumnya yaitu 𝑥 1 =11666,67 𝑥 2 =7333,33 𝑥 3 =6000 dan 𝑥 4 =12500 dengan keuntungan sebesar Rp. 9.938.333,35 belum menjadi solusi yang valid karena 𝑥 1 , 𝑥 2 tidak bilangan integer. Langkah berikutnya adalah memilih variabel keputusan yang memiliki nilai keputusan pecahan terbesar, lalu di cabangkan Dipilih salah satu variabel  yang  belum  bulat.  Dalam  masalah  ini  yang  di  pilih  adalah 𝑥 1 =11666,67  di  cabangkan  menjadi  sub- masalah 1 dan sub-masalah 2. Sub-masalah 1 ditambahkan kendala 𝑥 1 ≥ 11667 ,Sub-masalah 2 ditambahkan kendala 𝑥 1 ≤ 11666.
Dengan metode simpleks pada Software QM diperoleh solusi:
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306
Solusi Submasalah 1: tidak di temukannya solusi pada 𝒙 𝟏 = 11667(pembulatan keatas) Solusi Submasalah 2:

## Tabel 4. Solusi Integer Sub Masalah 2
Dari hasil perhitungan dengan menggunakan metode Branch and Bound hasil solusi sudah optimal dan semua variabel sudah bernilai integer ,  maka diambil sub-masalah dengan nilai optimal terbesar yaitu Z = Rp.  9.938.300 dengan  setiap  jenis  roti  masing-masing  diproduksi  yaitu 𝑥 1 =  11.666  Roti  Coklat, 𝑥 2 =7.334 Roti Srikaya, 𝑥 3 = 6.000 Roti Kelapa dan 𝑥 4 = 12.500 Roti Kacang Hijau. Dengan keuntungan penjualan senilai Rp. 9.938.300.

## Kesimpulan
Dari hasil analisis menggunakan metode Branch and Bound , jumlah roti  yang optimal diproduksi dalam sekali proes produksi yaitu 37.500 roti, dimana Roti Coklat diproduksi 11.666 roti, Roti Srikaya diproduksi 7.334 roti, Roti Kelapa diproduksi 6.000 roti dan Roti Kacang Hijau diproduksi 12.500 roti dengan keuntungan sebesar Rp. 9.938.300. Keuntungan Perusahaan sebelumnya adalah sebesar Rp. 8.520.000 dengan jumlah produksi 32.500 roti, dengan menggunakan metode Branch and Bound Keuntungan perusahaan naik sebesesar Rp. 9.938.300 dengan jumlah roti  yang harus diproduksi sebesar 37.500 roti, selisih perbandingan keuntungan  Perusahaan dengan  Keuntungan  menggunakan  metode Branch  and  Bound adalah  16,64%  atau  Rp.  1.418.300  dari keuntungan perusahaan dalam proses sekali produksi. Sehungga hasil yang diperoleh dengan branch and bound sudah optimum sebagai penyelesaian permasalahan jumlah produksi roti.

## Daftar Pustaka
[1] Akram, Sahari, Jaya, 2016. Optimalisasi Produksi Roti Dengan Menggunakan Metode Branch and boundPada Pabrik Roti Syariah Bakery. Jurnal Ilmiah Matematika dan Terapan. Vol 13 No 2 : 98-107.
[2] Aminudin, 2005. Prinsip-Prinsip Riset Operasi . Erlangga. Jakarta.
[3] Harsono, 2016. Insentif Buku Ajar Riset Operasi. Sekolah Tinggi Ilmu Ekonomi Graha Kirana,   Medan.
[4] Hartono,  Widi,  2014  .  “Implementasi  Algoritma Branch  and  Bound pada  0-1  Knapsack  Problem  untuk Mengoptimalkan Muatan Barang”. Jurnal Matematika
[5] Meflinda Astuti, 2011. Riset Operasi. Unri Press. Pekanbaru.
[6]  Nova  Elen,  2020.  Pengoptimalan  Jumlah  Truk  Pengangkut  Sampah  Dengan  Metode  Branch  and  Bound (Studi  kasus  :  Dinas  Kebersihan  dan  Pertanaman  Kota  Medan).  [Skripsi].  Medan  :  Universitas  Sumatera Utara, Program Sarjana.
[7] Purwanto, 2018. Teknik Penyusunan instrumen uji validitas dan uji reabilitas penelitian ekonomi syariah (1nd ed.). Magelang: Staial Press
Vol.  8, No. 2 (2022)
E-ISSN : 2685- 5585
Hal : 470 – 476 DOI : https://doi.org/10.36987/jpms.v8i2.3306
[8] Siswanto, 2007. Operation Research Jilid 1. Erlangga, Jakarta