Vol. 20, No. 3, May 2024, pp. 552-567 DOI: 10.20956/j.v20i3.32888

## Integer Linear Programming In Production Profit Optimization Problems Using Branch And Bound Methods & Gomory Cutting Plane
Integer Linear Programming Dalam Masalah Optimasi Keuntungan Produksi Menggunakan Metode Branch And Bound & Gomory Cutting Plane
Nurweni Putri 1 *, Maya Sari Syahrul 2 , Rosi Ramayanti 3
Universitas Dharma Andalas Email : 1 nurweniputri@gmail.com 2 maya@unidha.ac.id 3 rosiramayanti@gmail.com
Received: 25 January 2024 , revised: 12 March 2024 , accepted: 13 March 2024

## Abstract
Integer Linear Programming is a mathematical model that allows the results of solving cases in linear  programming  in  the  form  of  integers.  Methods  to  solve  Integer  Programming  problems include  the  Branch  and  Bound  Method  and  the  Gomory  Cutting  Plane  Method.  Both  of  these methods  have  certain  rules  for  adding  new  constraint  functions  until  an  optimal  solution  to  an integer  is  obtained.  The  purpose  of  this  study  is  to  optimize  the  profits  of  the  production  of UMKM  Capal  Classic  Shoes  Kab.  Agam    by  using  the  Branch  and  Bound  method  and  the Gomory  Cutting  Plane  method  and  analyzing  the  comparison  of  optimal  results  resulting  from the two methods. The data used in the study are data on raw materials for making classic sandals and  profit  data.  The  results  obtained  by  these  two  methods  produce  the  same  maximum  profit, namely  RP.  664,000  with  each  producing  15  pairs  of  men's  sandals  and  13  pairs  of  women's sandals.  But  in  its  completion,  the  Branch  and  Bound  method  requires  many  iterations  and  a longer time compared to the Gumory Cutting plane method.
Keywords: Linear Programming,  Integer Programming, Branch and Bound, Gomory Cutting Plane.

## Abstrak
Integer  Linear  Programming adalah  sebuah  model  matematis  yang  memungkinkan  hasil penyelesaian  kasus  pada  pemrograman  linier  yang  berupa  bilangan  bulat.  Metode  untuk menyelesaikan persoalan Integer Programming diantaranya adalah Metode Branch and Bound & Metode Gomory Cutting Plane. Kedua metode ini memiliki aturan tertentu dalam menambahkan fungsi  batasan  baru  hingga  diperoleh  solusi  optimal  bilangan  bulat.  Tujuan  dari  penelitian  ini adalah  mengoptimalkan  keuntungan  dari  produksi  UMKM Capal  Classic  Shoes Kabupaten Agam dengan menggunakan metode Branch and Bound dan metode Gomory Cutting Plane serta menganalisis  perbandingan  terhadap  hasil  optimal  yang  dihasilkan  dari  kedua  metode  tersebut.

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Data yang digunakan dalam penelitian adalah data bahan baku pembuatan sendal klasik dan data keuntungannya. Hasil yang diperoleh kedua metode ini menghasilkan keuntungan maksimalyang sama yaitu RP. 664.000 dengan masing-masing memproduksi 15 pasang sandal laki-laki dan 13 pasang  sandal  perempuan.  Namun  dalam  penyelesaiannya,  metode Branch  and  Bound memerlukan  iterasi  yang  banyak  dan  waktu  yang  lebih  lama  dibandingkan  dengan  metode Gumory Cutting plane .
Kata kunci: Linear Programming, Integer Programming, Branch and Bound, Gomory Cutting Plane.

## 1.  PENDAHULUAN
Pasca  pandemi  Covid-19  pemerintah  mengeluarkan  berbagai  strategi  kebijakan  guna memulihkan perekonomian Indonesia. Salah satu strategi yang dilakukan adalah membangkitkan industri Usaha Mikro, Kecil, dan Menengah (UMKM). Jumlah UMKM yang semakin meningkat menimbulkan  persaingan  bisnis  yang  semakin  ketat  dan  sulit.  Persaingan  pasar yang  meningkat menuntut pelaku UMKM menyusun strategi dengan baik agar mampu bertahan dan menjadi lebih unggul.  Selain  itu  pelaku  UMKM  juga  harus  membuat  keputusan  yang  tepat  dengan mempertimbangkan batasan-batasan yang ada sesuai dengan tujuan yang ingin dicapai [6].
Persoalan  umum  yang  dihadapi  oleh  pelaku  UMKM  adalah  dalam  melakukan  optimasi keuntungan  dalam  produksi.  Selain  itu  juga  bagaimana  mengkombinasikan  faktor-faktor produksi  atau  sumberdaya  yang  dimiliki  secara  bersama  dengan  tepat  agar memperoleh keuntungan  maksimal  dengan  biaya  yang  minimal  [11].  Pemanfaatan bahan  baku  yang  tepat sangat  diperlukan  untuk  memaksimalkan  hasil  produksi  sehingga  menghasilkan  keuntungan yang  maksimal  pula.  Oleh  karena  itu,  setiap  UMKM  harus  mengetahui  model  yang menghubungkan  antara  masalah  dengan  alternatif pemecahan sesuai dengan tujuan yang hendak dicapai. Model yang dapat  digunakan untuk permasalahan tersebut adalah program linier ( linear programming ) [26].
Dalam masalah program linier solusi optimal yang diperoleh mungkin saja bilangan pecahan. Untuk  beberapa  situasi,  solusi  berbentuk  pecahan  dapat  diterima.  Tetapi  dalam  situasi  tertentu solusi optimal haruslah bilangan bulat, misalnya jumlah barang dan jumlah orang. Menurut [13] persoalan  program  linier  menggunakan  solusi  variabel  keputusannya  harus  merupakan  bilangan bulat disebut program linier integer ( integer linear programming ). Program linier integer adalah program linier dengan penambahan fungsi batasan bahwa beberapa atau semua variabelnya harus bernilai bulat [25].
UMKM Capal  Classic  Shoes merupakan  salah  satu  UMKM  yang  bergerak  di  bidang produksi sendal klasik di Kabupaten Agam. Mengingat UMKM ini terus mengalami pertumbuhan, maka  sistem  produksinya  perlu  dioptimalkan  guna  diperolehnya  pendapatan  yang  maksimal. Salah satu  permasalahan  yang  dimiliki  UMKM Capal  Classic  Shoes dalam  hal proses  produksi adalah produk yang dihasilkan dan diproduksi berdasarkan pengalaman orang-orang yang bekerja di  bidang  tersebut  dan  tidak  diketahui  apakah  menggunakan  metode  yang  tepat  dalam memanfaatkan  bahan  baku  yang  tersedia.  Hal  ini  berakibat  pada  banyaknya  produk  yang dihasilkan belum tentu optimal.
Permasalahan diatas termasuk kedalam masalah integer linear programming untuk mencari solusi optimal. Ada banyak metode yang bisa digunakan untuk menyelesaikan permasalahan ini,

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
diantaranya  metode Branch  and  Bound dan  metode Gomory  Cutting  Plane. Kedua  metode  ini memiliki  aturan  tertentu  dalam  menambahkan  fungsi  batasan  baru  hingga  diperoleh  solusi optimal bilangan bulat. Metode Branch and Bound merupakan pengembangan dari program linier dimana  beberapa  atau  semua  variabel  keputusannya  harus  integer.  Metode  ini  membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas  dan  bawah  bagi  masing-masing  solusi  yang  bernilai  pecahan  agar  bernilai  bulat  sehingga setiap  pembatasan  akan  menghasilkan  cabang  baru  [22].  Sedangkan  metode  Gumory Cutting Plane menggunakan  penambahan  batasan  baru  yang  disebut  gomory  dalam  menyelesaikan persamaan linier yang memiliki solusi tidak bulat atau pecahan agar bernilai bulat [22].
Sebelumnya  pada  [1],  [14]  &  [21]  sudah  menggunakan  metode Branch  and  Bound dalam menyelesaikan  permasalahan  integer  programming  dalam  mencari  solusi  optimal.  Menurut penelitian  tersebut  dengan  metode Branch  and  Bound dalam  pengoptimalan  diperoleh  hasil kapasitas  pengalokasian  produk  yang  optimal  sehingga  diperoleh  juga  keuntungan  yang  lebih besar.  Selain  itu  metode  ini  dianggap  lebih  efisien  dibanding  metode  lain.  Penelitian  mengenai metode Gomory Cutting Plane pernah dilakukan oleh  [7] & [16] untuk mengetahui konsep dan langkah  kerja  metode  ini  serta  mengetahui  hasil  optimal  maksimasi  pendapatan  laba  penjualan dan  minimasi  biaya  produksi.  Hanya  saja  dalam  penerapannya  metode Gomory  Cutting  Plane jarang digunakan dibanding metode lainnya. Penelitian lain juga ada tentang perbandingan antara kedua metode tersebut yaitu [4] &[ [27] dimana menemukan hasil yang berbeda, yaitu pada [4] menghasilkan  optimasi  produksi  menggunakan  metode Branch  and  Bound memberikan keuntungan yang lebih baik, sedangkan pada [27] memperlihatkan bahwa hasil optimasi produksi menggunakan  metode Branch  and  Bound &  metode Gomory  Cutting  Plane memperoleh  hasil yang  sama,  tetapi  metode Branch  and  Bound memerlukan  iterasi  yang  lebih  banyak  dan  waktu yang lebih lama.
Berdasarkan  uraian  diatas,  maka  penelitian  mengkaji  tentang  integer  linier  programming dalam  masalah  optimasi  keuntungan  produksi.  Pada  penelitian  ini  akan  menghitung  keuntungan optimal menggunakan metode Branch and Bound dan metode Gomory Cutting Plane. Selain itu, penelitian  ini  juga  akan  melakukan  analisis  perbandingan  terhadap  hasil  optimal  dari  kedua metode  tersebut.  Untuk  mempermudah  proses  perhitungan  pada  kedua  metode  ini  digunakan bantuan software POM-QM.

## 2. METODE

## 2.1 Pengumpulan dan Pengolahan Data
Pengumpulan  data  dilakukan  melalui  wawancara  langsung  dengan  pemilik  UMKM  Capal Classic  Shoes.  Data  yang  dikumpulkan  dari  hasil  wawancara  berupa  informasi penggunaan  dan kesediaan bahan baku pembuatan sendal klasik beserta data keuntungnnya. Pada pengolahan data menggunakan metode Branch and Bound dan Gomory Cutting Plane.

## 2.2 Metode Penelitian
(a). Metode Simpleks
Langkah-Langkah Metode Simpleks dalam masalah maksimasi yaitu [5]:

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
1. Mengganti fungsi tujuan serta kendala ke bentuk baku dan menambahkan variabel Slack pada semua fungsi kendala dan fungsi tujuan.
2. Membuat tabel awal metode simpleks seperti berikut
Tabel 2.2.1 Tabel Simpleks CB 𝐶𝑗 𝑏𝑖 𝑅𝑖 Basis 𝑋1  𝑋2 𝑆1 𝑆2
𝑆1 𝑆2 𝑍𝑗 𝐶𝑗 - 𝑍𝑗
Keterangan Tabel Simpleks: - CB
= Koefisien fungsi tujuan untuk variabel basis.
- Variabel Basis = Variabel yang nilainya bukan nol. - Koef 𝑥 1 & 𝑥 2 = Produksi mix - Variabel Slack = Koefisien variabel slack dalam fungsi tujuan. - 𝑏 𝑖 = Kuantitas atau nilai kanan - Kepala kolom = Variabel & koefisien dalam fungsi tujuan. - 𝑆 1 & 𝑆 2 = Persamaan dalam fungsi batasan - 𝑍 𝑗 = Total profit yang diperoleh - 𝐶 𝑗 − 𝑍 𝑗 = Net profit (masalah yang ingin diselesaikan) - 𝑅 𝑖 = 𝑏 𝑖 dibagi kolom kunci.
3. Memilih kolom kunci yang memiliki fungsi tujuan dengan nilai terbesar.
4. Memilih  baris  kunci;  baris  kunci  ditentukan  dengan  membagi  nilai 𝑏𝑖 dengan  masing masing  angka  pada  kolom  kunci.Yang  menjadi  baris  kunci  adalah  baris  yang  hasil baginya paling kecil dan tidak  negatif. Jika ada yang sama boleh pilih salah satu.
5. Mengubah nilai-nilai selain baris kunci, sehingga nilai yang ada pada baris kunci bernilai = 0.
6. Periksa  apakah  tabel  sudah  optimal.  Untuk  tujuan  maksimasi,  keoptimalan  tabel  dilihat dari  koefisien  fungsi  tujuan  (nilai  pada  baris  z).  Tabel  sudah  optimal  jika  semua  nilai pada baris z sudah positif atau 0, sehingga iterasi dihentikan. Jika belum, lakukan kembali iterasi mulai langkah 3.
7. Memperoleh  solusi  optimal  dengan  berdasarkan  nilai  pada  masing-masing  baris  untuk setiap variabel keputusan (b i ).

## (b). Metode Branch and Bound
Metode Branch  and  Bound merupakan  salah  satu  metode  untuk  menghasilkan penyelesaian  optimal  pemrograman  linier  yang  menghasilkan  variabel-  variabel  keputusan bilangan  bulat.  Sesuai  dengan  namanya,  metode  ini  membatasi  penyelesaian  optimum  yang akan  menghasilkan  bilangan  pecahan  dengan  cara  membuat  cabang  atas  dan  bawah  bagi masing-  masing variabel keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru [24].

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Langkah-langkah dalam metode Branch and Bound yaitu [11]:
1. Dapatkan  solusi  simpleks  optimal  dari  model  program  linier  dengan  batasan  integernya dilepaskan,
2. Tentukan solusi simpleks sebagai batas atas sedangkan solusi hasil pembulatan ke bawah sebagai batas bawah.
3. Pilih  variabel  dengan  bagian  pecahan  yang  terbesar  untuk  pencabangan.  Ciptakan  dua batasan  baru  untuk  variabel  ini  yang  mencerminkan  pembagian  nilai  integer.  Hasilnya adalah sebuah batasan ≤ dan sebuah batasan ≥ . Jika solusi up )
4. Ciptakan  dua  node  baru,  satu  dengan  batasan  ≤  dan  satu  dengan  batasan  ≥.,  (e0 Selesaikan model program linier dengan batasan baru yang ditambahkan pada tiap node.
5. Solusi  simpleks  awal  merupakan  batas  atas  pada  setiap  node  sedangkan  solusi  integer maksimum yang ada pada node mana saja merupakan batas bawah.
6. Jika  proses  ini  menghasilkan  solusi  integer  ﬁsibel  dengan  nilai  batas  atas  terbesar  pada akhir node yang mana saja, maka solusi integer optimal telah tercapai,
7. Jika tidak muncul suatu solusi integer ﬁsibel, lakukanlah pencabangan lagi,
8. Ulangi langkah 3
(c) Metode Cutting Plane
Pendekatan  yang  dilakukan  pada  metode  cutting  plane  adalah  dengan  membuat  batasan tambahan sehingga dapat mengeliminasi solusi yang tidak integer. Proses ini akan berakhir apabila diperoleh solusi dengan variabel (yang dikehendaki) bernilai integer [26].
Langkah-langkah penyelesaian metode cutting plane yaitu [5]:
1. Menyelesaikan masalah integer programming dengan menggunakan metode simpleks dan mengabaikan syarat integer.
2. Memeriksa  solusi  optimum.  Jika  semua  variabel  basis  memiliki  nilai  integer,  solusi optimum  integer  telah  diperoleh  dan  proses  solusi  telah  berakhir.  Jika  satu  atau  lebih variabel basis masih memiliki nilai pecah, dilanjutkan memilih sembarang baris dari tabel akhir  metode  simpleks  dengan  nilai  b  pecahan  terbesar.  Hal  ini  dilakukan  untuk mempercepat iterasi
3. Pada  baris  yang  telah  dipilih,  tambahkan  kendala  seperti  pada  persamaan  di bawah ini:

## 𝑆 ∑ ( 𝑘) 𝑥
Keterangan : 𝑆 : Kendala gomory ke – i
: Pecahan dalam
: Pecahan dalam 𝑏
4. Selesaikan metode Cutting Plane menggunakan dual simpleks.

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Identifikasi
Masalah
Pengumpulan Data Formulasi Model
- Menentukan Variabel Keputusan
- Menentukan Fungsi Tujuan dan Fungsi Kendala Mulai Apakah semua variabel keputusan berupa bilangan bulat Gunakan Metode Branch and Bound dan Metode Cutting Plane Tidak Model Matematika Pengoptimalan  Produksi UMKM Capal Calssics Shoes Penyelesaian Menggunakan Metode Simpleks S olusi Optimal Kesimpulan Selesai
5. Solusi  dikatakan  optimal,  apabila  semua  variabel  pada  ruas  kanan  mempunyai  nilai integer.  Jika  belum  integer,  maka  gomory  harus  ditambahkan  lagi  dan  metode  dual simpleks digunakan sampai mencapai solusi integer
Untuk mempermudahkan dalam menganalisis metode penelitian yang akan digunakan, alur penelitian ini disusun dalam bentuk diagram alir ( Flowchart ) di bawah ini
Gambar 2.1 Diagram Alir Penelitian

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti

## 3. HASIL & PEMBAHASAN
Pada  artikel ini akan  dikaji  tentang  optimasi  keutungan  produksi  UMKM  Capal Classic Shoes  Kabupaten  Agam  yang  diperoleh  setelah  dilakukan  perhitungan integer  programming dengan menggunakan metode Branch and Bound dan metode Gomory Cutting Plane.
Tabel 3.1 Data Bahan Baku Pembuatan Satu Pasang Sendal (per hari) No. Bahan Jenis sandal (Variabel) Kapasitas Satuan 𝑥 1 𝑥 2 𝑥 3 Persediaan 1. Sol kulit 20 0 10 400 Gram 2. Busa 3 1 2 100 Lembar 3. Songket 200 1.250 200 20.000 𝑐𝑚 4. Besi alas 2 2 2 70 Buah 5. Mika 0,142 0,142 0,142 4 Lembar 6. Tali kulit 10 0 7 175 𝑐𝑚 7. Gesper 2 0 2 50 buah Tabel 3.2 Data Keuntungan Penjualan Satu Pasang Sendal Jenis    sandal Variabel Modal (Rp) Penjualan (Rp) Keuntungan (Rp) Sandal laki-laki 𝑥 1 105.000 125.000 20.000 Sandal perempuan 𝑥 2 127.000 155.00 28.000 Sandal anak-anak 𝑥 3 85.000 105.000 20.000
Berdasarkan Tabel 3.2 diperoleh sistem linier dengan fungsi kendala,
20 𝑥 1 + 10 𝑥 3 ≤ 400,
3 𝑥 1 + 𝑥 2 + 2 𝑥 3 ≤ 100,
200 𝑥 1 + 1.250 𝑥 2 + 200 𝑥 3 ≤ 20.000,
2 𝑥 1 + 2 𝑥 2 + 2 𝑥 3 ≤ 70,
0,142 𝑥 1 + 0,142 𝑥 2 + 0,142 𝑥 3 ≤ 4,
10 𝑥 1 + 7 𝑥 3 ≤ 175,
2 𝑥 1 + 2 𝑥 3 ≤ 50.
Akibatnya diperoleh fungsi kendala yang memuat variabel Slack ,
20 𝑥 1 + 10 𝑥 3 + 𝑆 1 = 400,
3 𝑥 1 + 𝑥 2 + 2 𝑥 3 + 𝑆 2 = 100,
200 𝑥 1 + 1.250 𝑥 2 + 200 𝑥 3 + 𝑆 3 = 20.000,
2 𝑥 1 + 2 𝑥 2 + 2 𝑥 3 + 𝑆 4 = 70,
0,142 𝑥 1 + 0,142 𝑥 2 + 0,142 𝑥 3 + 𝑆 5 = 4, 10 𝑥 1 + 7 𝑥 3 + 𝑆 6 = 175,

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
2 𝑥 1 + 2 𝑥 3 + 𝑆 7 = 50.
𝑥 𝑖 ≥ 0, 𝑖 = 1, 2, 3, dan 𝑆 j ≥ 0, 𝑗 = 1,2 7.
dengan fungsi tujuan yaitu,
Maks Z = 20.000 𝑥 1 + 28.000 𝑥 2 + 20.000 𝑥 3 + 0 𝑆 1 + 0 𝑆 2 + 0 𝑆 3 + 0 𝑆 4 + 0 𝑆 5 + 0 𝑆 6 + 0 𝑆 7 .
Berdasarkan Tabel 3.1 dan Tabel 3.2 maka terbentuklah Tabel Awal dalam memperoleh keuntungan maksimum menggunakan Metode Tabel Simpleks seperti berikut ini
Tabel 3.3 Tabel Awal CB 𝐶𝑗 20.000 28.000 20.000 0 0 0 0 0 0 0 𝑏 𝑖 𝑅 𝑖 Basis 𝑥 1 𝑥 2 𝑥 3 𝑆 1 𝑆 2 𝑆 3 𝑆 4 𝑆 5 𝑆 6 𝑆 7 0 𝑆 1 20 0 10 1 0 0 0 0 0 0 400 20 0 𝑆 2 3 1 2 0 1 0 0 0 0 0 100 100 0 𝑆 3 200 1.250 200 0 0 1 0 0 0 0 20.000 16 0 𝑆 4 2 2 2 0 0 0 1 0 0 0 70 35 0 𝑆 5 0,142 0,142 0,142 0 0 0 0 1 0 0 4 28,16 0 𝑆 6 10 0 7 0 0 0 0 0 1 0 175 17,5 0 𝑆 7 2 0 2 0 0 0 0 0 0 1 50 25 𝑍 j 0 0 0 0 0 0 0 0 0 0
𝐶 j 𝑍 j 20.000 28.000 20.000 0 0 0 0 0 0 0 = kolom kunci = baris kunci = angka
Selanjutnya mencari angka baru pada baris non kunci  dengan cara yang sama pada saat mencari  angka  baru  pada  baris  non  kunci  dan  nilai  Z j sehingga  diperoleh  tabel  Iterasi  1 sebagai berikut :
Tabel 3.4 Tabel Iterasi 1 (Hasil Akhir Tabel Iterasi 1)
CB 𝐶𝑗 20.000 28.000 20.000 0 0 0 0  0 0 0 𝑏 𝑖 𝑅 𝑖 Basis 𝑥 1 𝑥 2 𝑥 3 𝑆 1 𝑆 2 𝑆 3 𝑆 4 𝑆 5 𝑆 6 𝑆 7 0 𝑆 1 20 0 10 1 0 0 0  0 0 0 400 20 0 𝑆 2 2,84 0 1,84 0 1 -0,0008  0  0 0 0 84 29,58 28.000 𝑥 2 0,16 1 0,16 0 0 0,0008 0  0 0 0 16 100 0 𝑆 4 1,68 0 1,68 0 0 -0,0016  1  0 0 0 38 22,61 0 𝑆 5 0,1193 0 0,1193 0 0 -0,0001  0 1 0 0 1,728 14,48 0 𝑆 6 10 0 7 0 0 0 0  0 1 0 175 17,5 0 𝑆 7 2 0 2 0 0 0 0  0 0 1 50 25 𝑍 j 4.480 28.000 4.480 0 0 22,4 0  0 0 0  448.000 𝐶 j 𝑍 j 15.520 0 15.520 0 0 -22,4 0  0 0 0 = kolom kunci = baris kunci = angka
Berdasarkan Tabel 3.4 hasil dari nilai dari 𝐶𝑗 - 𝑍𝑗 masih positif maka nilainya masih belum maksimum  sehingga  dilanjutkan  ke  Tabel  Iterasi  berikutnya  dengan  cara  yang  sama  pada  saat membuat  Tabel  Iterasi  1.  Setelah  dilakukan  pencarian  beberapa  Tabel  Iterasi  hasil  akhir  yang optimal didapat pada Tabel Iterasi ke-2 berikut:

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Tabel 3.5 Tabel Iterasi 2 (Hasil Akhir Tabel Iterasi 2) CB 𝐶𝑗 20.000 28.000 20.000 0 0  0 0  0 0 0 𝑏 𝑖 Basis 𝑥 1 𝑥 2 𝑥 3 𝑆 1 𝑆 2 𝑆 3 𝑆 4 𝑆 5 𝑆 6 𝑆 7 0 𝑆 1 0 0 -10 1 0  0,019 0  -167,6727 0 0  110,26 0 𝑆 2 0 0 -1,0 0 1  0,0019 0  -23,8095 0 0  42,85 28.000 𝑥 2 0 1 0 0 0  0,001 0  -1,3414 0 0  13,68 0 𝑆 4 0 0 0 0 0  0 1  -14,0845 0 0  13,66
Karena nilai pada kolom 𝐶 j − 𝑍 j sudah bernilai nol atau negatif maka solusinya sudah optimal dan perhitungan  dihentikan  dengan  melakukan  dua  kali  Iterasi,  hasil  penyelesaian  nilai  variabel diperoleh 1 =14,48, 𝑥 2 = 13,68 𝑥 3 = 0 serta nilai Z = 672.837. Pada hasil ini terlihat bahwa ada nilai  optimal  yang  diperoleh  bukan  bilangan  integer,  maka  penyelesaian  dilanjutkan menggunakan metode Branch and Bound & metode Gumory Cutting Plane .

## Penyelesaian Menggunakan Metode Branch and Bound
Berdasarkan  hasil  dari  program  linear  melalui  Metode  Simpleks  diperoleh  nilai optimal 𝑥 1 =14,48, 𝑥 2 =  13,68 𝑥 3 =  0  serta  nilai  Z  =  672.837.  Karena  nilai  variabel  keputusan  yang diharapkan  bernilai Integer, kemudian  dilanjutkan  dengan Integer  Linear  Programming menggunakan Metode Branch and Bound .
Langkah-langkah perhitungan Metode Branch and Bound adalah sebagai berikut:
a) dari  hasil  solusi  simpleks  bisa  terlihat  variabel  yang  masih  belum Integer dengan  pecahan terbesar adalah 𝑥 1 = 14,48 dan 𝑥 2 = 13,68
b) Hasil Solusi simpleks adalah 𝑥 1 = 14,48 𝑥 2 = 13,68, 𝑥 3 = 0 dan Z = Rp 672.837, karena 𝑥 1 dan 𝑥 2 bukan bilangan Integer maka solusi ini belum layak. Namun nilai pendapatan dari solusi simpleks  Z  =  Rp  672.837  dijadikan  batas  atas  (BA).  Dengan  metode  pembulatan  kebawah diperoleh nilai solusi Z = Rp 664.000
c) Pilih  variabel  dengan  bagian  pecahan  yang  terbesar  untuk  pencabangan.  Ciptakan  dua batasan  baru  untuk  variabel  ini  yang  mencerminkan  pembagian  nilai Integer. Hasilnya adalah sebuah batasan ≤ dan sebuah batasan ≥. Variabel pecahan terbesar yaitu 𝑥 2 =  13,68. Ciptakan dua batasan baru dari
d) Ciptakan dua sub masalah yaitu, sub masalah satu dan sub masalah dua dengan nilai batasan variabelnya 𝑥 2 ≤ 13 dan 𝑥 2 ≥ 14.
e) Model  Program  linier  yang  digunakan  adalah  Metode  Simpleks  dengan  bantuan software POM-QM V5 dapat terlihat pada gambar pohon percabangan berikut ini:
Sebelum  mencari  nilai  dari  setiap  batasan  asumsikan  terlebih  dahulu  nilai  solusi  awal berupa nilai solusi dari Metode Simpleks dapat terlihat pada pohon percabangan berikut ini :

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Gambar 3.1 . Pohon percabangan nilai awal dari batasan 𝑥 2 ≤ 13 dan 𝑥 2 ≥ 14
Selanjutnya  mencari  nilai  percabangan  sub  masalah  satu  dan  sub  masalah  dua menggunakan  Program  Linier  Metode  Simpleks  dengan  bantuan software POM-QM  V5  dapat terlihat pada gambar berikut ini:
Gambar 3.2 Output nilai awal sub masalah 1

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Pada  Gambar  3.2  dapat  dilihat  tampilan  output    nilai  awal  untuk  sub  masalah  1 pada software POM-QM. Adapun tampilan output solusinya terlihat pada gambar berikut
Gambar 3.3 Output solusi sub masalah 1
Pada  Gambar  3.3  terlihat  bahwa  solusi  optimal  yang  diperoleh  masih  belum  bilangan  integer, yaitu untuk 𝑥 1 = 15,17 dan 𝑥 2 = 13. Sehingga dilanjutkan mencari solusi untuk sub masalah 2.  Dengan  menggunkan software POM-QM maka diperoleh tampilan output nilai  awal  untuk sub masalah 2 seperti gambar berikut ini :
Gambar 3.4. Output nilai awal sub masalah 2
Pada  Gambar  3.4  dapat  dilihat  tampilan  output    nilai  awal  untuk  sub  masalah  2 pada software POM-QM. Adapun tampilan output solusinya terlihat pada gambar berikut ini :

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
Gambar 3.4. Output solusi sub masalah 2
Pada  Gambar  3.4  dapat  dilihat  bahwa  solusi  sub  masalah  2  belum  bernilai  integer  sehingga perhitungan terus dilakukan hingga solusi dari sub masalah bernilai integer. Setelah mendapatkan hasil solusi output dari masing-masing sub masalah satu dan sub masalah dua maka selanjutnya hasil dari solusi tersebut dijabarkan seperti gambar berikut ini:

## Gambar 3.5 Hasil akhir nilai solusi dari percabangan nilai awal
Nilai  yang  paling  optimal  serta  nilai  solusi  nya  yang  berada  di  antara  batas  atas  dan  batas bawah dan sudah berrnilai integer berada pada sub masalah 5 dengan nilai variabel 𝑥 1 = 15, 𝑥 2 =

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
13, 𝑥 3 = 0 dan Z = 664.000. maka nilai solusi optimum berada pada sub masalah 5 dengan batasan 𝑥 3 ≥ 0.
Berdasarkan  hasil  dari  perhitungan  Metode Branch  and  Bound diperoleh  keuntungan maksimum   dengan hasil penyelesaian variabel nya yaitu: 𝑥 1 =15, 𝑥 2 =13, 𝑥 3 = 0 yaitu
Z  = 20.000 𝑥 1 + 28.000 𝑥 2 + 20.000 𝑥 3
= 20.000 (15) + 28.000 (13) + 20.000 (0))
= 664.000
Sehingga  dapat  disimpulkan  UMKM  menghasilkan  keuntungan  optimal  penjualan  sebesar Rp.  664.000  Jika  produksi  ditingkatkan  untuk  sandal  laki-laki  sebanyak  15  pcs,  dan  sandal perempuan sebanyak 13 pcs, lebih banyak dari produksi sebelumnya sehingga terjadi peningkatan keuntungan  dari  keuntungan  awal  sebesar  Rp.  60.000  mencapai  keuntungan  optimal  sebesar Rp.664.000.

## Penyelesaian Menggunakan Metode Gumory Cutting Plane
Selanjutnya  menentukan  solusi integer  linear  programming dengan  menggunakan  metode Cutting  Plane .  Adapun  langkah-langkah  dalam  menyelesaikan  metode Cutting  Plane adalah sebagai berikut :
a. Memilih  sembarang  baris  pada  tabel  optimum  simpleks  yang  variabel  keputusannya  pada solusi  optimum  bernilai non  integer. Dari  hasil  akhir  yang  didapat  tampak  bahwa  baik 𝑥 1 maupun 𝑥 2 bukan  merupakan  penyelesaian  bilangan  bulat  sehingga  bukanlah  penyelesaian optimalnya. Maka pemotongnya bisa  menggunakan 𝑥 1 maupun 𝑥 5 ,  tetapi  karena 𝑖 dari 𝑥 2 adalah  0,6821 (paling besar) sehingga pemotongan akan dilakukan berdasarkan baris 𝑥 1 b.  Baris ke-3 adalah baris yang terpilih dan persamaan yang terbentuk dalam baris ke-3 adalah sebagai
𝑥 𝑖 = 𝑏 𝑖 ∑ 𝑖j 𝑆 j ,  𝑏 𝑖 =  𝑜  𝑖 𝑡𝑒 𝑒𝑟 (baris sumber),
j=1
𝑥 2 = 13,6821 − (0,001 𝑆 3 − 1,3414 𝑆 5 ),
𝑏 𝑖 = [ 𝑏 𝑖 ] + 𝑖 ,
𝑏 3 = 13 + 0,6821,
𝑖 j = [ 𝑖 j ] + 𝑖 j ,
3,6 = 0 + 0,001,
3,8 = −2 + 0,6586
sehingga diperoleh
∑ 𝑖j 𝑆 j + 𝑆 g𝑖 = 𝑖 ,

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI
Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
j=1
(0,001𝑆 3 + 0,6586𝑆 5 ) + 𝑆 g1 =  0,6821,
0,001𝑆 3 0,6586𝑆 5 + 𝑆 g1 =  0,6821.
c. Kendala baru diatas dimasukan ke tabel simpleks terakhir kemudian selesaikan dengan metode dual  simpleks  kemudian  selesaikan  dengan  metode  dual  simpleks.  Adapun  hasilnya  seperti pada Tabel Simpleks Optimum Penambahan Pemotong Kendala Gomory I berikut,
Tabel 4.2.1 Tabel Dual Simpleks Optimum (Penambahan Pemotong Kendala Gomory I) 𝐶 j 20.000 28.000 20.000 0 0 0 0 0 0 𝐶 𝑏 Basis 𝑥 1 𝑥 2 𝑥 3 𝑠 1 𝑠 2 𝑠 3 𝑠 4 𝑠 5 𝑠 6 𝑠 7 𝑠 g 1 𝑏 𝑖 0 𝑠 1 0 0 -10 1 0 0 0 -180.186 0 0 19 97.301 0 𝑠 2 0 0 -1 0 1 0 0 -25.0608 0 0 1.9 41.561 28.000 𝑥 2 0 1 0 0 0 0 0 -2 0 0 1 13 0 𝑠 4 0 0 0 0 0 0 1 -14.0845 0 0 0 13.663 20.000 𝑥 1 1 0 1 0 0 0 0 9.0422 0 0 -1 15 0 𝑠 6 0 0 -3 0 0 0 0 -90.0931 1 0 9.5 23.650 0 𝑠 7 0 0 0 0 0 0 0 -18.0186 0 1 1.9 19.730 0 𝑠 3 0 0 0 0 0 1 0 658.6 0 0 1000 682.1 𝑍 j 20000 28000 20000 0 0 0 0 124844 0 0 800 664.000 𝑍 j 𝐶 j 0 0 0 0 0 0 0 124844 0 0 8000
Berdasarkan  hasil  dari  Tabel  Simpleks  Optimum  Penambahan  Pemotong  Kendala Gomory I tampak bahwa baik 𝑥 1 maupun 𝑥 2 merupakan penyelesaian bilangan bulat, Maka proses pembentukan kendala Gomory berakhir. Sehingga diperoleh jumlah penjualan yang optimal yaitu sandal laki-laki 15 pasang, sandal perempuan 13 pasang dengan keuntungan Rp. 664.000.
Dari  hasil  yang  diperoleh  diketahui  bahwa  kedua  metode  ini  menghasilkan  keuntungan maksimalyang  sama  yaitu  RP.  664.000  dengan  masing-masing  memproduksi  15  pasang  sandal laki-laki dan 13 pasang sandal perempuan. Sama halnya dengan penelitian sebelumnya pada [17], metode Branch and  Bound dan  metode Gumory Cutting Plane menghasilkan keuntungan yang sama.  Artinya  untuk  kasus  ini  kedua  metode  tersebut  sama-sama  efektif  digunakan  dalam mengoptimalkan  keuntungan  Namun  dalam  penyelesaiannya,  metode Branch  and  Bound memerlukan  iterasi  yang  banyak  dan  waktu  yang  lebih  lama  dibandingkan  dengan  metode Gumory Cutting plane .

## KESIMPULAN DAN SARAN
Berdasarkan perhitungan menggunakan metode Branch and Bound dan Gumory Cutting Plane ,  kedua  metode  menghasilkan  keuntungan  optimal  penjualan  dari  UMKM Capal  Classic Shoes Kab. Agam yang sama yaitu sebesar Rp. 664.000. Jika produksi ditingkatkan untuk sandal laki-laki  sebanyak  15  pcs,  dan  sandal  perempuan  sebanyak  13  pcs,  lebih  banyak  dari  produksi sebelumnya  sehingga  terjadi  peningkatan  keuntungan  dari  keuntungan  awal  sebesar  Rp.  60.000 mencapai  keuntungan  optimal  sebesar  Rp.664.000.  Akibatnya  didapat  selisih  keuntungan  dari sebelumnya  dan  setelah  dilakukan  optimasi  menjadi  Rp.  596.000.  Sehingga  dapat  disimpulkan

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
bahwa  penjualan  yang  telah  didapatkan  oleh  UMKM Capal  Classic  Shoes Kab.  Agam  saat  ini sudah mendekati keuntungan optimal.

## DAFTAR PUSTAKA
[1].  Akyuz, M. et. al ., 2012. Location and Allocation Based Branch And Bound Algorithms For The Capacitated Multifacility Weber Problem. Springer Vol.222, No.59: 45- 71.
[2].    Alpha  C.  Chiang  dan  Kevin  Wainwright,  2006.  Dasar-Dasar  Matematika  Ekonomi. Jakarta: Penerbit Erlangga .
[3].    Azzahrha,  Fatimah  Khilaliyah  et  al.,  2021.  Optimalisasi  Produksi  Tahu  Menggunakan Metode Branch and Bound dan Cutting Plane. STRING , Vol. 6 No. 2 : 175-184 [4].  Basriati S, 2018 .Integer Linear Programming Dengan Pendekatan Metode Cutting Plane dan Branch  and  Bound Untuk  Optimasi  Produksi  Tahu. Jurnal  Sains  Matematika  dan Statistika , Vol. 4, No. 2: 95 – 104
[5].    Bronson,  Richard,  1982. Theory    and    Problems  of  Operations  Research .McGraw-Hill, USA
[6].  Chadziqatun Najilatil Mazda and Dwi Agustina Kurniawati, 2020 IOP Conf. Ser.: Mater. Sci. Eng. 1003 012129
[7].    Devi,  Sari  Purba  dan  Faiz  Ahyaningsih,  2020. Integer  Programming Dengan  Metode Branch  and  Bound Dalam  Optimasi  Jumlah  Produksi  Setiap  Jenis  Roti  Pada  PT.  Arma Anugerah Abadi. Karismatika, Vol. 6 No. 3: 20-29
[8].    Dhuriattun,  2015.  Penerapan  Metode  Cutting  Plane  dalam  Menyelesaikan  Optimalisasi Perencanaan  Produksi  pada  Kelompok  Wanita  Tani  (KWT)  Seruni  Berbah. Tugas  Akhir Mahasiswa Universitas Islam Negeri Sunan Kalijaga Yogyakarta.
[9].  Huang, Lingying, et al., 2021. Branch and Bound in Mixed Integer Linear Programming Problems:  A  Survey  of  Techniques  and  Trends. Department  of  Electronic  Engineering, HKUST
[10].  M Fausi, 2022. Penerapan Metode Cutting Plane untuk Optimasi Biaya Pemupukan pada Tanaman Cabai . Jurnal Kajian dan Terapan Matematika, Vol. 8, Edisi 2: 85- 94
[11].    Marzukoh,  Ainul,  2017.Optimasi  Keuntungan  Dalam  Produksi  Dengan  Menggunakan Linear Programming Metode . Undergraduate Thesis, UIN Raden Intan Lampung .
[12].  Mulyono, S., 2002. Riset Operasi. Jakarta: Fakultas Ekonomi Universitas Indonesia [13].  Muslich, M. 2009. Metode Penganmbilan Keputusan Kuantitatif. Jakarta: Bumi Aksara [14].    Oberdieck,  R.,  dan  Psitikopoulos,  E.  N.,  2014.  A  Branch  And  Bound  Method  For  The Solution Of Multiparametric Mixed Integer Linear Programming Problems. J Glob Optim Vol. 22, No.59: 527–543.
[15].    Roflin  Eddy  et  al.,  2014.  Substituting  Gomory  Cutting  Plane  Method  Towards  Balas Algorithm For Solving Binary Linear Programming . Bulletin of Mathematics Vol. 06, No. 01 : 1–13.
[16].    Rosyidah,  Mita,  2021.  Optimasi  Jumlah  Produksi  Roti  Manis  pada  Bintang  Bakery dengan Metode Cutting Plane . Fakultas Sains dan Teknologi UNJA.
[17].  Tri Rahmayani & Devni Prima Sari, 2022. Perbandingan Metode Branch and Bound dan Metode  Cutting  Plane  dalam  Optimasi  Jumlah  Produksi  di  BSL  Store. Journal  Of Mathematics UNP Vol. 7, No. 2, 38-43.
[18].    Wang,  S.  dan  Liu,  M.,  2015.  A  Branch  And  Bound  Algorithm  For  Single-Machine Production  Scheduling  Integrated  With  Preventive  Maintenance  Planning .  International Journal of Production Research ,Vol.51,No.3:491–506.
[19].   Winston,  W.L.,  2003.  Operations  Research  Aplications and  Algorithm. Duxbury  Press , USA
[20].  Muslich, M., 2009. Metode Pengambilan Keputusan Kuantitatif. Jakarta: Bumi Aksara

## JURNAL MATEMATIKA, STATISTIKA DAN KOMPUTASI

## Nurweni Putri, Maya Sari Syahrul, Rosi Ramayanti
[21].    Oberdieck,  R.,  dan  Psitikopoulos,  E.  N.,  2014.  A  Branch  And  Bound  Method  For  The Solution Of Multiparametric Mixed Integer Linear Programming Problems. J Glob Optim Vol. 22, No.59: 527–543.
[22].    Rahmayani,  Tri  dan  Devni  Prima  Sari,  2022.  Perbandingan  Metode  Branch  and  Bound dan  Metode  Cutting  Plane  dalam  Optimasi  Jumlah  Produksi  di  BSL  Store. Journal  of Mathematics UNP Vol. 7 No. 2 : 38-43
[23].    Roflin  Eddy  et  al.,  2014.  Substituting  Gomory  Cutting  Plane  Method  Towards  Balas Algorithm For Solving Binary Linear Programming . Bulletin of Mathematics Vol. 06, No. 01 : 1–13.
[24].  Siswanto, 2007. Operation Reasearch , Jilid I. Jakarta: Penerbit Erlangga [25].    Taha,  H.A.,  2007. Operation  Research  An  Introduction.  Ed.  8. United  States  :  Pearson Education, Inc.
[26].  Thie, Paul R dan Keough Gerard E., 2008. An Introduction To Linier Programming And Game Theory Third Edition . Canada: Wiley.
[27].  Wahyudin Nur and Nurul M Abdal, 2016. Penggunaan Metode Branch and Bound dan Gomory  Cut dalam  Menentukan  Solusi Integer  Linear  Programming . Jurnal  Saintifik, Vol.II, No. 1: 9-15
[28].    Wang,  S.  dan  Liu,  M.,  2015. A  Branch  And  Bound  Algorithm  For  Single-Machine Production  Scheduling  Integrated  With  Preventive  Maintenance  Planning. International Journal of Production Research. Vol.51,No.3:491–506.
[29].  Winston,  W.L.,  2003. Operations  Research  Aplications  and  Algorithm .  Duxbury  Press, USA .