## FARABI Jurnal Matematika dan Pendidikan Matematika
Penerapan Metode Cutting Plane dalam Meminimumkan Biaya Pakan Ikan (Studi Kasus: Dinas Kelautan dan Perikanan Provinsi Sumatera Utara)
Rahman Pratama Hasibuan 1 , Rosman Siregar 2
1,2 Prodi Matematika, FMIPA, Universitas Sumatera Utara, Medan-Indonesia 20155 Email: 1 rahmanhsb98@gmail.com, 2 rosmansiregar@yahoo.com

## ABSTRAK
Dinas  Perikanan  dan  Kelautan  Provinsi  Sumatera  Utara  memproduksi  benih  ikan  sebanyak  tiga jenis  yang  diberi  pakan  dengan  lima  jenis  pakan  yaitu  S99,  Fengli,  CP  781,  MS  Preo  dan  Prima Feed  LP.  Dinas  Perikanan  Dan  Kelautan  juga  belum  pernah  menentukan  jumlah  yang  dipasok untuk  memproduksi  benih  ikan  sehingga  harus  mengeluarkan  biaya  yang  lebih  besar.  Agar perusahaan  dapat  memproduksi  pakan  ikan  dengan  biaya  serendah  mungkin,  maka  solusi  dari permasalahan  tersebut  akan  diterapkan  dengan  menggunakan  model  program  linier  dan penyelesaiannya  dengan  metode Cutting  Plane .  Metode  ini  diselesaikan  terlebih  dahulu  dengan metode  simpleks,  apabila  terdapat  variabel  basis  yang  memiliki  nilai  pecahan,  kendala  Gomory akan ditambahkan. Untuk menyelesaikan permasalahan tersebut dengan menggunakan metode dual simpleks sampai tidak ada lagi variabel basis dengan nilai pecahan. Berdasarkan hasil perhitungan,
diperoleh biaya yang optimal adalah sebesar Rp. 12.152.000 perbulan .
Kata kunci: Metode Cutting Plane , Optimasi Produksi, Program Linear

## ABSTRACT
The Department of Fisheries and Marine Affairs of North Sumatra Province produced three types of  fish  seeds  which  were  fed  with  five  types  of  feed,  namely  S99,  Fengli,  CP  781,  MS  Preo  and Prima  Feed  LP.  The  Department  of  Fisheries  and  Marine  Affairs  has  also  never  determined  the amount to be supplied to produce fish seeds, so they have to incur a higher cost. In order for  the company  to  produce  fish  feed  at  the  lowest  possible  cost,  the  solution  to  this  problem  will  be applied using a linear programming model and the solution using the cutting plane method. This method is solved first by the simplex method, if there is a base variable that has a fractional value, the Gomory constraint will be added. To solve this problem by using the dual simplex method until there  are  no  more  basic  variables  with  fractional  values.  Based  on  the  calculation  results,  the optimal cost is Rp. 12,152,000 per month.
Keywords: Cutting Plane Method, Fish Feed, Linear Programming

## A. Pendahuluan
Pada  dasarnya,setiap  perusahaan  atau lembaga selalu berusaha untuk mengoptimalkan setiap  biaya  yang  dikeluarkan  guna  mencukupi segala  kebutuhan,  sehingga  perusahaan  dapat terus  beroperasi  dan  berkembang.  Salah  satu cara  agar  memperoleh  biaya  optimal  yang dikeluarkan  setiap  perusahaan  adalah  dengan mengurangi  biaya  pada  persediaan  ( Freddy Rangkuti, 1995).
Dinas Kelautan Dan
Perikanan Sumatera  Utara  merupakan  Instansi  yang
bergerak  dalam  menyelenggarakan  pekerjaan pemerintah  daerah  berdasarkan  asas  otonomi dan  lembaga  pembantu,  termasuk  di  bidang perikanan.  Kekurangan  persediaan  pakan  ikan pada  Instansi  ini  terjadi  karena  banyaknya Instansi  atau  perusahaan  yang  sama-sama bergerak  dibidang  budidaya  ikan,  sehingga permintaan  bahan  baku  oleh  Instansi  tidak selalu  terpenuhi  sesuai  dengan  kebutuhan perusahaan. Ketersediaan  pakan  memiliki dampak  yang  signifikan  terhadap  pertumbuhan dan kelangsungan hidup ikan. Jumlah  makanan yang  dibutuhkan  ikan  setiap  hari  berkaitan  erat
dengan  ukuran  berat,  dan  umurnya.  Tetapi persentase  jumlah  pakan  yang  dibutuhkan semakin  berkurang  dengan  bertambahnya ukuran dan umur ikan (Djarijah, 1996).
Ada banyak metode
untuk
mengoptimalkan  biaya,  metode Cutting  Plane adalah  salah  satunya.  Menurut  Sauddin  et  al. (2015)  Metode Cutting  Plane dapat  digunakan untuk mencari solusi optimal pada pemrograman  bilangan  bulat. Metode  ini diimplementasikan dengan menambahkan kendala yang disebut kendala gomory. Kendala gomory  dapat  dilakukan  penambahan  pada tabel optimasi untuk mempersingkat perhitungan (Siagian, 2006).
Yuhendra  (2013)  meneliti  Pendekatan Branch  and  Bound dan  Metode Cutting  Plane untuk  mengoptimalkan  kombinasi  produk  dan menjelaskan  bahwa  Metode Cutting  Plane
memberikan hasil yang paling besar dibandingkan metode Branch and Bound ketika mengubah  harga  produk  selama  perencanaan produksi.  Untuk  perhitungan  manual,  metode Cutting  Plane memerlukan  waktu  yang  lebih efisien  dibandingkan  dengan  metode Branch and Bound. Hal ini dikarenakan metode Cutting Plane hanya berfokus pada solusi yang pecahan saja,  sedangkan  metode Branch  and  Bound masih harus  melakukan  pencabangkan  yang bernilai pecahan ke dalam dua sub permasalahan baru.
Berdasarkan latar belakang tersebut maka dalam  penelitian  ini,  penulis  tertarik  untuk melakukan penelitian terhadap sistem persediaan  pada  Dinas  Kelautan  dan  Perikanan Sumatera Utarayang merupakan sebuah Instansi yang  berlokasi  di  kota  Medan  supaya memperoleh  biaya  optimal dalam  persediaan bahan baku pakan ikan.
1. Operasi Riset Menurut Aminuddin (2005)
Permasalahan  kompleks  yang  muncul  dalam kehidupan sehari-hari dapat dipecahkan dengan operasi riset ( research operation ). Operasi riset memiliki  lima  fase  dalam  yaitu  perumusan masalah, membentuk model matematis, pencarian  solusi,  pengujian  model  (validasi), dan pemgambilan keputusan.
Research  operation ditujukan  untuk menetapkan  metode  ilmiah  untuk  sistem  yang menggabungkan  ukuran  faktor  seperti  peluang dan risiko untuk memprediksi dan
membandingkan  hasil dari  berbagai  keputusan, strategi  atau  kebijakan.  Semua  biaya  terkait kualitas  dipengaruhi  oleh  desain  produk  atau cara prodik yang diproduksi (Supranto, 1980).

## 2. Program Linear
Program  linier  adalah  teknik  solusi optimal  untuk  masalah  keputusan  dengan terlebih  dahulu  menentukan  fungsi  tujuan (maksimum  atau  minimum)  dan  kendala  yang ada  dalam  model  matematika  persamaan  linier (Parlin  Sitorus,  1997). Model  persamaan umum  dalam  pemrograman  linier  sebagai berikut:
Z = ∑ 𝐶 𝑗 𝑛 𝑗=1 𝑋 𝑗 (1)
Dengan kendala:
∑ 𝑎𝑖 𝑗 𝑛 𝑗=1 𝑋 𝑗 (≤, =, ≥) 𝑏 𝑗 (2) 𝑥 𝑗 ≥ 0 untuk i = 1, 2, 3, …, n untuk j = 1, 2, 3, …, n
Menurut  Mulyono  (2004),  setelah masalah diidentifikasikan dan tujuan ditetapkan, langkah selanjutnya adalah perumusan model matematika yang meliputi:
a. Menyatakan  simbol  matematika  dengan menentukan  variabel  yang  tidak  diketahui (variabel keputusan).
b. Membentuk  fungsi  tujuan  yang  dinyatakan sebagai  suatu  hubungan  linier  (bukan perkalian) dari variabel keputusan
c. Identifikasi  semua  kendala  masalah  tersebut dan  nyatakan  dalam  persamaan atau pertidaksamaan yang juga merupakan hubungan  linier  dari  variabel  keputusan yang mencerminkan keterbatasan.

## 3. Metode Cutting Plane
Menurut  Nico  et  al.  (2014) Metode Cutting  Plane adalah  solusi  yang  dapat menyelesaikan  pemrograman  linier  dalam bentuk  bilangan  bulat,  baik  asli  maupun campuran,  dengan  penambahan  gomory  atau disebut dengan kendala baru. Jika nilai variabel keputusan tidak konsisten (nilai pecahan) maka dilakukan penambahan gomory.
Kendala ini secara efektif akan menghapus  beberapa  ruang  solusi  yang  tidak mengandung  titik  integer  yang  layak,  tetapi tidak akan pernah menghapus titik integer yang mungkin  dari  program  ( Bu’ulӧlӧ,  2016) . Langkah-langkah  metode Cutting  Plane (Taha, 1996):
a. Memecahkan  masalah  pemrograman  linier dengan  metode  simpleks  tanpa  melihat kondisi bilangan bulat
b. Memverifikasi  hasil  optimal.  Jika  nilai integer  dimiliki  variabel  basis,  maka  solusi optimal  adalah  integer  dan  solusi  selesai.
diperoleh  dan  solusi  selesai.  Apabila  basis masih  mepunyai  nilai  interupsi,  lanjutkan langkah.
c. Untuk  memverifikasi  solusi  optimal  pada masalah  pemrograman  linier,  perhatikan tabel dibawah ini
Tabel 1. Optimasi Masalah Program Linear 𝐶 𝑖 𝑉 𝐵 𝑍 𝑗 𝐶 1 𝐶 2 … 𝐶 𝑚 0 … 0 … 0 𝑏 𝑖 𝑥 1 𝑥 2 … 𝑥 𝑚 𝑌 1 … 𝑌 𝑗 … 𝑌 𝑛 𝐶 1 𝑋 1 𝑏 1 1 0 … 0 𝑎 11 … 𝑎 1𝑗 … 𝑎 1𝑛 𝐶 2 𝑋 2 𝑏 2 0 1 … 0 𝑎 21 … 𝑎 2𝑗 … 𝑎 2𝑛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 𝐶 𝑚 𝑋 𝑚 𝑏 𝑚 0 0 … 1 𝑎 𝑚1 … 𝑎 𝑚2 … 𝑎 𝑚𝑛
𝐶 𝑗 𝑍 𝐶 1 𝐶 2 … 𝐶 𝑛 𝐶 1 ̅̅̅ … 𝐶 𝑗 ̅ … 𝐶 𝑛 ̅̅̅
𝐶 𝑗 − 𝑍 𝑗 0 0 … 0 𝐶 1 ̅̅̅ … 𝐶 𝑗 ̅ … 𝐶 𝑛 ̅̅̅
Asumsikan  variabel 𝑥 𝑖 mewakili  variabel  basis dan  variabel  non-basis  yaitu 𝑦 𝑗 .  Variabel- variabel  ini  didefinisikan  seperti  itu  untuk kemudahan.
d. Pada  langkah  ini,  sebuah  irisan  gomory terbentuk,  yang  digunakan  sebagai  batas baru.  Asumsikan  persamaan  ke- i di  mana variabel basis 𝑥 𝑖 memiliki nilai noninteger .
𝒙 𝒊 = 𝒃 𝒊 − ∑ 𝒂 𝒊𝒋 𝒚 𝒋 𝒏 𝒋=𝟏 , 𝒃 𝒊 tidak  integer  (baris sumber)
(3)
Kemudian  pisahkan 𝒃 𝒊 dan 𝒂𝒊 𝒋 menjadi  bagian yang bulat dan bagian pecah non negatif seperti berikut :
𝑏 𝑖 = 𝑏 𝑖 + 𝑓 𝑖 𝑎 𝑖𝑗 = 𝑎 𝑖𝑗 + 𝑓 𝑖𝑗 𝒔 𝒈 − ∑ 𝒂 𝒊𝒋 𝒚 𝒋 𝒏 𝒋=𝟏 = −𝒇 𝒊 (4)
dimana: 𝑠 𝑔 adalah variable slack non-negatif 𝑓 𝑖 adalah  bagian  pecahan  tak  negatif 𝑎 𝑖𝑗 adalah  koefisien  dari  fungsi kendala pada model matematika
𝑏 𝑖 adalah  konstanta  di  ruas  kanan setiap  kendala 𝒚 𝒋 adalah variabel bukan basis
e. Penambahan dari l Persamaan irisan gomory dibentuk  pada  langkah  2  sampai  ke  baris terakhir dari tabel dimana 𝒔 𝒈 adalah variabel slack  non-negatif  menjadi  variabel  basis seperti  pada  persamaan  pada  langkah  2. Persamaan (4)  adalah  irisan  gomory diperlukan  dan  mewakili  persyaratan  untuk 𝒙 𝒊 menjadi  bilangan  bulat.  Pada  tabel tersebut, nilai 𝒚 𝒋 =0 dan 𝒔 𝒊 = −𝛃 𝒊 adalah tidak layak,  jadi  irisan  ini  dapat  disimpulkan bahwa  memiliki  nilai  tidak  layak.  Oleh karena itu, metode dual simpleks digunakan untuk  kekurangan  ini.  Di  tabel  2,  tabel  baru akan  ditampilkan  setelah  menambahkan potongan Gomory.
Tabel 2. Setelah Penambahan Potongan Gomory
𝐶 𝑖 𝑉 𝐵 𝑍 𝑗 𝐶 1 𝐶 2 … 𝐶 𝑚 0 … 0 … 0 𝑏 𝑖 𝑥 1 𝑥 2 … 𝑥 𝑚 𝑌 1 … 𝑌 𝑗 … 𝑌 𝑛
𝐶 1 𝑋 1 𝑏 1 1 0 … 0 𝑎 11 … 𝑎 1𝑗 … 𝑎 1𝑛 𝐶 2 𝑋 2 𝑏 2 0 1 … 0 𝑎 21 … 𝑎 2𝑗 … 𝑎 2𝑛
𝐶 𝑖 𝑉 𝐵 𝑍 𝑗 𝐶 1 𝐶 2 … 𝐶 𝑚 0 … 0 … 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 𝐶 𝑚 𝑋 𝑚 𝑏 𝑚 0 0 … 1 𝑎 𝑚1 … 𝑎 𝑚2 … 𝑎 𝑚𝑛 0 𝑠 𝑔𝑖 −β i 0 0 … 0 −𝑎 𝑖1 … −𝑎 𝑖𝑗 … −𝑎 𝑖𝑛
𝐶 𝑗 𝑍 𝐶 1 𝐶 2 … 𝐶 𝑛 𝐶 1 ̅̅̅ … 𝐶 𝑗 ̅ … 𝐶 𝑛 ̅̅̅ 𝐶 𝑗 − 𝑍 𝑗 0 0 … 0 𝐶 1 ̅̅̅ … 𝐶 𝑗 ̅ … 𝐶 𝑛 ̅̅̅
f. Untuk  mendapatkan  solusi  optimal  baru maka  metode  dual  simpleks  yang  akan digunakan.  Apabila  akhir  dari  metode  dual simpleks  adalah  bilangan  bulat,  maka perhitungan  selesai.  Apabila  perhitungan bukan  bilangan  bulat  maka  selanjutnya adalah  mendefinisikan  kembali  dari  tabel langkah  4  dengan  membentuk  persamaan kendala  gomory  dan  menyelesaikannya dengan  metode  dual  simpleks.  Selanjutnya diulangi  sampai  diperoleh  solusi  bilangan bulat.
g. Nilai  Z  optimal  dan  variabel  keputusan bilangan bulat diperoleh pada  kolom 𝒁 𝒋 dan 𝒃 𝒊 .

## B.  Metode Penelitian
Langkah  yang  dilakukan  pertama  kali dalam  penelitian  ini  berupa  studi  literatur
dengan mencari referensi teori dari buku, jurnal, artikel penelitian terdahulu yang relevan dengan kasus  atau  permasalahan  mengenai  program linear,  program  integer  dengan  menggunakan metode Cutting Plane .

## C.  Hasil dan Pembahasan

## 1. Analisis Data
Data  pada  penelitian  ini  menggunakan data  primer,  yaitu  data  yang  dikumpulkan  oleh penulis  langsung  dari  Dinas  Kelautan  dan Perikanan  Sumatera  Utara  melalui  wawancara dengan  instansi  tersebut.  Data  yang  digunakan pada  pembahasan  ini  meliputi  jenis  ikan  yang dibudidayakan,  bahan  pakan  ikan,  harga  bahan baku,  jumlah  persediaan  dan  total  biaya penyimpanan  bahan  pakan  ikan.  Berikut  tabel jenis dan kebutuhan kandungan pakan ikan :

## Tabel 3. Jenis dan Kandungan Pakan Ikan
No Jenis Pakan ikan Kandungan pakan Ikan (Karung) Harga/Karung Kadar Protein Kadar Lemak Kadar Serat Kadar Abu Kadar Air Kadar Karbo- hidrat 1 S99 0,29 0,05 0,06 0,13 0,11 0,36 Rp.268.000 2 Fengli 0,40 0,05 0,03 0,16 0,11 0,25 Rp.555.000 3 CP 781 0,32 0,05 0,05 0,13 0,12 0,33 Rp.280.000 4 MS Preo 0,32 0,04 0,06 0,13 0,10 0,35 Rp.290.000 5 Prima Feed LP 0,33 0,05 0,04 0,12 0,10 0,36 Rp.305.000 Kebutuhan (Karung) 13,65 2,08 1,95 5,72 4,55 14,17

## 2.  Model Matematika
Terdapat langkah-langkah  dalam  metode
Cutting  Plane dalam  menyelesaikan  masalah
sebagai berikut: a. Analisis  permasalahan  linear  yang  terdapat pada Dinas Kelautan dan Perikanan
Sumatera Utara
b. Tentukan  fungsi  tujuan  yang  akan  dicapai dan fungsi kendala yang akan terjadi
c. Buat fungsi tujuan dan fungsi kendala dalam model matematika
d. Ubah  persamaan  dan  kendala,  pada  setiap kendala  lakukan  pengubahan  pembatas  "≥" menjadi  "≤"  dengan  mengalikan  -1  dan menambahkan  variabel  slack  (S),  kemudian diubah  menjadi  “=”  dengan  menambahkan variabel artificial(R) seperti berikut:
Minimumkan:
𝑍 = 268.000 𝑥 1 + 555.000 𝑥 2 + 280.000 𝑥 3 + 290.000 𝑥 4 + 305.000 𝑥 5 + 0 𝑆 1 +  0𝑆 2 + 0𝑆 3 + + 0𝑆 4 +  0𝑆 5 +  M𝑟 1 + M𝑟 2 +  M𝑟 3 + M𝑟 4 +  M𝑟 5 (5)
Dengan Kendala: 0,29 𝑥 1,1 +  0,40 𝑥 1,2 +  0,32 𝑥 1,3 +  0,32 𝑥 1,4 + 0,33 𝑥 1,5 - 𝑆 1 + 𝑀𝑟 1 = 13,65 0,05 𝑥 2,1 +  0,05 𝑥 2,2 +  0,05 𝑥 2,3 +  0,04 𝑥 2,4 + 0,05 𝑥 2,5 - 𝑆 2 + 𝑀𝑟 2 = 2,08 0,06 𝑥 3,1 +  0,03 𝑥 3,2 +  0,05 𝑥 3,3 +  0,06 𝑥 3,4 + 0,04 𝑥 3,5 - 𝑆 3 + 𝑀𝑟 3 = 1,95 0,13 𝑥 4,1 +  0,16 𝑥 4,2 +  0,13 𝑥 4,3 +  0,13 𝑥 4,4 + 0,12 𝑥 4,5 - 𝑆 4 + 𝑀𝑟 4 = 5,72
0,11 𝑥 5,1 +  0,11 𝑥 5,2 +  0,12 𝑥 5,3 +  0,10 𝑥 5,4 + 0,10 𝑥 5,5 - 𝑆 5 + 𝑀𝑟 5 = 4,55 0,36 𝑥 6,1 +  0,25 𝑥 6,2 +  0,33 𝑥 6,3 +  0,35 𝑥 6,4 + 0,36 𝑥 6,5 - 𝑆 6 + 𝑀𝑟 6 = 14,17 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 , 𝑥 5 , , 𝑆 1 , 𝑆 2 , 𝑆 3 , 𝑆 4 , 𝑆 5 , 𝑟 1 , 𝑟 2 , 𝑟 3 , 𝑟 4 , 𝑟 5 ≥ 0
e. Masukkan  data  fungsi  tujuan  dan  fungsi kendala kedalam tabel awal simpleks.
f. Masukkan  nilai  dari  tiap  variabel  kedalam tabel awal simpleks
Dari  solusi  yang  didapat,  jumlah  pakan ikan yang harus disediakan Dinas Kelautan dan Perikanan  Sumut  setiap  bulannya  adalah 14,33 karung  S99  ( 𝑥 1 ),  0  karung  Fengli  ( 𝑥 2 ) ,29,67 karung  CP  781( 𝑥 3 ),  0  karung  MS  Preo  ( 𝑥 4 ) , dan 0 karung Prima Feed LP ( 𝑥 5 ) dengan biaya minimum Rp.12.148.000. Karena solusi optimal  dari  tabel  simpleks  memiliki  nilai bukan  bilangan  bulat,  maka  dapat  diselesaikan dengan  metode Cutting  Plane sehingga  solusi optimalnya  adalah  nilai  bilangan  bulat.  Solusi ini  tidak  valid  karena  terdapat  nilai  pecahan pada variabel basis, sehingga dilakukan langkah selanjutnya yaitu menambahkan gomory .
Tabel 4. Setelah Penambahan Gomory
𝐶 𝑖 𝑉 𝑏 𝑍 𝑗 268 000 555 000 280 000 290 000 305 000 0 0 0 0 0 0 0 𝑏 𝑖 𝑥 1 𝑥 2 𝑥 3 𝑥 4 𝑥 5 𝑆 1 𝑆 2 𝑆 3 𝑆 4 𝑆 5 𝑆 6 𝑆 𝑔1 280 000 𝑥 3 30 0 1,66 1 1 2,47 0 0 0 75,5 4 0 0 -0,49 0 𝑆 5 0,92 0 0,26 0 0,02  0,41 0 0 0 0,08 1 0 -0,49 268 000 𝑥 1 14 1 - 0,43 0 0 - 1,54 0 0 0 - 82,2 3 0 0 0,49 0 𝑆 2 0,12 0 0,01 0 0,01 0 0 1 0 - 0,39 0 0 0 0 𝑆 6 1,78 0 0,81 0 - 0,02 1,10 0 0 0 - 4,46 0 1 -1,49 0 𝑆 3 0,06 0 - 0,19 0 - 0,01 - 0,40 0 0 1 1,39 0 0 0,49 0 𝑆 𝑔1 1 0 0,66 0 0 1,19 1 0 0 0,54 0 0 -1,49 𝐶 𝑗 1215 2000 268 000 349 520, 60 280 000 280 000 278 928, 36 0 0 0 - 116 647 2,24 0 0 - 5910,4 5
𝑍 𝑗 − 𝐶 𝑗 0 205 479, 40 0 100 00 260 71,6 4 0 0 0 116 647 2,24 0 0 5910,4 5
Dari  hasil  penelitian  diperoleh  data seperti  pada  Tabel  4.  Data  yang  diperoleh  dari Dinas  Kelautan  dan  Perikanan.  Sumatera  Utara akan diselesaikan dengan menggunakan metode
Cutting  Plane untuk  mendapatkan  feed  cost yang  minimum.  Pemecahan  kasus  seluruh program  ini  dimulai  dengan  penggunaan metode  simpleks. Dengan  metode  simpleks,
diperoleh  jenis  pakan  ikan  S99  ( 𝑥 1 )  14,33 karung,  Fengli  ( 𝑥 2 )  0  karung,  CP  781  ( 𝑥 3 ) 29,67 karung, MS Preo( 𝑥 4 ) 0 karung, dan Prima Feed  LP  ( 𝑥 5 )  0  karung.  Karena  hasil  metode simpleks selalu bernilai pecahan, maka penyelesaian dilanjutkan dengan metode Cutting  Plane dengan  menambahkan  potongan gomory 𝑆 𝑔1 − 0,44𝑥 2 − 0,8𝑥 5 − 0,67𝑆 1 − 0,36𝑆 4 = −0,67 . Kemudian dilanjutkan dengan  metode  dual  simpleks  karena  nilai 𝑆 𝑔1 bernilai  negatif.  Setelah  menggunakan metode Cutting  Plane ,  diperoleh  jenis  pakan ikan  S99  ( 𝑥 1 )  14karung,  Fengli( 𝑥 2 )  0  karung, CP 781 ( 𝑥 3 ) 30 karung, MS Preo( 𝑥 4 ) 0 karung, dan Prima Feed LP ( 𝑥 5 ) 0 karung, dengan biaya minimum  sebesar  Rp.12.152.000  perbulan. Dengan  komposisi  tersebut,  diperoleh  kadar protein  sebanyak  409,8  kg,  kadar  lemak sebanyak  66  kg,  kadar  serat  sebanyak  70,2  kg, kadar  abu  sebanyak  171,6  kg,  kadar  air sebanyak  154,2  kg,  dan  kadar  karbohidrat sebanyak 425,7 kg. Dengan hasil tersebut maka kebutuhan  kandungan  pakan  untuk  masing- masing  Dinas  Kelautan  dan  Perikanan  Provinsi Sumatera  Utara  terpenuhi,  bila  kebutuhan  akan kandungan  protein  sebanyak 409,5  kg,  kadar lemak  sebanyak  62,4  kg,  kadar  serat  sebanyak 58,5 kg, kadar abu sebanyak 171,6 kg, kadar air sebanyak  136,5  kg,  dan  kadar  karbohidrat sebanyak 425,1 kg.

## D.  Kesimpulan dan Saran
1.  Kesimpulan:
Berdasarkan pembahasan tugas akhir  ini, terdapat  tiga  jenis  ikan  yang  dibudidayakan oleh  Dinas  Kelautan  dan  Perikanan  Sumatera Utara  yaitu  Ikan Mas,  Ikan Nila dan  Ikan Lele. Kemudian  menyediakan  dua  jenis  pakan  ikan yaitu jenis pakan ikan S99 (𝑥 1 ) dan jenis pakan ikan  CP  781 (𝑥 3 ) dalam  periode  setiap  satu bulan  dan  meminimalkan  biaya  pengeluaran dengan cara membuat model masalah ke dalam bentuk  program  linier  kemudian  diselesaikan dengan metode Cutting Plane . Kesimpulan dari penelitian ini adalah sebagai berikut:
a. Dinas  Perikanan  dan  Kelautan  Sumut menyediakan 14 karung pakan ikan S99
(𝑥 1 ) per bulan.
b. Dinas  Kelautan  dan  Perikanan  Sumut harus  menyediakan  30  Cover  CP 781 (𝑥 3 ) c. Dinas kelautan dan Perikanan Sumatera Utara harus menyediakan biaya
minimum sebesar Rp.12.152.000 dalam sebulan
d. Berdasarkan  perhitungan  yang  telah dilakukan,  dapat  disimpulkan  bahwa metode  cutting  plane  dalam  penelitian ini  mampu  memberikan  solusi  dengan hasil  biaya  yang  minimum. Dalam penyelesaiannya, pada penelitian metode cutting plane ini kita membutuhkan  1  tambahan  batasan gomory. Dengan Menambahkan kendala  Gomory  ke  metode  Cutting Plane, bisa secara efektif menghilangkan solusi kontinu, sehingga menyederhanakan perhitungan.

## 2. Saran
a. Diharapkan  pihak  Dinas  Kelautan  dan
Perikanan Sumatera Utara dapat membentuk system pengendalian persediaan  bahan,  sedemikian  rupa sehingga semua biaya paling minimal.
b. Untuk  pengembangan  lebih  lanjut, kendala  yang  lebih  banyak  dapat digunakan  dan  kemudian  dibandingkan dengan metode lain.

## E.  Daftar Pustaka
Aminuddin. Prinsip  –  Prinsip  Riset  Operasi.
Jakarta: Erlangga, 2005. Bu’lölö, Faigiziduhu. Operasi Riset Program  Linear .  USU  Press.  Medan.
2016
Rangkuti,  Freddy. Manajemen  Persediaan .
Cetakan Pertama, 1995.
Mulyono,  S.  Riset  Operasi,  Jakarta:  Lembaga
Penerbit Fakultas Ekonomi Universitas Indonesia, 2004
Nico. Iryanto. Tarigan, Gim. . “ Aplikasi Metode Cutting  Plane  Dalam  Optimisasi Jumlah  Produksi  Tahunan  Pada  PT. XYZ ”. J. Saintia Matematika . Volume 2, No. 2, pp. 127-136, 2014.
S,  Djarijah. Usaha  Ternak  Sapi. Yogyakarta: Kanisius. 1996.
Sauddin,  Adnan  dan  Kiki  sumarni.  “Integer Programming dengan Pendekatan
Metode Branch  and  Cut Guna mengoptimalkan Jumlah Produk
dengan Keuntungan
Maksimal”.
Jurnal MSA . Vol. 3, No. 1, 2015.
Siagian, P. Penelitian Operasional . Universitas Indonesia. Jakarta, 2006.
Sitorus,  Parlin.  Program  Linier.  Universitas Trisakti, Jakarta, 1997.
Supranto,  J. Linier  Programming .  Lembaga
Penerbit Fakultas Ekonomi Universitas Indonesia, 1980.

## Yuhendra  dan  Eni.  Pendekatan  Metode
Branch  and  Bound dan  Metode
Cutting  Plane untuk  optimasi kombinasi produk. Universitas
Brawijaya. Malang, 2013.
Taha,  H.A. Riset  Operasi,  Jilid  I.  Ed  ke-5 . Editor: Dr. Lyndon Saputra. Binarupa Aksara. Jakarta, 1996.