Aplikasi Integer Linear Programming (Ilp) untuk

## Meminimumkan Biaya Produksi pada Siaputo
Aluminium
Hikmah *1 , Nusyafitri Amin 2 *1 Program Studi Matematika FMIPA Universitas Sulawesi Barat, 2 Program Studi Pendidikan Matematika FMIPA Universitas Sulawesi Barat e-mail: *1 hikmah.ugm@gmail.com, 2 nursyafitriamin@gmail.com

## Abstrak
Penelitian  ini  bertujuan  untuk  menyelesaikan  masalah  optimisasi,  khusunya meminimumkan  biaya  produksi  dengan  menggunakan  Integer  Linear  Programming (ILP).  Penelitian  dilaksanakan  pada  salah  satu  usaha  pembuatan  lemari  aluminium    di Majene  dan  melakukan  wawancara  langsung  dengan  pemilik  usaha  tersebut.  Langkah- langkah  proses  penelitian  ini  meliputi:  (1)  mengumpulkan  data  dengan  wawancara,  (2) menyusun model matematika yaitu menentukan fungsi tujuan dan fungsi kendala, dan (3) menyelesaikan  masalah.  Pada  langkah  menyelesaikan  masalah,  peneliti  menggunakan metode Branch and Bound, selanjutnya menggunakan program LINDO.
Kata kunci : optimasi, integer linear programming, fungsi tujuan dan kendala .

## 1. PENDAHULUAN
Permasalahan  optimalisasi  merupakan  bagian  dari  permasalahan  masyarakat  terutama yang  bergerak  di  bidang  usaha  produksi  barang.  Optimalisasi  tersebut  adalah meminimumkan  biaya  produksi  serta  memaksimumkan  keuntungan  penjualan.  Akan tetapi dalam menjalankan suatu usaha, manusia selalu menghadapi batasan-batasan dalam usaha pengoptimalisasian misalnya saja sumber daya dan modal yang terbatas.
Aplikasi  matematika  yang  digunakan  untuk  mengkaji  masalah  optimalisasi biasanya  disebut  penelitian  operasional  atau  riset  operasi,  yang  merupakan  teknik  untuk menyelesaikan  masalah  optimalisasi.  Riset  operasi  ( Operations  Research ),  dalam  arti luas,  dapat  diartikan  sebagai  penerapan  metode-metode,  teknik-teknik,  dan  alat-alat terhadap masalah-masalah yang menyangkut operasi dari sistem-sistem, sedemikian rupa sehingga memberikan penyelesaian optimal  Mulyono (2004).
Dalam memecahkan masalah optimalisasi ini, matematika menyediakan berbagai metode  untuk  menentukan  solusi  optimum.  Salah  satu  bagian  riset  operasi  yang  biasa digunakan adalah Pemprograman Linier ( Linear Programming ) dan Pemrograman Linier Bilangan  Bulat  ( Integer  Linear  Programming ).  Pada  penelitian  ini  akan  digunakan Integer  Linear  Programming (ILP) dengan  menggunakan  metode Branch  and  Bound (B&B).
Pada  penelitian  ini,  akan  dikembangkan  model ILP masalah  meminimumkan biaya produksi dan dari model tersebut akan ditentukan solusi optimum (jumlah produksi barang optimal) yang dapat meminimumkan biaya produksi.
Uraian ini memunculkan beberapa rumusan  masalah yakni  Bagaimana formulasi matematika dalam meminimumkan biaya produksi pada Sipatuo Aluminium? Bagaimana menyelesaikan model ILP masalah meminimumkan biaya produksi dengan menggunakan
metode  B&B?  Apakah  biaya  produksi  yang  dilakukan  di  Sipatuo  Aluminium  sudah minimum?
Secara  umum  masalah  (problem)  dapat  ditafsirkan  sebagai  suatu  kesenjangan antara  yang  seharusnya  terjadi  dan  yang  sesungguhnya  terjadi,  atau  antara  cita-cita (tujuan)  dan  keadaan  sekarang.  Menyelesaikan  masalah  berarti  menjembatani kesenjangan di  atas.  Analisis  system memberikan langkah-langkah penyelesaian  sebagai berikut:  mengidentifikasi  masalahnya,  mencari  metode-metode  penyelesaian,  memilih metode  yang  paling  cocok,  papling  murah,  atau  paling  cepat  (optimasi),  melaksanakan serta mengevaluasi hasil.
Pada  langkah  ke  (i)  matematik  berusaha  untuk  merumuskan  masalahdalam  arti menerjemahkan  masalah  ke  dalam  bahasa  matematka  (misalnya  menjadi  suatu  bentuk aljabar).  Usaha  ini  disebut  menyusun  model  matematika  dari  masalah  yang  ada, sedangkan  hasilnya  disebut  model  matematika.  Tentu  saja  suatu  model  tidak  dapat menggambarkan  masalahnya  dengan  tepat,  karena  untuk  sampai  ke  bentuk  model, masalah  nyata  sudah  mengalami  beberapa  penyederhanaan  (karena  adany  asumsi- asumsi), tetapi model diusahakan sedekat mungkin denga aslinya.
Optimasi dan Pemprograman Matematika Optimasi  adalah  sebuah  alat  yang  digunakan  secara  luas  pada  formulasi  model matematika  dan  berbagai  masalah  analisis  keputusan  yang  berkaitan  dengan  masalah sains dan teknik. Secara umum, masalah real di dunia  terjadi dalam model multi-criteria dan multi-choice dengan  konstrain  tertentu    dalam  A.K.  Ojha  dan  Rashmi  Ranjan  Ota (2014).
Konsep optimasi membahas prinsip dan analisis dari pengambilan keputusan dan masalah  alokasi.  Dalam    masalah  optimasi,  hal  yang  paling  sering  dihadapi  adalah masalah  pengambilan  keputusan  yang  melibatkan  fungsi  tujuan/  objektif  dan  fungsi kendala.  Fungsi objektif ini, membahas masalah memaksimumkan  atau meminimumkan tergantung  dari  masalah  yang  dihadapi.  Untuk  mencari    penyelesaian  suatu  masalah optimasi,  sangat  sulit  untuk  memasukkan  semua  hal  yang  berhubungan  dengan permasalahan  realnya,  misal  hubungan  berbagai  variabel,  kendala,  dan  fungsi  objektif sehingga hasil penyelesaiaanya tidak lain hanyalah suatu nilai pendekatan.
Kemampuan  pemodelan  sangat  diperlukan  dalam  menyelesaikan  masalah optimasi,  kemampuan  menentukan  faktor  yang  paling  berpengaruh  dengan  masalah  dan kemampuan  interpretasi  hasil  pemodelan  sangat  diperlukan  dalam  menarik  kesimpulan akhir.  Masalah  optimasi  jika  ditinjau  dari  fungsi  objektif  dan  fungsi  kendalanya  dapat dibagi menjadi 2 kelompok besar, yakni pemrograman linier dan pemrograman nonlinier Luenberger (2008).
Dalam  setiap  program  matematis,  kita  mencari  pemecahan  ( solution ).  Jika terdapat sejumlah pemecahan optimal yang setara, maka kita dapat mengambil yang mana saja  sebagai  pemecahannya.  Jadi  tidak  ada  yang  diistimewakan  antara  pemecahan- pemecahan  optimal  yang  setara  jika  tidak  terdapat  persyaratan  istimewa  dalam  kendala- kendalanya.
Secara umum, masalah optimasi dapat dinyatakan seperti bentuk di bawah
solusi  dari  model  adalah  solusi  yang  memenuhi  semua  syarat  fungsi  kendala dikutip dari Taha (2007)
Maksimumkan atau minimumkan Fungsi Objektif
dengan syarat
Pemrograman  matematika  adalah  masalah  optimasi  yang  di  dalamnya  terdapat fungsi tujuan/ objektif dan fungsi kendala. Biasanya pemrograman matematika berbentuk Optimumkan (Maksimumkan/ Minimumkan):
1 2 ( , ,..., ) n z f x x x =
dengan kendala: 1 1 2 1 2 1 2 2 1 2 ( , ,..., ) ( , ,..., ) ... ... ( , ,..., ) n n m n m g x x x b g x x x b
g x x x b ü ì £ ï ï ï ï = ý í ï ï ³ ï ï þ î
Adapun  fungsi  kendala  yang  disebut  fungsi  kendala  tak  negatif,  yaitu
1 2 , ,..., n x x x ³ 0.
1.1 Program Linear Bilangan Bulat (Integer Linear Programming)
ILP pada intinya berkaitan dengan program-program linear di mana beberapa atau semua  variabel  memiliki    nilai-  nilai  integer  atau  diskrit.  Sebuah ILP dikatakan  bersifat campuran  dan  murni  bergantung  pada  apakah  beberapa  atau  semua  variabel  tersebut dibatasi pada nilai-nilai integer dalam Taha (1993).
Misalnya,  jika  Sebuah  perusahaan  jasa  pengantar  barang  merakit  3  jenis  senter. Senter  jenis  A,  senter  jenis  B,  dan  senter  jenis  C.  Senter  jenis  A  dirakit  dengan membutuhkan  waktu  15  menit,  jenis  B  selama  4  menit  dan  jenis  C  selama  12  menit. Waktu  pengerjaan  yang  tersedia  tiap  minggunya  selama  2800  menit.  Senter  jenis  A membutuhkan besi seberat 150 g, senter jenis B membutuhkan besi seberat 100 gram, dan senter jenis C membutuhkan besi seberat  80 g. Jumlah besi  yang dapat disediakan oleh perusahaan  hanya  60000  gram  tiap  minggunya.  Untuk  senter  jenis  A  membutuhkan aluminium  seberat  10  g,  senter  B  membutuhkan  aluminium  seberat  80  g,  dan  senter  C seberat  90  g. Jumlah  aluminium  yang  dapat  disediakan  oleh  perusahaan  tiap  minggunya mencapai 12000 gram. Jika keuntungan bersih yang diperoleh dari hasil penjualan senter A, senter B, senter C berturut-turut sebesar 5000, 5000, 24000. Akan menghasilkan solusi ! " = 87,804878  ! # = 123,57724  $ = 3404,878 .  Apabila  kita  mengambil  solusi  ini maka kita akan memproduksi 87,804878 Senter A dan 123,57724 senter C. Maka masalah ini termasuk masalah Integer Linear Programming .

## 1.2 Metode Branch and Bound
Suatu  program  bilangan  bulat  adalah  program  linear  dengan  tambahan  syarat bahwa  semua  atau  sebagian  variabelnya  haruslah  bilangan  bulat.  Meskipun  demikian, pendekatan  pertama  untuk  beberapa  kasus  program  bilangan  bulat  mugkin  dapat diperoleh  dengan  mengabaikan  syarat  bilangan  bulatnya  dan  menyelesaikan  program linear dengan satu dari beberapa metode yang bisa digunakan (Bronson, 1996: 54).
Dalam  LP,  metode  simpleks  didasari  oleh  pengenalan  bahwa  pemecahan optimum terjadi di titik ekstrim dari ruang pemecahan.  Sebaliknya ILP memulai dengan sejumlah titik pemecahan yang terbatas (dengan asumsi ILP murni yang dibatasi). Tetapi sifat  variabel  yang  berbentuk  bilangan  bulat  mempersulit  perancangan  sebuah  algoritma yang  efektif  untuk  mencari  secara  langsung  di  antara  titik  integer  yang  layak  dari  ruang pemecahan. Mengingat kesuitan ini, para peneliti telah mengembangkan sebuah prosedur pemecahan  yang  didasari  oleh  pemanfaatan  keberhasilan  besar  dalam  memecahkan masalah LP. Strategi untuk prosedur ini dapat diringkaskan dalam tiga langkah:
1. Melonggarkan  ruang  pemecahan  dari  masalah  integer  yang  bersangkutan  dengan mengabaikan  batasan  integer  sama  sekali.  Langkah  ini  mengonversikan  dari ILP menjadi LP.
2. Memecahkan  model  LP  yang  longgar  yang  dihasilkan  dan  mengidentifikasi  titik optimum dari LP itu.
3. Dengan  dimulai  dari  titik  optimum  kontinyu,  menambahkan  batasan  khusus  yang akan  secara  berulang-ulang  memaksa  titik  ekstrim  optimum  dari  model  LP  yang dihasilkan untuk bergerak ke suatu batasan integer yang diinginkan (Taha, 1993:325).
Metode Branch and Bound memiliki 2 komponen utama, yaitu:
1. Branching,  jika  pendekatan  pertama  variabelnya  bukan  sebuah  bilangan  bulat  sebut saja ! " , maka # $ < ! " < # % dimana # $ dan # % adalah bilangan bulat tak negatif. Dua program bilangan bulat yang baru menambah ILP yang lama dengan kendala ! & # $ atau dengan kendala ! ' # % . Proses ini dikatakan branching.
2. Bounding,  mengasumsikan  bahwa  fungsi  tujuannya  adalah  kasus  memaksimumkan. Branching  dilanjutkan  sampai  menemukan  solusi  untuk  pendekatan  pertama.  Nilai fungsi tujuan untuk pendekatan pertama adalah lower bound untuk masalah tersebut dan semua program hasil percabangan yang variabelnya bulat atau tidak, nilai fungsi tujuannya  pasti  lebih  kecil  daripada lower  bound .  Jika  dalam  prosesnya  fungsi tujuannya lebih besar daripada lower bound maka nilai fungsi tujuan tersebut menjadi lower  bound yang  baru.  Maka lower  bound yang  lama  diganti  dengan lower  bound yang baru.
Jika fungsi objektif adalah  kasus meminimumkan prosedurnya  hampir  sama  tapi bukan  lagi lower  bound yang  digunakan  melainkan upper  bound .  Nilai  fungsi  tujuan untuk pendekatan pertama adalah upper bound dan sub problem dieliminasi apabila nilai fungsi tujuannya lebih besar daripada upper bound dalam Bronson (1996) Misalkan  diperoleh  titik  optimum  A.  Maka  metode  ini  didasarkan  pada  konsep bilangan  bulat  terbesar ()* dimana ) + , - .  Maka  metode  ini  menguji ()* yang  lebih kecil  dari  titik  optimum  dan  bilangan  bulat ()* . 1 . Sehingga  daerah  antara ()* < ) < ()* . 1 dihilangkan  akibatnya  sistem  terbagi  menjadi  2  daerah.  Hal  inilah  yang mengakibatkan terjadinya percabangan ( Branching ).

## 2. METODE PENELITIAN

## 2.1 Tahapan Penelitan
Adapun  tahapan-tahapan  yang  dilakukan  dalam  penelitian  ini  adalah  sebagai berikut :
Tabel 1 Tahapan Penelitian No. Tahapan Penelitian Keterangan 1 Mengumpulkan data Pengumpulan  data  dilakukan  dengan wawancara  langsung  dengan  pemilik Sipatuo Aluminium 2 Menyusun model matematika Setelah mengumpulkan data, akan dilakukan pendefinisian variabel, dilanjutkan  dengan  penyusunan  fungsi optimasi  atau  fungsi  tujuan  dan  fungsi kendala 3 Menyelesaikan masalah Menyelesaikan  masalah  optimasi  dengan fungsi  kendala  yang  ada,  sehingga diperoleh hasil yang optimal.

## 2.2 Lokasi Penelitian
Penelitian  akan  dilakukan  di  Sipatuo  Aluminium  yang  ada  di  lingkungan Kampung  Baru,  Kelurahan  Labuang  Utara,  Kecamatan  Banggae  Timur,  Kabupaten Majene.

## 2.3 Peubah yang diamati/ diukur
Peubah yang akan diamati/ diukur adalah bahan-bahan dan biaya yang digunakan untuk  pembuatan  berbagai  model  lemari  aluminium.  Semua  variabel  yang  berpengaruh terhadap biaya pembuatan lemari akan digunakan pada saat membuat model matematika dan menghasilkan solusi optimum.

## 2.4 Teknik Pengumpulan dan Analisis Data
Dilakukan wawancara langsung kepada pemilik usaha Sipatuo Aluminium. Data yang  diperoleh  akan  diterjemahkan  dalam  model  matematika  dan  ditentukan  nilai optimumnya.

## 2.5 Metode Branch and Bound
Langkah-langkah  menyelesaikan  masalah  meminimumkan  kasus integer murni adalah sebagai berikut: Menyelesaikan  kasus ILP dengan  menganggap  kasus  tersebut  seperti  kasus LP. Dalam menentukan solusi LP sebaiknya menggunakan metode simpleks.
1. Apabila  solusi  optimal  telah  diperoleh  dan  semua  variabelnya  bilangan  bulat,  maka solusi LP tersebut menjadi solusi optimal ILP. Tetapi apabila sebagian atau semua variabel  bukan  bilangan  bulat,  maka  dipilih  salah  satu  variabel  untuk  dilakukan percabangan ( Branching) sehingga diperoleh 2 submasalah ILP.
2. Menyelesaikan  kedua  masalah  tersebut  seperti  langkah  pertama  dan  menentukan Lower  Bound  (Bounding).Lower  Bound adalah  solusi  submasalah  yang  memiliki nilai terendah.
3. Apabila  submasalah  yang  solusinya  menjadi Lower  Bound belum  memenuhi  syarat integer ,  maka  kita  melakukan  proses  proses  percabangan  dan  menyelesaikan submasalah tersebut seperti langkah ketiga.

## 2.6 LINDO
LINDO  adalah  salah  satu  program  riset  operasi  yang  dapat  digunakan  untuk menyelesaikan  berbagai  masalah  riset  operasi.  Kelebihan  program  ini  adalah  cukup mudah  digunakan  meskipun  kasusnya  cukup  besar.  Selain  itu,  tampilannya  yang  baik dibandingkan  dengan  program  lainnya.  Oleh  sebab  itu,  peneliti  akan  menggunakan program  LINDO  dalam  menyelesaikan  masalah  meminimumkan  biaya  produksi  pada Sipatuo Aluminium. Selanjutnya produk tersebut didefinisikan dalam variabel:
X 1 = Lemari pakaian X 2 = Lemari tempat piring X 3 = Lemari sepatu X 4 = Lemari jualan X 5 = Lemari P3K Selanjutnya, diperoleh fungsi tujuan: Meminimumkan: 2.829.000 X 1 + 3.104.000 X 2 + 1.230.000 X 3 + 1.399.500 X 4 + 266.250 X 5 Dengan fungsi kendala sebagai berikut: 3X 1 + 3X 2 + 2X 3 + 2X 4 + 0,5X 5 ' 75 3X 1 + 6X 2 + 2X 3 ' 60
1,5X 1 + 2X 2 + 0,4X 3 ' 25
X 1 + X 2 + 0,4X 3 + 1,2X 5 ' 50
5X 1 + 5X 2 + 2X 3 + 3X 4 ' 70 120X 1 + 120X 2 + 1X 3 + 2X 4 + X 5 ' 300 4X 1 + 5X 2 + 2X 3 +4X 4 ' 70 X 1 + 2X 2 + 0,3X 3 + 0,3X 4 + 0,15X 5 ' 20
3X 1 + 3X 2 + 1,5X 3 + 0,5X 5 ' 65
X 1 + X 2 + 0,25X 5 ' 15
6X 1 + 6X 2 + 2X 3 + 0,5X 5 ' 75
3X 1 + 6X 2 + 2X 3 + X 5 ' 70 3X 1 + 6X 2 + 2X 3 + X 4 + X 5 ' 80 30X 1 + 30X 2 + 25X 3 + 25X 4 + 15X 5 ' 180 25X 1 + 25X 2 + 20X 3 + 20X 4 + 10X 5 ' 170 X 1 + X 2 + 0,75X 3 + 0,5X 4 + 0,3X 5 ' 50 0,5X 1 + 0,5X 2 + 0,75X 3 + 0,75X 4 + 0,75X 5 ' 20 4,5X 1 + 4,5X 2 + 1,5X 3 + 4,5X 4 + 0,5X 5 ' 75 4X 1 + 4X 2 + 4X 3 + 6X 4 ' 80
5X 1 + 5X 2 + 2X 3 + 5X 4 ' 75 6X 1 + 6X 2 + 3X 3 ' 65 4X 4 + 2X 5 ' 40 3X 2 ' 10
25X 2 ' 45
X 1 , X 2 , X 3, X 4 , dan X 5 ' 0

## 4. HASIL DAN PEMBAHASAN
Diperoleh output sebagai berikut dengan menggunakan program LINDO
Dari output di atas, diperoleh solusi optimum X 1 = 2, X 2 = 8, X 3 = 15, X 4 = 0, dan X 5 =  30.  Artinya  untuk  meminimalkan  biaya  produksi  pada  Sipatuo  Aluminium  maka sebaiknya  memproduksi  lemari  pakaian  sebanyak  2,  lemari  tempat  piring  sebanyak  8, lemari  sepatu  sebanyak  15,  lemari  P3K  sebanyak  30,  dan  tidak  memproduksi  lemari jualan. Dengan solusi tersebut diperoleh biaya minimum sebesar Rp 56.927.500,-.

## 4. KESIMPULAN
Metode Branch  and  Bound adalah  metode  yang  dapat  digunakan  untuk menyelesaikan masalah ILP yang mengharuskan seluruh variabelnya merupakan bilangan bulat.  Adapun  langkah-langkah  menyelesaikan  masalah  meminimumkan  kasus integer murni adalah sebagai berikut:
1. Menyelesaikan  kasus ILP dengan  menganggap  kasus  tersebut  seperti  kasus LP. Dalam menentukan solusi LP sebaiknya menggunakan metode simpleks.
2. Apabila  solusi  optimal  telah  diperoleh  dan  semua  variabelnya  bilangan  bulat,  maka solusi LP tersebut menjadi solusi optimal ILP. Tetapi apabila sebagian atau semua variabel  bukan  bilangan  bulat,  maka  dipilih  salah  satu  variabel  untuk  dilakukan percabangan ( Branching) sehingga diperoleh 2 submasalah ILP.
3. Menyelesaikan  kedua  masalah  tersebut  seperti  langkah  pertama  dan  menentukan Lower  Bound  (Bounding).Lower  Bound adalah  solusi  submasalah  yang  memiliki nilai terendah.
4. Apabila  submasalah  yang  solusinya  menjadi Lower  Bound belum  memenuhi  syarat integer ,  maka  kita  melakukan  proses  proses  percabangan  dan  menyelesaikan submasalah tersebut seperti langkah ketiga.
Berdasakan  hasil  penelitian,  diperoleh  bahwa  untuk  meminimumkan  biaya produksi Sipatuo Aluminium, maka sebaiknya memproduksi lemari pakaian sebanyak 2, lemari  tempat  piring  sebanyak  8,  lemari  sepatu  sebanyak  15,  lemari  P3K  sebanyak  30, dan tidak memproduksi lemari jualan.
DAFTAR PUSTAKA
A.K.  Ojha  dan  Rashmi  Ranjan  Ota.  2014.  Multi-objective  geometric  programming problem  with  Karush-Kuhn-Tucker  condition  using  Iu-constraint  method. RAIRO  - Operations Research . 48(4):429-453.
Kementerian  Pendidikan  dan  Kebudayaan.  (2014) Matematika :  MA/MA/SMK/MAK Kelas  XI  Semester  1.  Edisi  Revisi.  Jakarta:  Kementerian  Pendidikan  dan Kebudayaan,
Luenberger,  D.G.  and  Yinyu  Ye.  2008. Linear  and  Nonlinear  Programming .  Springer, USA. Susanta B. 1994. Program Linear. Yogyakarta. Taha,  Hamdy  A.  2007. Operations Research:  An  Introduction  Eighth  Edition .  Prentice- Hall International Inc, New Jersey.