## OPTIMALISASI PRODUKSI TAHU MENGGUNAKAN METODE BRANCH AND BOUND DAN CUTTING PLANE
Fatimah Khilaliyah Azzahrha 1 , Rianita Puspa Sari 2* , Muhamad Dhika Rahma Fauzi 3
Program Studi Teknik Industri, Universitas Singaperbangsa Karawang 1,2,3 1810631140009@student.unsika.ac.id 1 , rianita.puspasari@ft.unsika.ac.id 2 , 1810631140104@student.unsika.ac.id 3
Submitted September 23, 2021; Revised December 3, 2021; Accepted December 3, 2021

## Abstrak
Kegiatan  alokasi  sumber  daya  pada  proses  produksi  merupakan  hal  penting  yang  perlu  diperhatikan untuk mencapai tingkat produksi optimal. Permasalahan optimalisasi produksi masih menjadi kendala bagi sebagian besar usaha yang bergerak di bidang makanan.  Salah satunya, Pabrik Tahu Pak Yayat yang  memproduksi  dua  jenis  tahu,  yaitu  tahu  putih  dan  tahu  kuning.  Penelitian  ini  bertujuan  untuk mengoptimalkan  jumlah  produksi  tahu  melalui  alokasi  sumber  daya  yang  tepat  untuk  mencapai keuntungan  usaha  yang  maksimum.  Metode  yang  digunakan  adalah  metode branch  and  bound dan cutting  plane .  Teknik  pengambilan  sampel  dilakukan  dengan purposive  sampling. Hasil  penelitian metode branch  and  bound diperoleh  kombinasi  produksi  36  papan  tahu  putih  dan  75  papan  tahu kuning  yang  memberikan  keuntungan  maksimum  Rp.1.872.000,00.  Sedangkan  metode cutting  plane diperoleh hasil kombinasi produk 37 papan tahu putih dan 75 papan tahu kuning dengan keuntungan Rp.1.886.500,00.  Dapat  disimpulkan  bahwa  metode cutting  plane memberikan  hasil  yang  optimal dengan  keuntungan  yang  maksimum  dibandingkan branch  and  bound .  Pada  penelitian  ini, software lingo digunakan untuk mempermudah proses pengolahan data serta membandingkan hasil perhitungan antara manual dan software untuk menghindari kesalahan perhitungan.
Kata Kunci : Branch and Bound, Cutting Plane, Purposive Sampling, Lingo

## Abstract
Resource allocation activities in the production process are important things need to be considered to achieve optimal production levels. The problem of optimizing production is still an obstacle for most businesses engaged in the food sector. One of them, Pak Yayat's Tofu Factory, produces two types of tofu,  that  is  white  tofu  and  yellow  tofu.  This  study  aims  to  optimize  the  amount  of  tofu  production through the allocation of appropriate resources to achieve maximum profits. The method used is the branch  and  bound  method  and  cutting  plane.  The  sampling  technique  was  done  by  purposive sampling. The results of the research using the branch and bound method obtained a combination of production  of  36  white  tofu  boards  and  75  yellow  tofu  boards  which  gave  a  maximum  profit  of Rp.1,872,000.00. While the cutting plane method results in a combination of 37 white tofu boards and 75  yellow  tofu  boards  with  a  profit  of  Rp.1,886,500.00.  It  can  be  concluded  that  the  cutting  plane method provides optimal results with maximum profit compared to branch and bound. In this study, lingo software is used to simplify the data processing process and compare the results of calculations between manual and software to avoid calculation errors.
Key Words : Branch and Bound, Cutting Plane, Purposive Sampling, Lingo

## 1. PENDAHULUAN
Kegiatan produksi erat kaitannya dilakukan pada sebuah usaha, khususnya di bidang makanan. Kegiatan produksi dimulai  dari input yang  melibatkan berbagai  macam  bahan  baku  sampai menghasilkan output ,  yaitu  berupa  barang
ataupun  jasa  yang  memiliki  nilai  guna untuk  dapat  memenuhi  kebutuhan  [1]. Pengelolaan  dan  penggunaan  sumber  daya pada  proses  produksi,  perlu  dilakukan dengan  baik  oleh  pelaku  usaha  agar tercapainya  hasil  produksi  yang  optimal dan  efisien  [2].  Tingkat  produksi  yang
optimal  akan  meningkatkan  keuntungan yang  maksimal  pada  sebuah  usaha [3]. Selain  itu,  sumber  daya  merupakan komponen  penting  untuk  menghasilkan banyaknya  kuantitas  dari  produk  jadi. Maka,  perlunya  pemanfaatan  sumber  daya yang  tepat  agar  tercapainya  keuntungan yang  maksimal  [4].  Tujuan  utama  pada kegiatan usaha adalah memperoleh keuntungan maksimal dengan biaya sumber daya yang minimal [5].
Permasalahan optimalisasi jumlah produksi untuk  mendapatkan  keuntungan  yang maksimum,  dapat  diselesaikan  melalui penggunaan  teknik  program  linier,  yaitu program  linier integer dengan  variabel keputusannya  adalah  bilangan  bulat  [6]. Program  linier  atau linear  programming adalah  sebuah  teknik  perencanaan  bersifat sistematis  dengan  analisis  yang  dilakukan menggunakan  model  matematis  untuk memperoleh  beberapa  solusi  penyelesaian optimum  dari  suatu  masalah  [7].  Adapun tujuan  dari  pengunaan  program  linier adalah untuk mencari keuntungan maksimum dengan mengalokasikan sumber daya secara optimal [8].
Terdapat  beberapa  metode  program  linier yang  digunakan  untuk  mencari  solusi optimal  pada  jumlah  produksi,  seperti metode  simpleks.  Akan  tetapi,  hasil  yang diperoleh  dapat  berupa  bilangan  bulat ataupun  pecahan  [5].  Realita  yang  terjadi dilapangan, sebuah usaha yang memproduksi makanan akan menghasilkan produk  dalam  jumlah  bilangan  yang  bulat dan  tidak  dalam  bentuk  pecahan.  Maka, model  program  linier integer dibutuhkan dalam  permasalahan  optimalisasi  jumlah produksi  karena  variabel  keputusan  yang dihasilkan,  berupa  bilangan  bulat  atau integer .  Metode branch  and  bound serta metode cutting  plane merupakan  metode yang telah dikembangkan untuk
menyelesaikan permasalahan program linier integer [2].  Metode branch  and bound merupakan  metode  yang  membagi
masalah kedalam sub masalah ( branching ). Pembagian masalah tersebut akan membentuk  sebuah  pohon  dan  batasan baru  ( bound )  untuk  memperoleh  solusi optimal  [5].  Metode  ini  membatasi  hasil penyelesaian  yang  menghasilkan  bilangan pecahan  dengan  menambahkan  batasan atas  dan  bawah  untuk  variabel  keputusan, sehingga  didapatkan  hasil  optimal  berupa bilangan integer [9].  Sedangkan,  metode cutting  plane merupakan  metode  yang digunakan apabila variabel keputusan yang dihasilkan  berbentuk  pecahan.  Dengan menambahkan  batasan  baru  yang  disebut sebagai gomory. Metode cutting  plane digunakan untuk memperoleh penyelesaian baru  yang  optimal  dan  hasil  merupakan bilangan integer [3].
Sebagai  studi  kasus  dalam  penelitian, yakni  Pabrik  Tahu  Pak  Yayat  yang beralamat  di  di  Jl  KH.  Agus  Salim  Kp. Bulak  Slamet  No.98  RT/RW  006/008 Kelurahan Bekasi Jaya, Kecamatan Bekasi Timur,  Kota  Bekasi,  Jawa  Barat.  Pabrik Tahu  Pak  Yayat  memproduksi  tahu  putih dan  tahu  kuning.  Setiap  harinya,  pabrik tersebut memproduksi tahu dengan kisaran 100-112  papan  tahu  perhari  dengan  total keuntungan berkisar Rp.1.706.000- Rp.1.805.000,00. Namun, Pabrik Tahu Pak Yayat  mengalami  permasalahan  dalam penentuan kombinasi produksi tahu, sehingga  sumber  daya  yang  dimiliki  tidak teralokasi  secara optimal. Adanya  masalah tersebut berdampak pada keuntungan  yang didapatkan.  Hal  ini  diperoleh  berdasarkan hasil  wawancara  dengan  pemilik  Pabrik Tahu  Pak  Yayat.  Permasalahan  tersebut dapat  dipecahkan  dengan integer  linear programming guna  meminimalkan  biaya bahan baku, sehingga diperoleh keuntungan yang maksimum.
Metode branch  and  bound dan cutting plane adalah  metode  yang  sesuai  dalam optimalisasi jumlah produksi guna memperoleh  keuntungan  yang  maksimum, dengan variabel keputusan yang dihasilkan
Vol. 6 No. 2 Desember 2021
bernilai integer .  Hal  ini  sesuai  dengan penelitian  yang  dilakukan  [2]  dimana metode branch  and  bound dan cutting plane digunakan  untuk  optimalisasi  hasil produksi  tahu  dan  tempe  dengan  hasil keuntungan  metode branch  and  bound lebih  besar  dibandingan  metode cutting plane .  Jumlah  produk  yang  diproduksi, yaitu  tahu  besar  69  papan,  tahu  kecil  19 papan,  tempe  batang  393  bungkus,  dan tempe  kecil  33  bungkus  dengan  total keuntungan  Rp.7.398.900  lebih  besar  dari keuntungan  yang  diperoleh  dari  metode cutting  plane yaitu  Rp.7.300.000  [2]. Penelitian lain yang dilakukan [10] metode branch  and  bound  digunakan untuk optimasi  keuntungan  usaha Sentral  Me Landry .  Dari  hasil  perhitungan  diperoleh bahwa  untuk  memperoleh  keuntungan optimum  sebesar  Rp.5.095.420,  usaha laundry perlu  untuk  mencuci  bedcover, boneka,  pakaian  dan  selimut  berturut  turut sebanyak 53 kg, 188 kg, 1350 kg, dan 101 kg [10].
Tujuan dari penelitian ini adalah mengoptimalkan  jumlah  produksi  tahu melalui  pengalokasian  sumber  daya  yang tepat  untuk  mencapai  keuntungan  usaha yang  maksimum  menggunakan  metode branch and bound dan cutting plane . Hasil dari  kedua  metode  tersebut  dibandingkan untuk  mendapatkan  jumlah  produksi  yang paling  optimal.    Perbandingan  hasil  dari penggunaan kedua metode tersebut merupakan  salah  satu  pembaharuan  dalam penelitian yang dilakukan. Hal itu dikarenakan  masih  sedikitnya  sumber literatur  dari  penelitian  terdahulu.  Melalui penelitian  ini,  dapat  diketahui  metode manakah  yang  memberikan  kombinasi hasil  produksi  optimal  sehingga  diperoleh kentungan  maksimum  untuk  mengatasi permasalahan  pada  Pabrik  Tahu  Pak Yayat.  Selain  itu,  pada  penelitian  ini menggunakan software Lingo (versi  19.0) untuk  memudahkan  proses  perhitungan serta menghindari kesalahan dalam perhitungan yang dilakukan secara manual .

## 2. METODE PENELITIAN
Pada  bagian  rangkaian  alur  penelitian  ini menjelaskan  kegiatan  yang  dilakukan dilapangan, tentunya dimulai dari identifikasi  masalah  dan  rumusan  masalah agar  hasil  akhir  penelitian  sesuai  dengan tujuan  dan  manfaat  yang  telah  ditentukan. Penelitian  ini  dilakukan  di  Pabrik  Tahu Pak Yayat  yang beralamat  di  Jl  KH. Agus Salim  Kp.  Bulak  Slamet  No.98  RT/RW 006/008 Kelurahan Bekasi Jaya, Kecamatan  Bekasi  Timur,  Kota  Bekasi, Jawa  Barat.  Objek  penelitiannya  adalah jenis  tahu  yang  diproduksi  pabrik,  yaitu tahu  putih  dan  tahu  kuning.  Adapun  alur proses penelitian yaitu:
1. Identifikasi Masalah
Berdasarkan  studi  lapangan,  masalah yang ditemukan yaitu jumlah kombinasi  tahu  yang  diproduksi.
Sumber  daya  yang  dimiliki  tidak teralokasi secara optimal dan berpengaruh  pada  keuntungan  yang didapatkan. Studi
pendahuluan dilakukan  melalui  studi  pustaka  dan studi  lapangan.  Pada  studi  pustaka dilakukan  pencarian  literatur-literatur mengenai  permasalahan  dan  hasil penelitian  terdahulu  yang  diperlukan sebagai  pendukung  penelitian  yang akan  dilakukan.  Sedangkan  studi lapangan  dibutuhkan  untuk  melihat dan mengetahui kondisi langsung yang terjadi  pada  Pabrik  Tahu  Pak  Yayat terutama  berkaitan  dengan  objek penelitian.
2. Pengumpulan dan Pengolahan Data Pengumpulan  data  dilakukan  melalui wawancara  langsung  dengan  pemilik pabrik  tahu.  Data  yang  dikumpulkan terdiri  dari  data  primer  dan  sekunder. Data primer berupa informasi penggunaan  bahan  baku  pembuatan tahu yang diperoleh dari hasil wawancara.  Sedangkan  data  sekunder berasal  dari  studi  literatur  penelitian terdahulu  yang  memuat  informasi terkait  objek  maupun  metode  yang
digunakan. Teknik pengambilan sampel menggunakan purposive sampling dikarenakan objek penelitian dipilih berdasarkan pertimbangan peneliti. Pada pengolahan data menggunakan  metode branch  and bound dan cutting plane.
3. Metode Simpleks Langkah-Langkah  Metode  Simpleks dalam masalah maksimasi yaitu [5]:
a. Mengganti  fungsi  tujuan  serta kendala  ke  bentuk  baku  dan menambahkan variabel slack pada semua  fungsi  kendala  dan  fungsi tujuan.
b. Membuat  tabel  awal  metode simpleks
c. Memilih kolom kunci yang memiliki  fungsi  tujuan  dengan nilai terbesar.
d. Memilih baris kunci.
e. Mengubah  nilai  yang  ada  pada baris kunci.
f. Mengubah  nilai-nilai  selain  baris kunci,  sehingga  nilai  yang  ada pada baris kunci bernilai=0.
g. Melanjutkan iterasi atau perbaikan sehingga nilai yang ada pada baris z sudah bernilai tak negatif.
h. Memperoleh solusi optimal dengan  berdasarkan  nilai  pada masing-masing  baris  untuk  setiap variabel keputusan (b i ).
4. Metode Branch and Bound Metode branch and bound merupakan metode yang membagi masalah kedalam  sub  masalah  ( branching ) dengan  menambahkan  batasan  baru ( bound ). Langkah-langkah dalam metode branch and bound yaitu [11]:
a. Langkah pertama selesaikan masalah Integer Linear Programming (ILP) dan menganggap masalah tersebut sebagai Linear Programming
(LP).  Selesaikan  masalah  tersebut menggunakan metode simpleks.
b. Apabila sudah mendapatkan solusi  optimal  dan  hasil  tersebut bernilai integer pada  LP,  maka hasil  tersebut  juga  merupakan solusi  optimal  dari  ILP.  Namun, jika solusi dari variabel keputusan bernilai  pecahan,  maka  dari  salah satu  variabel  dipilih  dan  dibuat percabangan  untuk  mendapatkan sub-masalah ILP.
c. Selanjutnya,  kembali  ke  langkah awal  dan  selesaikan  masalah tersebut dan tentukan sub-masalah dengan  nilai  tertinggi  ( upper bound ) d. Jika  solusi upper  bound sub- masalah belum menghasilkan nilai integer , lakukan percabangan kemudian selesaikan seperti
langkah pada poin c.
5. Metode Cutting Plane Langkah-langkah penyelesaian metode cutting plane yaitu [5]:
a. Menyelesaikan  permasalahan  ILP menggunakan metode simpleks.
b. Apabila  solusi  yang  dihasilkan dari  langkah  pertama  bernilai pecahan, maka dilanjutkan
memilih  sembarang  baris  dari tabel  akhir  metode  simpleks dengan  nilai  b  pecahan  terbesar. Hal ini dilakukan untuk mempercepat iterasi.
c. Pada  baris  yang  telah  dipilih, tambahkan  kendala  seperti  pada persamaan di bawah ini: ∑ ( ) (1)
: Kendala gomory ke- Pecahan dalam Pecahan dalam
d. Selesaikan  metode cutting  plane menggunakan dual simpleks.
6. Aplikasi Lingo Aplikasi Lingo digunakan  untuk membandingkan hasil perhitungan yang diperoleh secara manual data.
7. Analisis Hasil
Setelah  tahap  pengolahan  data,  hasil yang  diperoleh  di  analisis  untuk mengetahui  jumlah  kombinasi  produk yang  akan  menghasilkan  keuntungan maksimum.
8. Kesimpulan dan Saran Kesimpulan  merupakan  keseluruhan hasil,  analisis  serta  hipotesis  yang dapat  diperoleh  dari  penelitian.  Saran diberikan  kepada  Pabrik  Tahu  Pak Yayat  sebagai  bahan  rekomendasi dalam penentuan jumlah produksi tahu sehingga  sumber  daya  yang  dimiliki teralokasi  secara  optimal  dan  dapat memperoleh keuntungan maksimum.

## 3. HASIL DAN PEMBAHASAN
Dalam  satu  hari  Pabrik  Tahu  Pak  Yayat memproduksi  100-112  papan  tahu.  Satu papan tahu putih terdapat 100 pcs, dan satu papan tahu kuning 85 pcs tahu. Dari kedua jenis  tahu  tersebut  memiliki  perbedaan dalam jumlah bahan baku yang digunakan.
Untuk menyelesaikan permasalahan
optimalisasi jumlah
produksi tahu
digunakan  metode  simpleks  kemudian dilanjutkan  dengan  metode cutting  plane dan branch  and  bound .  Adapun  data  yang diperoleh  dari  hasil  penelitian  yang berkaitan dengan bahan baku produksi tahu dapat dilihat pada Tabel 1 di bawah ini.

## Tabel 1. Data Kebutuhan dan Ketersediaan Bahan Baku
No Kendala Tahu Putih Tahu Kuning Ketersediaan 1 Kacang Kedelai 12 kg 9,5 kg 1.160 kg 2 Garam 15 gr 30 gr 2.850 gr 3 Air 39 ltr 35 ltr 4.200 ltr 4 Kunyit 0,8 gr 30 gr 2.300 gr 5 Vinegar 50 ml 110 ml 13.600 ml 6 Kapasitas Produksi 1 papan 1 papan 112 papan Sumber : Pabrik Tahu Pak Yayat Tahapan-tahapan dalam
perhitungan metode simpleks yaitu:
1. Menentukan Variabel
X 1 = Tahu putih
X 2 = Tahu kuning
2. Fungsi tujuan
Z = 14.500 X 1 +18.000 X 2
3. Fungsi Kendala atau Batasan 12X 1 +9,5X 2 ≤ 1.160 15X 1 +30X 2 ≤ 2.850 39X 1 +35X 2 ≤ 4.200
0,8X 1 +30X 2 ≤ 2.300
50X 1 +110X 2 ≤ 13.600
X 1 +X 2 ≤ 112
4. Bentuk Baku Fungsi Tujuan
Z  =  14.500  X 1 +18.000  X 2 +0X 3 +0X 4 + 0X 5 +0X 6 +0X 7 +0X 8
5. Bentuk Baku Fungsi Kendala
12X 1 +9,5X 2 +X 3 ≤ 1.160 15X 1 +30X 2 +X 4 ≤ 2.850 39X 1 +35X 2 +X 5 ≤ 4.200
0,8X 1 +30X 2 +X 6 ≤ 2.300 50X 1 +110X 2 +X 7 ≤ 13.600 X 1 +X 2 +X 8 ≤ 112 X 1, X 2 ≥ 0 ( integer )
6. Memasukkan  Fungsi  Kendala  pada Tabel Awal Metode Simpleks

## Tabel 2. Tabel Awal Metode Simpleks
Basis X 1 X 2 X 3 X 4 X 5 X 3 12 9,5 1 0 0 X 4 15 30 0 1 0 X 5 39 35 0 0 1 X 6 0,8 30 0 0 0 X 7 50 110 0 0 0 X 8 1 1 0 0 0 Cj 14,500 18,000 0 0 0 Basis X 6 X 7 X 8 b X 3 0 0 0 1.160 X 4 0 0 0 2.850 X 5 0 0 0 4.200 X 6 1 0 0 2.300 X 7 0 1 0 13.600 X 8 0 0 1 112 Cj 0 0 0 Sumber : Pengolahan Data
Pada  tabel  2  diperoleh  variabel  masuk  X 2; variabel keluar X 6; elemen pivot 30.
7. Melakukan Iterasi 1
Tabel 3. Iterasi 1 Basis X 1 X 2 X 3 X 4 X 5 X 3 11,747 0 1 0 0 X 4 14,2 0 0 1 0 X 5 38,067 0 0 0 1 X 2 0,027 1 0 0 0 X 7 47,067 0 0 0 0 X 8 0,973 0 0 0 0 Cj 14,020 0 0 0 0 Basis X 6 X 7 X 8 b X 3 -0,317 0 0 431,667 X 4 -1 0 0 550 X 5 -1,167 0 0 1.516,667 X 2 0.033 0 0 76,667 X 7 -3,667 1 0 5.166,667 X 8 -0,033 0 1 35,333 Cj -600 0 0 Sumber : Pengolahan Data
Pada  iterasi  1,  hasil  belum  optimal  karena masih  terdapat  nilai  positif  pada  Cj, sehingga  dilakukan  perhitungan  iterasi  2 dengan  variabel  masuk  X 1; variabel  keluar X 8; dan elemen pivot 0.973.

## 8. Melakukan Iterasi 2

## Tabel 4. Iterasi 2
Basis X 1 X 2 X 3 X 4 X 5 X 3 0 0 1 0 0 X 4 0 0 0 1 0 X 5 0 0 0 0 1 X 2 0 1 0 0 0 X 7 0 0 0 0 0 X 1 1 0 0 0 0 Cj 0 0 0 0 0 Basis X 6 X 7 X 8 b X 3 0,0856 0 -12,07 5,247 X 4 -0,5137 0 -14,59 34,521 X 5 0,137 0 -39,11 134,795 X 2 0,03425 0 -0,027 75,699 X 7 -2,05497 1 -48,36 3.458,082 X 1 -0,0342 0 1,027 36,301 Cj -119,863 0 -1.404 Sumber : Pengolahan Data
Tabel  4  merupakan  tabel  iterasi  2  dimana nilai Cj sudah bernilai tak positif sehingga iterasi  2  merupakan  hasil  akhir  metode simpleks  dengan  nilai  X 1 =36,301  dan X 2 =75,699. Hasil perhitungan metode simpleks disubstitusikan  kedalam  fungsi  tujuan yaitu:
Z = 14.500 X 1 +18.000 X 2 Z = 14.500 (36,301) +18.000 (76,699) Z = Rp.1.888.945,21
Hasil  perhitungan  menggunakan  metode simpleks  diperoleh  keuntungan  sebesar Rp.1.888.945,21  dengan  kombinasi  tahu yang  di  produksi  yaitu  36,301  papan  tahu putih, dan 76,699 papan tahu kuning.
Dalam  studi  kasus  ini,  solusi  optimal variabel keputusan yang diharapkan adalah berupa bilangan integer , maka perhitungan dilanjutkan  menggunakan integer  linear programming dengan  metode branch  and bound dan cutting plane.
Metode Branch and Bound
Berdasarkan  tabel  akhir  metode  simpleks, nilai optimal yang diperoleh yaitu X 1 =36,301  dan  X 2 =75,699.  Karena  nilai variabel keputusan yang diharapkan bernilai integer ,  maka  dilanjutkan  dengan integer  linear  programming menggunakan metode branch  and  bound. Langkah- langkah  perhitungan  metode branch  and bound yaitu:
1. Memilih  variabel  keputusan  yang masih  bernilai  pecahan  terbesar  yaitu X 2 =75,699 untuk membuat cabang.
2. Variabel  X 2 dicabangkan  menjadi  2 sub-masalah,  yaitu  sub-masalah  1  dan 2.
3. Untuk  sub-masalah  1,  tambahkan kendala  X 2 ≤75  dan  sub-masalah  2
X 2 ≥ 76.
4. Mencari  solusi  penyelesaian  dari setiap sub-masalah. Penyelesaian dapat terlihat pada gambar 2.
Gambar 2.  Pohon Percabangan Branch and

## Bound
Berdasarkan  gambar  2,  solusi  yang diperoleh  dengan  adanya  penambahan batasan  sub-masalah  1,  X 2 ≤75  dan  sub- masalah  2  X 2 ≥ 76.  sudah  mendapatkan solusi integer .  Untuk  batasan  X 2 ≤75 didapatkan  hasil  X 1 =36  dan  X 2 =75. Sedangkan  X 2 ≥ 76  hasil  yang  diperoleh yaitu X 1 =25 dan X 2 =76. Dengan menggunakan  metode branch  and  bound, kombinasi  produk  yang  menghasilkan
keuntungan maksimum sebesar Rp.
1.872.000,00  yaitu  X 1 =36  dan  X 2 =75  atau tahu  kuning  yang  diproduksi  sebanyak  36 papan dan tahu putih 75 papan.

## Metode Cutting Plane
Hasil  akhir  dari  perhitungan  metode simpleks  diperoleh  nilai  X 1 =36,301  dan X 2 =75,699.  Metode cutting  plane dapat dijalankan  dengan  menambahkan  batasan baru  yang disebut sebagai kendala gomory berdasarkan  variabel  yang  memiliki  nilai pecahan terbesar yaitu X 2.
Penambahan kendala gomory yaitu: X 2 +0,03425X 6 -0,027X 8 =75,699
X 2 +0X 6 -X 8 -75=0,699-0,03425X 6 -0,973 X 8 0,699-0,03425X 6 -0,973 X 8 +Sg 1 ≤ 0 -0,03425X 6 -0,973 X 8 +Sg 1 ≤ -0,699
Selanjutnya  memasukkan  kendala gomory kedalam tabel akhir simpleks. Berdasarkan tabel  5,  ruas  kanan  dari  kendala gomory bernilai  negatif  dan  menjadi  tidak  layak, sehingga  untuk  dapat  menyelesaikan  tabel tersebut digunakan metode dual simpleks.
Tabel 5. Penambahan Kendala Gomory
Basis X 1 X 2 X 3 X 4 X 5
X 6 X 7 X 8 Sg 1 b X 3 0 0 1 0 0 0,0856 0 -12,07 0 5,247 X 4 0 0 0 1 0 -0,5137 0 -14,59 0 34,521 X 5 0 0 0 0
1 0,137 0 -39,11 0 134,795 X 2 0 1 0 0 0 0,03425 0 -0,027 0 75,699 X 7 0 0 0 0
0 -2,05497 1 -48,36 0 3.458,082 X 1 1 0 0 0 0 -0,0342 0 1,027 0 36,301 Sg 1 0 0 0 0 0 -0,03 0 -0,97 1 -0,699 Cj 0 0 0 0 0 -119,863 0 -1.404 0 Sumber : Pengolahan Data Tabel 6. Hasil Penyelesaian Cutting Plane Basis X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 Sg 1 b X 3 0 0 1 0
0 0 0 -14,50 2,50 3,50 X 4 0 0 0 1 0 0
0 0 -15 45 X 5 0 0 0 0 1
0 0 -43 4 132 X 2 0 1 0 0 0 0
0 -1 1 75 X 7 0 0 0 -3,94 0,23 2,05 1 58,36 -60 3.348,89 X 1 1 0 0 0
0 0 0 2 -1 37 X 6 0 0 0 0 0 1 0 28,40 -29,20 20,40 Cj 0 0 0 0 0
0 0 -11.000 -3.500 Sumber : Pengolahan Data
Z   = Rp. 1.888.945,21 X 1 = 36,301 X 2 = 75,699 x 2 ≤ 75 Z   = Rp. 1.872.000,00 X 1 = 36 X 2 = 75 1 2 x 2 ≥ 76 Z   = Rp. 1.730.500,00 X 1 = 25 X 2 = 76
Berdasarkan  hasil  perhitungan  dengan penambahan  kendala gomory Sg 1 ,  tabel  6 sudah optimal karena nilai b sudah bernilai positif  dan  baris  Cj  bernilai  tak  positif. Dari  hasil  akhir  metode cutting  plane diperoleh  nilai integer untuk  variabel keputusan  X 1 =37  dan  X 2 =75.  Sehingga kentungan maksimum
yang dapat diperoleh yaitu:
Z = 14.500 X 1 +18.000 X 2 Z = 14.500 (37) +18.000 (75)
Z = Rp.1.886.500,00

## Perbandingan Hasil Perhitungan

## Tabel 5. Perbandingan Hasil Dua Metode
Variabel Metode Branch and Bound Metode Cutting Plane X 1 36 37 X 2 75 75 Z Rp. 1.872.000,00 Rp. 1.886.500,00 Sumber : Pengolahan Data
Tabel  di  atas  merupakan  perbandingan hasil  dari  metode branch  and  bound dan cutting  plane. Terlihat  metode cutting plane memiliki  penyelesaian  yang  lebih optimal  dibandingkan  dengan  metode branch  and  bound. Keuntungan  yang dihasilkan  dari  metode cutting  plane sebesar Rp.1.886.500,00 dengan kombinasi
tahu  yang  diproduksi  yaitu  37  papan  tahu putih dan 75 papan tahu kuning. Sedangkan  dengan  menggunakan  metode branch  and  bound keuntungan  yang diperoleh  sebesar  Rp.1.872.000,00  lebih kecil  dari  hasil  yang  diperoleh  metode cutting plane .
Pengolahan Data Menggunakan Software Lingo Gambar  3  merupakan  hasil  pengolahan data  menggunakan software lingo.  Pada tampilan  hasil,  terdapat  total  variabel, banyaknya nonlinear variabel, integer variabel,  total  batasan,  batasan nonlinear , hasil  nilai integer dari  setiap  variabel,  dan total keuntungan. Hasil yang diperoleh dari software dapat diketahui bahwa kombinasi jumlah  produk  yang  optimal  dalam produksi  tahu  yaitu  37  papan  tahu  putih dan  75  papan  tahu  kuning.  Dengan  total keuntungan yang diperoleh sebesar Rp.1.886.500.  Penggunaan software  lingo diperlukan  untuk  memudahkan  dalam proses pengolahan data  serta  menyamakan hasil  perhitungan  secara manual dan  hasil yang diperoleh dari software serta menghindari  kesalahan  dalam  perhitungan ( human error ).
Gambar 3. Hasil Pengolahan Menggunakan Software Lingo

## 4. SIMPULAN
Berdasarkan hasil analisa dan pembahasan yang telah dijabarkan, permasalahan penentuan  kombinasi  produksi  tahu  dan alokasi  sumber  daya  untuk  mencapai keuntungan  maksimum  yang  dialami Pabrik  Tahu  Pak  yayat,  dapat  diselesaikan menggunakan integer linear programming. Dalam penelitian ini, metode yang digunakan  adalah  metode branch  and bound dan cutting plane. Keuntungan yang diperoleh  dengan  menggunakan  metode branch
and bound
sebesar
Rp.1.872.000,00  dan kombinasi  produk yaitu tahu kuning yang diproduksi sebanyak  36  papan  tahu  putih  dan  75 papan  tahu  kuning.  Sedangakan  metode cutting  plane keuntungan  yang  diperoleh Rp.1.886.500,00  dengan  kombinasi  tahu yang diproduksi  yaitu  37 papan tahu putih dan  75  papan  tahu  kuning.  Maka  dapat ditarik  kesimpulan  bahwa  metode cutting plane memberikan hasil kombinasi produksi  yang  optimal  dan  memberikan
keuntungan maksimum. Selain itu, penggunaan software lingo menunjukkan hasil  yang  sama  dengan  perhitungan  yang dilakukan secara manual. Adanya keterbatasan  penelitian  yaitu  penelitian dilakukan  hanya  pada  aktivitas  produksi dengan  produk  yang  dihasilkan  berupa makanan.  Jika  penelitian  dilakukan  pada aktivitas  produksi  barang  mungkin  akan berbeda  dari  segi  pengumpulan  dan pengolahan  data.  Selain  itu  saran  untuk penelitian selanjutnya yaitu dapat memperhatikan  dan  mempertimbangkan faktor-faktor lain seperti biaya, dan jumlah tenaga kerja.

## UCAPAN TERIMAKASIH
Ucapan  terimakasih  penulis  sampaikan kepada Universitas
Singaperbangsa
Karawang  yang telah mendukung jalannya penelitian ini.

## DAFTAR PUSTAKA
[1]  Sri  Adiningsih, Ekonomi  Mikro . Yogyakarta: BPFEYogyakarta, 1999.
[2]  Raudhatul  Jannah  A.M,  Arnellis,  and Riry  Sriningsih,  "Optimasi  Hasil Produksi  Tahu  dan  Tempe  dengan Metode  Branch  and  Bound  dan Metode  Cutting  Plane," Journal  of Mathematics  UNP , vol.  III, no. 1, pp. 42 - 47, 2018.
[3]  Nico,  Iryanto,  and  Gim  Tarigan, "Aplikasi  Metode  Cutting  Plane Dalam  Optimisasi  Jumlah  Produksi Tahunan  di  PT.  XYZ," Saintia Matematika ,  vol.  II,  no.  2,  pp.  127  -
136, 2014.
[4]  Sari Devi Purba and Faiz
Ahyaningsih,  " Integer Programming Dengan  Metode  Branch  and  Bound Dalam  Optimasi  Jumlah  Produksi Setiap  Jenis  Roti  Pada  PT.  Arma Anugerah  Abadi," KARISMATIKA , vol. VI, no. 3, pp. 20 - 29, 2020.
[5]  Sri Basriati,
" Integer Linear Programming  Dengan  Pendekatan Metode Cutting Plane dan Branch and Bound  Untuk  Optimasi  Produksi
Tahu," Jurnal  Sains  Matematika  dan
Statistika , vol. IV, no. 2, pp. 95 - 104, 2018.
[6]  Intan  Syahrini,  Radhiah,  and  Faizah Amalina, "Mengoptimalkan Keuntungan Produksi Dengan Menggunakan  Metode  Branch  And Bound Dan Metode Cutting Plane," in Seminar  Nasional  Matematika  dan Terapan , Aceh, 2019.
[7]  Aminudin, Prinsip-prinsip Riset Operasi ,  Lemeda  Simarmata,  Ed.
Jakarta, Indonesia: Erlangga, 2005.
[8]  Astuti Meflinda and Mahyarni, Operation  Research  (Riset  Operasi) .
Pekanbaru,  Indonesia:  UR  PRESS
Pekanbaru, 2011.
[9]  Siswanto, Operation Reasearch .
Jakarta, Indonesia : Erlangga, 2007.
[10] Sri  S  Supatimah,  Farida,  and  Siska Andriani, "Optimasi Keuntungan dengan  Metode  Branch  and  Bound," AKSIOMA:  Jurnal  Matematika  dan Pendidikan Matematika , vol. X, no. 1, pp. 13-23, Juli 2019.
[11] Wahyudin  Nur  and  Nurul  M  Abdal, "Penggunaan  Metode  Branch  and Bound  dan  Gomory  Cut  dalam Menentukan  Solusi Integer Linear Programming," Jurnal  Saintifik ,  vol.
II, no. 1, pp. 9-15, Januari 2016.