## Maksimasi Keuntungan Layanan Jasa Be Clean Laundry Dengan Menerapkan Metode Branch And Bound
Bayu Teza Syahputra 1 , Riri Syafitri Lubis 2 , Hendra Cipta 3
1 Universitas Islam Negeri Sumatera Utara Medan, bayuteza98@gmail.com
2 Universitas Islam Negeri Sumatera Utara Medan, riri_syafitri@uinsu.ac.id
3 Universitas Islam Negeri Sumatera Utara Medan, hendracipta@uinsu.ac.id
DOI 10.31102/zeta.2021.6.2.1-5

## ABSTRACT
The purpose of this research is to find the maximize benefits from Be Clean Laundry business. In optimize laundry business by looking at the limited resources of the business used branch and bound method. Using the branch and bound method assisted by QM software in more optimal laundry, coat 53 kg, doll 32 kg, blanket 95 kg, bedcover 105 kg, gordyn 91 kg, and clothes 805 kg with a profit of Rp. 4.027.000, while the previous profit based on estimate made by the laundry Owner of Rp. 4.000.000  increase of 0,7 %.
Keywords: Branch and bound, Integer Linear Programming, Maximize Benefit.

## ABSTRAK
Tujuan penelitian ini adalah mencari keuntungan maksimal yang diperoleh dari usaha Be Clean Laundry. Dalam optimasi usaha laundry dengan melihat keterbatasan sumber daya usaha digunakan metode Branch And Bound.  Dari  hasil  perhitungan  menggunakan  metode  Branch  and  Bound  berbantuan  software  QM,  hasil keuntungan cucian lebih optimal yaitu jas 53 kg, boneka 32 kg, selimut 95 kg, bedcover 105 kg, gordyn 91 kg dan pakaian  805  kg    dengan  keuntungan  sebesar  Rp.  4.027.000  sedangkan  keuntungan  sebelumnya  dengan  cara perkiraan yang dibuat oleh pemilik Laundry yaitu Rp. 4.000.000, memiliki kenaikan sebesar 0,7%.
Kata Kunci : Metode Branch and Bound, Integer Linear Programming, Keuntungan Maksimal.
e-ISSN: 2579-5864

## 1. PENDAHULUAN
Dalam  masyarakat  perkotaan,  usaha laundry menjadi  salah  satu  bidang  usaha  yang  semakin banyak  jasanya.  Hal  ini  terjadi  karena  aktifitas masyarakat  yang  tinggi  dan  pendapatan  yang memadai  mempengaruhi  perilaku  masyarakat  yang cenderung menginginkan kebutuhan tertentu dengan secara instan. (Anwar, 2014). Be Clean Laundry perlu membuat  perencanaan  produksi  yang  optimal  untuk dapat  bersaing  dari  layanan  jasa laundry lainnya.
Setiap pelaku usaha pasti melakukan prinsip ekonomi yakni dengan  usaha  dan  modal yang sedikit  mampu menghasilkan  keuntungan  yang  banyak  sehingga muncul  masalah  optimisasi.  Masalah  optimisasi tersebut meliputi biaya minimal atau biaya maksimal terhadap suatu keuntungan dengan kapasitas sumber daya yang ada agar mampu mendapatkan hasil yang optimal (Wijaya, 2013).
Dalam perkembangannya, layanan jasa Be Clean Laundry melayani  2  jenis  layanan  jasa  cuci:  cuci kering  gosok  yakni  jas,  selimut, bed  cover,  gordyn , pakaian.  dan  cuci  kering  saja  yakni  boneka.  Untuk hitungan  pencucian  ada  2  jenis  yakni  perkilogram atau  per piece (pcs)  tetapi  ada  perbedaan  harga  di setiap  item  cucian,  jas  Rp.  15.000/pcs,  boneka  Rp. 30.000, selimut Rp. 12.0000, bed cover Rp. 20.000, gordyn Rp. 8.000 dan pakaian Rp. 5.000. Dalam  menghitung  keuntungannya, Be  Clean Laundry masih mengalami kendala dalam menghitung keuntungannya yakni masih menggunakan cara perkiraan/manual sehingga belum dapat mencapai hasil yang maksimal. Oleh karena itu untuk  memaksimalkan  keuntungan  pada  usaha Be Clean Laundry ini, digunakan sebuah metode Branch and  Bound untuk  memaksimalkan  keuntungan berskala  besar  pada  layanan  jasa Be  Clean  Laundry ini.  Metode Branch  and  Bound dapat  digunakan untuk  memecahkan  suatu  masalah  program  linear yang berskala besar dikarenakan hasil yang diperoleh dalam  pemecahan  masalah  optimasi  ini  lebih  akurat dan lebih baik dari metode lainnya (Angeline, 2014).

## 2. TINJAUAN PUSTAKA
2.1. Linear Programming Model  umum  dalam linear  programming dirumuskan (Aminudin, 2005):
Maksimum atau minimumkan:
𝑍 = 𝑐 1 𝑥 1 + 𝑐 2 𝑥 2 + 𝑐 3 𝑥
3 + ⋯ 𝑐 𝑛 𝑥 𝑛 (1) dengan kendala: 𝑎 11 𝑥 1 + 𝑎 12 𝑥 2 + 𝑎 13 𝑥 3 + ⋯ + 𝑎 1𝑛 𝑥 𝑛 ≤ atau ≥ 𝑏 1 𝑎 21 𝑥 1 + 𝑎 22 𝑥 2 + 𝑎 13 𝑥 3 + ⋯ + 𝑎 2𝑛 𝑥 𝑛 ≤ atau ≥ 𝑏 1 .            .            .       .         .           .             . .            .            .       .         .           .             . 𝑎 𝑚1 𝑥 1 + 𝑎 𝑚2 𝑥 2 + 𝑎 𝑚3 𝑥 3 + ⋯ + 𝑎 𝑚𝑛 𝑥 𝑛 ≤ atau ≥ 𝑏 𝑚 𝑥 𝑗 ≥ 0
untuk 𝑗 = 1,2,3, . . . , 𝑛
2.2. Integer Linear Programming
Metode  pemecahan  masalah integer  linear programming diawali dengan memanfaatkan metode simpleks. Pemecahan masalah optimal yang didapatkan dengan metode ini mungkin tidak integer. Ada dua metode untuk mendapatkan batasan-batasan khusus  yang  akan  didapat  jalan  keluar  masalah optimal  dari  masalah linear  programming relaksasi untuk mencapai ke arah mencari jalan keluar integer yang  dibutuhkan  yakni Branch  and  Bound dan Cutting Plane (Syafwan, 2018).
2.3. Metode Branch And Bound Metode Branch  and  Bound digunakan  untuk menyelesaikan suatu problem program integer linear karena  hasil  yang  diperoleh  dalam  menyelesaikan optimasi lebih teliti (Beloti, 2013).
Dalam Branch  and  Bound terdapat  masalah meminimalkan fungsi 𝑓(𝑥) dari variabel (𝑥1 . . . 𝑥𝑛) sepanjang ruang solusi yang mungkin, 𝑆 : 𝑚𝑖𝑛 𝑥∈𝑆 𝑓(𝑥) (2)
dimana  fungsi 𝑓 disebut  fungsi  objektif  dan  dapat berupa berbagai tipe.
Didalam  metode Branch  and  Bound juga terdapat  fungsi  pembatas (bounding). Fungsi pembatas  biasanya  muncul  dalam  hubungan  dengan satuan solusi potensial 𝑃 dan fungsi 𝑔 . 𝑚𝑖𝑛 𝑥∈𝑃 𝑔(𝑥) ≤   { 𝑚𝑖𝑛 𝑥∈𝑃 𝑓(𝑥) 𝑚𝑖𝑛 𝑥∈𝑆 𝑔(𝑥) ≤   𝑚𝑖𝑛 𝑥∈𝑆 𝑓(𝑥) (3)
Prosedur pemecahan problema memaksimalkan Integer Linear Programming dengan metode Branch and Bound yaitu sebagai berikut (Bonami, 2011):
Langkah 1 :   Problema diselesaiakan terlebih dahulu
dengan
memanfaatkan
linear
programming (metode  grafik  atau simplek) sampai didapat hasil optimum.
Langkah 2 :   Pemeriksaan Pemecahan Optimal Pada langkah diatas hasil optimal yang diperoleh  harus    diperiksan  apakah variabel  keputusannya  berupa  nilai integer  atau  bukan.  Jika  nilai  variabel keputusannya ternyata adalah bilangan positif bulat, maka pemecahan masalah optimal  sudah  selesai.  Jika  nilai variabel keputusannya bukan bilangan positif  bulat,  maka  proses  iterasi dilanjutkan.
Langkah 3 :   Penyusunan subproblema (branching) Jika  pemecahan  masalah  optimum belum berhasil, maka masalah tersebut dimasukan ke dalam dua subproblema dengan merubah kendala lama dengan kendala  yang  baru  ke  masing-masing subproblema tersebut.
Volume 6 No. 2, Juni 2021 – November 2021
Langkah 4 :  Penentuan Nilai Batas (Bounding)
Hasil  optimal  yang  didapat  dengan menggunakan metode linear programming adalah  nilai  batas  atas (upper bound) untuk setiap subproblema.  Sedangkan  nilai  hasil yang  optimal  dengan  pemecahan masalah Integer  Linear  Programming adalah nilai batas bawah (lower bound)
untuk  masing-masing  subproblema. Jika dalam pemecahan masalah integer linear  programming mendapatkan nilai  yang  sama  atau  lebih  baik  dari nilai  batas  atas  dari  setiap  masalah, maka  pemecahan  masalah  optimal integer telah tercapai.

## 3. METODE PENELITIAN
Jenis penelitan yang digunakan adalah penelitian terapan yakni penelitian yang menerapkan dan  mengaplikasikan  suatu  metode  yang  sudah  ada. Studi lapangan digunakan untuk mengumpulkan data dengan  cara  mewawancarai  pemilik  usaha laundry . Data  penelitian  ini  adalah  data  primer  dengan mewawancarai  pemilik  layanan  jasa laundry untuk mengetahui berapa besar keuntungannya. Sedangkan analisa  data  yang  digunakan  adalah  perhitungan menggunakan  metode Branch  and  Bound dengan bantuan software QM.

## 4. HASIL PENELITIAN
4.1. Menentukan Variabel Keputusan Tabel 1. Simbol Variabel Keputusan Jenis Bahan Variabel Jas 𝒙 𝟏 Boneka 𝒙 𝟐 Selimut 𝒙 𝟑 Bed Cover 𝒙 𝟒 Gordyn 𝒙 𝟓 Pakaian 𝒙 𝟔

## 4.2. Membuat Model Permasalahan Awal
Permasalahan awal berdasarkan variabel keputusan pada Tabel 1 akan diformulasikan kedalam model program linier: Maksimalkan: 𝑍 = 265.000𝑥 1 + 320.000𝑥 2 + 282.000𝑥 3 +   525.000𝑥 4 + 870.000𝑥 5 + 805.000𝑥 6 dengan fungsi kendala:
18𝑥 1 + 21𝑥 2 + 27𝑥 3 + 36𝑥 4 + 45𝑥 5 + 65𝑥 6 ≤ 250 9𝑥 1 + 10,2𝑥 2 + 13𝑥 3 + 15,8𝑥 4 + 19,6𝑥 5 + 29𝑥 6 ≤ 105 8𝑥 1 + 8𝑥 2 + 8𝑥 3 + 8𝑥 4 + 8𝑥 5 + 8𝑥 6 ≤ 60 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 17 4𝑥 1 + 4𝑥 2 + 4𝑥 4 + 4𝑥 5 ≤ 22 4𝑥 2 + 4𝑥 3 + 4𝑥 5 + 4𝑥 6 ≤ 22 4𝑥 1 + 4𝑥 2 + 4𝑥 3 ≤ 15 4𝑥 1 + 4𝑥 2 + 4𝑥 3 + 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 28
4.3. Menyelesaikan Permasalahan Dengan Metode Simpleks
Maksimalkan:
𝑍 − 265.000𝑥 1 + 320.000𝑥 2 + 282.000𝑥 3
+   525.000𝑥 4 + 870.000𝑥 5
+ 805.000𝑥 6 dengan fungsi kendala :
18𝑥 1 + 21𝑥 2 + 27𝑥 3 + 36𝑥 4 + 45𝑥 5 + 65𝑥 6 ≤ 250
9𝑥 1 + 10,2𝑥 2 + 13𝑥 3 + 15,8𝑥 4 + 19,6𝑥 5 + 29𝑥 6 ≤ 105
8𝑥 1 + 8𝑥 2 + 8𝑥 3 + 8𝑥 4 + 8𝑥 5 + 8𝑥 6 ≤ 60
4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 17
4𝑥 1 + 4𝑥 2 + 4𝑥 4 + 4𝑥 5 ≤ 22 4𝑥 2 + 4𝑥 3 + 4𝑥 5 + 4𝑥 6 ≤ 22 4𝑥 1 + 4𝑥 2 + 4𝑥 4 ≤ 15
4𝑥 1 + 4𝑥 2 + 4𝑥 3 + 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 28

## 4.4. Menghitung  Nilai  Variabel  Keputusan Dengan Software QM
Karena  masih  terdapat  nilai  negatif  pada  baris fungsi  tujuan  maka  dilakukan  perbaikan,  iterasi berhenti  apabila  nilai  baris  fungsi  tujuan  tidak  ada yang bernilai negatif, selain itu karena variabel yang terlalu  banyak  yakni 𝑥 1 sampai 𝑥 10 memerlukan hitungan iterasi yang banyak juga maka  dikerjakan dengan bantuan software QM agar penghitungannya lebih maksimal daripada hitung manual.
Gambar 1. Solusi dan Hasil Iterasi
Dari  hasil  iterasi  menggunakan software QM, diperoleh hasil yang optimal yaitu : x 1 = 0,7585, x 2 = 0,4915, x 3 = 0,7585, x 4 = 0, x 5 = 4,25, x 6 = 0
Berdasarkan  perhitungan, Be  Clean  Laundry sudah  hampir  mencapai  hasil  yang  optimal  tetapi keuntungan  masih  kurang  optimal,  agar  optimal Be Clean Laundry harus menambah pencucian jas yang awalnya 53 kg menjadi 53,76 kg,  boneka 32,49 kg, selimut  94,76  kg, bedcover tetap  105  kg, gordyn 91,25  kg  dan  pakaian  tetap  sebanyak  805  kg  untuk mencapai  keuntungan  maksimal  sebesar  Rp. 4.269.674.

## 4.5. Analisis Metode Branch And Bound
Hasil  yang  diperoleh  sebelumnya  yaitu 𝑥 1 = 53, 76 , 𝑥 2 = 32,49 , 𝑥 3 = 94,76 , 𝑥 4 = 105 , 𝑥 5 = 91,25 , 𝑥 6 = 805 dengan  keuntungan  sebesar Rp. 4.269.674 ,  belum  menjadi  solusi  yang  valid karena  nilai 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 5 ,  bukan  bilangan  integer. Namun  nilai  keuntungan  Rp. 4.269.674 yang menjadi batas atas (BA). Sedangkan dengan metode pembulatan  kebawah 𝑥 1 = 53 , 𝑥 2 =  32, 𝑥 3 = 94, 𝑥 4 =  100, 𝑥 5 = 91, 𝑥 6 = 800, dengan 𝑍  = 4.200.586 . Nilai keuntungan dengan pembulatan ke bawah dijadikan sebagai batas bawah (BB). Proses  Pencabangan  ini  tetap  dilanjutkan sampai semua nilai variabel keputusan bernilai bulat dan fisibel.
Pencabangan Submasalah 1 Maksimalkan : 𝑍 = 265.000𝑥 1 + 320.000𝑥 2 + 282.000𝑥 3
+ 525.000𝑥 4 + 870.000𝑥 5 + 805.000𝑥 6 dengan kendala : 8𝑥 1 + 21𝑥 2 + 27𝑥 3 + 36𝑥 4 + 45𝑥 5 + 65𝑥 6 ≤ 250 9𝑥 1 + 10,2𝑥 2 + 13𝑥 3 + 15,8𝑥 4 + 19,6𝑥 5 + 29𝑥 6 ≤ 105 8𝑥 1 + 8𝑥 2 + 8𝑥 3 + 8𝑥 4 + 8𝑥 5 + 8𝑥 6 ≤ 60 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 17 4𝑥 1 + 4𝑥 2 + 4𝑥 4 + 4𝑥 5 ≤ 22 4𝑥 2 + 4𝑥 3 + 4𝑥 5 + 4𝑥 6 ≤ 22 4𝑥 1 + 4𝑥 2 + 4𝑥 3 ≤ 15 4𝑥 1 + 4𝑥 2 + 4𝑥 3 + 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 28 𝑥 6 ≥ 805 sebagai kendala baru 𝑥 𝑗 ≥  0

## Pencabangan Submasalah 2
Maksimalkan : 𝑍 = 265.000𝑥 1 + 320.000𝑥 2 + 282.000𝑥 3
+  525.000𝑥 4 + 870.000𝑥 5
+ 805.000𝑥 6 dengan kendala : 18𝑥 1 + 21𝑥 2 + 27𝑥 3 + 36𝑥 4 + 45𝑥 5 + 65𝑥 6 ≤ 250 9𝑥 1 + 10,2𝑥 2 + 13𝑥 3 + 15,8𝑥 4 + 19,6𝑥 5 + 29𝑥 6 ≤ 105 8𝑥 1 + 8𝑥 2 + 8𝑥 3 + 8𝑥 4 + 8𝑥 5 + 8𝑥 6 ≤ 60 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 17 4𝑥 1 + 4𝑥 2 + 4𝑥 4 + 4𝑥 5 ≤ 22 4𝑥 2 + 4𝑥 3 + 4𝑥 5 + 4𝑥 6 ≤ 22 4𝑥 1 + 4𝑥 2 + 4𝑥 3 ≤ 15 4𝑥 1 + 4𝑥 2 + 4𝑥 3 + 4𝑥 4 + 4𝑥 5 + 4𝑥 6 ≤ 28 𝑥 6 ≤ 800 sebagai kendala baru 𝑥 𝑗 ≥  0
Dengan metode simpleks diperoleh solusi yaitu: Solusi sub masalah 1: 𝑥 1 = 53,76 , 𝑥 2 = 33,74 , 𝑥 3 = 96,45 , 𝑥 4 = 105 , 𝑥 5 =
95,5 , 𝑥 6 = 805, 𝑍 = 4.291.646
Solusi sub masalah 2: 𝑥 1 = 55, 01 , 𝑥 2 = 33,18 , 𝑥 3 = 94,76 , 𝑥 4 = 109,25 , 𝑥 5 = 91,25 , 𝑥 6 = 800 , 𝑍 = 4.200.246
Gambar 2. Hasil Perhitungan Akhir Metode Branch and Bound dengan Software QM
Dengan  menggunakan  metode Branch  and Bound maka agar mencapai keuntungan optimal, Be clean  laundry harus  mencuci  sebanyak  53  kg  jas menjadi  54  kg  jas,  boneka  32  kg,  selimut  95  kg, bedcover tetap  105  kg, gordyn 91  kg  dan  pakaian tetap sebanyak 805 kg. Untuk mencapai keuntungan maksimal  sebesar  Rp.  4.027.000  yang  awalnya dengan sistem perkiraan yang dibuat oleh pemilik Be Clean  Laundry hanya  mendapatkan  keuntungan sebesar Rp.4.000.000, sekarang naik sebesar 0,7 %.

## 5. KESIMPULAN
Perhitungan menggunakan metode Branch and Bound memberikan hasil lebih optimal dibandingkan dengan  hasil  keuntungan  sebelumnya  dengan perhitungan manual pada Be Clean Laundry . Setelah menggunakan metode Branch  And Bound Be Clean Laundry mencapai  keuntungan  maksimal  sebesar Rp. 4.027.000 yang awalnya dengan sistem perkiraan yang dibuat oleh pemilik Be Clean Laundry memiliki keuntungan  sebesar  Rp.4.000.000,  sekarang  naik sebesar 0,7 %.

## DAFTAR PUSTAKA
Angeline,  I,  dan    Tarigan,  G.  (2014). Penerapan Metode  Branch andBound Dalam  Menentukan Jumlah  Produksi  Optimum  Pada  CV.  XYZ . Saintia Matematika (pp. 137– 145).
Anwar,  C.  (2014). Hakikat  Manusia  Dalam
Pendidikan  Sebuah Tinjauan . Filosofis.
Yogyakarta: SUKA-Press.
Aminuddin. (2005), Prinsip-prinsip Riset Operasi , Jakarta: Erlangga.
Belotti, P. (2013). Bound Reduction Using Pairs Of
Linear inqualities . Department Of
Mathematical Sciences, Clemson University.
Bonami P., Lee J., Leyffer S., dan Wachter A. (2011). More Branch and Bound Experiments in Convex Nonlinear Integer Programming .
Syafwan, H. (2018). Penerapan Metode Branch And
Bound Dalam Penyelesaian
Masalah  Pada Integer Programming (pp. 89-96).
Wijaya, A. (2013). Pengantar Riset Operasi. 3 Ed . Jakarta: Penerbit Mitra Wacana Media, 2013.