PENYELESAIAN MASALAH PEMOTONGAN ROL KERTAS DENGAN METODE PENGHASIL KOLOM SKRIPSI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PENYELESAIAN MASALAH PEMOTONGAN ROL KERTAS DENGAN METODE PENGHASIL KOLOM

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun oleh: Rosa Ajeng Mahadika NIM: 123114003

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2016


PENYELESAIAN MASALAH PEMOTONGAN ROL KERTAS DENGAN METODE PENGHASIL KOLOM

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun oleh: Rosa Ajeng Mahadika NIM: 123114003

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2016

i


PAPER ROLL CUTTING PROBLEM SOLUTION WITH THE COLUMN GENERATION METHOD

A THESIS

Presented as Partial Fulfillment of the Requirements to Obtain the Degree of Sarjana Sains Mathematics Study Program

Written by: Rosa Ajeng Mahadika Student ID: 123114003

MATHEMATICS STUDY PROGRAM DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2016

ii




HALAMAN PERSEMBAHAN

Skripsi ini saya persembahkan untuk Tuhan Yesus dan Bunda Maria, orang tua saya tercinta, Barnabas Bambang Pitoyohadi dan Anastasia Sumarni, serta adik saya terkasih, Agata Woro Mahastuti

v



ABSTRAK

Industri kertas memproduksi rol kertas pada mesin kertas. Rol kertas kemudian dipotong menjadi beberapa rol dengan lebar yang berbeda. Lebar rol ditentukan oleh permintaan pelanggan dan jumlah rol yang dipesan berbeda-beda. Oleh karena itu dibutuhkan penyusunan pola pemotongan dari sebuah rol jumbo menjadi rol-rol kecil. Penyusunan pola pemotongan ini bertujuan untuk meminimumkan jumlah rol jumbo yang digunakan. Penelitian ini mengimplementasikan metode penghasil kolom untuk menyelesaikan masalah tersebut. Metode Penghasil Kolom merupakan salah satu teknik program linear untuk masalah pemotongan persediaan. Iterasi metode penghasil kolom menggunakan Metode Simpleks direvisi dan masalah Knapsack dengan penyelesaian metode cabang-batas. Jika solusi bukan bilangan bulat, maka diperlukan metode first-fit decreasing. Kemudian dibuat suatu program tampilan dengan MATLAB berdasarkan algoritma penghasil kolom tersebut. Pada program ini, solusi yang dihasilkan berupa banyaknya rol atau berat rol. Selanjutnya, solusi dapat dipindahkan ke File Excel. Contoh numerik diberikan untuk menunjukkan efektivitas metode. Berdasarkan hasil penelitian ini diperoleh solusi optimal yaitu jumlah rol minimum. Dibandingkan dengan perhitungan manual yang biasa dilakukan oleh industri kertas, hasilnya sesuai. Namun untuk masalah yang besar, pendekatan ini lebih baik karena perhitungan manual hampir tidak mungkin dilakukan. Kata kunci: rol kertas, pola pemotongan, program linear, masalah Knapsack, penghasil kolom

vii


ABSTRACT Paper industry produces jumbo paper rolls by using a paper machine. The jumbo paper rolls are then cut into smaller rolls with different widths. The widths of rolls are determined by the customers’ demands and the different number of ordered rolls so that it is necessary to have an organization of cutting pattern from a jumbo into small rolls. The organization of cutting pattern aims to minimize the number of jumbo rolls used. This research implements a column generation method to solve the problem. The column generation method is one of the linear programming techniques for the problem of cutting stock. The iteration of column generation method uses revised simplex and Knapsack problem with the completion of branch-and-bound method. If a solution is not an integer, the solution is converted into the integer using the first-fit decreasing method. Then, a display program with MATLAB is made based on the column generation algorithm. In this program, the solution may be in form of the number of rolls or the weight of rolls. Moreover, the solution can be transferred to Excel File. Numerical examples are then carried out to show the effectiveness of the method. Based on the result of this research, the optimal solution is obtained, namely the minimum number of jumbo rolls. In comparison to the manual calculation commonly practiced by paper industry, the results are well fitted. However, for big problems our approach is better because manual calculation is almost impossible done due to the expanding number of possible cutting pattern combinations. Keywords: paper roll, cutting pattern, linear programming, Knapsack problem, column generation

viii



KATA PENGANTAR Puji dan syukur kepada Tuhan Yesus dan Bunda Maria atas berkat yang selalu menyertai penulis dalam menyelesaikan skripsi ini tepat waktu. Skripsi ini dibuat sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika, Universitas Sanata Dharma. Banyak tantangan dalam proses penulisan skripsi ini, namun dengan penyertaan Tuhan serta dukungan dari berbagai pihak akhirnya skripsi ini dapat diselesaikan. Untuk itu penulis ingin mengucapkan terima kasih kepada: 1.

Bapak Sudi Mungkasi, S.Si., M.Math.Sc., Ph.D. selaku Dekan Fakultas Sains dan Teknologi.

2.

Bapak Hartono, Ph.D. selaku Kepala Program Studi Matematika dan dosen pembimbing yang dengan sabar dan penuh antusias dalam membimbing selama proses penulisan skripsi ini.

3.

Seluruh Dosen Program Studi Matematika serta karyawan Fakultas Sains dan Teknologi. Terimakasih atas bimbingan, pelajaran, dan masukan yang diberikan selama berkuliah di Universitas Sanata Dharma.

4.

Bapak Tjoeng Chayahin selaku mentor di divisi PPIC PT. Indah Kiat Tangerang yang dengan sabar membimbing selama penelitian dan proses penulisan skripsi ini.

5.

Bapak Bambang S. Hardono selaku kepala divisi PPIC PT. Indah Kiat Tangerang dan seluruh karyawan PT Indah Kiat Tangerang yang memberikan masukan serta menerima saya dengan baik selama penelitian.

x


6.

Ibu Theresia Titirani selaku HRD PT Indah Kiat yang sudah memberikan kesempatan untuk melaksanakan penelitian dan mengambil data di PT Indah Kiat.

7.

Kedua orang tuaku, Barnabas Bambang Pitoyohadi dan Anastasia Sumarni, serta adikku Agata Woro Mahastuti yang selalu mendoakan dan mendukungku dengan penuh kasih dan memberikan masukan positif kepadaku.

8.

Sahabat dan teman-teman angkatan 2012 (Arum, Happy, Ilga, Auxi, Boby, Rian, Budi, Ega, Lia, Putri, Noni, Dewi, Sila, Ferni, Risma, Anggun, Manda, Juli, dan Tika), Stanislaus Yhanna Pradita, Vianita, Maya, Clement yang sudah memberikan dukungan serta semangat kepadaku. Penulis juga mengucapkan terima kasih kepada semua pihak yang telah

membantu dalam penyusunan skripsi ini. Semoga segala doa, perhatian, dukungan, bantuan, dan cinta yang telah diberikan mendapatkan balasan dari Tuhan Yesus. Penulis menyadari bahwa masih banyak kekurangan dalam penulisan skripsi ini. Oleh karena itu, penulis mengharapkan kritik dan saran demi penyempurnaan skripsi ini. Harapan penulis, semoga skripsi ini bermanfaat bagi pembaca dan menjadi referensi belajar yang baik.

Yogyakarta, Agustus 2016 Penulis,

Rosa Ajeng Mahadika

xi


DAFTAR ISI HALAMAN JUDUL ........................................................................................................... i HALAMAN JUDUL DALAM BAHASA INGGRIS ........................................................ ii HALAMAN PERSETUJUAN PEMBIMBING ................................................................ iii HALAMAN PENGESAHAN............................................................................................ iv HALAMAN PERSEMBAHAN ......................................................................................... v PERNYATAAN KEASLIAN KARYA ............................................................................ vi ABSTRAK ........................................................................................................................ vii ABSTRACT..................................................................................................................... viii LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI............................................. ix KATA PENGANTAR ........................................................................................................ x DAFTAR ISI..................................................................................................................... xii BAB I PENDAHULUAN ................................................................................................... 1 A.

Latar Belakang Masalah.......................................................................................... 1

B.

Rumusan Masalah ................................................................................................... 9

C.

Pembatasan Masalah ............................................................................................... 9

D.

Tujuan Penulisan ................................................................................................... 10

E.

Manfaat Penulisan ................................................................................................. 10

F.

Metode Penulisan .................................................................................................. 10

G.

Sistematika Penulisan ........................................................................................... 11

xii


BAB II PROGRAM LINEAR .......................................................................................... 13 A.

Program Linear ..................................................................................................... 13

B.

Metode Simpleks Direvisi ..................................................................................... 24

C.

Program Linear Bilangan Bulat ............................................................................ 34

D.

Masalah Knapsack ................................................................................................ 43

BAB III MASALAH PEMOTONGAN PERSEDIAAN .................................................. 61 A.

Masalah Pemotongan Persediaan (Cutting Stock Problem) .................................. 61

B.

Metode Penghasil Kolom ...................................................................................... 64

BAB IV PENERAPAN METODE PENGHASIL KOLOM UNTUK MASALAH PEMOTONGAN ROL KERTAS ..................................................................................... 84 BAB V PENUTUP ........................................................................................................... 91 A.

Kesimpulan ........................................................................................................... 91

B.

Saran ..................................................................................................................... 92

DAFTAR PUSTAKA ....................................................................................................... 93 LAMPIRAN A .................................................................................................................. 95 LAMPIRAN B ................................................................................................................ 124

xiii


BAB I PENDAHULUAN

A. Latar Belakang Masalah Masalah pemotongan persediaan (cutting stock) sering terjadi pada proses produksi. Masalah pemotongan persediaan biasanya berkaitan dengan pemakaian bahan baku yang optimal yaitu yang meminimumkan biaya produksi bahan baku. Pada industri kertas, untuk dapat meminimumkan biaya produksi salah satu cara yang ditempuh adalah dengan memproduksi jumlah rol yang optimal dalam arti yang sesuai dengan kebutuhan/pesanan dan juga harus memperhatikan pola pemotongan. Semakin sedikit jumlah rol yang digunakan untuk memenuhi pesanan maka efisiensi akan meningkat. Masalah di atas terjadi di perusahaan pulp and paper PT Indah Kiat Tangerang. Sebelum dilakukan pemotongan, terjadi proses pewarnaan dan pencampuran pada pulper (bubur kertas). Lalu diproses pada mesin kertas (paper machine) menjadi rol kertas besar (dengan berat sekitar 4 – 6 ton) yang nantinya akan menuju mesin penggulung (rewinder machine), pisau pemotong rangkap (double cutter), atau pisau pemotong tunggal (single cutter). Jika rol kertas masuk ke mesin penggulung maka produk berupa rol kertas. Dari mesin penggulung, rol kertas juga dapat langsung ke mesin pemotong untuk ukuran kertas kecil (echwill machine) di mana rol kertas akan dipotong lalu dikemas dengan ukuran yang sudah ditentukan (cut size).

1


2

Proses pemotongan rol kertas pada mesin penggulung yang menghasilkan rolrol kecil dapat dilihat pada gambar 1.1.

Gambar 1.1: Proses yang terjadi pada mesin penggulung Berikut gambar produk kertas yang dapat dipesan dan siap untuk dikirim yaitu rol kertas, lembar kertas besar, dan potongan kertas kecil.

(b)

(a)

(c) Gambar 1.2: Produk kertas: (a) rol kertas, (b) large sheet, dan (c) cut size


3

Jika rol kertas masuk ke pisau pemotong rangkap dan pisau pemotong tunggal maka produk berupa lembar kertas besar. Perbedaan pisau pemotong rangkap dan pisau pemotong tunggal terdapat pada cara pemotongannya. Pada pisau pemotong rangkap terdapat 2 pisau pemotong dimana hasil dari setiap potongan memiliki ukuran yang sama, sedangkan pisau pemotong tunggal memiliki 1 pisau pemotong dimana hasil dari setiap potongan ada salah satu yang berbeda ukuran. Proses pemotongan rol kertas pada pisau pemotong rangkap ditunjukkan pada gambar 1.3. 5 Slitter Knives

Reel Produce by Paper Machine (Input)

2 Cutter Knives

Large Sheet (Output)

Gambar 1.3: Proses yang terjadi pada pisau pemotong rangkap Kemudian dari pisau pemotong (rangkap atau tunggal), kertas dipotong sesuai ukuran yang diminta lalu dikemas atau dapat juga langsung dikemas dengan ukuran potongan kertas dalam bentuk besar (large size). Terdapat juga pisau pemotong kecil (mini cutter) yang digunakan memotong rol kertas yang sudah dipotong menjadi beberapa rol kecil menjadi ukuran yang diminta.


4

Berikut skema proses produksi kertas. Mesin kertas Mesin penggulung

Pisau pemotong

Mesin pemotong ukuran kertas kecil

Penyortiran

Mesin pemotong

Pengemasan Manual

Rol kertas

Kertas ukuran kecil

Pengemasan

Kertas ukuran besar

Gambar 1.4: Skema proses produksi kertas Sebelum rol jumbo dipotong menjadi potongan kertas atau rol kecil, maka harus diperhitungan berbagai macam kemungkinan pola pemotongan dari rol jumbo tersebut yang kemudian akan dipilih yang paling optimal. Pola tersebut berupa gabungan dari beberapa ukuran kertas atau rol yang diinginkan nasabah. Berikut gambar pemotongan dari rol jumbo menjadi rol-rol kecil dalam memenuhi pesanan.

Gambar 1.5: Pemotongan dari rol jumbo ke rol kecil


5

Pembentukan pola tersebut juga harus memperhatikan beberapa kendala berikut agar didapat hasil yang optimal. Berikut kendala yang perlu diperhatikan: 1.

Lebar kertas maksimal (deckle) 276 cm untuk 70 gsm (grams per square meter) ke atas dan 272 untuk 70 gsm ke bawah.

2.

Dalam 1 rol jumbo yang akan dipotong menjadi rol-rol kecil haruslah memuat pesanan dengan diameter rol, panjang rol, jenis kertas, warna kertas, dan gsm yang sama. Terdapat banyak metode untuk menyelesaikan masalah tersebut salah satunya

dengan program linear. Banyak persoalan yang dapat diselesaikan menggunakan metode program linear diantaranya persoalan transportasi, program penugasan, program dinamis, dan program bilangan bulat. Secara umum, masalah program linear dapat dirumuskan sebagai berikut: Maksimumkan atau minimumkan =

Dengan kendala

dengan

[

=

,

,…,

�

,

=

= ,

,…,

,

=[

⋱

, ,

], dan

=

].

Contoh 1.1 Sebuah industri kertas menghasilkan rol jumbo dengan lebar 3 meter. Pelanggan menginginkan rol dengan lebar yang lebih kecil. Misalkan dari rol jumbo


6

ini dapat dipotong menjadi 2 rol dengan lebar 93 cm,1 rol dengan lebar 108 cm, dan menyisakan rol dengan lebar 6 cm. Misalkan pesanan yang diterima adalah sebagai berikut. Tabel 1.1 Pesanan yang diterima untuk contoh 1.1 Banyak rol Lebar rol (cm) 97

135

610

108

395

93

211

42

Permasalahannya menjadi bagaimana menentukan pola pemotongan rol jumbo agar pesanan dapat dipenuhi dengan banyaknya rol jumbo yang harus dipotong sesedikit mungkin. Ada 12 kemungkinan/cara memotong rol jumbo ke dalam rol kecil sesuai pesanan (dengan sisa pemotongan kurang dari 42 cm) yaitu: Kemungkinan

Lebar rol Sisa

�

135

108

93

42

1

2

0

0

0

30

2

1

1

0

1

15

3

1

0

1

1

30

4

1

0

0

3

39

5

0

2

0

2

0


7

6

0

1

2

0

6

7

0

1

1

2

15

8

0

1

0

4

24

9

0

0

3

0

21

10

0

0

2

2

30

11

0

0

1

4

39

12

0

0

0

7

6

Pola 1 dari tabel di atas berarti 1 rol jumbo dengan lebar 3 meter akan dipotong menjadi 2 rol kecil dengan lebar 135 cm dengan sisa kemungkinan 30 cm. Pola 2 berarti 1 rol jumbo akan dipotong menjadi 1 rol kecil dengan lebar 135, 1 rol kecil dengan lebar 108 dan 1 rol kecil dengan lebar 42 cm dengan sisa kemungkinan 15 cm. Demikian seterusnya berlaku cara membaca data yang sama untuk pola-pola pemotongan yang lain. Untuk setiap kemungkinan pola � di atas, kita memperkenalkan variabel

yang menunjukkan banyaknya rol jumbo yang harus dipotong menurut pola

� . Dengan demikian, fungsi tujuan adalah meminimumkan jumlah rol jumbo yang

dipotong yaitu ∑

=

. Agar pesanan terpenuhi maka untuk setiap ukuran lebar

yang dipesan ditambahkan 1 kendala. Sebagai contoh, untuk pesanan 395 rol dengan lebar 93 cm, maka fungsi kendala dapat dituliskan +

+

+

+

+


8

yang berarti jumlah rol kecil dengan lebar 93 cm yang dihasilkan dengan memotong rol jumbo menurut berbagai pola pemotongan tidak boleh kurang dari 395 rol (jumlah rol pesanan). Demikian seterusnya sehingga diperoleh masalah program linear berikut. Minimumkan

∑ =

Dengan kendala +

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

Dalam menyelesaikan masalah program linear, metode yang sering digunakan adalah metode simpleks. Selain metode simpleks, metode yang lebih cocok digunakan untuk menyelesaikan masalah pemotongan yaitu metode penghasil kolom. Pada skripsi ini akan dibahas mengenai bagaimana penerapan metode penghasil kolom dalam menyelesaikan masalah pemotongan rol kertas untuk mendapatkan solusi optimal. Masalah pemotongan rol kertas dibatasi hanya pada pemotongan dari rol ke rol yang berarti hanya untuk pemotongan dari rol jumbo


9

menjadi rol-rol kecil dan dengan pola pemotongan satu dimensi (lihat gambar 1.1 dan 1.5). Yang dimaksud dengan pola pemotongan satu dimensi adalah memotong rol kertas dengan mempertimbangkan satu ukuran saja yaitu lebar rol sehingga untuk ukuran panjang dan tebal/diameter rol adalah sama untuk setiap potongan. Sedangkan untuk pola pemotongan dua dimensi yaitu memotong rol kertas dengan mempertimbangkan dua ukuran yaitu lebar dan panjang kertas (lihat gambar 1.3).

B. Rumusan Masalah Berdasarkan latar belakang tersebut, secara garis besar uraian rumusan masalah yang dibahas dalam tugas akhir ini adalah: 1.

Bagaimana memodelkan masalah pemotongan kertas agar didapat solusi yang optimal?

2.

Bagaimana menyelesaikan masalah pemotongan kertas dengan menggunakan metode penghasil kolom?

3.

Bagaimana menyelesaikan masalah pemotongan kertas dengan menggunakan MATLAB?

C. Pembatasan Masalah Agar penulisan dan pembahasan isi menjadi lebih terarah dan tidak menyimpang dari masalah yang dibahas maka dalam penulisan tugas akhir ini dibatasi, yaitu pemotongan kertas dari rol jumbo menjadi pesanan rol kecil dengan pola pemotongan satu dimensi meminimumkan jumlah rol.

(lebar) dan fokus pada (optimalisasi)


10

D. Tujuan Penulisan Tujuan yang ingin dicapai penulis dalam penulisan tugas akhir ini selain untuk memenuhi syarat tugas akhir dalam Program Studi Matematika Universitas Sanata Dharma, yaitu sebagai berikut. 1.

Memodelkan masalah pemotongan kertas.

2.

Menyelesaikan masalah pemotongan kertas dengan metode penghasil kolom.

3.

Menyelesaikan masalah pemotongan kertas dengan program MATLAB.

E. Manfaat Penulisan Manfaat penulisan dari tugas akhir ini adalah: 1.

Dapat memodelkan dan mengaplikasikan program linear dalam masalah pemotongan kertas.

2.

Dapat membantu berbagai pihak untuk menentukan pola pemotongan kertas yang optimal.

F. Metode Penulisan Metode yang digunakan penulis dalam penyusunan tugas akhir yaitu studi pustaka, yaitu dengan mempelajari buku atau jurnal yang berkaitan dengan masalah pemotongan persediaan (cutting stock problem). Penulis juga menggunakan studi kasus untuk memperoleh data yang akan digunakan dalam penelitian.


11

G. Sistematika Penulisan BAB I. PENDAHULUAN A. Latar Belakang Masalah B. Perumusan Masalah C. Pembatasan Masalah D. Tujuan Penulisan E. Manfaat Penulisan F. Metode Penulisan G. Sistematika Penulisan

BAB II. PROGRAM LINEAR A. Program Linear B. Metode Simpleks Direvisi C. Program Linear Bilangan Bulat D. Masalah Knapsack (Knapsack Problem)

BAB III. MASALAH PEMOTONGAN PERSEDIAAN A. Masalah Pemotongan Persediaan (Cutting Stock Problem) B. Metode Penghasil Kolom

BAB IV. PENERAPAN METODE PENGHASIL KOLOM UNTUK MENYELESAIKAN MASALAH PEMOTONGAN ROL KERTAS


12

BAB V. PENUTUP A. Kesimpulan B. Saran DAFTAR PUSTAKA LAMPIRAN A LAMPIRAN B


BAB II PROGRAM LINEAR

A. Program Linear Program Linear muncul pada tahun 1939 di Departemen Pertahanan Inggris dan Amerika untuk menjawab masalah optimisasi perencanaan operasi perang melawan Jerman dalam Perang Dunia ke-II. Pada tahun 1947 teori dan teknik simpleks dikembangkan oleh Dantzig dan para pakar lainnya. Masalah dalam program linear adalah mengoptimumkan suatu fungsi linear yang terbatas oleh kendala-kendala berupa persamaan dan pertidaksamaan linear. Program linear termasuk model yang relatif sederhana di antara model-model riset operasi. Beberapa contoh penggunaan program linear ialah penjadwalan produksi, penjadwalan penerbangan, siasat perang, analisis sosial, dan lain-lain. Model program linear memiliki tiga komponen dasar yaitu: 1.

Variabel keputusan adalah variabel yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat, yang merupakan formulasi dari apa yang dicari dalam persoalan tersebut. Variabel keputusan ini dituliskan dengan

2.

, = , ,…, .

Fungsi tujuan merupakan fungsi dari variabel keputusan yang harus dicapai agar solusi optimal dapat ditentukan dari semua nilai-nilai yang layak.

3.

Fungsi kendala merupakan formulasi dari kendala-kendala yang dihadapi dalam menentukan nilai variabel-variabel keputusan. Adapun syarat dari model program linear adalah:

13


14

1.

Linearitas Fungsi tujuan dan kendala haruslah fungsi linear.

2.

Proporsionalitas Nilai variabel dari semua fungsi kendala dan fungsi tujuan yang linear haruslah proporsional atau sebanding. Sebagai contoh, satu potong roti menghasilkan 77,5 kalori maka untuk 2 potong roti menghasilkan 155 kalori.

3.

Aditivitas Fungsi tujuan adalah jumlahan langsung dari kontribusi individual dari variabel-variabel yang berbeda. Sebagai contoh, 2 potong roti menghasilkan 155 kalori dan 1 butir telur menghasilkan 80 kalori maka dihasilkan 235 kalori dengan mengkonsumsi 2 potong roti dan 1 butir telur.

4.

Kepastian Setiap parameter (koefisien fungsi tujuan, koefisien kendala, dan nilai di sisi kanan) diketahui dengan pasti dan tidak berubah selama periode analisis. Secara umum, masalah umum program linear bisa dinyatakan sebagai

berikut: Memaksimumkan atau meminimumkan

Dengan kendala

= + +

{

+

+ + +

+

+

+ +

+ + , ,…,

Perumusan di atas dapat ditulis secara ringkas menjadi

2.1

= =

=

2.2


15

Memaksimumkan atau meminimumkan 2.3

=∑ =

Dengan kendala ∑ =

=

2.4

, = ,…,

, = ,…,

2.5

dimana setiap pertidaksamaan (2.4) memiliki simbol,

, , =, yang hanya dipilih

salah satu yang disebut kendala utama, sedangkan pertidaksamaan (2.5) disebut kendala tak negatif. Kendala tak negatif mengasumsikan nilai variabel bernilai tak negatif. Fungsi linear (2.3) disebut fungsi tujuan. Dengan koefisien teknis,

disebut koefisien ongkos, dan

disingkat “suku tetap” atau “ruas kanan”. Jika

harus disebut

disebut suku tetap di ruas kanan , = ,…,

memenuhi semua

kendala maka disebut solusi layak. Solusi layak yang juga mengoptimumkan disebut solusi optimum. Untuk menyelesaikan masalah minimum maka bentuk minimum dapat diubah menjadi bentuk maksimum dengan cara mengalikan fungsi tujuan dengan − . Selanjutnya, diselesaikan seperti masalah maksimum. Solusi yang diperoleh untuk masalah maksimum ini akan sama dengan solusi untuk masalah minimum, tetapi dengan nilai yang sama dengan negatif nilai masalah maksimumnya. Jadi, masalah program linear adalah masalah dari fungsi linear maksimum (atau minimum) dengan kendala linear yang terbatas.


16

Metode yang sering digunakan untuk menyelesaikan masalah program linear adalah metode grafik dan metode simpleks. Metode grafik digunakan untuk memecahkan persoalan model program linear dua variabel. Lalu pada tahun 1947, Dantzig mengembangkan metode yang dapat memecahkan persoalan model program linear dengan lebih dari dua variabel yang disebut metode simpleks.

Metode Simpleks Metode simpleks yang dikenalkan oleh George B. Dantzig telah dikembangkan dan diterapkannya ke persoalan bisnis. Metode simpleks adalah metode sistematis dari suatu solusi layak ke solusi layak lainnya dan dilakukan berulang-ulang sehingga tercapai suatu solusi layak yang optimum.

Definisi 2.1 Variabel pengetat (slack variable) merupakan variabel tambahan yang mengubah suatu pertidaksamaan menjadi persamaan, dengan cara menambahkan variabel pengetat pada ruas kiri suatu pertidaksamaan. Variabel pengetat ini digunakan pada kendala pertidaksamaan yang berbentuk lebih kecil sama dengan (≤).

Misalkan diberikan masalah program linear bentuk standar sebagai berikut. Memaksimumkan =∑ =


17

Dengan kendala ∑

, = ,…,

=

, = ,…,

Maka dapat didefinisikan variabel pengetat

+

sebagai berikut.

+

2.6

=

−∑

,

+

,…,

dan fungsi tujuan

+

2.7

, = ,…,

=

2.8

=∑ =

Dengan notasi ini, masalah ini dapat diuraikan kembali menjadi Memaksimumkan

Setiap solusi layak bulat tak negatif

,

dengan kendala

,

,…,

,

,…,

2.9

+

dari (2.6) ditunjukkan oleh

dengan

+

,…,

+

,

+

,…,

+

bilangan

yang didefinisikan

+

pada (2.7). Hal ini dapat dikatakan bahwa (2.7) menunjukkan kesamaan/ekuivalensi antara (2.6) dan (2.9). Untuk lebih jelasnya yaitu sebagai berikut. 1.

Setiap solusi layak

,

,…,

ditunjukkan oleh (2.7), menjadi 2.

Setiap solusi layak

,

,…,

dari (2.6) dapat diperluas, dengan cara yang ,

+

,…,

+

dari (2.9).

dari (2.9) dapat dipersempit dengan

menghapus variabel pengetat, menjadi solusi layak 3.

,

,…,

dari (2.6).

Solusi optimal (2.6) termuat dalam solusi layak (2.9), begitu sebaliknya.


18

,

Di setiap iterasi, metode simpleks mengganti solusi layak menjadi solusi layak lain ̅ , ̅ , … , ̅

+

∑

,…,

+

yang lebih baik dari sebelumnya sehingga ̅ >∑

=

=

Sistem linear untuk menemukan solusi layak dengan menyatakan nilai-nilai variabel sisi kanan menjadi nilai-nilai yang sesuai dari variabel sisi kiri dan fungsi tujuan disebut kamus (dictionaries). Dengan demikian, setiap kamus dari (2.6) akan menjadi suatu sistem persamaan linear dalam variabel Pertama definisikan

+

,

+

,…,

+

,

,…,

dan , serta

+

+

dan . +

variabel

yang saling bergantung. Saling ketergantungan ini harus didasarkan oleh setiap kamus terkait (2.6) dimana terjemahan harus tepat. Lebih tepatnya, kamus-kamus harus memenuhi syarat-syarat berikut. 1.

Setiap solusi dari himpunan persamaan yang memuat kamus harus juga solusi dari (2.7), begitu sebaliknya.

2.

Persamaan setiap kamus harus memperlihatkan dan fungsi tujuan

3.

dalam

variabel tersisa.

variabel dari

,

,…,

+

Menetapkan variabel sisi kanan nol dan mengevaluasi variabel sisi kiri sampai pada solusi layak. Kamus-kamus yang memenuhi ketiga syarat tersebut disebut kamus-kamus

layak. Dengan demikian, setiap kamus layak menunjukkan suatu solusi layak. Solusi layak yang dapat ditunjukkan dengan kamus-kamus disebut dasar (basic).


19

Definisi 2.2 Variabel dasar (basic) adalah variabel yang diperoleh dari banyaknya persamaan pada masalah program linear. Sedangkan variabel lainnya adalah variabel tidak dasar (nonbasic). Variabel ini adalah variabel yang dihasilkan dari selisih banyaknya variabel dengan banyaknya persamaan pada masalah program linear dan merupakan variabel yang bernilai nol.

Variabel

yang muncul pada sisi kiri kamus disebut dasar dan variabel

yang muncul pada sisi kanan disebut tidak dasar. Variabel dasar merupakan basis. Basis berubah pada setiap iterasi. Pada setiap iterasi, dipilih variabel tidak dasar untuk masuk basis lalu mengeluarkan variabel dasar dari basis. Pemilihan variabel masuk disebabkan oleh keinginan untuk meningkatkan nilai

dan penentuan

variabel keluar didasarkan pada persyaratan bahwa semua variabel harus diasumsikan bernilai tak negatif. Variabel keluar adalah variabel dasar tak negatif yang menyebabkan batas atas terketat pada kenaikan variabel masuk. Rumus untuk variabel keluar muncul di baris sumbu (pivot row) kamus. Proses perhitungan dari pembuatan kamus baru disebut berputar (pivoting).

Contoh 2.1 Maksimumkan +

Dengan kendala +

+ +


20

−

− +

,

+

+

,

−

Pada contoh ini, kamus layak awal dapat dituliskan sebagai berikut. =

−

=

−

= =

=

−

+

−

−

+

−

−

−

+

2.10

+

+

Kamus layak ini menunjukkan variabel keputusan tidak dasar (diberi nilai nol) dan variabel pengetat dasar. Jadi solusi layak yang bersesuaian adalah ,

= ,

= ,

dalam kamus.

= , dan

,

,

,

,

merupakan variabel ,

merupakan variabel

= ,

= ,

= ,

=

= . Sehingga memenuhi syarat kedua dan ketiga

Pada iterasi pertama, kita mencoba meningkatkan nilai salah satu variabel sisi kanan positif. Terdapat tiga variabel dipilih. Biasanya akan dipilih variabel pada

dengan membuat ,

,

yang akan

yang memiliki koefisien terbesar

sehingga nilai

lebih cepat meningkat. Pada contoh ini akan dipilih sebarang

variabel antara

dan

. Di sini dipilih

positif. Karena nilai

meningkat dan


21

,

nilai

,

, dan

tidak satupun diizinkan menjadi negatif, maka diberikan

batas pada tiap variabel yaitu =

−

=

−

=

−

−

−

+

Dimana nilai

−

−

+

meningkat sehingga tidak menjadi batas atas kenaikan

=

dan

adalah batas atas terketat dan mengimplikasikan

. Sehingga kendala

. Dalam meningkatkan solusi layak diperoleh masuk menjadi basis dan variabel

=

dan

= . Variabel

keluar menjadi variabel tidak dasar (diberi

nilai nol). Persamaan keempat (2.10) dapat dituliskan sebagai berikut. =

−

+

2.11

−

Substitusikan (2.11) ke dalam persamaan yang tersisa dari (2.10). =

−

+

−

=

−

−

+

=

−

−

−

=

=

+

−

−

+

2.12

+

−

Kamus (2.12) menyelesaikan iterasi pertama metode simpleks. Kamus layak ini menunjukkan variabel tidak dasar ,

,

,

,

,

(diberi nilai nol) dan variabel dasar

. Jadi solusi layak yang bersesuaian adalah

= ,

= ,

=


22

,

= ,

= ,

= ,

= , dan

dan ketiga dalam kamus.

= . Sehingga memenuhi syarat kedua

Pada iterasi kedua, untuk meningkatkan nilai

dipilih

positif. Hal ini karena

adalah satu-satunya variabel tidak dasar yang memiliki koefisien positif pada di (2.12). Karena nilai ,

nilai

, dan

,

memberikan batas atas pada kenaikan = ,

batas tiap variabel yaitu

= / ,

batas atas terketat dan mengimplikasikan = /

layak diperoleh variabel

= / . Namun,

menurun, dan tidak satu pun diizinkan menjadi negatif. Ketiga

,

kendala

meningkat, maka begitu juga nilai

dan

=

sehingga kendala

, diberikan adalah

/ . Dalam meningkatkan solusi

= . Variabel

masuk menjadi basis dan

keluar menjadi variabel tidak dasar (diberi nilai nol). Dengan cara

substitusi seperti iterasi pertama, maka dapat dituliskan kamus ketiga sebagai berikut. =

+

+

−

=

−

−

−

=

−

+

=

−

−

+

+

−

−

=

2.13


23

Kamus (2.13) menyelesaikan iterasi kedua metode simpleks. Kamus layak ini ,

menunjukkan variabel tidak dasar ,

/ ,

,

,

,

(diberi nilai nol) dan variabel dasar = / ,

. Jadi solusi layak yang bersesuaian adalah

= ,

= / ,

= ,

= , dan

kedua dan ketiga dalam kamus.

=

= ,

=

/ . Sehingga memenuhi syarat

Pada iterasi ketiga, untuk meningkatkan nilai

dipilih

positif. Hal ini karena

adalah satu-satunya variabel tidak dasar yang memiliki koefisien positif pada di (2.13). Karena nilai

meningkat, maka nilai

,

,

, dan

tidak satu pun diizinkan menjadi negatif. Keempat kendala ,

memberikan batas atas pada kenaikan =

yaitu

/

,

=

/

,

= /

,

adalah batas atas terketat dan mengimplikasikan solusi layak diperoleh variabel

= /

dan

menurun, dan ,

,

, diberikan batas tiap variabel

=

= . Variabel

sehingga kendala /

. Dalam meningkatkan masuk menjadi basis dan

keluar menjadi variabel tidak dasar (diberi nilai nol). Dengan cara

substitusi seperti iterasi pertama, maka kamus yang dihasilkan. =

−

+

−

=

−

−

−

=

−

−

+

=

+

−

+

2.14


24

=

−

−

−

,

Kamus layak ini menunjukkan variabel tidak dasar ,

variabel dasar /

= /

,

,

,

=

,

,

(diberi nilai nol) dan

. Jadi solusi layak yang bersesuaian adalah /

,

= /

,

= ,

= ,

Sehingga memenuhi syarat kedua dan ketiga dalam kamus.

= , dan

=

=

.

Pada kamus (2.14) tidak terdapat variabel tidak dasar yang dapat dimasukkan basis. Sedemikian hingga kamus terakhir (2.14) menunjukkan solusi optimal, yaitu ,

=

,

=

dan menghasilkan

ketiga dalam kamus. Untuk setiap pilihan bilangan

,

,

= ,

=

. Hal ini memenuhi syarat kedua dan

,

,

,

dan , berikut pernyataan

ekuivalen yang memenuhi syarat pertama dalam kamus: 1. 2. 3. 4.

,

,

,

,

,

,

dan

merupakan solusi (2.10)

dan


,

,

,

,

,

, ,

dan


,

dan


, ,

, ,

, ,

, ,

, ,

B. Metode Simpleks Direvisi Metode ini menggunakan langkah-langkah yang sama dengan metode simpleks. Perbedaannya terdapat dalam perincian perhitungan variabel masuk dan variabel keluar. Tidak hanya itu untuk masalah yang lebih besar metode simpleks direvisi bekerja lebih cepat dibandingkan dengan metode simpleks. Iterasi dari


25

metode simpleks direvisi kurang dari sama dengan iterasi dari metode simpeks. Kita dapat menuliskan masalah program linear bentuk standar sebagai berikut. Maksimumkan =

Dengan kendala

=

Dimana

dan

=[

,

�

,…,

=

,

,

,…,

⋱

=[

,

, ,

],

].

Setelah ditambahkan dengan variabel pengetat ini menjadi sebagai berikut.

+

,

+

,…,

+

maka masalah

Maksimumkan =

Dengan kendala

(2.15)

= Dimana [

⋱

, + , +

= ], dan

,

,…, =[

+

].

(2.16)

�

,

=

,

,…,

+

,

=


26

Pendekatan umum dari metode simpleks dan metode simpleks direvisi adalah memperoleh suatu urutan solusi-solusi layak yang semakin baik sampai tercapai suatu solusi optimal. Salah satu ciri pokok dari metode simpleks direvisi mencakup dengan cara mana setiap solusi layak akan diselesaikan, yaitu setelah variabelvariabel dasar dan tidak dasar diketahui. Untuk setiap solusi layak dasar dan

∗

,

yaitu

,…,

+

dibagi ke dalam

variabel tidak dasar. Contohnya, membagi vektor

sehingga matriks

terbagi menjadi =

demikian kita dapat menuliskan [

=

Dimana matriks

=[

�,

dan

menjadi

menjadi

�] [

Dengan =

dan

�

−

variabel

menjadi dan

dan �.

Dengan

(2.17)

]=

�] [

�

� �

�

]=

+

� �

adalah nonsingular.

Teorema 2.1 Matriks

adalah nonsingular.

Bukti: Kita tunjukkan bahwa matriks

∗

=

=

adalah nonsingular dengan menunjukkan

tepat memiliki satu solusi. Karena solusi layak dan

∗ �

∗

memenuhi persamaan

= , maka persamaan tersebut memenuhi persamaan

∗

=


27

∗

∗ � �

−

= . Untuk memeriksa bahwa tidak ada solusi lain, dimisalkan

terdapat sebarang solusi layak ̃

sedemikian hingga

Dengan demikian vektor ̃ memenuhi memenuhi

̃=

̃ +

persamaan di kamus yang bersesuaian dengan

maka ̃ =

∗

−

� �

lain adalah vektor −

. Tetapi karena ̃� =

dan ∗

=

−

+

�

−

−

�

dan �.

dapat kita −

akan

menjadi

=

adalah matriks nonsingular maka

selalu ada. Sehingga kita dapat menuliskan persamaan −

∗

= , itu harus

disebut juga matriks basis atau basis. Matriks basis

notasikan menjadi matriks . Karena

−

� ̃�

dan ̃� = .

adalah nonsingular.█

. Jadi, terbukti matriks

Matriks

̃ =

Tentunya

−

tak

yang menentukan nilai dari variabel dasar dan haruslah

. Pada metode simpleks direvisi akan dilakukan dengan iterasi yang terus

berulang sampai diperoleh solusi yang optimal. Di setiap iterasi metode simpleks direvisi, pertama-tama kita memilih variabel masuk lalu mencari variabel keluar dan akhirnya memperbaharui solusi layak. Untuk memilih variabel masuk dengan koefisien positif, maka perhatikan vektor baris

�

−

−

�

. Dalam metode simpleks direvisi, vektor ini dihitung

melalui dua langkah. Pertama, menemukan sistem vektor

�

=

−

. Kedua, menghitung �

�

−

= �

−

dengan menyelesaikan

kemudian dipilih elemen dari

yang paling positif untuk menjadi variabel masuk (kolom ). Jika

semua elemen bernilai negatif maka iterasi berhenti dan solusi optimal.


28

Untuk menentukan variabel keluar, maka variabel masuk dinaikan sebesar �

dari nol sampai suatu nilai positif. Nilai variabel dasar berubah sampai nilai variabel

berubah dari

∗

∗

menjadi

−�

dengan

∗

−� =

keluar.

−

−

merupakan kolom

bersesuaian dengan variabel masuk atau dapat dituliskan elemen yang memenuhi

∗

=

turun ke nol meninggalkan basis. Pada persamaan

=

−

� �,

−

�

yang

. Jika terdapat

maka variabel tersebut menjadi variabel

Berikut iterasi dari metode simpleks direvisi yaitu sebagai berikut. 1.

=

Selesaikan sistem ditemukan vektor .

2.

dimana

adalah matriks basis awal, sehingga

Tentukan kolom yang masuk, yaitu jika variabel tidak dasar dengan elemen

dari

�

dan kolom

dari

Untuk masalah maksimum (minimum), kolom

�,

maka

�

−

berhubungan �

=

dipilih yang memiliki

−

.

−

paling positif (negatif). Untuk masalah maksimum (minimum) jika semua elemen

−

<

( −

> ), maka tidak terdapat kolom masuk dan

iterasi berhenti sehingga didapatkan solusi optimal. Jika tidak, maka lanjut ke langkah 3. = , sehingga didapat vektor .

3.

Selesaikan sistem

4.

Tentukan kenaikan nilai � terbesar dari nol sampai suatu nilai positif dengan cara mencari nilai paling minimum dari

∗

sedemikian hingga

Jika tidak terdapat nilai � atau terdapat elemen di

∗

−�

.

, maka solusi optimal


29

tak terbatas atau tidak memiliki penyelesaian. Jika terdapat elemen yang memenuhi 5.

∗

−� =

maka kolom tersebut menjadi kolom keluar.

Menukar kolom keluar dari

dengan kolom masuk dan tukar variabel keluar

dengan variabel masuk. Lalu kembali pada langkah 1 sampai solusi optimal diperoleh.


30

Berikut diagram alir metode simpleks direvisi.

Awal

Menentukan nilai awal B dan

Menyelesaikan sistem

−

=

∗

.

Mencari vektor a (kolom masuk) yaitu elemen paling positif dari � − � . Apakah semua elemen � − � <0?

Didapat nilai B dan ∗ dengan menggantikan kolom keluar dengan kolom masuk.

Ya

Tidak

Terdapat kolom masuk

Terdapat suatu komponen ∗ − � = 0 yang berkorespondensi dengan kolom keluar.


Ya

=

−

Apakah terdapat kenaikan nilai t terbesar sedemikian hingga ∗ 0? −�

Tidak Tidak terdapat penyelesaian

Akhir Gambar 2.1 : Diagram alir metode simpleks direvisi

Tidak terdapat kolom masuk

Solusi optimal dan didapat nilai B dan yang baru

∗


31

Contoh 2.2 Misalkan diberikan masalah program linear berikut. Maksimumkan

Dengan kendala

+

=

+

+

+

+

+

+

+

,

+

+

+

,

,

+

Ketiga kendala tersebut kemudian diubah ke dalam bentuk persamaan. +

+

+

Dimana

,

dan

+

+

+

+

+

+

+

+

=

=

=

adalah variabel pengetat. Sehingga persamaan di atas dapat

dituliskan dalam bentuk matriks

=[

+

],

=

dengan

=[

], dan

=

. [ ]


32

Setelah iterasi kedua dengan metode simpleks didapatkan kamus berikut. =

− ,

− ,

− ,

+ ,

=

+ ,

− ,

+ ,

+ ,

=

=

− ,

− ,

− ,

+ ,

+ ,

− ,

− ,

− ,

Untuk menekankan fakta bahwa hanya variabel dasar

,

dan

yang tidak

diketahui, maka dapat ditulis seperti persamaan (2.17) dimana

=[ [

], dan

], =[

�

=[

],

= [ ],

�

= [ ],

=[

],

�

=

].

Dengan menggunakan metode simpleks direvisi, penyelesaian dari masalah program linear tersebut yaitu:

Pertama, menentukan matriks awal

[

yaitu matriks

dan vektor

∗

=[

], kemudian mulai iterasi.

Iterasi 1: 1.


=

sehingga diperoleh vektor

, = [ , ].

∗

∗ �] ∗ �

=


33

2.

Tentukan kolom yang masuk dengan menyelesaikan yaitu sebagai berikut

[

�

−

�

=

−

− , , ]=[ ] − , − ,

, ]− [ , ][

Dari hasil tersebut terlihat bahwa terdapat satu elemen yang memenuhi >

yaitu elemen kedua yang berkaitan dengan variabel

−

. Jadi, variabel

adalah variabel masuk dan vektor kolom dari variabel yang terkait

merupakan kolom masuk. = , sehingga didapat vektor

3.

Selesaikan sistem

4.

Didapatkan nilai � =

komponen dari 5.

∗

sedemikian hingga

−� =

Didapat matriks awal

yaitu variabel

∗

, = [ , ]. ,

−�

dan terdapat 1

yang menjadi variabel keluar.

yang baru dengan menukar kolom masuk dengan

kolom keluar yaitu =[

] dan vektor

∗

=[

].

Iterasi 2: =

1.


2.

Tentukan kolom yang masuk dengan menyelesaikan yaitu sebagai berikut

sehingga diperoleh vektor

�

= [ ].

−

�

=

−


34

[

] − [ ][

− ] = [− ] − −

Dari hasil tersebut terlihat bahwa semua elemen memenuhi

−

< . Jadi,

tidak terdapat kolom masuk dan iterasi berhenti sehingga didapatkan solusi optimal yaitu =[

] dan

∗

=[

].

C. Program Linear Bilangan Bulat Pada program linear, solusi dapat berupa pecahan dan bilangan bulat. Namun untuk kasus tertentu solusi mengharuskan untuk berupa bilangan bulat. Contohnya pada masalah transportasi, masalah Knapsack, masalah penjadwalan, masalah pengiriman barang, dan masalah pemotongan persediaan. Program linear dengan solusi bilangan bulat inilah yang disebut sebagai program linear bilangan bulat. Program linear bilangan bulat terdiri dari dua macam yaitu program linear bilangan bulat murni dan program linear bilangan bulat campuran. Program linear bilangan bulat dikatakan program bilangan bulat murni jika semua variabel adalah bilangan bulat. Sedangkan jika sebagian variabelnya bukan bilangan bulat atau sebagian bilangan real maka dapat dikatakan program linear bilangan bulat campuran. Terdapat dua metode untuk menyelesaikan program linear bilangan bulat yaitu metode pemotongan bidang, dan metode pencabangan dan pembatasan. Pada skripsi ini akan dibahas metode pencabangan dan pembatasan untuk menyelesaikan masalah porgram linear bilangan bulat murni.


35

Metode Pencabangan dan Pembatasan (Branch and Bound Method) Metode pencabangan dan pembatasan adalah suatu metode untuk menyelesaikan persoalan program linear bilangan bulat murni dan persoalan program linear bilangan bulat campuran. Metode ini diusulkan pertama kali oleh A. H. Land dan A. G. Doig pada tahun 1960. Metode ini dilakukan dengan melakukan perhitungan satu persatu atau mengenumerasi

semua

nilai

variabelnya

melalui

pencabangan.

Dengan

mengenumerasi semua variabel tersebut, maka diperoleh suatu solusi optimal, yaitu solusi yang meminimumkan atau memaksimumkan fungsi tujuannya. Metode pencabangan dan pembatasan merupakan suatu pendekatan untuk menyelesaikan persoalan yang didasarkan pada pembagian semua solusi layak terhadap sebuah masalah ke dalam sub-masalah yang lebih kecil. Selanjutnya, submasalah ini dapat diselesaikan secara sistematis sampai diperoleh solusi optimal. Cara inilah yang kemudian menjadi dasar metode pencabangan dan pembatasan. Dalam menyelesaikan program linear bilangan bulat menggunakan pencabangan dan pembatasan terdapat 3 langkah utama, yaitu: 1.

Pencabangan Pencabangan dilakukan ketika solusi belum berbentuk bilangan bulat yaitu dengan memecah masalah program linear awal

� menjadi dua bagian yaitu

� dan � dengan menambahkan kendala baru. Dalam pencabangan, kendala

yang ditambahkan merupakan pembulatan ke atas dan pembulatan ke bawah

dari solusi yang masih berbentuk pecahan. Sehingga dari pencabangan tersebut dihasilkan 2 sub-masalah baru, yaitu:


36

a.

� = � +

, dimana

� = � +

, dimana

adalah pembulatan ke bawah dari

solusi program linear berbentuk pecahan. b.

adalah pembulatan ke atas dari solusi

program linear berbentuk pecahan. Proses ini terus berlangsung sampai diperoleh solusi bilangan bulat untuk pertama kalinya. 2.

Pembatasan Pembatasan dilakukan setelah proses pencabangan. Langkah ini untuk membatasi solusi agar didapatkan solusi optimal. Terdapat dua batas pada metode ini yaitu batas bawah dan batas atas. Batas bawah digunakan untuk menyelesaikan masalah maksimum. Jika � menghasilkan solusi bilangan bulat yang lebih baik atau lebih besar dari batas bawah, maka perbarui batas

bawah dengan solusi tersebut. Jika tidak, maka solusi diabaikan dan memilih sub-masalah baru

lalu mengulangi terus sampai semua sub-masalah diteliti

dan diperoleh solusi optimal yaitu batas bawah terakhir. Sedangkan untuk batas atas digunakan untuk menyelesaikan masalah minimum. Jika

�

menghasilkan solusi bilangan bulat yang lebih baik atau lebih kecil dari batas atas, maka perbarui batas atas dengan solusi tersebut. Jika tidak, maka solusi diabaikan dan memilih sub-masalah baru lalu mengulangi terus sampai semua sub-masalah diteliti dan diperoleh solusi optimal yaitu batas atas terakhir. 3.

Penghentian cabang Penghentian cabang dilakukan jika: a.

Sub-masalah tidak memiliki daerah layak,


37

b.

Sub-masalah menghasilkan semua variabel keputusan bernilai bulat, dan

c.

Pada masalah maksimasi, fungsi tujuan tidak lebih besar atau sama dengan nilai batas bawah. Sebaliknya, pada masalah minimisasi, fungsi tujuan tidak lebih kecil atau sama dengan nilai batas atas.

Berikut langkah-langkah metode pencabangan dan pembatasan untuk menyelesaikan program linear dengan solusi bilangan bulat: 1.

Menyelesaikan masalah program linear sampai menghasilkan solusi optimum. Apabila solusi berbentuk bilangan bulat, maka perhitungan dihentikan. Sebaliknya, jika solusi berbentuk bilangan pecahan maka perhitungan dilanjutkan.

2.

Kemudian menambah kendala baru yang membatasi nilai salah satu variabel yang tidak bulat.

3.

Penambahan ini akan berakibat terbelahnya daerah layak menjadi 2 bagian sehingga terbentuklah 2 sub-masalah baru yang kemudian harus diselesaikan. Dengan kata lain, terjadi pencabangan dari masalah aslinya menjadi 2 submasalah baru.

4.

Batas untuk nilai fungsi tujuan kemudian dapat ditentukan. Batas ini dapat digunakan untuk mengeliminasi sub-masalah yang tidak diperlukan dan menentukan apakah solusi optimalnya sudah tercapai.

5.

Jika solusi berbentuk bukan bilangan bulat, maka kembali ke langkah 2. Jika solusi berbentuk bilangan bulat, maka kembali ke langkah 4.


38

Contoh 2.3 Misalkan diberikan masalah program linear awal Minimumkan Dengan kendala

=

+

{ Jawab: 1.

�

sebagai berikut.

+ + dan bilan�an bulat

,

Menyelesaikan masalah program linear tersebut sehingga mendapatkan solusi optimal

= , ,

= , dan

= , . Solusi yang diperoleh tidak berbentuk

bilangan bulat maka lanjut ke langkah 2. 2.

Selanjutnya, masalah program linear bulat di atas dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala

 dan

 . 3.

Sehingga didapatkan dua sub-masalah baru yang harus diselesaikan sebagai berikut. Sub-masalah 1: � = � + ,

Minimumkan

Dengan kendala

dan

=

,

+

{

+ + ,




39

Sub-masalah 2: � = � + ,

Minimumkan

Dengan kendala

4.

=

,

+

{

+ +



,

Batas untuk nilai tujuan belum dapat ditentukan karena belum mendapatkan solusi bilangan bulat.

5.

Dari sub-masalah 1 diperoleh

= ,

= , , dan

= , . Solusi yang

diperoleh tidak berbentuk bilangan bulat maka kembali ke langkah 2.

Langkah 2: Sub-masalah program linear dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala

 dan

 .

Langkah 3: Sehingga didapatkan dua sub-masalah baru yang harus diselesaikan sebagai berikut. Sub-masalah 3: � = � + , Minimumkan

Dengan kendala

=

,

+

+ + {

dan

Sub-masalah 4: � = � + , Minimumkan

=

+

 

, ,


40

Dengan kendala + + {

,

 

Langkah 4: Batas untuk nilai tujuan belum dapat ditentukan karena belum mendapatkan solusi bilangan bulat. Langkah 5: Dari sub-masalah 3 cabang dihentikan karena sub-masalah tidak memiliki daerah layak. Dari sub-masalah 4 diperoleh

= ,

,

= , dan

berbentuk bilangan bulat maka kembali ke langkah 2.

= ,

. Solusi tidak

Langkah 2: Sub-masalah program linear dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala

 dan

 .


Dengan kendala

=

,

+

+ +

dan

{

Sub-masalah 6: � = � + ,

,

  

,


41

Minimumkan Dengan kendala

=

+ + + {

  

,

Langkah 4: Batas untuk nilai tujuan belum dapat ditentukan karena belum mendapatkan solusi bilangan bulat. Langkah 5: Dari sub-masalah 5 diperoleh

= ,

= , , dan

= , .

Solusi yang diperoleh tidak berbentuk bilangan bulat maka kembali ke langkah 2. Langkah 2: Sub-masalah program linear dicabangkan menjadi dua masalah program linear bulat baru dengan menambahkan kendala

 dan

 .


Dengan kendala

=

,

+

+ +

{

,

   


42

dan Sub-masalah 8: � = � + ,

Minimumkan

Dengan kendala

=

,

+

+ +

{

   

,

Langkah 4: Batas untuk nilai tujuan belum dapat ditentukan karena belum mendapatkan solusi bilangan bulat. Langkah 5: Dari sub-masalah 7 cabang dihentikan karena sub-masalah tidak memiliki daerah layak. Dari sub-masalah 8 diperoleh bilangan bulat maka

=

=

= , dan

= . Solusi berbentuk

= ,

= , dan


= , dan


dijadikan sebagai batas atas.

Dari sub-masalah 6 diperoleh bilangan bulat dan

= ,

lebih kecil dari batas atas sebelumnya maka

dijadikan sebagai batas atas yang baru. Dari sub-masalah 2 diperoleh bilangan bulat dan

=

= ,

lebih kecil dari batas atas sebelumnya maka

dijadikan sebagai batas atas yang baru. Jadi, diperoleh solusi optimal yaitu

= ,

= , dan

= .

=

=


43

Berikut gambar pohon pecabangan dari contoh 2.3.

1

2

1

2

Tidak memiliki daerak layak 1

1

2

1

�4

2

= 1,67 2 =2

3

1 2

=3 =0

1

�8

=2 =4

=6

1

1

4

2

= 2,5

�2

Tidak memiliki daerah layak

=1 = 3,6

1

= 3,67

2

�5

�7

= 4,6

2

= 2,5 =0

1

2

= 3,2 �0

3

2

=2 = 1,2

1 2

�1

�3

2

1 2

�6

=2 =2

=4

=3

Gambar 2.2: Pohon pencabangan contoh 2.3 Seperti yang sudah diketahui sebelumnya bahwa program linear bilangan bulat digunakan untuk kasus-kasus tertentu yang mengharuskan solusi berupa bilangan bulat. Salah satu contohnya adalah masalah Knapsack. Pada bagian ini akan dibahas mengenai masalah Knapsack dan penyelesaiannya dengan metode cabang dan batas.

D. Masalah Knapsack Masalah Knapsack adalah masalah program linear bilangan bulat dengan hanya memiliki satu kendala dan solusi berupa bilangan bulat. Masalah Knapsack


44

biasanya digunakan untuk menyusun barang ke dalam karung besar yang tidak dapat memuat semua barang. Permasalahan Knapsack ini mencari solusi terbaik dari semua kemungkinan susunan barang yang akan dimasukkan ke dalam karung. Masalah Knapsack dapat dituliskan sebagai berikut. Maksimumkan Dengan kendala

=∑=

∑ Dimana

=

(2.18)

�

adalah bilangan bulat tak negatif

= , ,...,

banyaknya barang ke- yang dimasukan ke dalam karung,

dan merupakan

adalah ukuran barang

ke-i yang bernilai positif dan � adalah ukuran karung yang bernilai positif.

adalah nilai barang ke-i yang bernilai positif (variabel

Kita asumsikan

dengan

dapat segera dihapus). Perbandingan

⁄

merupakan nilai per

satuan ukuran dari barang ke- atau sebagai efisiensi variabel lagi efisiensi variabel

. Kita asumsikan

diurutkan secara menurun: ⁄

⁄

⁄

(2.19)

Untuk setiap solusi optimal dari masalah Knapsack memenuhi:

�−∑ =

<

(2.20)

Pertidaksamaan (2.20) artinya sisa ukuran dari karung haruslah kurang dari ukuran barang ke-

sehingga

tidak dapat ditingkatkan 1 unit. Solusi-solusi layak dari


45

masalah Knapsack dapat dibuat menjadi pohon enumerasi yang memuat cabangcabang yang merupakan solusi-solusi layak itu sendiri. Untuk membuat suatu cabang, pada setiap cabang dibuat nilai mungkin lalu dilanjutkan pada cabang berikutnya dengan nilai mungkin begitu seterusnya. Secara resmi, dengan membulatkan nilai

sebesar +

sebesar

adalah bilangan bulat yang diperoleh

ke bawah, solusi ini didefinisikan dengan rekursi

(perulangan)

= Dengan = , , . . . ,

−

(2.21)

�−∑ =

dan biasanya,

⁄ = �⁄

. Sekarang mencari solusi terbaik

dan mengganti solusi lain dengan yang lebih baik. Karena sudah didapatkan solusi ,

layak

,…,

, maka solusi layak diperbaharui dengan solusi layak yang lebih

baik. Misalkan solusi terbaik yang didapatkan

∑ =

Jika ∑ = ∗

,

∗

,…,

∗

>

∗

,

,…,

,

∗

,…,

∗

menghasilkan

=

, maka mengganti

dengan

∗

.

dengan ∑ =

dan mengganti

,

Selanjutnya menemukan cabang yang baru dari solusi layak (

dengan didapatkan

=

−

dan tetap mereduksi

sampai

terbesar sedemikian hingga

ditunjukkan bahwa ̅ =

untuk = , , . . . , −

−

>

dan

dan ̅ =

,…,

)

ditemukan. Jika >

maka dapat

− .


46

Berdasarkan (2.19), setiap variabel paling besar

+

⁄

maka

+

∑

+

̅

= +

,

+

∑

+

= +

+

,…,

+

memiliki efisiensi

̅

Oleh karena itu asumsi ∑

�

=

mengimplikasikan ∑

̅

=

∑ =

+

̅ +

+

(� − ∑ =

Kecuali kalau sisi kanan dari persamaan di atas melebihi

̅) , maka tidak ada solusi

̅ , ̅ , … , ̅ yang memiliki kesempatan untuk meningkatkan nilai ∑ =

̅ +

+

+

(� − ∑ =

∗

,

∗

,…,

∗

.

(2.22)

̅)

Jika pertidaksamaan di atas terpenuhi maka ̅ , ̅ , … , ̅

dibuatkan cabang lagi (atau cabang dipotong) dimana koefisien

tidak layak untuk adalah bilangan

bulat positif. Sehingga harus dibuatkan cabang lagi yaitu dengan menemukan terbesar sedemikian hingga untuk = , , . . . , −

dan ̅ =

− dan − .

>

dan ditunjukkan bahwa ̅ =

Jika pertidaksamaan tersebut terpenuhi, maka cabang dapat diperpanjang dan

mulai memeriksa ̅

+

,̅

+

,…, ̅

secara rekursif seperti (2.21) yang mengarah

ke solusi layak ̅ , ̅ , … , ̅ . Iterasi berhenti jika sudah tidak ada cabang lagi yang


47

=

dapat dibuat yaitu ketika

dan

= . Pertidaksamaan (2.22) dapat diganti

bukan bilangan bulat positif menjadi

ketika koefisien

∑

+

̅ +

=

+

(� − ∑

̅)

=

+

Metode ini disebut dengan metode cabang dan batas yang akan ditunjukkan dengan ringkas pada langkah-langkah di bawah. =

= .

1.

Menentukan nilai awal yaitu

2.

Menemukan perpanjangan cabang. Untuk = −

⌊(� − ∑ =

terbaik 3.

∗

∗

,

)⁄

,…,

∗

∗

,

,…,

∗

dengan

Menemukan cabang selanjutnya. Menemukan

a. Jika

b. Jika

=

,

,…,

.

untuk = , , . . . , − .

maka berhenti; selain itu ganti

−

dengan

= , maka kembali ke 4a, selain itu ganti �

̅ + ��+1 (� − ∑ = �+1

bilangan bulat positif) atau ∑ =

koefisien

̅)

dimana

− .

dengan

> . Kita

=

(untuk koefisien �

̅ + ��+1 (� − ∑ = �+1

=

dengan ∑ =

Pencarian cabang yang lebih baik. Jika ∑ =

maka

. Maka didapat solusi

, maka mengganti

terbesar sedemikian hingga

dapat tuliskan ̅ =

5.

.

>

+ , + ,...,

= �⁄

⌋. Biasanya untuk

Memperbaiki solusi. Jika ∑ =

dan mengganti 4.

∗

dan

̅)

− . bukan

+

(untuk

bilangan bulat positif) maka ̅ , ̅ , … , ̅ tidak layak diperiksa.

Oleh karena itu, harus kembali ke langkah 4. Selain itu, kembali ke langkah 2.


48

Berikut diagram alir masalah Knapsack dengan penyelesaian cabang dan batas.


49

Awal Menentukan nilai awal yaitu = 0 dan = 0.

Menentukan perpanjangan cabang. Untuk = + 1, + 2, . . . , maka −1 = ⌊(� − ∑ =1 dan )⁄ ⌋ didapat solusi terbaik 1∗ , 2∗ , … , ∗ .

M Tidak berubah

Tidak

Apakah ∑ =1

> ?

Ya

Mengganti M dengan ∑ =1 Mengganti solusi sebelumnya ( 1∗ , 2∗ , … , ∗ ) dengan 1, 2, … , .

Tidak

Ya

Apakah ∑ =1 ̅ + +1 (� − ∑ =1 ̅ )

?

+1

Tidak

Apakah terdapat = 0 dan = 1?

Ya

Mereduksi k sampai diperoleh > 0 lalu mengganti Tidak dengan ̅ = − 1, dimana ̅ = untuk = 1, 2, . . . , − 1.

Apakah koefisien bilangan bulat positif?

Vektor a

Akhir

Gambar 2.2: Diagram alir masalah Knapsack Contoh 2.4

Ya

Apakah ∑ =1 ̅ + +1 (� − ∑ =1 ̅ ) +1

+1?

Ya

Tidak


50

Maksimumkan +

Dengan kendala +

,

Jawab:

+

,

+

1.


2.

Menemukan cabang. Untuk = =

⁄

,

−

= .

dan

+ , + ,...,

maka

⁄

−∑

)⁄

⌋=

−

, .

= ⌊(

−∑

)⁄

⌋=

−

, . +

, .

= ⌊(

−∑

)⁄

⌋=

−

, . +

, . +

=

−

=

−

=

∗

= ,

∗

∗

=

=

∗

,

= ⁄

= ⁄

.

= .

=

Menentukan apakah solusi yang diperoleh meningkat?

diganti menjadi

=

Didapatkan k=3 , maka kita ganti

5.

+

= ⌊(

Karena ∑ =

4.

=

=

Maka didapat solusi terbaik 3.

+

>

= , =

=

= , maka

=

=

=

dan

= .

∗

= ,

∗

=

∗

=

lalu dikurangkan sampai diperoleh k=1 dimana menjadi ̅ = .

∗

= >

Apakah cabang layak untuk dibuatkan cabang lagi? Karena koefisien

bukan bilangan bulat positif, maka kita uji pertidaksamaan

berikut dengan k=1 dan ̅ = .


51

∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

. + +

+

/ ,

+

=

=

−

, .

= ,

>

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2 2.

3.

Diketahui k=1 dan −∑

̅ )⁄

⌋=

−

, .

= ⌊(

−∑

̅ )⁄

⌋=

−

, . +

, .

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

, . +

, . +

=

−

=

−

=

Karena ∑ = =

∗

=

= ,

>

diganti menjadi

Didapatkan k=3

=

= , maka

= ,

= ,

,

= ,

= ,

= ⁄

dan = .

= . )⁄ ∗

⌋

= ,

lalu dikurangkan sampai diperoleh k=2 dimana

diperoleh. Maka kita ganti 5.

⁄

= ⌊(

=

∗

4.

−

= ̅ = , maka diperoleh

=

dengan ̅ = .

Apakah cabang layak untuk dibuatkan cabang lagi?

∗

= >


52

Karena koefisien


berikut dengan k=2 dan ̅ = , ̅ = . ∑ =

∑

̅ +

=

+

̅ +

( . + . )+

+

+

̅)

=

(

−

+

̅)

=

(� − ∑

+

/

(� − ∑

,

, . + =

, . )

,

,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4 4.

diperoleh 5.

=

Didapatkan k=2

lalu dikurangkan sampai diperoleh k=1 dengan

> . Maka kita ganti

=

dengan ̅ = .



berikut dengan k=1 dan ̅ = . ∑ =

∑ =

̅ + ̅ +

( . )+ +

+

+

+

+

/ ( , ,

(� − ∑ =

(� − ∑ =

− = ,

̅) ̅)

,

, . )

, ,


53

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. > , maka kita ganti

4.

Kita peroleh k=1 dimana

5.


=

dengan ̅ = .



∑ =

+

̅ + ̅ +

( . )+

+

+

+

/ ( ,

(� − ∑

̅)

=

(� − ∑ =

−

̅)

,

, . )

,

= ,

,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. 4.

Kita peroleh k=1 dan

= , maka iterasi berhenti.

Jadi didapatkan solusi optimal yaitu ,

.

∗

= ,

∗

= ,

∗

= ,

∗

=

dan

Berikut pohon enumerasi dari solusi-solusi yang sudah didapat diatas.

=


54

=

=

=

=

=

=

=

=

=

dipotong

=

dipotong

=

dipotong

Gambar 2.4: Pohon enumerasi yang dihasilkan dari contoh 2.4


=

Dengan kendala ,

Jawab:

+

,

1.


2.

Menemukan cabang. Untuk = =

⁄

,

−

+ +

=

=

+ +

dan

= .

+ , + ,...,

maka

⁄

= ⌊(

−∑

)⁄

⌋=

−

, .

= ⌊(

−∑

)⁄

⌋=

−

, . +

=

−

=

, , .

= ⁄

=


55

= ⌊(

−

−∑

)⁄

=

⌋= ∗


diganti menjadi

=

Didapatkan k=3 , maka kita ganti

5.

∗

∗

=

, . + ∗

=

, . +

⁄

.

= .

=

Menentukan apakah solusi yang diperoleh meningkat? Karena ∑ =

4.

= ,

−

>

= , =

= , maka

=

=

=

dan

∗

= .

= ,

∗

=

∗

=


=

menjadi

= .

∗

= >



berikut dengan k=1 dan ̅ = . ∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

( −∑

̅)

=

=

. + +

+

/ ,

+

=

=

−

, .

= ,

>


Diketahui k=1 dan = ⌊(

−

−∑ =

= ̅ = , maka diperoleh ̅ )⁄

⌋=

−

, .

⁄

,

=


56

3.

−∑

̅ )⁄

⌋=

−

, . +

, .

= ⌊(

−∑

̅ )⁄

⌋=

−

, . +

, . +

=

−

=

∗

=

=

= ,

dengan

=

Didapatkan k=3

>

= ,

= , maka

= ,

= ,

= ,

= .

dan

∗

⁄

= .

= ,


=

. Maka kita ganti 5.

⁄

= ⌊(

Karena ∑ = ∗

4.

−

dengan ̅ = .

=

∗

= >



berikut dengan k=2 dan ̅ = , ̅ = . ∑ =

∑ =

+

̅ + ̅ +

( . + . )+

+

+

/

+

(

+

(� − ∑

̅)

=

(� − ∑

̅)

=

−

, . +

= ,

, , . )

,

> ,


Diketahui k=2, = ⌊(

−

−∑ =

=̅ =

dan

̅ )⁄

⌋=

= ̅ = , maka diperoleh −

, . +

, .

⁄

=


57

= ⌊(

3.

Karena ∑ = ,

∗

= ,

−

−∑ =

∗

=

̅ )⁄

⌋=

= ,

> ∗

dengan

= , ∗

= ,

−

, . +

, . +

= ,

, maka ∗

= ,

> , maka kita ganti

∗

= ,

=

4.

Didapatkan k=3 dan

5.


. dan

= .

∗

⁄ = ,

=

∗

=

menjadi ̅ = .


berikut dengan k=3 dan ̅ = , ̅ = , ̅ = . ∑ =

∑ =

+

̅ + ̅ +

( . + . + . )+

/

+

+

+

(� − ∑ =

(� − ∑ =

(

−

+

̅) ̅)

,

, . +

, . +

= ,

. )

,

,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. > , maka kita ganti

=

4.

Didapatkan k=3 dan

5.


menjadi ̅ = .



̅ +

+

+

(� − ∑ =

̅)


58

∑ =

+

̅ +

( . + . + . )+

(� − ∑

+

/

)

=

(

−

+

,

, . +

= ,

, . +

. )

,

,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. 4.

dan kita ganti 5.

=

Didapatkan k=3

=

lalu dikurangkan sampai diperoleh k=1 dimana dengan ̅ = .

>




∑ =

+

̅ + ̅ +

( . )+ +

+

+

+

/ ( , ,

(� − ∑ =

(� − ∑

)

=

−

̅) ,

, . )

,

= ,

,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. <

=

4.

Kita peroleh k=1 dengan

5.


dan kita ganti

dengan ̅ = .


59

Karena koefisien



∑ =

+

̅ + ̅ +

( . )+

+

+

+

/ ( ,

(� − ∑

̅)

=

(� − ∑

̅)

=

−

, . )

= ,

, ,

,


Kita peroleh k=1 dengan

=

maka iterasi berhenti.

Jadi didapatkan solusi optimal yaitu ,

.

∗

= ,

∗

= ,

∗

= ,

∗

=

dan

=


60

Berikut pohon enumerasi dari solusi-solusi yang sudah didapat diatas. =

=

=

=

=

=

=

=

dipotong

=

dipotong

=

=

=

=

=

=

dipotong

dipotong



Dengan kendala ,

Jawab:

+

+

,

+

+

+

Dengan langkah-langkah seperti contoh sebelumnya didapatkan solusi yaitu ∗

= ,

dengan

∗

= ,

∗

= , dan

= , ∗

∗

= ,

=

∗

dengan = ,

∗

= ,

= , ∗

=

∗

= ,

dengan

∗

= ,

= .

∗

= ,

∗

=


61


=

=

=

=

=

=

= =

=

=

dipotong

=

=

=

=

=

dipotong

=

dipotong

=

=

=

=

=

dipotong

=

dipotong

=

dipotong

=

dipotong

dipotong


=


BAB III MASALAH PEMOTONGAN PERSEDIAAN

A. Masalah Pemotongan Persediaan (Cutting Stock Problem) Dalam suatu industri kertas, mesin kertas (paper machine) memproduksi rol kertas jumbo, dengan lebar maksimum yang sudah ditetapkan yang disebut dengan deckle. Kemudian rol jumbo melewati beberapa proses produksi dalam memenuhi pesanan. Salah satu proses produksi yang paling penting adalah pemotongan rol kertas jumbo menjadi rol yang lebih kecil atau potongan kertas persegi panjang. Proses pemotongan tersebut harus dapat meminimumkan jumlah rol jumbo yang akan dipotong. Sebelum proses pemotongan berlangsung, hal yang dilakukan adalah membuat pola pemotongan pada rol jumbo. Pada masalah nyata, untuk menemukan pola pemotongan yang optimal biasanya dilakukan secara manual yaitu dengan membuat semua kemungkinan pola pemotongan lalu menentukan jumlah rol yang akan dipotong pada masing-masing pola sampai semua pesanan terpenuhi. Pola pemotongan pada rol jumbo dapat berupa pola pemotongan untuk rol ke rol (satu dimensi) atau rol ke potongan kertas (dua dimensi). Proses pemotongan satu dimensi dan dua dimensi dapat dilihat pada gambar 1.1 dan 1.3. Pada tulisan ini akan dibahas tentang pemotongan rol jumbo menjadi potongan rol kecil dengan ukuran yang bervariasi (pola pemotongan satu dimensi). Misalkan terdapat

kemungkinan pola pemotongan untuk rol jumbo dengan

lebar �, rol kecil memiliki lebar

untuk = , … ,

61

, dan � adalah banyaknya rol


62

kecil dengan lebar

(� bilangan bulat tak negatif) sehingga ∑ = �

�. Maka

masalah pemotongan ini dapat diselesaikan dalam program linear sebagai berikut. Minimumkan (3.1)

=∑ =

Dengan kendala

(3.2)

∑� =

dan � adalah banyaknya rol kecil dengan lebar

dalam pola pemotongan ke-j,

adalah banyaknya permintaan rol kecil dengan lebar

, variabel

menunjukkan

banyaknya rol jumbo yang dipotong pada pemotongan ke- . Berikut gambar pemotongan satu dimensi dari rol jumbo menjadi rol kecil.

Gambar 3.1:Pemotongan rol jumbo menjadi beberapa bagian (rol kecil). Masalah program linear dalam contoh 1.1 dapat diselesaikan dengan metode simpleks yang telah diberikan pada bab sebelumnya. Tetapi karena variabel yang terlibat dalam model cukup banyak maka masalah tersebut akan diselesaikan


63

dengan program QM for Windows yang merupakan perangkat lunak digunakan untuk membantu proses perhitungan secara teknis pengambilan keputusan secara kuantitatif. Program ini menyediakan modul-modul dalam area pengambilan keputusan bisnis seperti assignment, forecasting, integer programming, linear programming, quality control, inventory, dan lain-lain. Berikut adalah hasil yang didapat menggunakan QM.

Gambar 3.2: Hasil QM pada contoh 1.1 Dari gambar di atas, didapatkan solusi optimal yaitu =

=

, ,

=

,

,

, , dan selainnya bernilai 0. Itu berarti untuk memenuhi pesanan

diperlukan rol sebanyak 48,5 untuk pola pemotongan pertama, 206,25 rol untuk pola pemotongan kelima, dan 197,5 rol untuk pola pemotongan keenam. Dengan demikian, banyaknya rol jumbo yang digunakan sebanyak 452,25 rol. Namun, pada masalah nyata di industri kertas, banyaknya dan jenis pesanan akan sangat beragam sehingga masalah ini tidak mungkin diselesaikan secara


64

manual (menyusun tabel kemungkinan pemotongan kemudian diselesaikan dengan program linear). Masalah lain yang mungkin muncul dan tidak mudah diselesaikan adalah solusi yang didapatkan belum tentu merupakan bilangan bulat sehingga diperlukan cara tertentu untuk mengubah solusi tersebut menjadi bilangan bulat. Dalam kasus rol kecil yang dipesan dengan jumlah yang tidak banyak, maka pola yang digunakan pada solusi optimal bilangan bulat mungkin berbeda dengan solusi optimal aslinya (dalam pecahan). Oleh karena itu, skripsi ini menggunakan metode penghasil kolom (column generation) yang dapat menyelesaikan masalah pemotongan secara lebih efisien.

B. Metode Penghasil Kolom Metode penghasil kolom adalah suatu metode untuk menemukan himpunan dari pola pemotongan optimum pada masalah pemotongan persediaan. Dalam metode ini, pada dasarnya, setiap pola merupakan suatu kolom dari masalah program linearnya. Pada masalah nyata, banyaknya pola pemotongan dapat menjadi sangat banyak. Daripada mempertimbangkan banyaknya kemungkinan pola pemotongan, metode penghasil kolom bekerja dengan membangun suatu model bagian dari masalah pemotongan persediaan yang secara sistematis menghasilkan pola baru sehingga solusi optimum dapat dicapai. Pola baru ini ditambahkan ke model bagian dengan program bantuan bilangan bulat. Model bagian pemotongan persediaan dapat dimulai dengan banyak cara. Pilihan termudah adalah memasukkan satu pola untuk setiap ukuran rol. Setiap pola terdiri dari maksimum banyaknya rol yang dapat dipotong dari rol jumbo.


65

Diasumsikan terdapat beberapa pola pemotongan model bagian pemotongan persediaan. Misalkan

�

yang bukan bagian dari

komponen dari vektor

�.

Setiap komponen berkorespondensi dengan banyaknya rol ukuran yang digunakan

adalah koefisien pada fungsi tujuan yang

pada pola pemotongan. Misalkan

berhubungan dengan setiap keperluan permintaan pada model bagian pemotongan persediaan. Maka pola pemotongan sewaktu-waktu adalah

� �

yang harus ditambahkan ke model bagian

−∑ =

<

Kondisi ini adalah syarat optimal pada metode simpleks direvisi ketika diaplikasikan ke model pola pemotongan persediaan. Perhatikan masalah pemotongan persediaan dimana rol jumbo berukuran �

dan banyaknya pesanan tiap rol kecil

= , ,…,

dengan lebar

. Maka

masalah pemotongan persediaan dengan metode penghasil kolom dapat dimodelkan sebagai berikut. Minimumkan Dengan kendala Dimana

= ,

adalah vektor kolom dengan komponen

vektor baris dengan komponen , , . . . , . Setiap kolom

�

,

=[

,…, ,

menunjukkan pola pemotongan rol jumbo menjadi rol kecil = , ,…,

. Jadi

�

adalah kolom dari

jika hanya jika

adalah bilangan bulat tak negatif sedemikian hingga ∑

dan adalah ,…,

�

] dari

dengan lebar ,

,…,

�. Dengan metode


66

simpleks yang direvisi ditunjukkan adanya kolom tidak dasar dari dari setiap iterasi, yaitu ketika kolom baru menghitung vektor baris ,

,…,

�

di langkah 2

(kolom masuk) ditemukan. Setelah

(harus berupa bilangan bulat tak negatif), kita mencari

bilangan bulat tak negatif sedemikian hingga , untuk setiap bilangan bulat �

∑ =

−∑ =

Ketika ∑�=

(3.4)

�

�

(3.3)

(3.5)

<

> , maka pertidaksamaan (3.5) terpenuhi. Pertidaksamaan

ini dapat ditulis sebagai fungsi tujuan dengan kendala pertama dan kedua dari formulasi model (3.3) dan (3.4) di atas. Ketika nilai optimal dari program matematika lebih besar dari satu, maka pola pemotongan ditemukan. Ketika nilai optimal kurang dari atau sama dengan satu, maka tidak terdapat pola pemotongan yang dapat meningkatkan nilai tujuan dari masalah pemotongan persediaan. Sehingga model penghasil pola pemotongan dapat dituliskan sebagai berikut. Maksimumkan Dengan kendala

=∑=

∑ =

�

, untuk setiap bilangan bulat Model ini yang nantinya akan diselesaikan menggunakan masalah Knapsack.


67

Dalam menyelesaikan masalah pemotongan persediaan dengan metode simpleks direvisi yang menggunakan metode penghasil kolom, perlu diawali dengan solusi layak terdekat: jika nilai awal dari fungsi tujuan dekat dengan nilai optimum, maka banyaknya iterasi simpleks yang diperlukan untuk mencapai optimum sedikit.

Mencari Nilai Awal

lebar

Misalkan rol jumbo dengan lebar � dan banyaknya pesanan rol kecil dengan adalah

. Diasumsikan lebar rol kecil diurutkan dari terbesar sampai

terkecil:

Akan dibentuk nilai awal diketahui � terdiri

�, terdapat

′

− +

dan

>

∗

>

dengan

iterasi. Dimulai iterasi ,

dari subscript , , . . . ,

. Untuk setiap subscript di

yang menunjukkan sisa permintaan rol kecil dengan lebar

nilai awal kita tentukan kolom ke-j dengan

Solusi awal terpenuhi. Nilai ′

⁄

′

=

=[ , =

terkecil dari

>

∗

untuk setiap i). Pada iterasi ke-j, kita definisikan ]� yang akan membentuk .

,…, −

{

(untuk

�−∑ =

, jika

⁄

�

, jika

�

akan menggunakan pola ini sampai sisa permintaan

berkorespondensi dengan kolom ke-j dari dengan

� dan

> . Sehingga

′

dan merupakan nilai ′

untuk setiap


68

� dan

=

�, mengganti

′ ′

�. Kemudian hapus subscript

untuk paling tidak suatu ′

dengan

−

dari

, dan memulai proses iterasi ke + .

Contoh 3.1 Misalkan rol jumbo ukuran 91 inchi dengan pesanan berikut: 78 rol kecil berukuran 25,5 inchi, 40 rol kecil berukuran 22,5 inchi, 30 rol kecil berukuran 20 inchi, dan 30 rol kecil berukuran 15 inchi. Pertama, kita urutkan lebar rol kecil dari yang terbesar sampai terkecil sehingga diperoleh Tabel 3.1 : Pesanan rol contoh 3.1 yang sudah diurutkan (inchi)

(rol)

25,5

78

22,5

40

20

30

15

30

Iterasi 1. Diketahui Karena

= , =

�, maka kita peroleh

= ⌊(

−∑ =

dan R terdiri dari 4 subscript (i=1,2,3,4).

=

⁄

)⁄

⌋=

,

= −

, . ⁄

,

=


69

= ⌊( = ⌊(

� dan

−

. =

)⁄

=

−∑ > ′

,

maka =

=

′

� dan

=

⌋= ′⁄

= ⌊(

−

. =

setiap −

. =

)⁄

=

)⁄

=

> ,

⁄

, . + , . + +

/ =

= ⁄

= ′

. Sehingga

untuk

=

−

. =

′

.

=

dan R terdiri dari 3 subscript (i=2,3,4).

� maka diperoleh

−∑

� dan

′

,

= , =

−∑

Karena

− =

=

⁄

= = ⌊(

−

. Jadi kita hapus subscript k=1 dari R dan diperoleh


⌋=

)⁄

=

Karena setiap

−∑

′

maka =

=

′

⌋=

⌋= =

= −

−

′⁄

,

=

, . + , . +

/ =

, .

, . + . Sehingga

⁄ .

= ⁄

= ′

untuk


−

. =

.

′

=


70

= , =


,

� dan

� maka diperoleh =

= = ⌊(

−∑

setiap

)⁄

=

Karena � dan

− , . =

> .

=

′

� dan

⌋= =

maka

′⁄

= /

− =

= , . +

, . +

.

⁄

= ′

/ = , . Sehingga

untuk


= , =

Iterasi 4. Diketahui , ,

dan R terdiri dari 2 subscript (i=3,4).

� maka diperoleh

=

=

Karena

−∑ =

>

)⁄ maka

⌋= =

′⁄

=

dan R terdiri dari 1 subscript (i=4). Karena

=

= ⌊(

′

− =

, . + / = .

Jadi diperoleh solusi layak sebagai berikut.

, . +

.

⁄

=


71

=[

] dan

∗

=[

,

].

Langkah-langkah dari metode penghasil kolom merupakan gabungan dari langkah metode simpleks direvisi dengan Knapsack yaitu: 1.

Menyelesaikan masalah dengan metode simpleks direvisi.

2.

Pada langkah kedua di setiap iterasi metode simpleks direvisi dihitung dengan metode cabang dan batas masalah Knapsack. Berikut diagram dari metode penghasil kolom. 1. Menyelesaikan masalah metode simpleks direvisi.

dengan

2. Pada langkah 2 metode simpleks direvisi menggunakan metode cabang dan batas masalah knapsack. Gambar 3.3: Diagram alir metode penghasil kolom

Contoh 3.2 Misalkan rol jumbo ukuran 91 inchi dengan pesanan berikut: 78 rol kecil berukuran 25,5 inchi, 40 rol kecil berukuran 22,5 inchi, 30 rol kecil berukuran 20 inchi, dan 30 rol kecil berukuran 15 inchi. Kita dapat memulainya dengan metode simpleks direvisi dengan nilai awal yang sudah didapatkan pada contoh 3.1 sebagai berikut


72

=[

∗

] dan

=[

,

]

Kemudian kita memulai iterasi pertama yang dilakukan melalui langkahlangkah berikut. 1.


2.

[ , , , ].

= [ , , , ], sehingga diperoleh nilai

Mencari bilangan bulat tak negatif +

,

+

,

,

+

,

+

, +

=

sedemikian hingga +

>

Masalah di atas sudah diselesaikan pada bab sebelumnya (lihat contoh 2.5) dan diperoleh

3. 4.

[ , , , ]� . Karena ∑�=

= , >

= ,

maka

=

= [ , , , ]� menjadi kolom masuk.

Mencari kenaikan nilai � terbesar sedemikian hingga karena

−

=[

,

Sehingga kita mendapatkan

=[

] dan

∗

�

=[ , , , ] .

−�

. Didapatkan

⁄ dan , ⁄ . Kolom ketiga adalah kolom keluar

dari perbandingan ∗

=

atau dapat ditulis

= , sehingga didapat vektor


�=

5.

= ,

∗

, , ]� .

=[

− �/ �

]=[

]

Kemudian dapat dimulai iterasi kedua yaitu sebagai berikut


73

1.


2.

[ , , , ].

= [ , , , ], sehingga diperoleh nilai ,

Mencari bilangan bulat tak negatif ,

+

+

,

+

,

+

, +

=

sedemikian hingga +

>

Masalah di atas sudah diselesaikan pada bab sebelumnya (lihat contoh 2.4) = ,

dan diperoleh

3. 4.

[ , , , ]� . Karena ∑�=

>

= ,

maka

=

atau dapat ditulis

Mencari kenaikan nilai � terbesar sedemikian hingga ⁄ ,

dari perbandingan

keluar karena

∗

−

=[ , ,


=[

] dan

∗

=[

,

=




�=

5.

= ,

∗

�

=[ , , , ] .

−�

. Didapatkan

⁄ dan ⁄ . Kolom pertama adalah kolom ]� .

� − �/

]=[

− �/

]

Kemudian dilanjutkan iterasi ketiga yaitu sebagai berikut. 1.


2.

[ , ,


, ].

Mencari bilangan bulat tak negatif ,

+

,

,

+

,

,

sedemikian hingga +

=


74

+

+

+

>

Masalah di atas sudah diselesaikan pada bab sebelumnya (lihat contoh 2.6) = ,

dan diperoleh Karena ∑�=

=

= ,

maka

= ,

=

= [ , , , ]� .

atau dapat ditulis

= [ , , , ]� tidak dapat menjadi kolom masuk. Jadi,

iterasi berhenti dan didapatkan solusi

dan

∗

yang optimal.

Sehingga didapatkan pola pemotongan sebagai berikut dimana semua permintaan dapat terpenuhi. Tabel 3.2: Hasil pola pemotongan contoh 3.2 Lebar rol Pola Banyak rol pemotongan ke-

25,5

22,5

20

15

1

2

1

0

1

24

2

0

4

0

0

4

3

2

0

2

0

15

4

0

0

0

6

1

Perbandingan hasil perhitungan contoh 3.2 dengan menggunakan metode penghasil kolom (A), program QM (B), toolbox Optimization pada MATLAB (C), dan toolbox Solver pada Excel (D). Tabel 3.3: Perbandingan hasil perhitungan contoh 3.2 Lebar rol Sisa A B Pola 25.5 22.5 20 15 (inchi) (roll) (roll)

C

D

(roll)

(roll)

1

2

1

0

1

2.5

24

24

24

24

2

2

0

2

0

0

15

15

15

15

3

0

4

0

0

1

4

4

4

4


75

4

0

0

0

Jumlah rol

6

1

1

1

1

1

44

44

44

44

Dari tabel di atas dapat disimpulkan sebagai berikut. Tabel 3.4: Kesimpulan dari perbandingan perhitungan contoh 3.2 Metode Hasil yang didapat Kelebihan dan Kelemahan Penghasil

Pesanan untuk lebar rol 25,5 1. Semua

Kolom

inchi terpenuhi yaitu 78 rol,

pesanan

dapat

terpenuhi.

pesanan rol 22,5 inchi terpenuhi 2. Sisa

yang

dihasilkan

yaitu 40 rol, pesanan rol 20

kurang dari sama dengan


lebar minimum pesanan

pesanan rol 42 inchi terpenuhi

rol.

yaitu 30 rol. Program QM Pesanan untuk lebar rol 25,5 1. Semua inchi terpenuhi yaitu 78 rol,

pesanan

dapat

terpenuhi.


yang

dihasilkan






rol.

yaitu 30 rol. Toolbox


Optimization inchi terpenuhi yaitu 78 rol,

pesanan

dapat

terpe-nuhi.

pada


MATLAB


yang

dihasilkan



76




rol.

yaitu 30 rol. Toolbox


Solver pada inchi terpenuhi yaitu 78 rol, Excel

pesanan

dapat

terpenuhi.


yang

dihasilkan






rol.

yaitu 30 rol.

Contoh 3.3 Sekarang kita selesaikan contoh 1.1 menggunakan metode penghasil kolom sehingga didapatkan pola pemotongan sebagai berikut dimana semua permintaan dapat terpenuhi. Tabel 3.5: Hasil pola pemotongan contoh 3.3 Lebar rol Pola

Banyak

pemotongan ke-

135

108

93

42

rol

1

2

0

0

0

48,5

2

0

2

0

2

105,5

3

0

2

0

0

100,75

4

0

1

2

0

197,5


77

Perbandingan hasil perhitungan contoh 3.3 dengan menggunakan metode penghasil kolom (A), program QM (B), toolbox Optimization pada MATLAB (C), dan toolbox Solver pada Excel (D). Tabel 3.6: Perbandingan hasil perhitungan contoh 3.3 Lebar rol Sisa A B Pola (roll) 135 108 93 42 (cm) (roll)

C

D

(roll)

(roll)

1

2

0

0

0

30

48,5

48,5

48,5

48,5

2

0

2

0

2

0

105,5

206,5

206,5

206,5

3

0

1

2

0

6

197,5

197,5

197,5

197,5

4

0

2

0

0

84

100,75

0

0

0

Jumlah rol

452,25 452,25 452,25 452,25

Dari tabel di atas dapat disimpulkan sebagai berikut. Tabel 3.7: Kesimpulan dari perbandingan perhitungan contoh 3.3 Metode Hasil yang didapat Kelebihan dan Kelemahan Penghasil

Pesanan untuk lebar rol 135 cm 1. Semua pesanan dapat terpe-

Kolom

terpenuhi yaitu 97 rol, pesanan

nuhi dengan jumlah yang

rol 108 cm terpenuhi yaitu 610

tepat/tidak berlebih.

rol, pesanan rol 93 cm terpenuhi 2. Namun terdapat pola (pola yaitu 395 rol, pesanan rol 42 cm

4) yang menghasilkan sisa

terpenuhi yaitu 211 rol.

dengan lebar melebih dari lebar minimum pesanan rol.

Program QM Pesanan untuk lebar rol 135 cm 1. Semua pesanan dapat terpeterpenuhi yaitu 97 rol, pesanan

nuhi. Namun pada pesanan

rol 108 cm terpenuhi yaitu

rol 42 cm dan 120 cm


78

610,5 rol, pesanan rol 93 cm

menghasilkan


melebihi pesanan.

rol 42 cm terpenuhi yaitu 413 2. Sisa rol.

yang

rol

yang

dihasilkan

kurang dari sama dengan lebar mi-nimum pesanan rol.

Toolbox


Optimization terpenuhi yaitu 97 rol, pesanan


pada



MATLAB


menghasilkan


melebihi pesanan.


yang

rol

yang

dihasilkan

kurang dari sama dengan lebar minimum pesanan rol.

Toolbox


Solver pada terpenuhi yaitu 97 rol, pesanan


Excel




menghasilkan


melebihi pesanan.


yang

rol

yang

dihasilkan



79

lebar minimum pesanan rol.

Dari contoh 3.2 dan 3.3 di atas dapat disimpulkan bahwa masing-masing metode mempunyai kelebihan dan kelemahan. Tabel 3.8: Kelebihan dan kelemahan metode penghasil kolom, program QM, toolbox Optimization pada MATLAB, dan toolbox Solver pada Excel. Metode Kelebihan Kelemahan Penghasil kolom 1. Semua

pesanan

dapat 1. Terdapat

sisa

yang

dari

lebar

terpe-nuhi dengan jumlah

melebihi

yang tepat/tidak berlebih.

minimum pesanan rol.

2. Tidak perlu membentuk 2. Solusi belum tentu berupa semua pola kemungkinan. Program

QM, 1. Sisa

yang

bilangan bulat.

dihasilkan 1. Jumlah rol yang dihasil-

toolbox


kan dapat melebihi jumlah

Optimization


rol yang diminta/dipesan.

pada MATLAB,

rol.

dan

toolbox

Solver

pada

Excel

2. Harus membentuk semua pola kemungkinan. 3. Solusi belum tentu berupa bilangan bulat.

Solusi dari contoh 3.3 bukan bilangan bulat, maka diperlukan suatu metode untuk memberikan solusi berupa bilangan bulat. Metode yang digunakan adalah first-fit decreasing.


80

Metode First-Fit Decreasing Pada itersi ke-j dari metode ini yaitu menemukan pola pemotongan rol jumbo ke-j. Iterasi dimulai dengan sisa permintaan setelah jumlah rol dibulatkan ke bawah yaitu

′

′

,

,…,

′

. Pola pemotongan yang dihasilkan untuk setiap iterasi yaitu

= min Untuk = , , … ,

−

{

′

�−∑

⁄

=

, kemudian ganti setiap nilai

′

dengan

proses iterasi ke-j+1.

′

−

dan lanjutkan

Contoh 3.4 Mencari solusi bilangan bulat untuk contoh 3.3. Diketahui hasil yang diperoleh dengan metode penghasil kolom yaitu pada tabel 3.5. Karena solusi belum bernilai bilangan bulat, maka dengan menggunakan metode first-fit decreasing solusi diubah menjadi bilangan bulat. Pertama, semua solusi yang diperoleh dibulatkan ke bawah. Sehingga untuk pola 1 memerlukan 48 rol, pola 2 memerlukan 105 rol, pola 3 memerlukan 100 rol, dan pola 4 memerlukan 197 rol. Karena semua solusi dibulatkan ke bawah, maka jumlah produksi rol pesanan kurang atau sama dengan permintaan rol. Tabel 3.9: Hasil pembulatan ke bawah solusi contoh 3.3 Lebar Permintaan Produksi (setelah Sisa ( ′ ) Rol (

)

135 cm

( )

dibulatkan ke bawah)

97 rol

96 rol

1 rol


81

108 cm

610 rol

607 rol

3 rol

93 cm

395 rol

394 rol

1 rol

42 cm

211 rol

210 rol

1 rol

Iterasi 1 Diketahui = min {

′

= ,

�⁄

= min {

′

′

= ,

′

= min {

=

′

= min { ⌊(� − ∑ =

= min { =

=

−

Sehingga didapatkan

= min { =

)⁄

⌋

)⁄

⌋

)⁄

⌋

= min { = min {

−

. ⁄

−

. +

′

= min { ⌊(� − ∑ = min {

= .

⁄

′

⌊(� − ∑

′

= ,

′

. +

= ,

′

. +

= ,

′

. ⁄

= ,

′

= min { =

= .

Iterasi 2 = min {

�⁄

′

= min {

⁄

= min { =

= min { =

. ⁄


82

′

= min { ⌊(� − ∑ =

′

= min { ⌊(� − ∑ =

= min { =

=

−

Sehingga didapatkan

⌋

)⁄

⌋

)⁄

⌋

= min {

−

= min {

−

. ⁄ . +

= min { =

. ⁄

′

= min { ⌊(� − ∑ = min {

)⁄

′

. +

= ,

′

. +

= ,

′

. ⁄

= ,

′

= min { =

= .

Iterasi 3 = min {

�⁄

′

= min {

= min { ⌊(� − ∑ =

= min { ⌊(� − ∑ = min { =

=

′

′

= min { =

⁄ )⁄

⌋

)⁄

⌋

= min { = min {

− −

. ⁄ . +

= min { =

. ⁄


83

=

{

= min {

′

⌊(� − ∑

)⁄

=

−

Sehingga didapatkan

′

. +

= ,

⌋

′

. +

= ,

′

. ⁄

= ,

′

= min { =

= . Proses iterasi diberhentikan

karena semua pesanan sudah terpenuhi. Jadi, didapatkan 3 rol tambahan dengan 3 pola yang berbeda.

Tabel 3.10: Hasil perhitungan contoh 3.3 setelah menggunakan metode first-fit decreasing Lebar rol pesanan Pola Jumlah rol 135 108 93 42 1

2

0

0

0

48

2

0

2

0

2

105

3

0

2

0

0

100

4

0

1

2

0

197

5

1

1

0

1

1

6

0

2

0

0

1

7

0

0

1

0

1


BAB IV PENERAPAN METODE PENGHASIL KOLOM UNTUK MASALAH PEMOTONGAN ROL KERTAS

Pada bab ini akan dijelaskan mengenai cara menggunakan aplikasi yang sudah penulis buat berdasarkan metode penghasil kolom. Aplikasi ini dibuat dengan Graphical User Interface (GUI) MATLAB. Berikut penjelasan dan cara tentang aplikasi ini. Sebelum membuka aplikasi ini, masukkan data ke dalam File Excel seperti gambar 4.1.

Gambar 4.1: Contoh tampilan File Excel Sheet 1 Agar data dapat lebih mudah dipahami, maka pada satu File terdapat 3 Sheet. Tampilan sheet pertama yaitu seperti pada gambar di atas, sheet kedua dan ketiga

84


85

yaitu pada gambar di bawah. Pada sheet pertama berisi data yang akan diproses, pada sheet kedua menampilkan output berupa jumlah rol, dan sheet ketiga menampilkan output berupa berat rol. Berikut gambar sheet kedua dan ketiga pada File Excel.

(a)

(b) Gambar 4.2: Contoh tampilan File Excel: (a) Sheet 2 untuk menampilkan output jumlah rol, (b) Sheet 3 untuk menampilkan output berat rol.


86

Lalu buka aplikasi GUI MATLAB yang sudah dibuat maka akan terlihat tampilan seperti gambar 4.3.

Gambar 4.3: Tampilan program penghasil kolom Kemudian kita dapat memilih hasil konversi yang diinginkan dengan memilih menu ‘Konversi’ lalu pilih jenis konversi (rol atau berat) seperti pada gambar 4.4.

Gambar 4.4: Tampilan program penghasil kolom untuk memilih hasil konversi


87

Jika dipilih hasil konversi berupa rol, maka akan muncul tampilan seperti gambar 4.5.

Gambar 4.5: Tampilan program penghasil kolom dengan hasil konversi rol Sedangkan jika dipilih hasil konversi berupa berat, maka akan muncul tampilan seperti gambar 4.6.

Gambar 4.6: Tampilan program penghasil kolom dengan hasil konversi berat


88

Setelah itu, tentukan lebar rol jumbo dan banyak jenis rol yang dipesan berdasarkan lebarnya dengan cara mengetikkannya pada tempat yang tersedia. Input data ini juga akan digunakan dalam proses perhitungan. Kemudian pilih hasil output yaitu berupa bilangan bulat (integer) atau bukan bilangan bulat (noninteger). Setelah itu, tekan tombol ‘Cari File & Proses’ maka akan muncul jendela “Select File to Open” yang berisi file-file. Kemudian cari file yang berisi data yang akan diolah, lalu pilih tombol ‘Open’. Berikut tampilan yang muncul ketika akan memilih File.

Gambar 4.7: Tampilan untuk memilih File yang akan diproses


89

Tunggu beberapa saat, maka solusi optimal akan muncul pada tempat yang telah tersedia seperti tampak pada gambar 4.8.

Gambar 4.8: Hasil yang didapat berupa rol Untuk memindahkan penyelesaian ke suatu file, pilih tombol ‘Pindahkan ke Excel’ lalu pilih File. Berikut tampilan hasil output pada File Excel.

Gambar 4.9: Hasil konversi rol yang sudah dipindahkan ke File Excel


90

Untuk hasil berupa konversi berat digunakan langkah-langkah yang sama seperti di atas sehingga akan diperoleh hasil berikut.

(a)

(b) Gambar 4.10: Hasil konversi berat: (a) pada tampilan program, (b) pada File Excel.


BAB V PENUTUP

A. Kesimpulan Masalah pemotongan kertas merupakan masalah penting pada proses produksi selain untuk mendapatkan hasil pemotongan yang baik juga untuk meminimumkan produksi jumlah rol. Sehingga biaya produksi bahan baku juga menjadi minimum. Masalah ini juga memiliki berbagai kendala yang harus dipertimbangkan sehingga tidak mudah diselesaikan secara manual. Pada skripsi ini masalah tersebut diselesaikan dengan 2 metode yang berbeda. Pertama, memodelkan masalah program linear lalu diselesaikan dengan metode simpleks. Cara memodelkan masalah ini yaitu dengan membuat semua kemungkinan pola pemotongan dengan syarat sisa pemotongan kurang dari lebar pesanan minimum kemudian menyelesaikan model ini sehingga diperoleh kombinasi pola yang paling optimal. Dari solusi yang didapat, solusi masih berupa pecahan dan menghasilkan rol yang melebihi pesanan sehingga diperlukan suatu metode yang lebih efektif dalam menyelesaikan permasalahan ini. Kedua, menggunakan metode penghasil kolom untuk menyelesaikan masalah pemotongan. Terlihat bahwa dengan metode penghasil kolom dihasilkan solusi optimal untuk masalah pemotongan kertas yaitu menghasilkan jumlah rol yang optimal atau sesuai pesanan. Metode ini juga lebih efektif dibandingkan dengan metode pertama karena tidak perlu membuat semua kemungkinan pola. Sisa yang

91


92

dihasilkan juga dapat digunakan untuk produk lain, didaur ulang atau dimasukkan penyimpanan. Pada tugas akhir ini juga terdapat aplikasi yang dibuat dengan GUI MATLAB untuk menyelesaikan masalah pemotongan berdasarkan metode penghasil kolom dimana hasil dapat berupa jumlah rol dan berat. GUI menggambarkan informasi dan perintah yang tersedia dalam bentuk grafis untuk penguna. Dengan demikian, aplikasi ini dapat dipahami oleh pengguna dan dengan perhitungan yang lebih mudah diproses.

B. Saran Penulis menyadari skripsi ini masih banyak kekurangan. Oleh sebab itu, penulis mengharapkan kelak ada yang melanjutkan penelitian ini. Pada skripsi ini hanya dibahas metode penghasil kolom yang merupakan suatu metode untuk menyelesaikan permasalahan pemotongan kertas berdimensi satu. Penulis berharap penelitian selanjutnya metode ini dapat diperluas untuk menyelesaikan masalah pola pemotongan dua dimensi yaitu dengan mempertimbangkan ukuran lebar dan panjang kertas. Pada skripsi ini juga hanya terbatas pada pemotongan dari rol ke rol dan meminimumkan jumlah penggunaan rol, sehingga untuk penulisan selanjutnya dapat diperluas dengan pemotongan dari rol menjadi potongan kertas atau gabungan dari rol dan potongan kertas dengan ukuran tertentu serta dapat meminimumkan sisa.


DAFTAR PUSTAKA

Anton, H. (2010). Elementary Linear Algebra: Applications version. Hoboken: John Wiley & Sons. Bisschop, Johannes. (2016). AIMMS Optimization Modeling. AIIMS B.V. Chvatal, Vasek. (1983). Linear programming. New York: W. H. Freeman and Company. Desrosiers, Jackques dan Marco E. Lubbecke. (2005). A Primer in Column Generation. Springer. Gilat, Amos. (2011). MATLAB An Introduction. Fourth Edition. Ohio: John Wiley and Sons, Inc.. Harsanto, Budi. (2011). Naskah Tutorial QM for Windows. Bandung. Hu, T. C. dan Andrew B. Kahng. (2016). Linear and Integer Programming Made Easy. Switzerland: Springer. Ignizio, J. P. dan Cavalier T. M. (1994). Linear Programming. Mac Graw Hill Book Company, Inc. Irawan, Feriza A. (2012). Buku Pintar Pemrograman MATLAB. Yogyakarta: MediaKom. Lubbecke, Marco E. Dan Jacques Desrosiers. (2005). Selected Topics in Column Generation. Operations Research. Informs. Matousek, Jiri dan Bernd Gartner. (2007). Understanding and Using Linear Programming. Verlag: Springer.

93


94

Parmar, Kashyap B. dkk. (2014). Cutting Stock Problem: A Survey of Evolutionary Computing Based Solution in 2014 International Conference on Green Computing Communication and Electrical Engineering. Susanta. (1996). Program Linear. Jakarta: Depdikbud. Taha, Hamdy A. (2011). Operations Reasearch An Introduction. Ninth Edition. New Jersey: Prentice Hall. Winston, Wayne L. (2004). Operations Research Applications and Algorithms. Fourth Edition. Toronto: Thomson Learning.


LAMPIRAN A Berikut ini adalah langkah-langkah penyelesaian dari contoh soal. 1.

Jawaban dari contoh soal 2.6

Maksimumkan +

Dengan kendala +

,

Jawab:

+

,

+

1.


2.

Menemukan cabang. Untuk = ⁄

=

,

−

=

=

+ = .

dan

+ , + ,...,

maka

⁄

= ⌊(

−∑

)⁄

⌋=

−

, .

= ⌊(

−∑

)⁄

⌋=

−

, . +

, .

= ⌊(

−∑

)⁄

⌋=

−

, . +

, . +

=

−

=

−

=

∗


+

= ,

∗

=

∗

=

∗

,

= .

= ⁄

= ⁄

.

=

Menentukan apakah solusi yang diperoleh meningkat? Karena ∑ = ∗

=

∗

=

= ,

>

diganti menjadi

= , maka

= ,

95

=

=

= ,

= .

dan

∗

= ,

∗

=


96

4.

=

Didapatkan k=3

=


lalu dikurangkan sampai diperoleh k=1 dimana menjadi ̅ = .

>




∑ =

+

̅ + ̅ + . + +

+

+

+

/ ,

(� − ∑

̅)

=

(� − ∑

̅)

=

−

, .

= ,

, ,

> ,

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. 2.

Diketahui k=1 dan −

= ̅ = , maka diperoleh ⁄

= ⌊(

−∑

̅ )⁄

⌋=

−

, .

= ⌊(

−∑

̅ )⁄

⌋=

−

, . +

, .

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

, . +

, . +

=

=

−

=

−

=

,

= ⁄

= . )⁄

⌋


97

3.

Karena ∑ = ∗

4.

=

=

= ,

=

Didapatkan k=3

=

, maka

= ,

diganti menjadi


>

= ,

= ,

=

dan = .

∗

= ,

∗

=

lalu dikurangkan sampai diperoleh k=2 dimana dengan ̅ = ..

∗

= >



berikut dengan k=2 dan ̅ = , ̅ = . ∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+

+

=

+

/

(

=

−

+

, . +

, . )

=


dan kita ganti 5.

=

Didapatkan k=2

=


>




̅ +

+

+

(� − ∑ =

̅)


98

∑

̅ +

=

(

. )+ +

+

(� − ∑

+

/ ( , ,

̅)

=

−

, . )

= ,

>


3.


Diketahui k=1 dan −

⁄

= ⌊(

−∑

̅ )⁄

⌋=

−

, .

= ⌊(

−∑

̅ )⁄

⌋=

−

, . +

, .

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

, . +

, . +

=

=

−

=

−

=

Karena ∑ =

menjadi

= ,

=

=

= ,

= , maka

= ,

=

= .

dan

< , maka kita ganti

4.

Didapatkan k=3 dimana

5.


,

=

= ⁄

∗

= ,

= . )⁄ ∗

=

⌋

diganti

dengan ̅ = .



̅ +

+

+

(� − ∑ =

̅)


99

∑ =

(

+

̅ +

/

. + . + )+

(� − ∑

+

=

(

+

̅)

− ,

, . +

= ,

, . +

)

>


Diketahui k=3, −

= ⌊(

3.

= ̅ = , dan

̅ )⁄

−

−∑ =

=

Karena ∑ =

= ,

Didapatkan k=3

=

=

, maka kita ganti 5.

⌋ = ⌊(

= ,

diganti menjadi 4.

=̅ = ,


, . +

= , maka

= ,

= ,

= .

, . + =

dan

. )⁄ ∗

⌋

= ,


∗

= <




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+

+

/

=

+

(

=

−

, . +

, . )


100

= ,

+

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. < , maka kita ganti

4.


5.


=

dengan ̅ = .



̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+

+

=

+

/

=

(

+

− .

, . +

, . )

= ,


=

Didapatkan k=2

=



<




̅ +

+

+

(� − ∑ =

̅)


101

∑

̅ +

=

(

. )+

+

+

(� − ∑

/ ( ,

̅)

=

−

= ,

, . ) >


3.

−

−∑

̅ )⁄

⌋=

−

, .

= ⌊(

−∑

̅ )⁄

⌋=

−

, . +

, .

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

, . +

, . +

=

=

−

=

−

=

Karena ∑ =

= ,

Didapatkan k=3


⁄

= ⌊(

menjadi 4.


Diketahui k=1 dan

=

= , =

=

= , maka

= ,

= .

=

dan

,

=

∗

⁄

= ,

= . )⁄ ∗

=

⌋

diganti


<



berikut dengan k=2 dan ̅ = , ̅ = .


102

∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+

+

/

=

+

=

(

−

,

= ,

+

, . +

, . )


4.


5.


=

dengan ̅ = .


Karena koefisien


̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+ +

+

/

=

+

(

=

−

, . +

, . )

= ,



< , maka kita ganti

=

dengan ̅ = .


103

5.




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+

+

/

=

+

=

(

−

,

= ,

+

, . +

, . )


4.


5.


=

dengan ̅ = .


Karena koefisien


̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

(

. + . )+

+

/

=

+

(

=

− = ,

, . +

, . )


104




Jadi didapatkan solusi yaitu ∗

= ,

dengan

∗

= ,

= .

∗

= ,

∗

=

∗

= ,

∗

= ,

= , dan

dengan

∗

∗

= ,

= ,

∗

∗

=

= ,

dengan ∗

= ,

∗

= , =


=

=

=

=

=

= =

=

=

=

dipotong

=

=

=

=

=

dipotong

=

dipotong

=

=

=

=

=

dipotong

=

dipotong

=

dipotong

=

dipotong

dipotong


=


105

2.

Jawaban contoh 3.3 Pertama, kita mencari nilai awal

dan

∗

dengan mengurutkan lebar rol kecil

dari terbesar sampai terkecil. (cm)

(rol)

135

97

108

610

93

395

42

211

= , =


�, maka kita peroleh

= ⌊( = ⌊( = ⌊(

)⁄

=

=

−∑ =

⁄

=

−∑ −∑

dan R terdiri dari 4 subscript (i=1,2,3,4).

)⁄ )⁄

=

⌋=

−

⌋= ⌋=

− −

. ⁄ ⁄

. + . +

=

+

= ⁄

=


106

Karena � dan

setiap −

>

, . =

,

=

′

′

� dan

=

=

−

, . =

= , =

= ⌊(

−∑

=

)⁄

=

−∑

)⁄

=

,

Karena

, . Sehingga

>

maka ′

,

� dan

′

,

= ⁄

=

−

, . =

′

.

=

=

⌋=

−

⌋= =

untuk setiap

= , =

. +

−

′

.

Iterasi 3. Diketahui

Karena

untuk

dan R terdiri dari 3 subscript (i=2,3,4).

subscript k=4 dari R dan diperoleh , . =

′

, . Sehingga

� maka diperoleh

= = ⌊(

/ =


Iterasi 2. Diketahui

Karena

′⁄

=

maka

′⁄

=

. + ,

=

−

, . =

=

= ⁄

.

′

=

⁄ ,

⁄

. Jadi kita hapus ,

′

=

−

dan R terdiri dari 2 subscript (i=2,3).

� maka diperoleh

=

. +

′⁄

� dan

⁄

.

= ⁄

=


107

= ⌊(

untuk setiap ′

=

)⁄

=

>

Karena

diperoleh

−∑

� dan

=

−

Iterasi 4. Diketahui , ,

� dan

=

maka

⌋=

′

′⁄

, . = .

= , =

� maka diperoleh

>

maka

=

=

=

/ =

] dan

∗

.

⁄

, . Sehingga

=

′

′⁄

dan R terdiri dari 1 subscript (i=3). Karena

=

=

⁄

=

=

=

/ =

Jadi diperoleh solusi layak sebagai berikut.

=[

. +

. Jadi kita hapus subscript k=2 dari R dan

=

Karena

−

=[

, ,

,

.

, ] ,

Kemudian, kita menggunakan metode simpleks direvisi dengan nilai awal di atas.


108

1.


2.

[ , , , ].

= [ , , , ], sehingga diperoleh nilai ,


+

+

,

,

sedemikian hingga

+

+

=

>

Masalah di atas dikenal dengan masalah Knapsack. Berikut langkah-langkah metode cabang dan batas Knapsack. 1) Menentukan nilai awal yaitu 2) Menemukan cabang. Untuk = ⁄

=

−

=

=

= .

dan

+ , + ,...,

maka

⁄

= ⌊(

−∑

)⁄

⌋=

−

.

= ⌊(

−∑

)⁄

⌋ = ⌊(

−

. +

)⁄

⌋

=

= ⌊(

=

=

−

=

−

−∑

−

=

. +

Maka didapat solusi terbaik

. + ∗

= ,

.

∗

⁄

=

∗

=

=

∗

= . )⁄

⌋

= .

3) Menentukan apakah solusi yang diperoleh meningkat? Karena ∑ = ∗

=

=

>

diganti menjadi

= , maka

= ,

=

=

=

dan = .

∗

= ,

∗

=

∗

=


109

=

4) Didapatkan k=3 dimana

lalu dikurangkan sampai diperoleh k=1

> , maka kita ganti

=

menjadi ̅ = .

5) Apakah cabang layak untuk dibuatkan cabang lagi? Karena koefisien

bukan bilangan bulat positif, maka kita uji

pertidaksamaan berikut dengan k=1 dan ̅ = . ∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

. +

+

/

+

=

=

−

+

.

= ,

>

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. 2) Diketahui k=1 dan −


= ⌊(

−∑

̅ )⁄

⌋=

−

.

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

. +

̅ )⁄

⌋

=

−

=

= = ⌊( = ⌊(

−

−∑ −

=

. +

. +

. )⁄

⌋=

= . )⁄

⌋


110

3) Karena ∑ = ∗

=

=

= , maka

diganti menjadi =


= ,

=

= ,

∗

dan

= ,

= ,

∗

= .

=

∗

=


> . Maka kita ganti

=

menjadi ̅ = .



pertidaksamaan berikut dengan k=2 dan ̅ = , ̅ = . ∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . )+

+

/

+

=

(

+

=

−

. +

= ,

. )

>

Karena pertidaksamaan tersebut tidak terpenuhi makacabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. 2) Diketahui k=2 dan −

= ̅ = ,

= ⌊(

−∑

̅ )⁄

⌋=

= ⌊(

−∑

̅ )⁄

⌋

= ⌊(

=

−

−

=

. +

. +


. )⁄

. +

⌋=

. ⁄

=


111

3) Karena ∑ = ,

∗

= ,

∗

= ,

=

<

diganti menjadi

4) Didapatkan k=3 dimana .

=

=

maka = ,

∗

dan

= ,

= ,

< , maka kita ganti

=

= , =

∗

=

dengan ̅ =



pertidaksamaan berikut dengan k=3 dan ̅ = , ̅ = , ̅ = . ∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . + . )+

+

+

( +

=

=

−

. +

. +

. )

= , <

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. =



< , maka kita ganti

=

dengan ̅ = .



pertidaksamaan berikut dengan k=1 dan ̅ = ∑ =

̅ +

+

+

(� − ∑ =

̅)


112

∑ =

̅ +

( . )+

+

/

+

(� − ∑

̅)

−

. )

=

(

= ,

>

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. = ̅ = , maka diperoleh

2) Diketahui k=1 dan −

= ⌊(

−∑

̅ )⁄

⌋=

−

. ⁄

=

= ⌊(

−∑

̅ )⁄

⌋=

−

. +

. ⁄

= ⌊(

−∑

̅ )⁄

⌋

=

3) Karena ∑ =

=

−

=

−

−

=

diganti menjadi

. +

=

= ,

. +

.

= , maka = ,

⁄

= ,

=

=

dan

= .

∗

= ,

∗

=

=

4) Didapatkan k=3 lalu dikurangkan sampai diperoleh k=2 dimana , maka kita ganti

=

dengan ̅ = .

∗

= <



pertidaksamaan berikut dengan k=2 dan ̅ = , ̅ = .


113

∑

̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . )+

+

/

+

=

=

(

−

+

. +

= ,

. )

>

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. =̅ = ,


= ⌊(

−∑

̅ )⁄

⌋=

= ⌊(

−∑

̅ )⁄

⌋

=

=

−

3) Karena ∑ = , ,

∗

= ,

= .

−

∗

=

= ,

. +

= , ∗

=

4) Kita peroleh k=3 dimana .

. + >


.

⁄

= , maka

diganti

. ⁄

. +

=

menjadi

= ,

> . Maka kita ganti

dan

= ,

=

= ,

=

∗

=

=

menjadi ̅ =



pertidaksamaan berikut dengan k=3 dan ̅ = , ̅ = , ̅ = .


114

∑ =

∑ ( . + . )+

+

+

̅ +

=

+

̅ + +

(

=

(� − ∑

̅) ̅)

=

− +

(� − ∑

. +

,

. +

. )

,

= , < ,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. > . Maka kita ganti


=

menjadi ̅ =

5) Apakah cabang layak untuk dibuatkan cabang lagi? bukan bilangan bulat positif, maka kita uji

Karena koefisien

pertidaksamaan berikut dengan k=3 dan ̅ = , ̅ = , ̅ = . =

∑ =

( . )+

+

̅ +

∑

+

̅ + (

+

+

− +

(� − ∑ =

̅)

(� − ∑

̅)

,

. +

. +

. )

=

= , < ,

,

Karena pertidaksamaan tersebut terpenuhi makacabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4.


115


> . Maka kita ganti

=

menjadi ̅ =



pertidaksamaan berikut dengan k=2 dan ̅ = , ̅ = . ∑ =

∑ =

+

̅ + ̅ +

+

+

=

(� − ∑

+

( . + . )+

(� − ∑

̅)

=

(

−

+

=

̅)

<

,

. +

. )

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. 4) Kita peroleh k=1 dimana

= , maka iterasi berhenti. ∗

Jadi didapatkan solusi optimal yaitu = ,

. Karena ∑�=

<

maka

∗

= ,

= ,

∗

= ,

�

4.

Mencari nilai t terkecil sedemikian sedemikian hingga , dari perbandingan rasio

5.


∗

−

dengan

=[ , , , ] .



keempat adalah kolom keluar karena

=


3.

Didapatkan � =

∗

,

, ⁄ dan =[

,

∗

,

,

−�

.

,

].

⁄ . Kolom


116

=[

∗

] dan

,

,

, ]=[ , − �/ �

=[

,

,

]

,

Kemudian dapat dimulai iterasi kedua yaitu sebagai berikut 1.


2.

[ , , , ].



+

,

,

+

,

sedemikian hingga

+

+

=

>

Masalah di atas dikenal dengan masalah Knapsack. Berikut langkah-langkah metode cabang dan batas Knapsack. =

1) Menentukan nilai awal yaitu

2) Menemukan cabang. Untuk = =

⁄

−

=

= .

dan

+ , + ,...,

maka

⁄

= ⌊(

−∑

)⁄

⌋=

−

.

= ⌊(

−∑

)⁄

⌋ = ⌊(

−

. +

)⁄

⌋

=

−

=

= = ⌊(

=

−

−∑

−

=

. +

Maka didapat solusi terbaik

. + ∗

= ,

.

∗

⁄

=

∗

=

=

∗

= .

= . )⁄

⌋


117

3) Menentukan apakah solusi yang diperoleh meningkat? ∗

Karena ∑ = ∗

=

=

>

= ,

=

> , maka kita ganti

=

diganti menjadi

=


= , maka

=

=

∗

dan = .

= ,

∗

∗

=

=

lalu dikurangkan sampai diperoleh k=1 menjadi ̅ = .




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

. +

+

/

+

+

=

=

− = ,

. >

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. 2) Diketahui k=1 dan −


= ⌊(

−∑

̅ )⁄

⌋=

−

.

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

. +

=

=

−

=

= . )⁄

⌋


118

−

= ⌊( = ⌊(

−∑

3) Karena ∑ = ∗

=

−

=

̅ )⁄ . +

=

diganti menjadi =


⌋ . +

. )⁄

= , maka

= ,

= ,

⌋=

=

∗

dan

= ,

= ,

= .

∗

=

∗

=


> . Maka kita ganti

=

menjadi ̅ = .




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . )+ +

+

/

+

(

=

=

− = ,

. +

. )

<

Karena pertidaksamaan tersebut terpenuhi makacabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. 4) Didapatkan k=2 dengan diperoleh

=


> . Maka kita ganti

=

dengan ̅ = .

5) Apakah cabang layak untuk dibuatkan cabang lagi?


119

Karena koefisien



̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

−

. )

=

=

+

/

( . )+

+

=

=

(

= ,

>

Karena pertidaksamaan tersebut tidak terpenuhi makacabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. = ̅ = , maka diperoleh


⁄

= ⌊(

−∑

̅ )⁄

⌋=

−

.

= ⌊(

−∑

̅ )⁄

⌋ = ⌊(

−

. +

̅ )⁄

⌋

=

−

=

=

−

= ⌊( = ⌊(

−∑ −

3) Karena ∑ =

diganti menjadi

=

. +

=

= ,

. +

. )⁄

= , maka

= ,

= ,

⌋= =

= .

dan

= . )⁄

∗

= ,

⌋

∗

=


120

=

4) Didapatkan k=3


< , maka kita ganti

dimana

=

dengan ̅ = .




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . )+

+

/

+

=

(

+

=

−

. +

= ,

. )

>

Karena pertidaksamaan tersebut tidak terpenuhi makacabang layak untuk dibuatkan cabang lagi. Kembali ke langkah 2. =̅ = ,


= ⌊(

−∑ =

=

−

= ⌊( = ⌊(

−∑ −

3) Karena ∑ = ,

∗

= ,

∗

=

=


̅ )⁄

⌋ = ⌊(

̅ )⁄

⌋

−

. +

. )⁄

diganti menjadi

= ,

. +

=

= , maka

. )⁄

. +

⌋=

=

= ,

dan = ,

∗

= ,

⌋

= .

∗

=


121


> . Maka kita ganti

=

menjadi ̅ =




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . + . )+

+

+

(

+

=

=

−

. +

=

. +

. )

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. 4) Kita peroleh k=3 dimana .

> . Maka kita ganti

=

menjadi ̅ =




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

+

+

=

=


122

( . + . + . )+

(

−

+

= ,

. +

. +

. )

Karena pertidaksamaan tersebut terpenuhi makacabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. > . Maka kita ganti


=

menjadi ̅ =




̅ +

+

(� − ∑

̅)

∑

̅ +

+

(� − ∑

̅)

=

=

( . + . )+

+

/

+

=

=

(

−

. +

. )

= ,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk dibuatkan cabang lagi. Kembali ke langkah 4. 4) Kita peroleh k=1 dimana


Jadi didapatkan solusi optimal yaitu = . Karena ∑�=

maka

∗

= ,

∗

= ,

∗

= ,

∗

=

dengan

= [ , , , ]� tidak dapat menjadi kolom

masuk. Jadi, iterasi berhenti dan didapatkan solusi

dan

∗

yang optimal.


123

Sehingga didapatkan pola pemotongan sebagai berikut dimana semua permintaan dapat terpenuhi. Lebar rol

Pola

Banyak

pemotongan ke-

135

108

93

42

rol

1

2

0

0

0

48,5

2

0

2

0

2

105,5

3

0

2

0

0

100,75

4

0

1

2

0

197,5

PENYELESAIAN MASALAH PEMOTONGAN ROL KERTAS DENGAN METODE PENGHASIL KOLOM SKRIPSI

Recommend Documents