Perencanaan Produksi Untuk Mengoptimalkan Keuntungan Dengan Metode Branch And Bound Di UKM “X”
Arselia Agatha Salim, Achmad Alfian
Prodi Teknik Industri, Fakultas Sains & Teknologi, Universitas Katolik Musi Charitas Palembang Jalan Bangau No. 60, Palembang
Telp. (0711) 378171 E-mail: agathaarselia@gmail.com ; a_alfian@ukmc.ac.id

## ABSTRAK
UKM  “X”  merupakan  sebuah  industri  rumah  tangga  yang  bergerak  dibidang  industri  makanan. Produk “X” yang di produksi di antaranya bola ubi kopong, ubi crispy dan keripik. Industri ini tidak memiliki  metode  tertentu  dalam  menentukan  jumlah  produksi  masing-masing  jenis  produk  yang  di produksi  dan  mengakibatkan  keuntungan  yang  didapat  kurang  optimal.  Oleh  karena  itu,  perlu dilakukan  penelitian  untuk  mengetahui  formulasi  produk  yang  optimal  dalam  pembuatan  ketiga produk di “X”. Metode yang akan digunakan dalam penelitian ini adalah metode Branch and Bound yang  terlebih  dahulu  menghitung  nilai  variabel  keputusan  dengan  menggunakan software POM. Penelitian  ini  ditinjau  berdasarkan  jumlah  persediaan  bahan  baku,  bahan  baku  pembuatan  ketiga produk, data produksi,biaya produksi, harga jual setiap jenis produk, dan  keuntungan. Sehingga dari analisis metode branch and bound diperoleh nilai keuntungan penjualan bersih sebesar Rp. 4.514.091, khusus  bulan  Juni  keuntungan  menjadi  sekitar  Rp  777.589,-.  Jadi  jumlah  ketiga  produk  yang diproduksi  dari  bahan-  bahan  yang  tersedia  selama  1  bulan  ialah  615  porsi  bola  ubi,  80  porsi  ubi crispy dan 44 porsi keripik. Perencanaan produksi ini mengalami peningkatan keuntungan sebesar Rp 1.181.993  dari keuntungan penjualan rata-rata sebelumnya.
Kata Kunci: Branch and bound , Linear Programming, Perencanaan produksi, Keuntungan.

## ABSTRACT
UKM “X” Small and Medium  Enterprise is a home  industry  which is engaged in the  food industry. Products that are produced include sweet potato balls, crispy sweet potatoes and chips. This industry does not have a certain method that is certain in determining the amount of production of each type of product that is produced and results in profits that are less than optimal. Therefore, research is needed to  find  out  the  optimal product  formulation  in  the manufacturing  of  the  three  products  at  UKM  “X”. The method to be used in this study is the Branch and Bound method which first calculates the value of the decision variable by using POM software. This research is reviewed based on the amount of raw material  inventory,  raw  material  for  making  the  three  products,  production  data,  production  costs, selling prices of each type of product, and profit. So that from the analysis of  the branch and bound method the profit value of Rp. 4,514,091, for special case in June net profit become Rp 777.589,-. So the number of the three products that can be produced from the available ingredients for a month is 615  packs  sweet  potato  balls,  80  packs  crispy  sweet  potatoes  and  44  packs  chips.  The  production planning has increasedprofits by Rp 1.181.993 from previous average sales profit. Keywords: Branch and bound , Linear Programming , Production planning, Profit.

## PENDAHULUAN
UKM  “X”  adalah  salah  satu  bisnis  cemilan  di  Palembang  yang  memulai  usahanya  sejak tahun 2017. Produk yang di tawarkan adalah bola ubi kopong dengan berbagai topping , ubi crispy dan  menu  baru  mereka  adalah  keripik.  Sampai  saat  ini,  UKM  “X”  mempunyai  1 stand tetap  yaitu  berada  di  depan  teras  Primastar  di  jalan  Bangau.  UKM  “X”  tidak memiliki metode tertentu untuk menentukan jumlah produksi masing-masing jenis produk sehingga  selama  ini  hanya  mengandalkan rata-rata  penjualan  dari  masing-masing  produk. Selama  ini,  perencanaan  yang  di  buat owner sebenarnya  sudah  baik,  bahan  baku  yang sudah  di  beli  untuk  1  bulan  jika  masih  sisa  maka  akan  tetap  di  gunakan  untuk  periode selanjutnya  namun  hal  yang  menyulitkan owner adalah  setiap  harinya  harus  membuat
adonan  lebih  dari  1  kali  jika  jumlah  permintaan  banyak.  Jika  di  produksi  berlebihpun, adonan dapat  di  masukkan ke kulkas dan bisa di  pakai  untuk  esok hari,  namun  rasa dari produk  itu  sendiri  akan  berubah  sehingga  mempengaruhi  kualitas. Owner tidak  mau mengambil resiko  besar  seperti  itu.  Dengan  adanya  perencanan  sehingga owner dapat memperkirakan jumlah  yang akan di  produksi.  Namun  perencanaan tidak bisa di  katakan fix atau  tetap  sehingga  dapat  naik  dapat  turun  sesuai  permintaan,  seperti  pada  data  bulan Juni  2019  terjadi  penurunan  permintaan  yaitu hanya  357  porsi  sebagian  besar  karena liburnya anak sekolah yang mengambil peran besar sebagai pelanggan UKM “X” sehingga untuk bulan-bulan tertentu perencanan tidak dapat di pakai sepenuhnya.
Selama  ini  UKM  “X”  sering  mengalami  kelebihan  bahan  baku  seperti  ubi  dan  tepung sehingga  mempengaruhi  ke  keuntungan.  Namun owner belum  bisa  menentukan  kisaran bahan  baku  sehingga  bahan  baku  yang  di  beli  sering  bersisa,  jika  yang  bersisa  adalah bahan  baku  yang  dapat  tahan  lama  tentunya  masih  dapat  di  gunakan  namun  beberapa bahan baku seperti ubi tidak dapat di simpan dalam waktu yang lama.
Ada  beberapa  cara  yang  dapat  digunakan  untuk  menyelesaikan  masalah  penentuan kuantitas produksi  dalam  suatu  perusahaan. Salah satunya  adalah dengan metode branch and bound . Di dalam matematika terdapat suatu teknik optimalisasi  yang bertujuan untuk menentukan  pemecahan  masalah  optimasi  yaitu  dengan  memaksimumkan  suatu keuntungan  atau  meminimumkan  biaya  dengan  kapasitas  bahan  baku  yang  ada  agar mampu memperoleh hasil yang maksimal.
Menyadari  bahwa  proses  keluar  masuk  perputaran  uang  cukup  mengkhawatirkan,  maka akan dilakukan pengoptimalisasi keuntungan penjualan dengan metode branch and bound . Metode Branch  and  Bound sering  digunakan  untuk  menyelesaikan  suatu  permasalahan program  linear  karena  hasil  yang  di  peroleh  dalam  penyelesaian  optimal  lebih  teliti  dan lebih  baik  dari  metode  yang lain.  Metode  ini  di  katakan  lebih  teliti  dan  lebih  baik  dari metode lain karena hasil optimal  yang di  peroleh biasanya  lebih  dari satu sehingga dapat memilih mana  yang paling optimal dan  paling sesuai dari hasil-hasil yang di peroleh [6]. Semua  menu  yang  tawarkan  pada  UKM  “X”  ini  akan  menjadi  variabel-variabel  dalam proses perhitungan. Kemudian bahan baku dan kebutuhan saat proses produksi seperti ubi, tepung,  gula  sampai  gaji  karyawan  dan  minyak  serta  gas  akan  menjadi  kendala  dalam proses pengolahan data.
Hal ini mendasari penulis mencoba menggunakan metode ini dengan kasus yang ada pada UKM “X”. Maka dari itu, dilakukan penelitian dengan judul “Perencanaan Produksi Untuk Mengoptimalkan Keuntungan Dengan Metode Branch And Bound Di UKM “X”.

## TINJAUAN PUSTAKA

## Program Linear
Program  linear  merupakan  suatu  model  matematika  untuk  mendapatkan  alternatif penggunaan  terbaik  atas  sumber-sumber  yang  tersedia.  Kata  linear  digunakan  untuk menunjukkan  fungsi  matematika  yang  digunakan  dalam  bentuk  linear,  sedangkan program  merupakan  penggunaan  teknik  matematika  tertentu.  Jadi  pengertian  program linear  adalah  suatu  teknis  perencanaan  yang  bersifat  analitis  yang  analisisnya menggunakan  model  matematika,  dengan  tujuan  menemukan  beberapa  alternatif pemecahaan optimum terhadap persoalan [2].
Karakteristik-karakteristik  dalam  program  linear  yang  biasa  digunakan  untuk memodelkan suatu              masalah dan memformulasikannya secara matematika, yaitu [5]:
1. Variabel Keputusan
Variabel  keputusan  adalah  variabel  yang  menguraikan  secara  lengkap  keputusan- keputusan yang akan dibuat. Variabel keputusan tidak negatif.
2. Fungsi Tujuan
Fungsi  tujuan  merupakan  suatu  hubungan  linear  dari  variabel  keputusan  yang  berupa fungsi  maksimum  atau  minimum  di  mana  tingkat  pencapaian  tujuan  ini  dibatasi  oleh kendala  yang  mencerminkan  keterbatasan  dari  kapasitas  waktu  produksi  kemampuan yang dimiliki.
3. Fungsi Kendala
Fungsi  kendala  merupakan  batasan-batasan  dalam  penyelesaian  program  linear  yang harus  diperhatikan.  Kendala  diekspresikan  dalam  persamaan  dan  pertidaksamaan  yang juga  merupakan  hubungan  linear  dari  variabel  keputusan  yang  mencerminkan keterbatasan sumber daya dalam suatu masalah.

## Metode Simpleks
Metode  simpleks  adalah  suatu  prosedur  ulang  yang  bergerak  dari  satu  jawab  layak basis  ke jawab  berikutnya  sedemikian  rupa  hingga  harga  fungsi  tujuan  terus  menaik (dalam  persoalan maksimasi)  dan  akan  berkelanjutan  sampai  dicapai  jawab  optimal (kalau ada) yang memberi harga maksimum.
Cara  yang  paling  sederhana  unrtuk  menyelesaikan  permasalahan  program  linear  adalah dengan pendekatan  grafikal.  Namun cara tersebut  hanya bisa diterapkan  untuk  program linear  dengan  dua  variabel  keputusan.  Pada  kenyataannya  sebagian  besar  permasalahan program  linear  mempunyai  lebih  dari  dua  variabel  keputusan.  Hal  ini  tentu  sulit  untuk menerapkan  pendekatan  grafikal  untuk  memperoleh  penyelesaian  dari  permasalahan tersebut.
Prosedur solusi aljabar yang paling banyak digunakan untuk masalah pemrograman linier disebut metode simpleks, yang dikembangkan oleh George Dantzig pada tahun 1947 [5]. Metode  simpleks  merupakan  prosedur  aljabar  yang  bersifat  iteratif  yang  bergerak selangkah  demi  selangkah,  dimulai dari  titik  ekstrim  pada  daerah feasible (ruang  sousi) menuju titik ekstrim yang optimum.
Berikut  langkah-langkah  dalam  menyelesaikan  permasalahan  program  linear  dengan metode simpleks [3]:
1. Konversikan formulasi persoalan ke dalam bentuk standar. Agar  persamaan  garis  batasan  memenuhi  persyaratan  penyelesaian  daerah  kelayakan ( feasible )  maka  semua  pertidaksamaan  diubah  menjadi  persamaan  dengan  cara menambahkan variabel slack, surplus dan variabel buatan ( artifisial variabel ) pada tiap batasan  ( constraint )  serta  member  harga  nol  pada  setiap  koefisien  tujuannya.  Batasan dapat dimodifikasi sebagai berikut:
a. Untuk  batasan  bernotasi  (≤)  diubah  ke  dalam  bentuk  persamaan  dengan menambahkan variabel slack.
b. Untuk  batasan  bernotasi  (≥)  atau  (=)  diselesaikan  dengan  menambahkan  variabel surplus dan variabel buatan. Dengan penambahan variabel buatan ini akan merusak sistem batasan, hal ini dapat diatasi dengan membuat suatu bilangan penalty M (M bilangan  positif  yang  sangan  besar)  sebagai  harga  dari  variabel  buatan  tersebut
dalam  fungsi  tujuan.  Untuk  kasus  maksimasi  maka  dibuat  –M  sebagai  harga  dari variabel  buatan  dan  untuk  kasus  minimasi  dibuat  +M  sebagai  harga  dari  variabel buatan. Cara pendekatan ini dikenal dengan metode M besar ( Big M method ).
2. Susun persamaan-persamaan ke dalam tabel simpleks.
3. Pilih  kolom  kunci,  yaitu  kolom  yang  memiliki  nilai  (-) yang  paling  positif  untuk kasus                        maksimasi  atau yang memiliki nilai (-) yang paling negatif untuk kasus minimasi.
4. Pilih  baris  kunci  yang  memiliki  nilai  indeks  terkecil.  Nilai  indeks  adalah perbandingan nilai kanan dengan kolom kunci.
5. Tentukan nilai elemen cell, yaitu nilai perpotongan antara kolom kunci dan baris kunci.
6. Lakukan iterasi  dengan  menentukan baris kunci  baru, baris Z baru, dan  baris variabel- variabel slack baru.
a. Baris kunci baru ditentukan dengan membagi baris kunci lama dengan elemen cell .
b. Baris Z baru dan baris-baris lainnya ditentukan dengan cara: Baris lama – (nilai kolom kunci baris yang sesuai × baris kunci baru)
c. Letakkan nilai-nilai baris yang baru diperoleh ke dalam tabel.
7. Lakukan uji optimalisasi. Jika semua koefisien pada baris ( - ) sudah tidak ada lagi yang bernilai positif (untuk kasus maksimasi) atau sudah tidak ada lagi yang bernilai negatif (untuk kasus minimasi) berarti sudah optimal. Jika kriteria belum terpenuhi, diulangi dari langkah 3.

## Metode Branch and Bound
Metode Branch  and  Bound pertama  kali  diperkenalkan  oleh  Land  dan  Doig  (1960).  Ide dasarnya adalah untuk membagi daerah solusi  fisibel  menjadi  daerah solusi fisibel yang lebih kecil. Ini merupakan prosedur sederhana yang menetapkan batasan yang lebih tinggi dan  rendah  menjadi  solusi  saat  menyelesaikan  sub  masalah  secara  sistematis.  Kemudian metode  ini  dimodifikasi  oleh  Dakin  (1965)  dan  dengan  sukses  menerapkannya  di  dalam kitab undang-undang hukum dagang banyak orang dalam memecahkan persoalan program integer.
Metode Branch  and  Bound merupakan  salah  satu  metode  untuk  menghasilkan penyelesaian  optimal  program  linear  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  atau  bawah bagi  masing-masing  variabel  keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru [4]. Metode ini sering digunakan untuk menyelesaikan  suatu  masalah  program  integer  karena  hasil  yang  diperoleh  dalam penyelesaian  optimal  lebih  teliti  dan  lebih  baik  dari  kedua  metode  lainnya.  Kelemahan pokok metode ini adalah prosedur untuk mencapai hasil optimal sangat panjang.
Prinsip  dasar  metode  ini  adalah  memecah  daerah  fisibel  layak  suatu  masalah  program linear dengan  membuat  submasalah.  Ada  dua  konsep  dasar  dalam  metode Branch  and Bound :
a. Branching adalah  proses  membagi-bagi  permasalahan  menjadi subproblem- subproblem yang mungkin mengarah ke solusi.
b. Bounding adalah  suatu  proses  untuk  mencari/menghitung  batas  atas  dan  batas bawah  untuk solusi optimal pada subproblem yang mengarah ke solusi.
Berikut  ini  adalah  langkah-langkah  penyelesaian  suatu  masalah  maksimisasi  dengan metode Branch and Bound : 1. Selesaikan masalah program linear dengan metode simpleks selesaikan masalah tanpa
pembatasan bilangan integer.
2. Teliti  solusi  optimalnya,  jika  variabel  keputusan  yang  diharapkan  adalah  bilangan integer, solusi optimum integer telah tercapai. Jika satu atau lebih variabel keputusan yang diharapkan ternyata bukan bilangan integer, lanjutkan ke langkah 3.
3. Jadikan  solusi  pada  penyelesaian  langkah  1  menjadi  batas  atas  dan  untuk  batas bawahnya merupakan solusi yang variabel keputusannya telah diintegerkan ( rounded- down ).
4. Pilih  variabel  yang  mempunyai  nilai  pecahan  terbesar  (artinya  bilangan  desimal terbesar dari masing-masing vaariabel untuk dijadikan pencabangan ke dalam sub-sub masalah.  Tujuannya  adalah  untuk  menghilangkan  solusi  yang  tidak  memenuhi persyaratan  integer  dalam  masalah  itu. Pencabangan  itu  dilakukan  secara mutually exclusive untuk memenuhi persyaratan integer dengan jaminan tidak ada solusi fisibel (layak)  yang  diikutsertakan.  Hasilnya  adalah  sebuah  sub  masalah  dengan  batasan  ≤ atau batasan  ≥.
5. Untuk setiap sub-masalah, nilai optimum fungsi tujuan ditetapkan sebagai batas atas. Solusi  optimum  yang  diintegerkan  menjadi  batas  bawah  (solusi  yang  sebelumnya tidak  integer  kemudian  diintegerkan).  Sub-sub  masalah  yang  memiliki  batas  atas kurang dari batas bawah yang ada, tidak diikutsertakan pada analisa selanjutnya. Suatu solusi  integer  fisibel  (layak)  adalah  sama  baik  atau  lebih  baik  dari  batas  atas  untuk setiap sub  masalah  yang dicari. Jika solusi  yang  demikian terjadi, suatu  sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 4.

## METODOLOGI PENELITIAN
Adapun urutan dalam melakukan penelitian ini diantarnya:
1) Studi Lapangan. Penelitian dilakukan dengan melakukan pengamatan secara langsung di  UKM  UKM  “X”  cabang  Primastar  dan  berlokasi  di  teras  depan  Primastar,  Jl. Bangau,  Palembang. Dengan wawancara juga dilakukan dengan pemilik usaha
2) Identifikasi  Masalah.  Permasalahan  yang  diidentifikasi  dalam  kegiatan  penelitian  ini adalah  membuat  model  Integer  Programming  dari  persoalaan  yang  dapat mempresentasikan sistem yang terjadi.
3) Merumuskan  Tujuan  Penelitian.  Rumusan  masalah  dalam  penelitian  ini  adalah membuat  perencanaan  produksiuntuk  mendapat  keuntungan  yang  optimal  dengan metode branch and bound di UKM UKM “X”.
4) Studi Pustaka. Pada tahap ini dilakukan pencarian referensi dari buku serta jurnal yang akan digunakan untuk menemukan solusi terhadap penelitian.
5) Pengumpulan  Data.  Data  yang  dikumpulkan  untuk  memecahkan  masalah  penelitian antara  lain  data  penjualan  Jan  –  Sept  2019,  data  biaya  kebutuhan  produksi  (bahan baku, tenaga kerja, biaya overhead ) dan harga jual produk.
6) Membangun  Model.  Setelah  mendapatkan  informasi  dan  data-data  didapat,  maka dibangun  model.  Model  yang  telah  dibangun  merupakan  gambaran  sistmatik berdasarkan sistem nyata. [1]
7) Menjalankan  Program.  Dalam  tahap  ini  dilakukan  serangkaian  pengolahan  data dengan bantuan menggunakan aplikasi POM For Windows V3.
8) Analisis.  Data  yang  telah  dikumpulkan  dan  diolah  kemudian  dianalisis  untuk mengetahui jumlah rencana produksi, dan keuntungan yang didapat nantinya.
9) Kesimpulan. Menjawab pertanyaan dari rumusan masalah.

## HASIL DAN PEMBAHASAN

## Membuat Model
1) Menentukan variabel keputusan (X 1 untuk bola ubi kopong, X 2 untuk ubi crispy dan X 3 untuk keripik).
2) Menentukan fungsi tujuan Berdasarkan  kasus  ini  fungsi  di  maksimumkan  karenna  berhubungan  dengan keuntungan dan bila membahas keuntungan tentunya ingin keuntungan yang maksimal sehingga fungsi tujuan di maksimalkan.
Maksimumkan: Z = 12357X1 +  11688X2 +  8609X3
3) Menentukan  batasan  atau  kendala-kendala  dari  permasalahan  tersebut. Fungsi batasan  / fungsi kendala dapat dituliskan sebagai berikut:
Langkah 1 : Mengubah fungsi tujuan dan batasan-batasan
Maksimumkan :  Z - 12357X1 -  11688X2 -  8609X3 = 0
Fungsi batasan di tambahkan slack pada variabel menjadi sebagai berikut: Ubi :  0,15 X1 + 0,15 X2 + 0,050 X3 + S1  = 292 Minyak :  0,02X1 + 0,015X2  + 0,016X3 + S2  =18  liter Gas :  0,025X1 + 0,025X2  + 0,025X3 + S3  = 24kg Topping :  0,016X1 + 0,01X2 + S4 = 11,5 kg Tepung tapioka   :  0.021 X1 + S5 = 50 Gula halus :  0.018 X1 + S6 = 50 Tepung maizena  :  0.009 X1 + S7 = 20 Garam :  0.0008 X1  + S8 = 0,5 Baking powder :  0,001 X1 + S9 = 2 Tepung terigu : 0,025X2 + S10 = 2 Bumbu keripik : 0,005 X3 + S11 = 0,25 Maks X1 :              X1 + S12 = 615 Maks X2 : X2 + S13 = 83 Maks X3 : X3 + S14 = 44 X1, X2, X3,S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14  ≥ 0 Ubi : 0,15 X1 + 0,15 X2 + 0,050 X3 ≤ 292 Minyak : 0,02X1 + 0,015X2 + 0,016X3 ≤ 18 liter Gas : 0,025X1 + 0,025X2 + 0,025X3 ≤ 24kg Topping : 0,016X1 + 0,01X2 ≤ 11,5 kg Tepung tapioka : 0.021 X1 ≤ 50 Gula halus : 0.018 X1 ≤ 50 Tepung maizena : 0.009 X1 ≤ 20 Garam : 0.0008 X1 ≤ 0,5 Baking powder : 0,001 X1 ≤ 2 Tepung terigu : 0,025X2 ≤ 2 Bumbu keripik : 0,005X3 ≤ 0,25 Maks X1 : X1 ≤ 615 Maks X2 : X2 ≤ 83 Maks X3 : X3 ≤ 44 X1, X2, X3 ≥  0

## Langkah 2: Menyusun persamaan-persamaan di dalam tabel
Tabel 1. Penyusunan Variabel Metode Simpleks

## Langkah 3: Memilih kolom kunci
Lalu  setelah  memasukkan  setiap  variabel,  selanjutnya  pilih  kolom  kunci  dengan  memilih nilai paling negatif (-) seperti pada tabel 2 sebagai berikut:
Tabel 2. Kolom Kunci

## Langkah 4: Memilih baris kunci
Rumusnya Rasio = (Nilai Kolom NK) / (Nilai kolom kunci). Batasan S1, nilai rasio S1 = 292/0,15  adalah  1946,667  dan  seterusnya.  Pilih  nilai  rasio  terkecil  positif  dan  hasil perpotongan  antara  kolom  kunci  dan  baris rasio  terkecil  di  anggap  sebagai  angka  kunci seperti pada tabel 3 angka kunci adalah 1.
Tabel 3. Baris Kunci

## Langkah 5: Melanjutkan perbaikan
Proses perhitungan di lakukan sampai pada batasan 14 dengan hasil perhitungan iterasi 1 dapat di lihat pada tabel 4 sebagai berikut:
Tabel 4. Iterasi 1 Metode Simpleks
Setelah mendapat hasil dari iterasi pertama, iterasi kedua di mulai seperti pada langkah 3 sampai langkah 5 seperti pada tabel 5 sebagai berikut:
Tabel 5. Iterasi 2 Metode Simpleks
Pada  iterasi  2  sudah  terlihat  bahwa  nilai  negatif  hanya  tinggal  satu  sehingga  daapat  di prediksi bahwa iterasi 3 merupakan iterasi terakhir pada tahap ini. Iterasi 3 dapat di lihat pada tabel  6  sebagai berikut:
Tabel 6. Iterasi 3 Metode Simpleks
Dapat di lihat pada tabel 6 bahwa sudah tidak ada lagi nilai negatif pada tabel sehingga perhitungan metode simpleks dapat di katakan telah optimal, X1 sebanyak 615 porsi, X2 sebanyak 80 porsi dan X3 sebanyak 44 porsi dengan keuntungan sebesar 9.024.091.

## Hasil Software POM
Setelah  membuat  model,  maka  masukkan  setiap  variabel  dan  angka  yang  terdapat  pada model  untuk  mendapat  hasil  optimaldari software POM  sesuai  langkah-langkah  yang terdapat  pada  bab  II  yaitu  landasan  teori.  Setelah  mengikuti  setiap  langkah  di  dapat  di lihat pada gambar 1 sebagai berikut:
Gambar 1. Hasil Perhitungan dengan software POM
Pada gambar 1 hasil output dari software POM di pada tabel 7 sebagai berikut:
Tabel 7. Hasil Output Software POM (Hasil Optimasi Pertama) Nama produk Jumlah produksi / bulan (porsi) X1 615 X2 80 X3 44 Total keuntungan (kotor) Rp 9.024.091

## SIMPULAN
Dari pengolahan data dan analisa yang di lakukan, dapat disimpulkan bahwa:
1) Dari  hasil  analisis  menggunakan  metode Branch  and  bound ,  jumlah  produksi  yang optimal  diproduksi  yaitu  keuntungan  yang  di  dapat  sebesar Rp  9.024.091 dan  dengan produksi 615 porsi bola ubi, 80 porsi ubi crispy dan 44 porsi keripik.
2) Dengan menggunakan metode Branch and bound , dan Software POM hasilnya sama.

## DAFTAR PUSTAKA
[1] Alfian,  Achmad.  2019. Model  Integer  Programming  Untuk  Mengoptimalkan Perencanaan              Produksi Di UKM “X” . Universitas Katolik Musi Charitas Palembang.
[2] Aminudin. 2005. Prinsip-Prinsip Riset Operasi . Jakarta : Erlangga.
[3] Handayani, Mila. 2014. Metode  Bound And Decomposition Untuk Menyelesaikan  Permasalahan  Program  Liner  Fuzzy  Penuh. Universitas  Sumatera Utara.
[4] Hartono,  Widi.  2014. Implementasi  Algoritma  Branch  and  Bound  pada  0-1 knapsack  Problem  untuk  mengoptimalkan  muatan  barang .  Jurnal  Matematika. Semarang.
[5] Mulyono, Sri., 2017, Riset Operasi Edisi 2. Jakarta: Mitra Wacana Media.
[6] Siswanto, 2006. Operations Research Jilid I. Bogor : PT Gelora Aksara Pratama
[7] Sitorus, Parlin. 1997. Program Linier . Jakarta : Universitas Trisakti.