Penggunaan Metode Branch and Bound dan Gomory Cut dalam Menentukan Solusi Integer Linear Programming
Wahyudin Nur 1 , Nurul Mukhlisah Abdal 2
1 Program Studi Matematika FMIPA Universitas Sulawesi Barat
2 Jurusan Matematika FMIPA Institut Teknologi Bandung
e-mail : 1 wnalafkar93@gmail.com , 2 nurulmukhlisah@gmail.com

## Abstrak
Integer  Linear  Programming  adalah  sebuah  model  matematis  yang  memungkinkan hasil penyelesaian kasus pada Pemrograman Linier berupa bilangan bulat.  . Masalah integer linear  programming  termasuk  salah  satu  bagian  riset  operasi  yang  sangat  penting  karena dalam  kehidupan  sehari-hari,  ada  banyak  permasalah  pemrograman  linear  yang mengharuskan solusinya integer. Ada beberapa metode untuk menyelesaikan persoalan Integer Programming,  tapi  yang  akan  dibahas  pada  penelitian  ini  adalah  Metode  Branch  and  Bound dan Metode Gomory Cut. Tujuan dari penelitian ini adalah untuk  menentukan solusi masalah Integer  Linear  Programming  dan  membandingkan  hasil  yang  diperoleh  dari  Metode  Branch and  Bound  dengan  Metode  Gomory  Cut.  Penelitian  ini  adalah  penelitian  kepustakaan  yang menggunakan berbagai literatur-literatur yang berkaitan dengan topik yang akan diteliti. Hasil penelitian ini menunjukkan solusi yang diperoleh dari metode Branch and Bound samadengan metode  Gomory  Cut.  Dalam  pemecahannya  metode  Branch  and  Bound  memerlukan  banyak iterasi simpleks dibanding metode Gomory Cut.
Kata kunci : Integer Linear Programming, Metode Branch Bound, Metode Gomory Cut

## 1. PENDAHULUAN
Riset Operasi adalah salah satu bagian matematika yang mengkaji cara menetapkan arah tindakan terbaik (optimum) dari sebuah masalah keputusan di bawah pembatasan sumber daya yang  terbatas.  Pada  tahun  1947  seorang  ahli  matematika  dari  Amerika  Serikat  yang  bernama George  D.  Danzig  menemukan  cara  untuk  menguraikan  dan  memecahkan  persoalan pemrograman  linear  dengan  Metode  Simpleks  ( Simplex  Method ).  Ia  menguraikannya  dalam buku  yang  berjudul Linear  Programming  and  Extension .  Keberhasilannya  karena  mampu menyelesaikan  berbagai  masalah  dalam  kehidupan  nyata  seperti  di  bidang  militer,  industri, pertanian, transportasi, ekonomi, kesehatan, dan ilmu sosial.
Pada  kenyataannya,  tidak  semua  masalah  seperti  di  atas  bisa  diselesaikan  dengan metode  yang  biasa  digunakan  dalam  menyelesaikan LP ,  terutama  jika  beberapa  atau  semua variabel  yang  telah  dimodelkan  untuk  memiliki  nilai-nilai  bulat (integer) ,  misalkan  kita  ingin menentukan  kombinasi  jumlah  produksi  kursi  dan  meja.  Kasus  ini  tidak  dapat  diselesaikan langsung dengan metode LP biasa sehingga diperlukan metode khusus yang dipadukan dengan metode penyelesaian LP sehingga dapat memaksa solusi kasus tersebut mengarah kepada solusi integer.
Bakhtiar  S.  Abbas  (2008) dosen jurusan Teknik  Industri,  Fakultas Teknik,  Universitas Bina  Nusantara  dalam  penelitiannya  “Sistem  Optimasi  Optimalisasi  Produksi  untuk Memaksimalkan  Laba”  mengatakan  masalah  yang  dihadapi  perusahaan  saat  ini  adalah ketidakmampuan  perusahaan  dalam  menentukan  jumlah  produksi  optimal.  Hal  itu mengakibatkan  perusahaan  seringkali  mengalami  kekurangan  dan  kelebihan  produksi  yang
menyebabkan  perusahaan  tidak  dapat  mencapai  laba  maksimum.  Metode  yang  dia  gunakan dalam  menghitung  unit  produksi  untuk  mencapai  laba  maksimum  adalah  Metode Branch  and Bound . Dalam penelitiannya beliau menyelesaikan suatu permasalahan yang melibatkan banyak variabel  dan  fungsi  kendala.  Karena  menurutnya  metode  inilah  yang  lebih  bersifat  umum dibanding  dengan  metode  lain  karena  keakuratannya  dalam  menentukan  solusi ILP .  Dalam penelitian  ini,  selain  membahas  mengenai  metode Branch  and  Bound ,  penulis  juga  akan memperkenalkan metode yang agak jarang digunakan yaitu metode Gomory Cut .

## 2. METODE PENELITIAN
Dalam penelitian ini, penulis menggunakan metode kajian pustaka (studi literatur), yaitu penelitian yang bertujuan untuk mengumpulkan data dan informasi dengan bantuan bermacam- macam material yang terdapat di ruang perpustakaan, seperti: buku-buku, jurnal, dokumentasi, catatan, dan juga internet. Adapun langkah-langkah yang dilakukan dalam penelitian ini adalah: 1) mencari referensi yang berkaitan dengan masalah Integer Linear Programming dan metode- metode  untuk  menentukan  solusinya  2)  memilih  beberapa  metode  yang  akan  dibahas  secara rinci  dalam  menentukan  solusi Integer  Linear  Programming yaitu  metode Branch  and  Bound dan  Metode Gomory  Cut 3)  mencari  referensi  yang  berkaitan  dengan  metode  yang  berkaitan dengan  metode Branch  And  Bound dan  metode Gomory  Cut 4)  memahami  alur  pikir  metode- metode  tersebut  dalam  menentukan  solusi Integer  Linear  Programming 5)  mencari  referensi penunjang.

## 3. HASIL DAN PEMBAHASAN
Pada  bab  ini  akan  dibahas  mengenai  penggunaan  metode Branch  and  Bound dan Gomory  Cut dalam  menentukan  solusi  optimal  terhadap  permasalahan  yang  berkaitan  dengan Integer Linear Programming . Misalkan sebuah perusahaan PT. Lightning merakit 3 jenis senter. Senter jenis A, senter jenis B, dan senter jenis C. Senter jenis A dirakit dengan membutuhkan waktu  3  menit,  jenis  B  selama  8  menit  dan  jenis  C  selama  5  menit.  Waktu  pengerjaan  yang tersedia  tiap  minggunya  selama  1500  menit.  Senter  jenis  A  membutuhkan  besi  seberat  9  g, senter jenis B membutuhkan besi seberat 6 gram, dan senter jenis C membutuhkan besi seberat 7  g.  Jumlah  besi  yang  dapat  disediakan  oleh  perusahaan  hanya  2000  gram  tiap  minggunya. Untuk senter jenis A membutuhkan aluminium seberat 5 g, senter B membutuhkan aluminium seberat 3 g, dan senter C seberat 8 g. Jumlah aluminium yang dapat disediakan oleh perusahaan tiap  minggunya  mencapai  1800  gram.  Jika  keuntungan  bersih  yang  diperoleh  dari  hasil penjualan  senter  A,  senter  B,  senter  C  berturut-turut  sebesar  Rp  9000,  Rp  7000,  Rp  8000. Berapa  kombinasi  dari  ketiga  senter  ini  yang  harus  diproduksi  sehinnga  keuntungan  dapat maksimum.
Kasus di atas dapat dimodelkan kedalam bentuk pemrograman linear, yaitu
1 2 3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 9 7 8 3 8 5 1500 9 6 7 2000
5 3 8 1800
, , 0
, , z x x x x x x x x x x x x x x x x x = + + + + £ + + £ + + £ ³ Î
Persamaan z dalam  ribuan,  selanjutnya  kita  mengubah  persamaan  di  atas  menjadi bentuk baku agar bisa diselesaikan dengan menggunakan metode simpleks.
1 2 3 4 5 6 1 2 3 4 1 2 3 5 1 2 3 6 9 7 8 0 0 0 3 8 5 1500 9 6 7 2000
5 3 8 1800 z x x s s s x x x s x x x s x x x s = + + + + + + + + = + + + = + + + =
selanjutnya kita membuat tabel simpleks awal seperti yang terlihat di bawah ini:
Tabel 1. Tabel Simpleks Awal
1 x 2 x 3 x 4 s 5 s 6 s b
9 7 8 0 0 0 4 s 0 3 8 5
1 0 0 1500 5 s 0 9 6 7
0 1 0 2000
6 s 0 5 3 8
0 0 1 1800 z 0 0 0 0 0 0 0 c z - 9 7 8 0 0
0 setelah melakukan beberapa kali iterasi simpleks. diperoleh tabel optimum:
Tabel 2. Tabel Optimum 1 x 2 x 3 x 4 s 5 s 6 s b
9 7 8 0 0 0 2 x 7 0 1 0 37/230 1/230 -12/115 1430/23 1 x 9 1 0 0 -27/230 49/230 -13/115 1070/23 3 x 8 0 0 1 3/230 -31/230 27/115 3970/23 z 9 7 8 4/23 20/23 3/23 2234.78 z c - 0 0 0 4/23 20/23 3/23 Dari  tabel  1  di  atas,  diperoleh  hasil  optimum 1 2 3 1070 1430 3970 , , 23 23 23 x x x = = = dan 2234,78 z = . Karena semua variabelnya bukan bilangan bulat, maka diperlukan metode khusus untuk menentukan solusi integernya yaitu metode Branch and Bound dan Gomory Cut.
3.1  Metode Branch and Bound
Metode Branch  and  Bound dapat  digunakan  untuk  menyelesaikan  masalah  yang mengharuskan  seluruh  variabelnya  merupakan  bilangan  bulat.  Adapun  langkah-langkah  dalam menyelesaikan masalah memaksimumkan untuk kasus integer murni adalah sebagai berikut:
· Selesaikan  kasus ILP dengan  menganggap  kasus  tersebut  seperti  kasus LP .  Dalam menentukan solusi LP tersebut sebaiknya menggunakan metode simpleks.
· Apabila  solusi  optimal  telah  diperoleh  dan  semua  variabelnya  bilangan  bulat  maka  solusi LP tersebut  menjadi  solusi  optimal ILP karena  telah  memenuhi  semua  syarat.  Sedangkan apabila sebagian variabel bukan bilangan bulat maka pilih salah satu variabel tersebut untuk dilakukan percabangan ( Branching ) sehingga kita memperoleh 2 submasalah ILP .
· Selesaikan kedua submasalah tersebut seperti langkah pertama, dan dari kedua submasalah tersebut  tentukan Upper  Bound  (Bounding). Upper  Bound adalah  solusi  submasalah  yang memiliki nilai tertinggi.
· Apabila submasalah yang solusinya menjadi Upper Bound belum memenuhi syarat integer maka  kita melakukan proses percabangan ( Branching ) dan selesaikan submasalah tersebut seperti langkah ketiga.
Berdasarkan tabel 1, diperoleh hasil optimum 1 2 3
1070 / 23, 1430 / 23, 3970 / 23 x x x = = = dan 2234,78 z = .  Karena  semua  variabelnya
noninteger ,  maka  kita  bisa  memiilih  salah  satu  variabelnya  misal 1 x untuk  dilakukan percabangan dan dijadikan kendala baru yaitu cabang I ( 1 6 x £ ) dan cabang II ( 1 7 x ³ ). Setelah itu  dicari  solusi  optimal  dengan  menggunakan  iterasi  simpleks,  sehingga  diperoleh  solusi optimum dari tiap cabang. Prosedur ini diulang sampai semua variabelnya integer .
Gambar 1. Percabangan metode Branch and Bound
diperoleh solusi optimum 1 2 3 47, 62, 172 x x x = = = dan 2233 z = . Sehingga dapat disimpulkan berdasarkan  metode Branch  and  Bound ,  perusahaan  tersebut  harus  memproduksi  senter  A
1
2 3 46.56 62.17 172.61 2234.78 x x x z = = = = 1 2 3 46 62.16 172.94 2232.65 x x x z = = = = 1 46 x £
1 47 x ³ 1 2 3 47 62.53 171.615 2234.23 x x x z = = = = 1 2 3 47 62 146.42 2234.14 x x x z = = = = 1 62 x £ 1 63 x ³ 1 2 3 47.41 63 170.75 2233.75 x x x z = = = = 1 2 3 67.33 62 146 2208 x x x z = = = = 1 146 x £ 1 147 x ³ 1 2 3 47 62 172.14 2234.14 x x x z = = = = 1 2 3 47.11 62 172 2234 x x x z = = = = 1 172 x £ 1 173 x ³ 1 2 3 47 60.3 173 2229.3 x x x z = = = = 1 2 3 47 62 172 2233 x x x z = = = = 1 47 x £
1 48 x ³ 1 2 3 48 62 170.85 2232.88 x x x z = = = =
sebanyak 47, senter B sebanyak 62 dan senter C sebanyak 172 agar menghasilkan keuntungan optimum 2.233.000. 3.2  Metode Gomory Cut Variabel ( 1, 2,..., ) i x i m = mewakili  variabel  dasar  dan  variabel ( 1, 2,..., ) j w j n =
mewakili  variabel  nondasar.  Variabel-variabel  ini  telah  diatur  demikian  untuk  kemudian pertimbangkan persamaan ke-i dimana variabel dasar i x memiliki nilai noninteger .
1 n j i i i j j x w b a = = - å i b noninteger (baris sumber)
Setiap persamaan seperti ini akan dirujuk sebagai baris sumber. Karena, pada umumnya koefisien fungsi tujuan dapat dijadikan integer , variabel z juga integer dan persamaan z tersebut dapat  dipilih  sebagai  baris  sumber.  Pada  kenyataanya,  bukti  konvergensi  dari  algoritma  ini mengharuskan z untuk berupa integer sehingga [ ] i i i j j i i ij f f b b a a = = é ù = + ë û Dimana [ ] N a = adalah  bilangan  bulat  terbesar  sedemikian  sehingga N a £ dan disimpulkan bahwa  0 1 i f < < dan  0 1 ij f < £ . Adapun batasan yang nantinya akan ditambahkan pada tabel simpleks terakhir adalah
1 n i ij j i j S f w f = = - å
Setelah  memperoleh  tabel  simpleks  yang  baru,  kita  akan  menentukan  solusi  optimum  yang baru. Apabila solusi optimumnya masih ada yang berupa noninteger , maka dilanjutkan kembali dengan pemberian batasan baru dan begitu seterusnya.
Berdasarkan tabel 4.2, diperoleh hasil optimum 1 2 3 12 4 14 46 , 62 , 172 23 23 23 x x x = = = dan 18 2234 23 z = .  Karena  semua  variabelnya noninteger maka  pemotongannya  bisa  menggunakan
baris 1 2 , x x ataupun 3 x tetapi  karena i f untuk  baris 3 x adalah 14 23 (paling  besar)  sehingga pemotongan akan dilakukan berdasarkan pada baris 3 x , yaitu:
3 4 5 6 3 199 27 14 ( 1 ) 172 230 230 115 23 x s s s + + - + + = +
Jadi pemotongan gomory ( Gomory Cut ) yang bersesuaian adalah
4 5 6 3 199 27 14 230 230 115 23 s s s + + ³ 4 5 6 7 3 199 27 14 230 230 115 23 s s s s + + - = 4 5 6 7 3 199 27 14 230 230 115 23 s s s s
- - - + = -
Kendala  baru  ini  dimasukkan  ke  tabel  simpleks  terakhir  sehingga  diperoleh  tabel simpleks baru, yaitu:
Tabel 3. Tabel simpleks (penambahan kendala pemotongan gomory I)
1 x 2 x 3 x 4 s 5 s 6 s 7 s b 9          7          8          0 0 0 0 2 x 7 0          1          0            37/230 1/230 -  12/115 0 62   4/23 1 x 9 1          0          0          -  27/230 49/230 -  13/115 0 46  12/23 3 x 8 0          0          1             3/230 -  31/230 27/115 0 172  14/23 4 s 0 0          0          0          -   3/230 - 199/230 -  27/115 1 -  14/23 z 9          7          8             4/23 20/23 3/23 0 2234  18/23 z c - 0          0          0             4/23 20/23 3/23 0
Tabel simpleks dual 3 di atas kemudian diselesaikan untuk memperoleh tabel optimum baru.  Apabila  solusinya  masih noninteger ,  maka  ulangi  prosedurnya  dengan  melakukan pemotongan  Gomory  sehingga  diperoleh  kendala  baru.  Proses  ini  diulangi  sampai  diperoleh tabel simpleks optimum seperti di bawah:
Tabel 4. Tabel simpleks optimum (penambahan kendala pemotongan gomory IV)
1 x 2 x 3 x 4 s 5 s 6 s 7 s 8 s 9 s 10 s b
9        7        8        0        0 0        0 0        0        0 2 x 7 0        1        0        0        0 0        -1 0        0        1 62 1 x 9 1        0        0        0           8/9 0        -   1/9 0        0        -   2/3 47 3 x 8 0        0        1        0        -1          0        1 0        0        0 172 6 s 0 0        0        0        0        3   5/9    1        -4   4/9    0        0           1/3 2   4/9 4 s 0 0        0        0        1        2   1/3    0        3   1/3 0        0        -6 2   2/3 8 s 0 0        0        0        0        1   4/9    0        2   4/9 1        0        -5   1/3    1   5/9 9 s 0 0        0        0        0           5/9 0        1   5/9 0        1        -4   2/3       4/9 z 9        7        8        0        0 0        0 0        0        1 2233 z c - 0        0        0        0        0 0        0 0        0        1 Dari tabel 4 di atas, diperoleh hasil optimum 1 2 3 47, 62, 172 x x x = = = dan 2233 z = .
Sehingga  dapat  disimpulkan  berdasarkan  metode Gomory  Cut ,  perusahaan  tersebut  harus memproduksi  senter  A  sebanyak  47,  senter  B  sebanyak  62  dan  senter  C  sebanyak  172  agar menghasilkan keuntungan optimum 2.233.000.

## 4. KESIMPULAN
Metode Branch  and  Bound dan Gomory  Cut dapat  digunakan  untuk  menyelesaikan masalah pemrograman linear integer . Berdasarkan contoh kasus yang diberikan, diperoleh hasil yang sama antara metode Branch and Bound dan Gomory Cut , yaitu perusahaan tersebut harus memproduksi  senter  A  sebanyak  47,  senter  B  sebanyak  62  dan  senter  C  sebanyak  172  agar menghasilkan keuntungan optimum 2.233.000. Dalam proses penyelesaiannya,  metode branch and  bound memerlukan  jumlah  iterasi  simpleks  yang  banyak  dan  waktu  yang  lama  tapi  lebih terjamin kekonvergenannya.

## DAFTAR PUSTAKA
Anton, Howard dan Chris Rorres. 2005. Elementary Linear Algebra with Applications . Wiley, USA. Bronson, Richard. 1982. Theory and Problems of Operations Research . McGraw-Hill, USA. Dantzig, G.B. 1963. Linear Programming and Extensions . The Rand Corporation, USA.
Eiselt,  H.A.  dan  C.L.  Sandblom.  2007. Linear  Programming  and  its  Applications .  Springer, Canada
Taha,  Hamdy  A..  2007. Operations  Research:  An  Introduction  Eighth  Edition .  Prentice-Hall International Inc, New Jersey. Winston, W.L.. 2003. Operations Research Aplications and Algorithm . Duxbury Press, USA.