Available online at http://jurnal.yudharta.ac.id/v2/index.php/jkie P-ISSN : 2460-0113 I E-ISSN : 2541-4461

## Journal Knowledge Industrial Engineering (JKIE)

## OPTIMASI PRODUKSI PIA CAKE MENGGUNAKAN METODE INTEGER PROGRAMMING DI UKM
XYZ DESA WARU REJO GEMPOL PASURUAN
(1) Mega Ryan Kevin 1 , (2) Khafizh Rosyidi
(1,2) Program Studi Teknik Industri Universitas Yudharta Pasuruan

## A BSTRAK
UKM  XYZ    merupakan  sebuah  industri  manufacturing  yang  bergerak  dibidang  industri makanan.  Industri  ini  tidak  memiliki  metode  tertentu  yang  pasti  dalam  menentukan  jumlah produksi masing-masing jenis pia cake dan mengakibatkan profit yang didapat kurang optimal. Oleh karena itu, perlu dilakukan penelitian untuk  mengetahui formulasi produk yang optimal dalam  pembuatan  pia  cake    di  UKM  XYZ.  Metode  yang  akan  digunakan  dalam  penelitian  ini adalah model Integer Programming dengan  metode Branch and Bound yang terlebih dahulu menghitung  nilai  variabel  keputusan  dengan  menggunakan  metode  simpleks.  Penelitian  ini ditinjau  berdasarkan  jumlah  persediaan  bahan  baku,  bahan  baku  pembuatan  pia  cake,  data produksi,biaya produksi, harga jual setiap jenis pia, dan  profit. Sehingga dari analisis metode branch and bound diperoleh nilai keuntungan sebesar Rp. 1.200.000 . Jadi jumlah pia yang bisa diproduksi  dari  bahan-  bahan  yang  tersedia  ialah  840  pia  ukuran  kecil  dan  180  pia  ukuran besar dengan jumlah untuk masing- masing jenis pia : pia isis kacang hijau 3 adonan (ukuran kecil), pia isi coklat pisang 2 adonan (ukuran kecil), pia isis keju pisang 1 adonan (ukuran kecil) dan 1 adonan (ukuran besar), dan pia isi tape 3 adonan (ukuran kecil). Sedangkan perkiraan UKM adalah dengan bahan- bahan yang tersedia dapat memproduksi 540 pia ukuran kecil dan 240  pia  ukuran  besar  dengan  keuntungan  Rp.  1.020.000.  Jadi  selisih  keuntungan  sebelum menggunakan  metode  Integer  Programming  dengan  sesudah  menggunakan  metode  Integer Programming adalah Rp. 180.000.

## Kata kunci: Optimasi; Integer Programming; Branch and Bound

## 1. Pendahuluan

## 1.1 Latar Belakang
Ketatnya persaingan pada usaha kecil dan menengah (UKM) yang memproduksi produk yang sejenis  akan  membuat  UKM  tersebut  terpacu  untuk  menciptakan  inovasi  –  inovasi  yang  lebih menarik  dan  beragam  serta  selektif  dalam  kualitas  produk  yang  diproduksi,  dan  pada  umunya tujuan  utama  didirikannya  suatu  usaha  adalah  memperoleh  laba  yang  cukup  dan  semaksimal mungkin dari operasional usaha yang dilakukan. Namun seringkali pada kenyataanya, suatu usaha sering  mengalami  banyak  hambatan  atau  masalah  yang  merintanginya  dalam  pencapaian  tujuan usaha  tersebut.  Persoalan  yang  dihadapi  oleh  usaha  pada  umumnya  adalah  bagaimana mengoptimalkan produk yang harus diproduksi agar diperoleh keuntungan maksimal.
UKM XYZ  adalah salah satu UKM yang berada di Kampung Pia di desa Waru Rejo – Gempol - Pasuruan.  Karena  bukan  hanya  UKM  XYZ  yang  memproduksi  pia cake di  daerah  tersebut,  maka persaingan  antar  UKM  pia  sangatlah  ketat.  Dengan  demikian  untuk  dapat  terus  bertahan  dan berkembang  pengusaha  pia    harus  dapat  menyelesaikan  setiap  permasalahan  yang  dihadapi. Permasalahan  yang  dihadapi  di  ukm  pia  ini  adalah  kurang  adanya  formulasi  produk  yang  harus
1 mega.ryankevin@gmail.com
diproduksi  dari  setiap  jenis  pia cake mengakibatkan  ukm  pia  tersebut  mengalami  kerugian  dan kuarng optimalnya profit yang didapat.
Agar  pembuatan  pia cake untuk  setiap  jenis  rasa  mencapai  optimal  maka  penulis menggunakan  model Integer  Programming dengan  metode Branch  and  Bound.  Integer Programming merupakan  bagian  dari Linear  Programming yang  merupakan  suatu  model  umum yang  dapat  digunakan  dalam  pemecahan  masalah  pengalokasian  sumber-sumber  yang  terbatas secara optimal.
Alasan peneliti menggunakan model Integer Programming dengan metode Branch and Bound karena  metode  sebelumnya  sudah  banyak  peneliti  yang  menggunakan  metode  tersebut  dan hasilnya optimal. Jadi dalam permasalahan ini peneliti menggunakan model Integer Programming dengan metode Branch and Bound untuk menentukan jumlah produk yang harus diproduksi setiap jenis pia cake yang dilakukan oleh UKM untuk meningkatkan laba .

## 1.2 Rumusan Masalah
a. Bagaimana  menentukan  formulasi  produk  yang  optimal  dalam  pembuatan  pia cake di  UKM XYZ?
b. Berapa  jumlah  profit  yang  dicapai  dari  model Integer  Programming pada    produk  pia cake di UKM XYZ?

## 1.3 Tujuan Penelitian
a. Mengetahui formulasi produk yang optimal dalam pembuatan pia cake di UKM XYZ.
b. Mengetahui jumlah profit yang dicapai dari model Integer Programming pada  produk pia cake di UKM XYZ

## 1.4 Batasan Penelitian
a. Jenis produk yang diteliti adalah pia cake isi kacang hijau, coklat pisang, keju pisang, dan tape.
b. Nilai yang ingin dicapai adalah maksimasi keuntungan.

## 2. Tinjauan Pustaka
Dimyati dan A. Dimyati (1987) juga mendefinisikan program linier sebagai suatu cara untuk menyelesaikan  persoalan  pengalokasian  sumber-sumber  yang  terbatas  di  antara  beberapa aktivitas, dengan cara yang terbaik yang mungkin dapat dilakukan.
Salah  satu  metode  untuk  menyelesaikan  masalah  program  linear  adalah  dengan menggunakan  metode  simpleks.  Metode  simpleks  merupakan  prosedur  aljabar  yang  bersifat iteratif,  yang  bergerak  selangkah  demi  selangkah  dimulai  dari  titik  ekstrem  pada  daerah  layak menuju  ke  titik  ekstrem  yang  optimum  untuk  mencari  nilai  optimal  dari  fungsi  tujuan  dalam masalah optimasi yang terkendala (Frederick S. Hillier dan Gerald J. Lieberman, 1995: 57).
Salah satu software yang digunakan untuk menyelesaikan metode simplekj adalah software QM for windows . QM adalah kepanjangan dari quantitatif method yang merupakan perangkat lunak dan menyertai buku-buku teks seputar manajemen operasi. QM for windows merupakan gabungan dari program terdahulu DS dan POM for windows , jadi jika dibandingkan dengan program POM for windows modul-modul yang tersedia pada QM for windows lebih banyak. Namun ada modul-modul yang  hanya  tersedia  pada  program  POM for  windows ,  atau  hanya  tersedia  di  program  DS  for windows dan tidak tersedia di QM for windows.
Menurut Mulyono (2004), program integer dibutuhkan ketika keputusan harus dalam bentuk bilangan integer. Model matematis dari program integer sebenarnya sama dengan model program
linier,  dengan  tambahan  batasan  bahwa  variabel  keputusannya  harus  bilangan  integer.  Program integer  adalah  suatu  program  linier  dengan  tambahan  persyaratan  bahwa  semua  atau  beberapa variabel bernilai bulat non negative.
Menurut Fien Zulfikarijah (2004), Branch and Bound adalah algoritma umum untuk mencari solusi  optimal  dari  berbagai  masalah  optimasi.  Metode  ini  pertama  kali  diperkenalkan  oleh  A.H. Land dan A.G. Doig pada tahun 1960. Branch and bound bukan sebuah teknik solusi khusus terbatas untuk masalah program integer. Branch and bound adalah pendekatan solusi yang dapat diterapkan pada beberapa jenis masalah.
1. Branching adalah  proses  membagi-bagi  permasalahan  menjadi  subproblem-subproblem  yang mungkin mengarah ke solusi.
2. Bounding adalah  suatu  proses  untuk  mencari/menghitung  batas  atas  (BA)  dan  batas  bawah (BB) untuk solusi optimal pada subproblem yang mengarah ke solusi.

## 3. Metode Penelitian

## 4. Pembahasan
Formulasi model Linear programming
1. Pia Isi Kacang Hijau
a. Fungsi obyektif atau fungsi tujuan Memaksimumkan Z = 75.000X1 + 150.000X2
b. Fungsi Batasan
4,5X1 + 5X2 ≤ 19
2X1 + 3X2  ≤ 8 0,25X1 + 0,5X2  ≤ 3 3X1 + 5X2  ≤ 9 2X1 + 3X2 ≤ 8 2X1 + 3X2 ≤ 10
2. Pia Isi Coklat Pisang
a. Fungsi obyektif atau fungsi tujuan Memaksimumkan Z = 120.000X1 + 200.000X2
b. Fungsi Batasan
5X1 + 5X2 ≤ 19
2X1 + 2X2 ≤ 8
0,25X1 + 0,25X2  ≤ 3
3X1 + 3X2  ≤ 9
2X1 + 2X2 ≤ 8 2X1 + 2X2 ≤ 5 2X1 + 2X2 ≤ 5
3. Pia Isi Keju Pisang
a. Fungsi obyektif atau fungsi tujuan Memaksimumkan Z = 90.000X1 + 200.000X2
b. Fungsi Batasan 4X1 + 5X2 ≤ 19
1,5X1 + 2X2 ≤ 8 0,15X1 + 0,25X2  ≤ 3 3X1 + 5X2  ≤ 9
1,5X1 + 2X2 ≤ 8
1,5X1 + 2X2 ≤ 6
2X1 + 3X2 ≤ 5
4. Pia Isi Tape
a. Fungsi obyektif atau fungsi tujuan Memaksimumkan Z = 105.000X1 + 150.000X2
b. Fungsi Batasan
4,5X1 + 5X2 ≤ 19
1X1 + 3X2 ≤ 8
0,25X1 + 0,5X2  ≤ 3
3X1 + 5X2  ≤ 9 2X1 + 3X2 ≤ 8 2X1 + 3X2 ≤ 6

## Perhitungan Dengan Menggunakan Software QM For Windows
1. Kacang Hijau
Gamabr 4.1: Tampilan Formulasi Pia Isi Kacang Hijau
Gambar  4.2: Solution List Dari Pia Isi Kacang Hijau
Maka  dapat  terlihat  bahwa  pia  isi  kacang  hijau  yang  harus  diproduksi  antara  lain:  Tidak memproduksi pia isi keju pisang yang berukuran kecil, dan memproduksi pia isi keju pisang yang berukuran  besar  =  1,8  adonan  dengan  keuntungan  Rp.270.000.  Untuk  memperoleh  hasil  berupa bilangan  integer  yang  diingkan,  maka  diperlukan  metode branch  and  bound dalam  perhitungan pencarian solusi.

## 2. Coklat Pisang
Gambar4.3: Tampilan Formulasi Pia Isi Coklat Pisang

## Gambar 4.4: Solution List Dari Pia Isi Coklat Pisang
Maka dapat terlihat bahwa pia yang yang harus diproduksi adalah  X1 =0 dan X2 = 2 maka Z = Rp. 400.000. Karena solusi yang ditemukan sudah terpenuhi, maka perhitungan dianggap selesai.

## 3. Keju Pisang
Gambar 4.5: Tampilan Formulasi Pia Isi Keju Pisang
Gambar 4.6: Solution List Dari Pia Isi Keju Pisang
Maka  dapat  terlihat  bahwa  pia  isi  keju  pisang  yang  harus  diproduksi  antara  lain:  Tidak memproduksi pia isi keju pisang yang berukuran kecil, dan memproduksi pia isi keju pisang yang berukuran besar  = 1,6  adonan dengan keuntungan Rp.333.333 . Untuk  memperoleh hasil  berupa
bilangan  integer  yang  diingkan,  maka  diperlukan  metode branch  and  bound dalam  perhitungan pencarian solusi.
4. Tape
Gambar 4.7: Tampilan Formulasi Pia Isi Tape
Gambar  4.8: Solution List Dari Pia Isi Tape
Maka dapat terlihat bahwa pia yang harus diproduksi adalah  X1 = 3 dan X2=0 maka Z = Rp. 315.000. Karena solusi yang ditemukan sudah terpenuhi, maka perhitungan dianggap selesai.

## Analisis Metode Branch and Bound

## 1. Pia isi Kacang hijau
Langkah  pertama  adalah  menentukan  batas  atas  (BA)  dan  batas  bawah  (BB).  Keuntungan dengan X1= 0 dan X2= 1,8 adalah Rp. 270.000, karena X2 bukan bilangan integer, maka solusi ini tidak  valid,  nilai  keuntungan  Rp.  270.000  dijadikan  batas  atas  (BA).  Dengan  metode  pembulatan kebawah,  didapatkan  X1=  0  dan  X2=  1  dengan  keuntungan  Rp.  150.000,  hasil  ini  fisibel  (layak) karena  kedua  variabel  merupakan  bilangan  integer.  Jadi  nilai  keuntungan  dengan  pembulatan (mengintegerkan) kebawah dijadikan batas bawah (BB).
Langkah  kedua  adalah  memilih  variabel  keputusan  yang  memiliki  pecahan  terbesar  untuk melakukan  pencabangan.  Karena  pecahan  terbesar  berada  pada  X2  yakni  sebesar  0,8  maka  X2 dicabangkan menjadi sub masalah 1 dan 2 dengan tambahan kendala untuk masing- masing sub- masalah X2 ≤ 1 dan X2 ≥ 2. Sehingga diperoleh formula untuk sub- masalah 1 dan 2 sebagai berikut:
 Solusi  sub-  masalah  1:  X1  =  1,3  dan  X2  =  1  maka  Z  =    Rp.  250.000  (belum  integer  dan  fisibel (layak)).
 Solusi sub- masalah 2: Tidak fisibel (tidak layak)
 Solusi sub- masalah 3: X1 = 0 dan X2 = 1,8 maka Z =  Rp. 270.000 (belum integer dan tidak fisibel (tidak layak)).
 Solusi  sub-  masalah  4:  X1  =  2  dan  X2  =  0,6  maka  Z  =    Rp.  240.000  (belum  integer  dan  fisibel (layak)).
 Solusi sub- masalah 5: X1 = 3 dan X2 = 0 maka Z =  Rp. 225.000 (integer dan fisibel (layak)).
 Solusi sub- masalah 6: X1 = 0 dan X2 = 1,8 maka Z =  Rp. 270.000 (belum integer dan tidak fisibel (tidak layak)).
Gambar 4.8: Hasil Perhitungan Branch and Bound Pia Isi Kacang Hijau

## 2.  Keju pisang
Langkah  pertama  adalah  menentukan  batas  atas  (BA)  dan  batas  bawah  (BB).  Keuntungan dengan X1= 0 dan X2= 1,6 adalah Rp. 333.333, karena X2 bukan bilangan integer, maka solusi ini tidak  valid,  nilai  keuntungan  Rp.  333.333  dijadikan  batas  atas  (BA).  Dengan  metode  pembulatan kebawah,  didapatkan  X1=  0  dan  X2=  1  dengan  keuntungan  Rp.  200.000,  hasil  ini  fisibel  (layak) karena  ketiga  variabel  merupakan  bilangan  integer.  Jadi  nilai  keuntungan  dengan  pembulatan (mengintegerkan) kebawah dijadikan batas bawah (BB).
Langkah  kedua  adalah  memilih  variabel  keputusan  yang  memiliki  pecahan  terbesar  untuk melakukan  pencabangan.  Karena  pecahan  terbesar  berada  pada  X2  yakni  sebesar  0,5  maka  X2 dicabangkan menjadi sub masalah 1 dan 2 dengan tambahan kendala untuk  masing- masing sub- masalah X2 ≤ 1 dan X2 ≥ 2. Sehingga diperoleh formula untuk sub- masalah 1 dan 2 sebagai berikut:
 Solusi sub- masalah 1: X1 = 1 dan X2 = 1 maka Z =  Rp. 290.000 (telah integer dan fisibel (layak)).
 Solusi sub- masalah 2: tidak fisibel (tidak layak).
Gambar 4.9: Hasil Perhitungan Branch and Bound Pia Isi Keju Pisang
5. Kesimpulan dan Saran
5.1 Kesimpulan
1. Pia  yang  akan  diproduksi  oleh  pihak  perusahaan  adalah  840  pia  ukuran  kecil  dan  180  pia ukuran besar, dengan pembagian sebagai berikut :
 Pia isi kacang hijau berukuran kecil 36 kardus
 Pia isi coklat pisang berukuran besar 12 krdus
 Pia isi keju pisang berukuran kecil 12 kardus dan berukuran besar 6 kardus
 Pia isi tape berukuran kecil 36 kardus
2. Keuntungan yang diperoleh dari hasil analisa dengan metode branch and bound (masih berupa adonan)adalah Rp. 1.030.000 dengan rincian sebagai berikut:
 Pia isi kacang hijau Rp. 225.000
 Pia isi coklat pisang Rp. 200.000
 Pia isi keju pisang Rp. 290.000
 Pia isi tape Rp. 315.000

## 5.2 Saran
1. Hasil dari penelitian ini menjadi bahan pertimbangan dan informasi tambahan bagi perusahaan dalam menetapkan rencana produksi.
2. Penggunaan  Software  QM For  Windows di  UKM  XYZ  sangat  diperlukan  untuk  menghitung keuntungan optimum yang diperoleh dari hasil produksi.
3. Hendaknya  pemilik  UKM  dalam  menentukan    kebijakan  dalam  hal  produksi  menggunakan program Integer dengan metode branch and bound , dimana dengan  menggunakan metode ini ditemukan jumlah produksi yang integer dan kombinasi yang optimum.

## DAFTAR PUSTAKA
Alkhoiroda’I,  Muhammad  Shofi.  2013.  Implementasi  Algoritma Brach  and  Bound untuk  Optimasi Rute Pengangkutan Sampah Kota Yogyakarta. Skripsi Sarjana Matematika Fakultas Sains dan Teknologi, UIN Sunan Kalijaga Yogyakarta.
Angeline, Iryanto dan Gim Tarigan. 2014. Penerapan Metode branch and bound dalam Menentukan Jumlah Produksi Optimum Pada CV. XYZ. Jurnal Saintia Matematika. Vol. 2, No. 2 (2014), pp. 137–145. ISSN: 2337-9197.
Kholilah,  Nusaibah.  2015.  Aplikasi  Metode  Branch  and  Cut  dalam  optimasi    Produksi  Pot  Bunga (studi  kasus:  UD.  Pot  Bunga  Mukhlis  Rangkuti,  Gelugur).  Skripsi  Sarjana  Sains,  Fakultas Matematika Dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara.
Muzaki,  Muhammad.  2012.  Optimalisasi  Keuntungan  pada  perusahaan  Keripik  Balado  Mahkota Dengan  Menggunan Metode Simpleks. Jurnal Matematika Unand Vol. 1 No.  1 Oktober 2012 ISSn : 2303-2910.
Nurhidayati,  Farida  Ulfa.  2010.  Penggunaan  Program  Dinamik  Untuk  Menentukan  Total  Biaya Minimum  Pada  Perencanaan  Produksi  Dan  Pengendalian  Persediaan.  Skripsi  Sarjana Matematika Fakultas Sains dan Teknologi, Universitas Islam Negeri Maulana  Malik Ibrahim Malang.
Putri  Delfianda,  Hanny  Komalig,  dan  Tohap  Manurung.  2015.  Optimalisasi  Biaya  Total Perencanaandan  Pengendalian  Persediaan  Menggunakan  Program  Dinamik.  Jurnal Matematika. JdC, Vol. 4, No. 1, Maret 2015.
Roland Ganda Simanjuntak, Faigiziduhu Bu’ulolo, dan Esther S M Nababan. 2013. Aplikasi Program Dinamik Untuk Mengoptimalkan Biaya Total Pada Pengendalian Produksi Minyak Sawit Dan
Inti Sawit (Studi Kasus: Ptpn Iv (Persero) PKS Sawit Langkat). Jurnal Matematika. Vol. 1, No. 5 (2013), pp. 419–433.
Taha, Hamdy A. 1996. Riset Operasi Edisi Ke Lima. Binarupa Aksara : Jakarta. Utami,  Arum  Tri.  2013.  Penerapan  Integer  Linear  Programing  (Metode  Brach  and  Bound  dan Metode  Cutting  Plane)  dan  Analisis  Titik  Impas  (BEP)  Multiproduk  Guna  Mengoptimalkan Jumlah  Produk.  Skripsi  Sarjana  Teknik  Industri  Fakultas  Sains  dan  Teknologi.  Universitas Islam Negeri Sunan Kalijaga Yogyakarta.