## PENDEKATAN LINEAR PROGRAMMING UNTUK PERSOALAN PEMOTONGAN STOK (POLA PEMOTONGAN SATU DIMENSI)

## M. Tutuk Safirin dan Sartin
Jurusan Teknik Industri Universitas Pembangunan Nasional “Veteran” Jawa Timur Email : tindustri@upnjatim.ac.id

## ABSTRACT
I n this study, one-dimensional cutting pattern is discussed. This includes fulfilling demands for some items with different lengths by cutting some stocks of standard length available. In this problem, the patterns – the way the standard length is cut – is obtained in such an optimal ways that the trim loss becomes as minimum as possible. The decision variables are the amount of the standard lengths cut according to certain patterns. Then the problem is formulated into a linear programming model. Due to very large number of the variables and restriction to integers, the problem is the type of large scale linear integer programming. For simplicity, restriction to integer is dropped. Then the very large number of the variables is handled by considering only the favorable cutting patterns; list of all possible ways in which a standard stock may be cut is not needed. The favorable cutting pattern is then generated by using column generation technique by solving auxiliary problem in the form of a knapsack problem. The integer optimal solution is obtained by rounding it upward.

## Keywords: column generation, cutting-stock, knapsack

## PENDAHULUAN
Perusahaan  kayu  umumnya  menghasilkan batangan kayu dengan panjang standar 7m. Pesanan khusus dengan panjang yang berbedabeda dipenuhi dengan memotong panjang standar. Contoh suatu pesanan  khusus  yang  bias  berubah  setiap  kali datang pesanan ditunjukkan dalam Tabel 1. Dalam praktek suatu pesanan dipenuhi dengan menyetel  pisau  pemotong  sesuai  dengan  panjang yang diminta. Biasanya, untuk memenuhi pesanan terdapat  beberapa  cara  atau  pola  pemotongan panjang  standar.  Gambar  1  menunjukkan  tiga macam pola pemotongan yang mungkin dilakukan pada suatu pesanan.
Meskipun  terdapat  pola  pemotongan  yang lain,  sebagai  contoh  dibatasi  untuk  Pola  A, B,  dan  C.  Untuk  memenuhi  pesanan  dengan panjang 1,5, 2, dan 3 m, ketiga pola diatas dapat dikombinasikan  sedemikian  cara.  Berikut  adalah dua  contoh  kombinasi  yang  layak  digunakan:  1. Potong panjang standar sebanyak 5 batang dengan mengunakan Pola A dan 15 batang dengan Pola C, serta 2. Potong panjang standar sebanyak 20 batang
dengan mengunakan Pola C dan 3 batang dengan Pola B.
Dari kedua pola di atas, kombinasi mana yang lebih  baik?  Pertanyaan  ini  dapat  dijawab  dengan mempertimbangkan  ‘sisa’  pemotongan.  Pada Gambar  1,  bagian  diarsir  menunjukkan  batang surplus yang tidak cukup panjang untuk memenuhi pesanan.  Sisa  pemotongan  yang  dihasilkan  dari kedua  kombinasi  itu  adalah.  Kombinasi  1:  15  x 0,5m = 7,5m Kombinasi 2: 20 x 0,5m + 3 x 1m = 13m.
Selanjutnya,  setiap  produksi  surplus  dengan panjang  1,5,  2,  dan  3  m  harus  dipertimbangkan dalam  perhitungan  sebagai  ‘sisa’  pemotongan. Pada kombinasi 1, Pola A menghasilkan 10 batang panjang 1,5 m dan 10 batang panjang 2 m sementara Pola C menghasilkan 15 batang panjang 1,5 m, 15 batang panjang 2 m, dan 15 batang panjang 3 m. Jadi,  pada  kombinasi  1  terjadi  produksi  surplus untuk panjang 2 m sebanyak 5 batang = 5 x 2 m = 10 m. Pada kombinasi 2, Pola C menghasilkan 20 batang.
Tabel 1. Contoh pesanan pada persoalan pemotongan stok. Pesanan Pesanan (i) Panjang yang diinginkan (m) Jumlah yang dipesan (batang) 1 1,5 25 2 2 20 3 3 15
Pembatas 2 menjadi x 2 + 2x 3 + x 5 + 3x 6 + 2x 7 ≥ 20 dan Pembatas 3 menjadi: x4 + x5 + x7 + 2x8 ≥ 15. Jadi,  model  Program  Linear  dari  persoalan pemotongan stok untuk persoalan di atas adalah (min) z = x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 terhadap pembatas (tp) 4x 1 + 3x 2 + 2x 3 + 2x 4 + x 5 ≥ 25 x 2 + 2x 3 + x 5 + 3x 6 + 2x 7 ≥ 20 x 4 + x 5 + x 7 + 2x 8 ≥ 15 x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 ≥ 0 dan bilangan bulat. Misalkan: n   =  banyaknya pola pemotongan yang mungkin, x j =  jumlah  panjang  standar  yang  dipotong menurut pola j,
L   =  panjang standar, l i =  jumlah pesanan untuk panjang i ; li ≤ L, a ij =  jumlah  potongan  untuk  panjang  li  dengan pola j,
b i =  banyaknya pesanan untuk panjang li , maka  bentuk  umum  persoalan  pemotongan  stok dalam upaya meminimumkan sisa pemotongan adalah min z = x 1 + x 2 + . . . + xn tp a i1 + a i2 + a in ≥ b i , i = 1, 2, . . . m x j ≥ 0 dan bilangan bulat, j = 1, 2, . . . n. Ada  dua  faktor  yang  menyebabkan  rumusan persoalan  pemotongan  stok  ini  tidak  praktis (Gilmore  &  Gomory  1961;  Dyckhoff  1982). Pertama,  banyaknya  n  pola  pemotongan  bisa berukuran sangat besar jika banyaknya m pesanan berukuran  besar.  Kedua,  pembatasan  terhadap bilangan bulat. Pada laporan ini dibahas teknik untuk mengatasi faktor yang pertama, banyaknya n pola pemotongan berukuran besar, dengan mengabaikan syarat  pembatas  bilangan  bulat.  Kemudian  solusi yang diperoleh, dibulatkan ke atas kebilangan bulat terdekat.
Penelitian ini bertujuan untuk memperlihatkan kemampuan  teknik  pembangkit  kolom  dalam menyelesaikan persoalan pemotongan stok dengan pola pemotongan satu dimensi.
Hasil  penelitian  ini nantinya  diharapkan dapat memperluas  penerapan  matematika  khususnya bidang  riset  operasi  (operations  research)  pada
industri dan perusahaan. Terlebih lagi negara kita ini  kaya  dengan  sumber  daya  alam.  Untuk  itu diperlukan  riset-riset  atau  penelitian-penelitian yang berkenaan dengan pengoptimalan penggunaan dan pemanfaatan sumber daya alam.

## METODE
Penelitian  ini  bersifat  studi  literatur  dengan mengkaji  jurnal-jurnal  dan  buku-buku  teks  yang berkaitan  dengan  bidang  yang  diteliti.  Aspek matematikanya tidak dibahas terlalu dalam; ini bisa  dirujuk  ke  kepustakaan  yang  digunakan. Disini  lebih  ditekankan  teknik  untuk  mencari solusi.  Selanjutnya  teknik  ini  digunakan  untuk menyelesaikan sebuah persoalan fiktip. Disamping cara manual, persoalan ini diselesaikan juga dengan menggunakan paket software LINDO edisi pelajar yang  mampu  menyelesaikan  persoalan  Program Linear  dengan  200  variabel  dan  100  pembatas. Pandang  kembali  model  umum  persoalan pemotongan  stok.  Model  itu  dapat  ditulis  dalam bentuk umum persoalan Program Linear sebagai:
∑ = = n j j j x c Z Min 1 tp ∑ = = ≥ n 1 j j ij m .... 2, 1, i bi, x a
xj ≥ 0 dan bilangan bulat, j = 1, 2, …, n dengan c j = 1 untuk setiap j. Dalam bentuk matriks, persoalan ini dapat ditulis: min z = cx, tp Ax ≥ b x ≥ 0 dan bilangan bulat.
Dengan  c  adalah  vektor  baris  berdimensi  n,  x adalah vektor kolom berdimensi n, b vektor kolom berdimensi m, dan A matriks berordo m × n. Dalam  bentuk  standar,  bentuk  terakhir  ditulis sebagai: min z = C B X B +C N X N , tp BX B + NX N = b X B , X N ≥ 0 dan bilangan bulat dengan x B adalah
variabel basis, x N variabel tak basis, dan B dan N berturut-turut adalah kolom matriks yang berkaitan dengan variabel xB dan xN.
Pada sebarang iterasi metoda simpleks, misalkan basis yang terkait didefinisikan oleh B = ( P 1 , . . . P i , . . . P m ) dengan P i vektor kolom berdimensi m,i = 1, 2,…,m. Misalkan c B = (c 1 ,c 2 , c m ) koefisien fungsi  tujuan  yang  berkaitan  dengan  P 1 ,  P 2 ,… P m .  Kemudian  dari  teori  Program  Linear  (Taha 1975; Taha 1982) pola pemotongan j memberikan perbaikan solusi Program Linear jika reduced cost zj − cj = c B B -1 P j − c j yang berkaitan bernilai positif (persoalan minimisasi), dengan P j = (a 1j , a 2j , . . . , a mj ) T adalah vektor yang menunjukkan banyaknya potongan dengan panjang li,, i = 1, 2, . . ., m, yang dihasilkan dari pola pemotongan j.
Sampai  disini  elemen  Pj  tidak  diketahui; yaitu,  pola  pemotongan  yang  baru  belum diketahui.  Dari  teori  Program  Linear,  pola  yang paling  memberikan  harapan  adalah  pola  yang memberikan  nilai  zj  -  cj  terbesar  diantara  semua pola  (tak  basis)  yang  mungkin.  Tetapi  pada persoalan  pemotongan  stok  berkala  besar,  yang melibatkan  banyak  variabel,  menghitung  nilai z j -  c j untuk  semua  variabel  tak  basis  merupakan pekerjaan yang membosankan. Disinilah diperlukan teknik  pembangkit  kolom  (column  generation technique).  Pada  persoalan  pemotongan  stok, setiap  kolom  atau  variabel  menunjukkan  sebuah pola pemotongan sebatang panjang standar L. Pada contoh  persoalan  sebelumnya,  sebuah  variabel dinyatakan oleh y1 , y2 dan y3 dengan yi adalah jumlah potongan berturut-turut dengan panjang 1,5, 2, dan 3 m yang dihasilkan dari pemotongan panjang standar 7 meter. Sebagai contoh, x5 dinyatakan oleh y1 =1, y2 = 1 dan y3 = 1. Jadi teknik pembangkit kolom  adalah  suatu  teknik  untuk  memperoleh kolom yang dapat memberikan nilai zj - cj terbaik (positif pada persoalan minimisasi). Ini ekuivalen dengan menyelesaikan sub persoalan:
∑ = − = m i i i y W maks 1 1 p tp ∑ = m i 1 l i y i ≤ L , y i ≥ 0 dan bilangan bulat
dengan  koefisien π i elemen  ke  i  dari  c B B -1 . Subpersoalan  ini  dinamakan  persoalan  knapsack; yaitu,  persoalan  Program  Linear  dengan  sebuah
pembatas. Dari teori Program Linear (Taha 1975; (Taha 1982) πi disebut juga nilai dual (dual prices) Untuk melakukan satu iterasi ke iterasi berikutnya digunakan metoda simpleks yang direvisi (revised simplex). Nilai xB dihitung dengan mengunakan x B = B -1 b Komputasi  pada  simpleks  yang  direvisi  banyak berkaitan dengan memperbarui (updating) B-1.
Anggaplah  suatu  persoalan  Program  Linear dengan m pembatas sedang diselesaikan. Misalkan x k akan masuk basis, uji rasio menunjukkan bahwa x k menjadi basis pada basis r. Misalkan kolom xk adalah [a 1k a 2k ... a mk ) T
Definisikan matriks E berukuran m × m :
Ringkasnya, E adalah matriks identitas berukuran m x m dengan kolom r ditukar dengan vector kolom
Selanjutnya  didefinisikan  Ei  sebagai  matriks elementer E yang berkaitan dengan iterasi simpleks ke  i.  Bentuk  hasil  kali  invers  (product  form  of invers) secara umum dapat ditulis (Winston 1991)
Bk -1 E k-1 E k-2 . . . E 1 E 0
Pada  umumnya,  computer  codes  untuk  Program Linear  menggunakan  metoda  simpleks  yang direvisi  dan  menghitung  serangkaian  B -1 dengan mengunakan bentuk hasil kali invers.

## HASIL DAN PEMBAHASAN
Pandang
kembali contoh persoalan sebelumnya.
Min z = x 1 + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 + x 8 tp 4x 1 + 3x 2 + 2x 3 + 2x 4 + x 5 ≥ 25
x 2 + 2x 3 + x 5 + 3 x 6 + 2x 7 ≥ 20 x 4 + x 5 + x 7 + 2x 8
≥ 15
x j ≥ 0 , j = 1 , 2 , . . . . , 8
x 1 ,  x 6 dan  x 8 dapat  digunakan  sebagai variabel  dasar  awal  (basis  awal)  berturut-turut untuk pembatas panjang 1,5 , 2, dan 3 meter. Jadi basis awal adalah variabel dasar (VD) = { x1, x6, x8}. Lalu diperoleh
Untuk basis kini, suatu pola yang dinyatakan oleh y 1 , y 2 dan y 3 akan ditentukan nilai z j - c j nya sebagai
y 1 , y 2 dan y 3 harus dipilih sedemikian sehingga tidak melebihi 7 meter. Juga y 1 , y 2 dan y 3 harus bilangan bulat tak negatip. Ringkasnya, untuk sebarang pola, y 1 , y 2 dan y 3 harus memenuhi 1,5y 1 + 2y 2 + 3y 3 ≥ 7 y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 1 , y 2 , y 3 bilangan bulat. Sekarang pola yang menguntungkan dicari dengan menyelesaikan persoalan knapsack yang ekuivalen berikut :
1,5y 1 + 2y 2 + 3y 3 ≥ 7 y 1 y 2 y 3 ≥ 0, dan bilangan bulat. Meskipun  secara  teoritis  persoalan  knapsack sulit  diselesaikan,  namun  metoda  cabang  dan batas  (branch  and  bound  method)  cukup  efisien dan  praktis  untuk  menyelesaikannya  (Taha  1982; Winston  1991).  Dengan  menggunakan  metoda cabang dan batas, solusi optimal untuk persoalan knapsack ini adalah w =1/6 , y 1 = 2 , y 2 = 2 , y 3 =  0.  Ini  berkorespondensi  dengan  pola  3  dan
variable x 3 . Jadi nilai z 3 - c 3 adalah 1/6 , dan dengan memasukkan  x 3 kedalam  basis  akan  mengurangi sisa pemotongan. Untuk memasukkan x 3 ke dalam basis, perlu dibentuk ruas kanan kini dan kolom x3 kini.
Uji rasio menunjukkan bahwa x 3 masuk basis pada baris  ke  2.  Variabel  dasar  yang  baru  adalah  VD (1) = {x 1 , x 3 , x 2 }. Menggunakan bentuk hasil kali invers, diperoleh
Kembali  digunakan  teknik  pembangkit  kolom untuk  menentukan  pola  yang  akan  masuk  basis. Untuk  nilai  dual  kini  (c B B 1 -1 ),  suatu  pola  yang dinyatakan oleh y 1 , y 2 dan y 3 ditentukan nilai z j - c j nya menjadi
Persoalan knapsack yang ekuivalen adalah
y 1 , y 2 , y 3 ≥ 0 dan bilangan bulat. Dengan  menggunakan  metoda  cabang  dan batas  diperoleh  solusi  optimal  dengan  nilai  w =  0.  Ini  berarti  bahwa  tidak  ada  lagi  suatu  pola yang  menguntungkan  bila  dimasukkan  ke  dalam
basis.  Jadi  VD  (1)  =  {x 1 ,  x 3 ,  x 8 }  sudah  optimal. Untuk menentukan nilai variabel dasar pada solusi optimal, dicari nilai ruas kanan sebagai berikut:
Jadi, solusi optimal untuk persoalan pemotongan stok di atas adalah x 1 = 5/4, x 3 = 10 dan x 8 =15/2. Solusi bilangan bulat diperoleh dengan pembulatan ke atas, yaitu, x 1 = 2 , x3 = 10 dan x 8 = 8. Permintaan sebanyak  25  batang  panjang  1,5  m,  20  batang panjang 2 m dan 15 batang panjangnya 3 m dapat dipenuhi  dengan  memotong  panjang  standar  7  m sebanyak 2 batang mengikuti pola pemotongan 1, 10 batang mengikuti pola 3 dan 8 batang mengikuti pola 8.
Implementasi  LINDO.  LINDO  (Linear Interactive  and  Discrete  Optimizer)  adalah  paket komputer  yang  digunakan  untuk  menyelesaikan Persoalan  Linear,  Integer  dan  Kuadratik Programming.  Untuk  menggunakan  teknik pembangkit  kolom  dengan  bantuan  LINDO,  ide dasarnya  dijelaskan  dengan  langkah-langkah sebagai berikut (Schrage 1995):
Bentuk  dan  selesaikan  Program  Linear  awal 1. yang  memiliki  semua  baris  dari  model  yang terdefinisikan  secara  utuh,  tetapi  dengan sejumlah kecil kolom yang dinyatakan secara eksplisit.
Dengan  nilai  dual  solusi  kini,  bentuk  kolom 2. (pola)  yang  menguntungkan;  yaitu,  jika  cj adalah  biaya  kolom  j,  aij  adalah  koefisien kolom j pada baris i untuk i = 1, 2, …, m, dan di adalah harga dual baris i, tentukan kolom j yang baru sedemikian sehingga cj + d1 a1j + d2 a2j +…+ dm amj < 0. Jika tidak ada kolom sedemikian, lalu berhenti. Selesaikan Program Linear dengan kolom baru 3. dari (2) yang telah ditambahkan.
Kembali ke (2).
4. Pandang kembali contoh persoalan sebelumnya.
Seperti yang terlihat pada Tabel 1, panjang standar 7 m dipotong paling banyak menjadi 3 jenis panjang yang  berbeda  dengan  118  perincian  berikut,  25 batang panjang 1,5 m, 20 batang panjang 2 m, dan 15 batang panjang 3 m.
Prosesnya  dimulai  dengan  mendefinisikan sebarang 3 pola pemotongan yang murni. Sebuah
pola murni hanya menghasilkan satu jenis panjang saja. Misalkan Pi = banyaknya stok standar yang dipotong mengikut pola i. Yang akan diminimumkan adalah  jumlah  total  stok  standar  yang  dipotong. Program Linear dengan pola ini adalah:
MIN P1 + P2 + P3
SUBJECT TO
4 P1 >= 25 ! Panjang 1,5 m
2) 3 P2 >= 20 ! Panjang 2 m
3) 2 P3 >= 15 ! Panjang 3 m
4) END
solusinya adalah: OBJECTIVE FUNCTION VALUE

## 20.41667 1)
VARIABLE VALUE    REDUCED COST P1                 6.250000  .000000 P2                 6.666667  .000000
P3                 7.500000  .000000 ROW  SLACK OR SURPLUS   DUAL PRICES 2)        .000000                         -.250000 3)        .000000                         -.333333 4)        .000000                         -.500000
Pola  baru  yang  akan  ditambahkan  dicari  dengan menyelesaikan persoalan knapsack.
Min 1 - 0,25 y 1 - 0,333333 y 2 - 0,5 y 3 tp  1,5y1 + 2y2 + 3y3 ≤ 7 y 1 , y 2 , y3 ≥ 0 dan bilangan bulat.
Fungsi  tujuan  dapat  ditulis  sebagai: maksimumkan  0,25y 1 +  0,333333y 2 +  0,5y 3 – 1  solusi  optimal  untuk  persoalan  knapsack  ini adalah y 1 = 2 y 2 = 2 dan y 3 = 0, yaitu, pola dengan memotong  2  batang  panjang  1,5  m  dan  2  batang panjang 2 m. Jika kolom ini, P4, ditambahkan ke dalam Program Linear di atas diperoleh formulasi (dalam bentuk picture):
P P P P 1 2 3 4
1: 1 1 1 1 MIN
2: 4 2 > B
3: ‘ 3’ 2 > B
4: 2 ‘ > B
solusinya adalah: OBJECTIVE FUNCTION VALUE 1) 18.75000 VARIABLE   VALUE       REDUCED COST P1                   1.250000     .000000 P2                     .000000     .250000
P3                   7.500000     .000000 P4                 10.000000     .000000 ROW     SLACK OR SURPLUS   DUAL PRICES 2)                      .000000                  -.250000 3)                      .000000                  -.250000 4)                      .000000                  -.500000 Sub persoalan pembangkit kolom adalah maks 0,25y 1 + 0,25y 2 + 0,50y 3 - 1 tp  1,5y 1 + 2y 2 + 3y 3 ≤ 7 y 1 , y2, y 3 ≥ 0 dan bilangan bulat.
Solusi  optimal  untuk  persoalan  knapsack  ini memberikan  nilai  fungsi  tujuan  nol.  Ini  berarti tidak  ada  lagi  pola  lain  yang  dapat  memberikan ‘keuntungan’.  Solusi  optimal  diperoleh,  setelah dilakukan pembulatan yang ‘sesuai’, adalah:
Potong  2  batang  panjang  standar  7m  masing- 1. masing menjadi 4 batang panjang 1,5 m. Potong 10 batang panjang standar 7 m masing- 2. masing menjadi 2 batang panjang 1.5 m dan 2 batang panjang 2 m.
Potong  8  batang  panjang  standar  7m  masing- 3. masing menjadi 2 batang panjang 3 m.

## KESIMPULAN
Pada  persoalan  pemotongan  stok,  tidak perlu  mencari  semua  pola  pemotongan  yang mungkin;  cukup  menentukan  sebuah  pola  awal yang  merupakan  pola  pemotongan  murni.  Pola pemotongan  yang  lebih  baik  diperoleh  dengan mengunakan teknik pembangkit kolom. Perkerjaan yang  agak  berat  adalah  menentukan  solusi subpersoalan  knapsack,  karena  subpersoalan  ini tidak  bisa  diselesaikan  dengan  LINDO.  Metode yang cukup praktis untuk menyelesaikan persoalan knapsack ini adalah metoda cabang dan batas. Bila jumlah  pesanan  semakin  banyak  (dalam  model matematis = jumlah baris semakin banyak) maka semakin banyak pula variabel yang terlibat dalam subpersoalan  knapsack. Akibatnya  semakin  berat menyelesaikannya.  Untuk  itu  perlu  dipikirkan metoda  lain  yang  lebih  mudah  dan  sistimatis daripada metode cabang dan batas.

## UCAPAN TERIMA KASIH
Kami  mengucapkan  terima  kasih  dan penghargaan  yang  tinggi  kepada  semua  pihak  di Proyek Pengkajian dan Penelitian Ilmu Pengetahuan Terapan,  Departemen  Pendidikan  Nasional  atas terselenggaranya penelitian ini dengan kontrak.

## DAFTAR PUSTAKA
Dyckhoff,  H.  1982. A  New  Linear  Programming Approach  to  the  Cutting-Stock  Problem. Operations Research 29: 1092-1104.
Gilmore,  P.C.,  &  R.E.  Gomory.  1961.  A  Linear Programming  Approach  to  the  Cutting-Stock Problem. Operations Research 9: 849-859.
Schrage, L. 1991. LINDO: Text and Software. San Francisco: Scientific Press.
Taha,  H.  A.  1975.  Integer  Programming  Theory :  Application  and  Computation.  New  York: Academic Press.
Taha,  H.  A.  1982.  Operations  Research:  An Introduction. New York: Macmillan Publishing Co.
Winston,  W.  L.  1991.  Operations  Research: Application  and  Algorithm.  California:  PWS- KENT Publishing Company.
Program Linear Persoalan Pemotongan Stok 119.