mengoptimalkan pemotongan guillotine kertas segi … · pola pemotongan pada gambar 1.8 tidak dapat...

i

MENGOPTIMALKAN PEMOTONGAN GUILLOTINE

KERTAS SEGI EMPAT

Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Oleh :

Yulia Sari

NIM: 133114009

PROGRAM STUDI MATEMATIKA, JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2017

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

GUILLOTINE CUTTING OPTIMIZATION OF

RECTANGULAR PAPER

Thesis

Presented as a Partial Fulfillment of the

Requirements to Obtain the Degree of Sarjana Sains

in Mathematics

By :

Yulia Sari

Student Number: 133114009

MATHEMATICS STUDY PROGRAM, DEPARTMENT OF MATHEMATICS

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2017


iii

SKRIPSI


KERTAS SEGI EMPAT

Oleh:

Yulia Sari

NIM: 133114009

Telah disetujui oleh:

Pembimbing

Hartono Ph.D. Tanggal Juli 2017


iv

SKRIPSI


KERTAS SEGI EMPAT

Dipersiapkan dan ditulis oleh:

Yulia Sari

NIM: 133114009

Telah dipertahankan di depan Panitia Penguji

pada tanggal 27 Juli 2017

dan dinyatakan telah memenuhi syarat

Susunan Panitia Penguji

Nama Lengkap Tanda Tangan

Ketua Ir. Ig. Aris Dwiatmoko, M.Sc. ..................................

Sekretaris Benny Utomo, M.Sc. ..................................

Anggota Hartono, Ph.D. ..................................

Yogyakarta, Juli 2017

Fakultas Sains dan Teknologi

Universitas Sanata Dharma

Dekan,

(Sudi Mungkasi, S.Si., M.Math.Sc., Ph.D.)


v

PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini

tidak memuat karya atau bagian orang lain, kecuali yang telah disebutkan dalam

kutipan atau daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 28 Juli 2017

Penulis,

Yulia Sari


vi

HALAMAN PERSEMBAHAN

“For I know the plans I have for you, declares the Lord,

plans to prosper you and not to harm you, plans to give

you hope and future.”

(Jeremiah 29:11)

Karya ini kupersembahkan untuk

Tuhan Yesus Kristus dan Bunda Maria yang senantiasa menyertaiku,

kedua orang tua tercinta, Edi Setiawan dan Sri Rahayu

kedua kakak tersayang, Maria Ratna Sari dan Felicia Rossita Sari

dan saudara/i keluarga besar dari kedua orang tua yang terkasih.


vii

ABSTRAK

Pabrik-pabrik kertas memproduksi kertas dalam ukuran rol yang besar. Rol

kertas tersebut kemudian dipotong menjadi segi empat yang kemudian akan

dipotong lagi menjadi segi empat berukuran lebih kecil sesuai dengan jumlah dan

ukuran yang diinginkan. Dalam proses pemotongan tersebut, kertas dipotong secara

Guillotine, yaitu memotong secara mendatar atau vertikal dari satu sisi ke sisi

sejajar yang lain sehingga menghasilkan dua potongan segi empat. Ada banyak pola

pemotongan Guillotine yang dapat dilakukan, namun banyak juga diantaranya yang

mengakibatkan sisa potongan yang tidak sedikit. Oleh karena itu, pembuatan dan

pemilihan pola yang tepat bertujuan untuk meminimumkan sisa pemotongan kertas.

Dalam makalah ini, dibahas mengenai bagaimana mendapatkan pola

pemotongan yang optimal untuk kertas segi empat tersebut. Masalah pembuatan

pola diselesaikan menggunakan metode kombinasi dan algoritma yang diciptakan

oleh P.Y. Wang, sedangkan pemilihan pola optimal diselesaikan dengan program

linear bulat. Metode ini menghasilkan pola-pola yang diperlukan untuk memenuhi

pesanan dengan sisa pemotongan minimal. Selanjutnya, dibuat program tampilan

dengan MATLAB berdasarkan algoritma metode kombinasi dan program linear

bulat tersebut. Pada program ini, solusi yang dihasilkan berupa total sisa dan pola

pemotongan dalam bentuk indeks.

Kata kunci: masalah pemotongan Guillotine stok, program linear bulat, masalah

mengoptimalkan dua dimensi.


viii

ABSTRACT

Paper industry produces paper in a jumbo roll. Those rolls then will be cut

into rectangles which is later will be cut again into smaller rectangles corresponding

to the amount and size we desired. The last cutting process is done with Guillotine

cutting, which is to cut a paper horizontal or vertically from an edge to another

parallel edge so that it will generate two smaller rectangular pieces. There are many

Guillotine cutting pattern that can be done, but many of them will produce a quite

amount of trim loss. Hence, we need to make and choose the right pattern in order

to minimalizing the trim loss.

This thesis will explain how to obtain the optimal cutting pattern for

rectangular shaped paper. The pattern making problem is done with combination

method and algorithm made by P.Y. Wang, while the pattern choosing problem is

done with integer programming. This method yields which patterns should be used

to fulfill the order with minimum trim loss. Furthermore, a MATLAB display

program is made based on the combination method, P.Y. Wang’s algorithm and

integer programming. This program yields the optimal cutting pattern solution in

index form and the total trim loss in numerical form.

Keywords: Guillotine cutting stock, integer programming, two dimensional

optimization problem.


ix

PERNYATAAN PERSETUJUAN PUBLIKASI

Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:

Nama : Yulia Sari

Nomor Mahasiswa : 133114009

demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan

Universitas Sanata Dharma karya ilmiah saya yang berjudul:


KERTAS SEGI EMPAT

beserta perangkat yang diperlukan (bila ada). Dengan demikian, saya memberikan

kepada Perpustakaan Universitas Sanata Dharma hak untuk menyimpan,

mengalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan data,

mendistribusikan secara terbatas, dan mempublikasikannya di internet atau media

lain untuk kepentingan akademis tanpa perlu meminta izin dari saya maupun

memberikan royalti kepada saya selama tetap mencatumkan nama saya sebagai

penulis.

Demikian pernyataan ini saya buat dengan sebenarnya.

Dibuat di Yogyakarta

Pada tanggal: Juli 2017

Yang menyatakan

(Yulia Sari)


x

KATA PENGANTAR

Puji dan syukur penulis panjatkan kepada Tuhan Yesus Kristus yang telah

mencurahkan rahmat dan Roh KudusNya sehingga penulis dapat mengerjakan dan

menyelesaikan skripsi ini dengan baik. Skripsi ini dibuat dengan tujuan memenuhi

salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi

Matematika, Fakultas Sains dan Teknologi, Universitas Sanata Dharma.

Penulis menyadari bahwa penulis melibatkan banyak pihak untuk

membantu dalam menghadapi berbagai macam tantangan, kesulitan, dan hambatan.

Oleh karena itu, pada kesempatan ini penulis mengucapkan terima kasih kepada:

1. Bapak Sudi Mungkasi, S.Si., M.Math.Sc., Ph.D., selaku Dekan Fakultas

Sains dan Teknologi.

2. Bapak Hartono, S.Si., M.Sc., Ph.D., selaku Kaprodi Matematika sekaligus

sebagai Dosen Pembimbing Skripsi.

3. Ibu M. V. Any Herawati, S.Si., M.Si., selaku Dosen Pembimbing

Akademik.

4. Romo Prof. Dr. Frans Susilo, S.J., Bapak Ir. Ig. Aris Dwiatmoko, M.Sc.,

Bapak Dr. rer. nat. Herry P. Suryawan, S.Si., M.Si., dan Ibu Lusia

Krismiyati Budiasih, S.Si., M.Si. selaku dosen-dosen Prodi Matematika

yang telah memberikan banyak pengetahuan kepada penulis selama proses

perkuliahan.

5. Bapak/Ibu dosen/tenaga kependidikan Fakultas Sains dan Teknologi yang

telah berdinamika bersama selama penulis berkuliah.


xi

6. Kedua orang tua, dua kakak, tante, om dan saudara-saudara yang telah

membantu dan mendukung penulis selama proses pengerjaan skripsi.

7. Teman-teman Matematika 2013: Inge, Ezra, Sorta, Melisa, Agung, Laras,

Ambar, Yuni, Rey, Dion, Wahyu, Indra, Bintang, Tia, Lya, Andre, Sisca,

Natali, Yola, Sari, Dita, dan Kristo yang selalu memotivasi, memberi

masukan, menghibur dan masih banyak yang tidak bisa disebutkan satu

persatu. Terima kasih atas kebersamaan dan kekompakan ini.

8. Teman-teman Kost De Bloemen: terimakasih untuk semangat dan

dukungannya selama penulis berkuliah dan menulis skripsi ini.

9. 방탄소년단: terimakasih atas karya-karyanya yang telah memberi

semangat, motivasi dan hiburan untuk penulis.

10. Semua pihak yang tidak dapat disebutkan satu per satu dalam proses

penulisan skripsi ini.

Semoga semua pihak yang telah memberikan perhatian, dukungan, bantuan dan

cinta kepada penulis mendapatkan balasan dari Tuhan Yesus Kristus. Penulis

menyadari bahwa masih banyak kekurangan dalam penulisan skripsi ini. Oleh

karena itu, penulis mengharapkan kritik dan saran demi penyempurnaan skripsi ini.

Semoga skripsi ini bermanfaat bagi pembaca dan menjadi referensi belajar yang

baik.

Yogyakarta, Juli 2017

Penulis,

Yulia Sari


xii

DAFTAR ISI

HALAMAN JUDUL ................................................................................................ i

HALAMAN PERSETUJUAN PEMBIMBING .................................................... iii

HALAMAN PENGESAHAN ................................................................................ iv

PERNYATAAN KEASLIAN KARYA ................................................................. v

HALAMAN PERSEMBAHAN ............................................................................ vi

ABSTRAK ............................................................................................................ vii

ABSTRACT ......................................................................................................... viii

PERNYATAAN PERSETUJUAN PUBLIKASI .................................................. ix

KATA PENGANTAR ............................................................................................ x

DAFTAR ISI ......................................................................................................... xii

BAB I ...................................................................................................................... 1

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

B. Rumusan Masalah ...................................................................................... 11

C. Pembatasan Masalah .................................................................................. 11

D. Tujuan Penulisan ........................................................................................ 12

E. Manfaat Penelitian ..................................................................................... 12

F. Metode Penelitian....................................................................................... 12

G. Sistematika Penulisan ................................................................................ 12


xiii

BAB II ................................................................................................................... 14

A. Program Linear........................................................................................... 14

B. Program Linear Bulat ................................................................................. 23

C. Pencabangan dan Pembatasan .................................................................... 25

BAB III ................................................................................................................. 32

A. Masalah Pemotongan Guillotine ................................................................ 32

B. Metode Kombinasi ..................................................................................... 34

C. Algoritma P.Y. Wang ................................................................................. 37

D. Intlinprog MATLAB .................................................................................. 40

BAB IV ................................................................................................................. 63

BAB V ................................................................................................................... 68

A. Kesimpulan ................................................................................................ 68

B. Saran ........................................................................................................... 69

DAFTAR PUSTAKA ........................................................................................... 70

LAMPIRAN .......................................................................................................... 71


1

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Kertas diproduksi dari kayu yang dihancurkan menjadi serpihan-serpihan

kecil yang kemudian diolah sedemikian rupa sehingga menjadi bubur kertas. Bubur

kertas tersebut lalu diwarnai untuk kemudian diproses dengan mesin kertas (paper

machine). Sebuah mesin kertas dapat memproduksi kertas dalam ukuran besar yang

kemudian digulung menggunakan mesin penggulung (rewinder machine) menjadi

rol besar yang memuat kertas berukuran lebar 8,5 m dan panjang 80 km dengan

berat 120 ton (lihat Gambar 1.1).

Rol besar tersebut kemudian dipotong menjadi rol kecil dengan pisau

pemotong putar (rotary blades) seperti pada Gambar 1.2. Rol kecil ini sudah dapat

dikemas untuk dikirim kepada pemesan.

Gambar 1.1

Rol kertas besar hasil produksi mesin kertas


2

Selain langsung dikirim kepada pemesan, rol kecil tersebut juga dapat

dipotong lagi sehingga menjadi kertas segi empat dengan pisau pemotong tunggal

(single cutter) maupun pisau pemotong rangkap (double cutter). Kertas segi empat

hasil pemotongan ini juga dapat langsung dikemas.

Gambar 1.2

Rol besar yang telah dipotong menjadi rol kecil

Gambar 1.3

Kertas segi empat yang telah dikemas


3

Setelah dipotong menjadi segi empat, kertas tersebut juga dapat dipotong

lagi menjadi segi empat yang lebih kecil. Pada proses ini, secara khusus,

pemotongan harus dilakukan secara Guillotine yaitu pemotongan yang tegak lurus

dari satu sisi ke sisi lain yang berseberangan (Nicos Christofides & Charles

Whitlock, 1976).

Sebagai contoh, sebuah kertas seperti pada Gambar 1.4 akan dipotong

dengan suatu pola pemotongan Guillotine menjadi empat kertas yang lebih kecil.

Garis putus-putus menandakan letak-letak dimana pemotongan akan dilakukan.

Gambar 1.4

Kertas yang akan dipotong secara Guillotine


4

Berikut adalah langkah-langkah pemotongan Guillotine. Garis putus-putus

yang berwarna merah menandakan letak dimana pemotongan dilakukan pada

masing-masing langkah (lihat Gambar1.5).

Pemotongan Guillotine yang pertama membagi dua kertas awal sedemikian

rupa sehingga kertas kecil bernomor 1 sudah terpisah dari kertas awal sedangkan

kertas kecil lain bernomor 2, 3 dan 4 masih belum terpotong sehingga harus

dilakukan pemotongan Guillotine lagi.

Gambar 1.6

Pemotongan Guillotine kedua: (a) sebelum dipotong dan (b) setelah dipotong

(a)

(b)

Gambar 1.5

Pemotongan Guillotine pertama: (a) sebelum dipotong dan (b) setelah dipotong

(a)

(b)


5

Selanjutnya pada pemotongan Guillotine kedua, kertas kecil bernomor 2

terpisah dari kertas awal dan hanya tersisa kertas kecil bernomor 3 dan 4 yang

belum terpisah.

Pemotongan terakhir yaitu pemotongan Guillotine ketiga, semua kertas

kecil sudah terpotong sesuai dengan pola pemotongan awal. Dengan demikian,

semua proses pemotongan telah selesai.

Sebagai pembanding, misalkan suatu kertas akan dipotong menjadi lima

kertas yang lebih kecil dengan pola non-Guillotine seperti pada Gambar 1.8.

Gambar 1.7

Pemotongan Guillotine ketiga: (a) sebelum dipotong dan (b) setelah dipotong

(a)

(b)


6

Pola pemotongan pada Gambar 1.8 tidak dapat dipotong secara Guillotine

karena tidak ada garis putus-putus yang ujungnya berada pada dua sisi sejajar dari

segi empat awal.

Sebagai contoh, pada Gambar 1.9, jika pemotongan Guillotine dilakukan

untuk mendapatkan segi empat kecil bernomor 1, maka segi empat kecil bernomor

4 tidak akan bisa didapat karena potongan lainnya tidak bisa mencakup segi empat

kecil tersebut. Dengan kata lain, pemotongan Guillotine tidak bisa diterapkan pada

pola pemotongan non-Guillotine.

Gambar 1.8

Pola pemotongan non-Guillotine

Gambar 1.9

Akibat pemotongan Guillotine pada pola non-Guillotine:

(a) sebelum dipotong dan (b) setelah dipotong

(a)

(b)


7

Kertas yang telah memiliki pola Guillotine kemudian dipotong menjadi

beberapa ukuran yang berbeda sesuai jumlah dan ukuran yang diinginkan.

Sayangnya, pada proses pemotongan tersebut sering terdapat banyak sisa potongan

kertas yang terbuang karena cara pemotongan yang tidak optimal. Oleh karena itu

pemotongan perlu dioptimalkan, salah satunya dengan cara membuat model

matematika untuk mengoptimalkan pemotongan kertas dengan harapan sisa

potongan menjadi minimal dan dapat mengurangi biaya bahan dan pembuatan

kertas.

Contoh 1.1

Contoh permasalahan dari pemotongan Guillotine adalah sebagai berikut:

Sebuah kertas diproduksi dengan lebar 8,27 m dan panjang 11,69 m. Kertas

tersebut akan dipotong ke dalam 4 ukuran berbeda scara Guillotine:

1) 4 m x 6,5 m

2) 4 m x 6 m

3) 5 m x 5 m

4) 3 m x 5 m

Ilustrasi pemotongan ditunjukkan dengan garis putus-putus sedangkan

urutan pemotongan ditunjukkan dengan angka romawi pada ujung garis putus-putus

sedangkan bagian berwarna abu-abu menujukkan sisa pemotongan pada kertas.

Berikut adalah 2 pilihan pemotongan yang dapat dilakukan:


8

(a)

Gambar 1.10

Pilihan pemotongan pertama: (a) kertas pertama dan (b) kertas kedua

(b)


9

Pada Gambar 1.10 (a), kertas kecil bernomor 1, 3 dan 4 sudah termuat dalam

satu kertas awal namun kertas bernomor 2 belum termuat sehingga perlu ditambah

satu kertas awal lagi untuk memperolehnya.

Pilihan pemotongan pertama memerlukan dua buah kertas awal dan pada

kertas awal kedua terlihat bahwa banyak kertas yang terbuang. Ini tentu saja akan

sangat merugikan apabila kertas tersebut diproduksi dalam jumlah banyak.

Pemilihan pemotongan kedua seperti pada Gambar 1.11 hanya memerlukan

satu buah kertas awal dan telah mencakup semua kertas kecil yang diperlukan untuk

memenuhi pesanan. Terlihat dengan jelas bahwa kertas awal yang terbuang pada

pilihan pemotongan pertama (berwarna abu-abu) lebih banyak dibandingkan

Gambar 1.11

Pilihan pemotongan kedua


10

dengan pilihan pemotongan kedua sehingga dapat dikatakan bahwa pilihan

pemotongan kedua lebih optimal.

Masalah pemotongan segi empat dapat didefinisikan sebagai berikut.

Misalkan 𝐻 × 𝑊 adalah segi empat awal dengan tinggi 𝐻 dan lebar 𝑊, dan R

adalah himpunan dari segi empat yang lebih kecil R1,R2,…, Rn yang berukuran h1

× w1, h2 × w2, … , hn × wn. Akan ditentukan pola pemotongan Guillotine yang sisa

potongannya minimum dan jumlah segi empat Ri yang ada pada pola tidak lebih

dari bi untuk i = 1, 2, … , n.

Dengan ai,j adalah banyaknya Ri pada pola pemotongan ke-j, xj adalah

banyaknya pola pemotongan ke-j, tj adalah sisa pada pola pemotongan ke-j (j = 1,

2, …, m) dan T adalah total sisa pemotongan, masalah tersebut dapat dirumuskan

sebagai berikut:

Meminimumkan

𝑇 = ∑ (𝐻𝑊 − ∑ ℎ𝑖𝑤𝑖𝑎𝑖,𝑗

𝑛

𝑖=1

)

𝑚

𝑗=1

𝑥𝑗

atau

𝑇 = ∑ 𝑡𝑗𝑥𝑗

𝑚

𝑗=1

𝑡𝑗 = 𝐻𝑊 − ∑ ℎ𝑖𝑤𝑖𝑎𝑖,𝑗

𝑛

𝑖=1

dengan kendala

0 ≤ ∑ 𝑥𝑗𝑎𝑖,𝑗

𝑚

𝑗=1

≤ 𝑏𝑖.


11

Banyak penelitian yang telah dilakukan untuk mencari solusi optimal

pemotongan segi empat, diantaranya adalah “Two Algorithms for Constrained

Two-Dimensional Cutting Stock Problems” (P.Y. Wang, 1983) dan “Constrained

Two-Dimensional Cutting: An Improvement of Christofides and Whitlock’s Exact

Algorithm” (M. Hifi & V. Zissimopoulos, 1997). Di dalam tugas akhir ini, penulis

akan menggunakan program linear dan metode kombinasi yang diciptakan oleh

P.Y. Wang. Penulis memilih metode ini karena penulis merasa metode inilah yang

cukup sederhana untuk dimengerti dan digunakan.

B. Rumusan Masalah

Berdasarkan latar belakang yang telah dipaparkan, penulis mengadakan

penelitian terhadap masalah-masalah berikut:

1. Bagaimana memodelkan pemotongan Guillotine kertas segi empat?

2. Bagaimana merumuskan algoritma pemotongan Guillotine kertas segi

empat?

3. Bagaimana mengoptimalkan pemotongan Guillotine kertas segi empat?

C. Pembatasan Masalah

Masalah dalam tugas akhir ini akan dibatasi pada:

1. Masalah pemotongan terbatas hanya pada pemotongan Guillotine.

2. Algoritma pemotongan Guillotine ini terbatas pada bidang segi empat.

3. Posisi kertas tidak dirotasi.


12

D. Tujuan Penulisan

Tujuan yang ingin dicapai oleh penulis adalah untuk:

1. Mengoptimalkan pemotongan Guillotine kertas segi empat.

2. Memperluas wawasan pembaca tentang aplikasi matematika dalam

mengoptimalkan pemotongan kertas.

E. Manfaat Penelitian

Manfaat dari penulisan tugas akhir ini adalah sebagai berikut:

1. Penulis memperoleh pengetahuan baru selama mengerjakan tulisan ini.

2. Pembaca mendapat gambaran tentang suatu aplikasi matematika dalam

kehidupan sehari-hari, khususnya dalam pemotongan kertas.

3. Mendapatkan pola pemotongan Guillotine optimal untuk kertas segi

empat.

F. Metode Penelitian

Metode yang digunakan penulis dalam penyusunan tugas akhir yaitu studi

pustaka, yaitu dengan mempelajari buku dan jurnal yang berkaitan dengan masalah

ini, serta praktik simulasi dengan MATLAB.

G. Sistematika Penulisan

Sistematika penulisan tugas akhir ini adalah sebagai berikut:

BAB I. PENDAHULUAN

A. Latar Belakang Masalah

B. Perumusan Masalah


13

C. Pembatasan Masalah

D. Tujuan Penulisan

E. Manfaat Penulisan

F. Metode Penulisan

G. Sistematika Penulisan

BAB II. PROGRAM LINEAR

A. Program Linear

B. Program Linear Bulat

C. Metode Pencabangan dan Pembatasan

BAB III. MASALAH PEMOTONGAN GUILLOTINE

A. Masalah Pemotongan Guillotine

B. Metode Kombinasi

C. Algoritma P.Y.Wang

D. Algoritma Intlinprog MATLAB

BAB IV. SIMULASI PEMOTONGAN GUILLOTINE

BAB V. PENUTUP

DAFTAR PUSTAKA

LAMPIRAN


14

BAB II

PROGRAM LINEAR

A. Program Linear

Program linear mulai dikenal sejak tahun 1947, tidak lama setelah Perang

Dunia ke-2 dan terus berkembang seiring kemajuan teknologi, terutama

perkembangan komputer. Saat ini, program linear telah digunakan secara luas di

berbagai bidang. Aplikasi program linear pada industri yang pertama dan paling

sukses adalah pada industri minyak bumi yaitu pengekstrakan, penjernihan,

penyampuran, dan pendistribusian. Industri pengepakan daging juga menggunakan

program linear untuk menentukan komposisi campuran paling ekonomis dari sosis

dan pakan ternak. Selain itu, pabrik kertas juga menggunakan program linear untuk

mengurangi jumlah potongan sisa. Secara garis besar, masalah program linear

adalah bagaimana memaksimalkan atau meminimalkan suatu fungsi tujuan linear

yang memiliki lebih dari satu variabel dengan kendala-kendala berupa persamaan

dan pertidaksamaan linear.

Definisi-definisi

1. Variabel keputusan

Variabel keputusan biasanya dinotasikan dengan xj (j = 1, 2, …, n), adalah

variabel yang akan menunjukkan keputusan yang telah dibuat oleh program

linear. Contohnya: jumlah jam sebuah mesin beroperasi, banyaknya makanan

jenis tertentu yang dikonsumsi.


15

2. Kendala

Suatu kondisi yang membatasi jumlah variabel keputusan yang digunakan.

Contohnya: variabel yang mengukur jumlah jam penggunaan sebuah mesin

tidak bisa kurang dari nol, jumlah kalori dalam makanan yang dikonsumsi harus

lebih besar dari yang dibutuhkan tubuh.

3. Fungsi objektif

Fungsi objektif berupa fungsi matematis dari variabel keputusan. Fungsi ini

merepresentasikan keinginan dari pembuat keputusan seperti memaksimalkan

keuntungan atau meminimalkan biaya.

4. Solusi

Solusi dari masalah mengoptimalkan adalah kumpulan nilai dari variabel

keputusan.

5. Solusi layak (feasible solution)

Suatu solusi dianggap layak apabila memenuhi semua kendala dan batas pada

masalah.

6. Daerah layak (feasible region)

Daerah layak dari suatu masalah mengoptimalkan adalah himpunan dari solusi-

solusi layak.

7. Nilai

Nilai dari suatu solusi layak adalah nilai dari fungsi objektifnya.


16

8. Solusi optimal

Solusi optimal dari masalah mengoptimalkan adalah solusi layak yang nilainya

setidaknya sama dengan nilai semua solusi layak yang lain. Jika masalahnya

adalah memaksimumkan, maka nilai solusi optimalnya setidaknya sama besar

dengan semua nilai solusi layak yang lain. Jika masalahnya adalah

meminimumkan, maka nilai solusi optimalnya tidak lebih besar dari nilai solusi

layak yang lain. Nilai dari solusi optimal disebut sebagai nilai optimal.

9. Masalah tak terbatas (unbounded problem)

Suatu masalah mengoptimalkan adalah tidak terbatas apabila untuk setiap solusi

layak x, terdapat solusi layak y yang lain yang nilainya lebih baik daripada x.

Pada masalah memaksimumkan, nilai y akan lebih besar dari x dan pada

masalah meminimumkan, nilai y akan lebih kecil dari x.

10. Masalah tak layak (infeasible problem)

Suatu masalah program linear disebut tidak layak apabila tidak memiliki solusi

layak sama sekali atau tidak memiliki satupun solusi yang memenuhi semua

kendala dan batas.

Bentuk Umum Program Linear

Bentuk umum dari model program linear dapat dinyatakan sebagai berikut:

Tentukan nilai dari variabel keputusan 𝐱 = (𝑥1, 𝑥2, … , 𝑥𝑛)𝑡 untuk

mengoptimalkan (memaksimalkan atau meminimalkan) fungsi objektif z:

𝑧 = 𝑐1𝑥1 + 𝑐2𝑥2 + … + 𝑐𝑛𝑥𝑛

dengan kendala


17

𝑎1,1𝑥1 + 𝑎1,2𝑥2 + ⋯ + 𝑎1,𝑛𝑥𝑛 {≤, =, ≥}𝑏1

𝑎2,1𝑥1 + 𝑎2,2𝑥2 + ⋯ + 𝑎2,𝑛𝑥𝑛 {≤, =, ≥}𝑏2

⋮

𝑎𝑚,1𝑥1 + 𝑎𝑚,2𝑥2 + ⋯ + 𝑎𝑚,𝑛𝑥𝑛 {≤, =, ≥}𝑏𝑚

𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0

Bentuk tersebut juga dapat disederhanakan penulisannya menjadi:

Mengoptimalkan

𝑧 = ∑ 𝑐𝑗𝑥𝑗

𝑛

𝑗=1

dengan kendala

∑ 𝑎𝑖,𝑗𝑥𝑗

𝑛

𝑗=1

{≤, =, ≥} 𝑏𝑖, 𝑖 = 1, … , 𝑚

𝑥𝑗 ≥ 0, 𝑗 = 1, … , 𝑛

Harus diperhatikan bahwa setiap kendala memiliki salah satu diantara

pertidaksamaan tipe I (≤,), pertidaksamaan tipe II (≥), dan persamaan (=).

Asumsi dari Program Linear

Setiap teknik pemodelan matematika memiliki asumsi-asumsi dasar, begitu

juga program linear. Terdapat 3 asumsi dasar dari program linear yang memastikan

bahwa suatu masalah nyata dapat direpresentasikan sebagai masalah program linear

yaitu:


18

1. Kejelasan: data yang diberikan (cj, bi dan ai,j; i = 1, …, m; j = 1, …, n) harus

jelas dan tidak berubah selama proses analisis.

2. Proporsionalitas: kontribusi dari variabel keputusan (xj) pada fungsi objektifnya

adalah cjxj dan kontribusinya pada kendala ke-i adalah ai,jxj, contohnya bila nilai

x1 = 500, maka 3x1 = 1500.

3. Sifat penjumlahan: asumsi ini memastikan bahwa kontribusi dari setiap variabel

dikombinasikan secara linear. Misalkan x1 = 500 dan x2 = 300, maka 2x1 + x2 =

2 x 500 + 300 = 1300 (David J. Rader Jr., 2010).

Contoh 2.1

Diberikan masalah program linear sebagai berikut:

Memaksimumkan

𝑧 = 8𝑥 + 7𝑦

dengan kendala

−18𝑥 + 38𝑦 ≤ 133 (2.1)

13𝑥 + 11𝑦 ≤ 125 (2.2)

10𝑥 − 8𝑦 ≤ 55 (2.3)

𝑥, 𝑦 ≥ 0


19

Melihat bahwa masalah di atas hanya memiliki dua variabel keputusan,

maka masalah dapat diselesaikan dengan metode grafik sebagai berikut:

Langkah pertama, digambar daerah yang memenuhi pertidaksamaan (2.1)

seperti pada Gambar 2.1. Daerah yang berwarna merupakan daerah yang memenuhi

pertidaksamaan.

Gambar 2.1

Langkah pertama penyelesaian Contoh 2.1


20

Langkah kedua, digambar daerah yang memenuhi pertidaksamaan (2.2)

seperti pada Gambar 2.2. Daerah yang memenuhi kedua pertidaksamaan (2.1) dan

(2.2) berwarna sedikit lebih gelap untuk memperjelas.

Gambar 2.2

Langkah kedua penyelesaian Contoh 2.1


21

Selanjutnya pada langkah ketiga, digambar daerah yang memenuhi

pertidaksamaan (2.3) seperti pada Gambar 2.3.

Sama seperti sebelumnya, daerah yang berwarna paling gelap menandakan

bahwa daerah tersebut memenuhi ketiga pertidaksamaan (2.1), (2.2) dan (2.3).

Setelah semua kendala sudah digambar, maka kita mendapatkan daerah layak untuk

masalah ini (lihat Gambar 2.4).

Gambar 2.3

Langkah ketiga penyelesaian Contoh 2.1


22

Dari Gambar 2.4, didapat 5 titik yaitu (0 ; 0), (5,5 ; 0), (7,5 ; 2,5), (0 ; 3,5),

dan (4,75 ; 5,75) yang berpotensi menjadi titik optimal. Untuk memastikan, kelima

titik tersebut disubstitusikan dalam fungsi objektif

𝑧 = 8𝑥 + 7𝑦 dengan hasil sebagai berikut:

𝑧(0; 0) = 8 ∙ 0 + 7 ∙ 0 = 0

𝑧(5,5; 0) = 8 ∙ 5,5 + 7 ∙ 0 = 44

𝑧(7,5; 2,5) = 8 ∙ 7,5 + 7 ∙ 2,5 = 60 + 17,5 = 77,5

𝑧(0; 3,5) = 8 ∙ 0 + 7 ∙ 3,5 = 24,5

𝑧(4,75 ; 5,75) = 8 ∙ 4,75 + 7 ∙ 5,75 = 38 + 40,25 = 78,25

Karena titik (4,75 ; 5,75) memiliki nilai fungsi objektif tertinggi, maka titik

optimal berada di koordinat (4,75 ; 5,75) yang berarti solusi optimalnya adalah x =

4,75 dan y = 5,75 dengan nilai solusi optimalnya 𝑧 = 8 ∙ 4,75 + 7 ∙ 5,75 = 78,25.

Gambar 2.4

Daerah layak untuk Contoh 2.1


23

B. Program Linear Bulat

Program linear bulat membahas tentang cara untuk menyelesaikan masalah

mengoptimalkan dengan variabel diskrit yang bernilai bulat. Masalah program

linear bulat dapat didefinisikan sebagai berikut:

Mengoptimalkan

𝑧 = ∑ 𝑐𝑗𝑥𝑗

𝑛

𝑗=1

dengan kendala


𝑛

𝑗=1

{≤, =, ≥} 𝑏𝑖, 𝑖 = 1, … , 𝑚

𝑥𝑗 ≥ 0, 𝑥𝑗 ∈ ℤ, 𝑗 = 1, … , 𝑛

Masalah program linear bulat memang merupakan pengembangan dari

masalah program linear sehingga memiliki banyak kesamaan. Namun, pada

masalah program linear bulat, xj sebagai variabel keputusan haruslah bernilai bulat.

Relaksasi Program Linear

Diberikan suatu masalah program linear bulat P, relaksasi program linear

dari P adalah masalah program linear yang dibentuk dari P dengan cara

menghilangkan kendala dimana xj haruslah bernilai bulat tetapi tetap

mempertahankan batas atas dan batas bawah P (David J. Rader Jr., 2010).

Contoh 2.2

Diberikan masalah program linear bulat P sebagai berikut:

Memaksimumkan


24

𝑧 = 8𝑥 + 7𝑦

dengan kendala

−18𝑥 + 38𝑦 ≤ 133

13𝑥 + 11𝑦 ≤ 125

10𝑥 − 8𝑦 ≤ 55

𝑥, 𝑦 ≥ 0, 𝑥, 𝑦 ∈ ℤ

Jika kita menghilangan kendala bilangan bulatnya, maka didapat suatu

masalah program linear yang merupakan relaksasi program linear dari P yaitu:

Memaksimumkan

𝑧 = 8𝑥 + 7𝑦

dengan kendala

−18𝑥 + 38𝑦 ≤ 133

13𝑥 + 11𝑦 ≤ 125

10𝑥 − 8𝑦 ≤ 55

𝑥, 𝑦 ≥ 0

Masalah di atas sama dengan Contoh 2.1 yang memiliki solusi optimal x =

4,75 dan y = 5,75 dengan nilai solusi optimalnya z = 8 x 4,75 + 7 x 5,75 = 78,25.


25

C. Pencabangan dan Pembatasan

Ketika kita mencoba untuk menyelesaikan suatu masalah program linear

bulat, semakin kecil daerah layak yang harus dievaluasi, maka semakin mudah bagi

kita untuk mencari solusi optimal. Salah satu cara memperkecil daerah layak

tersebut adalah dengan membagi daerah kemungkinan yang layak menjadi

beberapa sub-daerah yang lebih kecil dan mengevaluasi tiap sub-daerah tersebut.

Pencabangan dan pembatasan mencoba menyelesaikan masalah program

linear bulat dengan membagi daerah layak dan menguji tiap sub-daerah untuk

mendapatkan solusi optimal bulat. Batas atas pada awal metode pencabangan dan

pembatasan biasanya didapatkan dengan menyelesaikan relaksasi program linear

dari masalah program linear bulatnya. Kemudian setelah mendapat batas atas,

daerah layak selanjutnya dibagi menjadi sub-daerah untuk dievaluasi.

Contoh 2.3

Perhatikan lagi soal pada Contoh 2.1:

Memaksimumkan

z = 8𝑥 + 7𝑦

dengan kendala

−18𝑥 + 38𝑦 ≤ 133 (2.1)

13𝑥 + 11𝑦 ≤ 125 (2.2)

10𝑥 − 8𝑦 ≤ 55 (2.3)

𝑥, 𝑦 ≥ 0, 𝑥, 𝑦 ∈ ℤ


26

Pada Contoh 2.2, didapat penyelesaian yaitu x = 4,75, y = 5,75 dan z = 78,25.

Jika kita perhatikan pada variabel x, dapat disimpulkan dengan mudah bahwa solusi

optimalnya haruslah salah satu dari 𝑥 ≤ 4 atau 𝑥 ≥ 5. Dengan pendekatan ini, kita

bisa memulai memecah daerah layak menjadi dua sub-daerah yang memenuhi 𝑥 ≤

4 atau 𝑥 ≥ 5, dengan kata lain sub-daerah 4 < 𝑥 < 5 sudah dihapus dari daerah

layak.

Pencabangan dan Variabel Pencabangan (Branching and Branching Variable)

Pembagian suatu sub-daerah menjadi sub-sub daerah yang lebih kecil

disebut sebagai pencabangan dan variabel yang dipilih untuk dibagi daerahnya

disebut sebagai variabel pencabangan.

Gambar 2.5

Sebagian daerah layak Contoh 2.2 yang telah dipecah


27

Akar Masalah dan Simpul (Root Problem and Node)

Relaksasi program linear dari masalah program linear bulat awal disebut

akar masalah yang berkorespondensi dengan simpul. Sub-masalah (simpul) yang

sedang dicabang disebut simpul aktif.

Pohon Pencabangan dan Pembatasan (Branch and Bound Tree)

Pohon biner yang menjelaskan pemecahan sub-daerah layak disebut sebagai

pohon pencabangan dan pembatasan. Setiap simpul pada ujung-ujung pohon ini

berkorespondensi dengan sub-masalah yang didapatkan dari pemecahan sub-daerah

sedangkan setiap garis berarah berkorespondensi dengan bagaimana sub-masalah

tersebut bertransformasi menjadi sub-masalah yang baru.

Contoh 2.4

Perhatikan lagi Contoh 2.2. Karena tidak didapat penyelesaian bulat, maka

harus dipilih salah satu variabel sebagai variabel pencabangan. Pada contoh ini,

masalah awal dimisalkan sebagai P1 dan x akan dipilih sebagai variabel

pencabangan. Pada masalah P2, diasumsikan 𝑥 ≤ 4 sedangkan pada P3

diasumsikan 𝑥 ≥ 5.


28

Perlu diperhatikan ketika melakukan pemecahan sub-daerah layak,

mungkin bagi kita untuk menyatakan bahwa suatu sub-masalah tidak memiliki

solusi layak. Misalnya dipilih cabang pada 𝑥 ≥ 5 dan 𝑦 ≥ 6 , maka

pertidaksamaan (2.2) tidak bisa dipenuhi. Jika demikian, maka kita dapat

mengeliminasi sub-masalah ini.

Solusi dari sub-masalah yang bernilai bulat juga bisa ditemui selama

melakukan pencabangan dan pembatasan. Solusi tersebut berpotensi menjadi solusi

optimal dari masalah program linear bulat awal. Kandidat solusi ini kemudian

dibandingkan dengan solusi bulat terbaik yang sudah ada. Jika kandidat solusi

tersebut memiliki nilai fungsi objektif yang lebih baik, maka solusi ini disimpan

sebagai solusi sementara. Sub-masalah tersebut tidak akan dipecah lagi karena

solusi bulat terbaik di sub-daerah ini sudah ditemukan.

Kita dapat mengakhiri suatu simpul atau tidak melakukan pencabangan lagi

pada sub-masalah yang memenuhi satu atau lebih syarat berikut:

1. Sub-masalah tersebut menghasilkan sebuah solusi bulat.

P1 : z = 78,25

x = 4,75 ; y = 5,75

P2 : z = 68,763

x = 4 ; y = 5,395

P3 : z = 78,18

x = 5 ; y = 5,455

𝑥 ≤ 4 𝑥 ≥ 5

Gambar 2.6

Sebagian dari pohon cabang dan pencabangan untuk Contoh 2.4


29

2. Sub-masalah tersebut tidak memiliki daerah layak.

3. Sub-masalah tersebut menghasilkan batas yang tidak lebih baik dari solusi

sementara.

Contoh 2.5

Pada Contoh 2.2, didapatkan solusi optimal tak bulat yaitu 𝑥 = 4,75 dan

𝑦 = 5,75 dengan 𝑧 = 78,25. Kemudian pada contoh 2.4, x dipilih sebagai variabel

pencabangan yang memberikan sub-masalah sebagai berikut:

P2 (𝑥 ≤ 4) : 𝑧 = 69,763 ; 𝑥 = 4 ; 𝑦 = 5,395

P3 (𝑥 ≥ 5) : 𝑧 = 78,18 ; 𝑥 = 5 ; 𝑦 = 5,455.

Kedua sub-masalah tersebut tidak menghasilkan solusi bulat sehingga

dipilih P3 yang nilai fungsi objektifnya tertinggi untuk dicabang dengan variabel

pencabangan y yang menghasilkan sub-masalah sebagai berikut:

P4 (𝑥 ≥ 5, 𝑦 ≤ 5) : 𝑧 = 78,077 ; 𝑥 = 5,385 ; 𝑦 = 5

P5 (𝑥 ≥ 5, 𝑦 ≥ 6) : TIDAK LAYAK.

Selanjutnya, P5 dapat dihapus karena tidak berada dalam daerah layak.

Kemudian P4 dipilih untuk dicabang dengan variabel pencabangan x dan didapat

sub-masalah berikut:

P6 (𝑥 = 5, 𝑦 ≤ 5) : 𝑧 = 75 ; 𝑥 = 5,385 ; 𝑦 = 5

P7 (𝑥 ≥ 6, 𝑦 ≤ 5) : 𝑧 = 77,077 ; 𝑥 = 6 ; 𝑦 = 4,273.

Sampai pada langkah ini, didapat solusi ( 5, 5 ) sebagai solusi sementara dan

simpul ini dapat diakhiri. Namun kita tetap harus melakukan pencabangan untuk P7

dengan variabel pencabangan y. Ini memberikan sub-masalah baru sebagai berikut:


30

P8 (𝑥 ≥ 6, 𝑦 ≤ 4) : 𝑧 = 77,846 ; 𝑥 = 6,231 ; 𝑦 = 4

P9 (𝑥 ≥ 6, 𝑦 = 5) : TIDAK LAYAK.

P9 dapat diakhiri sehingga simpul yang aktif hanya P8, ini menghasilkan

sub-masalah berikut:

P10 (𝑥 = 6, 𝑦 ≤ 4) : 𝑧 = 76 ; 𝑥 = 6 ; 𝑦 = 4

P11 (𝑥 ≥ 7, 𝑦 ≤ 4) : 𝑧 = 77,636 ; 𝑥 = 7 ; 𝑦 = 3,091

Sub-masalah P10 menghasilkan solusi bulat yang nilainya lebih dari solusi

sementara yang ada sehingga solusi ( 6, 4 ) adalah solusi sementara yang baru.

Sekarang hanya terdapat simpul aktif P11 sehingga didapat sub-masalah baru yaitu:

P12 (𝑥 ≥ 7, 𝑦 ≤ 3) : 𝑧 = 77,615 ; 𝑥 = 7,077 ; 𝑦 = 3

P13 (𝑥 ≥ 7, 𝑦 = 4) : TIDAK LAYAK.

Simpul P13 diakhiri sehingga tersisa satu simpul aktif P12 yang memberikan

sub-masalah:

P14 (𝑥 = 7, 𝑦 ≤ 3) : 𝑧 = 77 ; 𝑥 = 7 ; 𝑦 = 3

P15 (𝑥 ≥ 8, 𝑦 ≤ 3) : TIDAK LAYAK.

Perhatikan bahwa ( 7, 3 ) memiliki nilai solusi bulat yang lebih dari solusi

sementara yang ada sehingga itu menjadi solusi sementara yang baru. Kemudian

karena P15 diakhiri , maka tidak ada lagi simpul aktif. Ini artinya solusi optimal dari

masalah program linear bulatnya adalah ( 7, 3 ) dengan nilai optimal z = 77. Skema

langkah-langkah pencabangan dan pembatasan yang lengkap dari masalah ini

dapat dilihat di Gambar 2.7.


31

P12: z = 77,615

x = 7,077 ; y = 3

P13:

TIDAK LAYAK

P14: z = 77

x = 7 ; y = 3

P15:

TIDAK LAYAK

P8: z = 77,846

x = 6,231 ; y = 4

P9:

TIDAK LAYAK

P10: z = 76

x = 6 ; y = 4

P11: z = 77,636

x = 7 ; y = 3,091

P1: z = 78,25

x = 4,75 ; y = 5,75

P2: z = 68,763

x = 4 ; y = 5,95

P3: z = 78,18

x = 5 ; y = 5,455

P5:

TIDAK LAYAK

P4: z = 78,077

x = 5,385 ; y = 5

P6: z = 75

x = 5; y = 5

P7: z = 77,909

x = 6 ; y = 4,273

𝑥 ≤ 4 𝑥 ≥ 5

𝑦 ≤ 5 𝑦 ≥ 6

𝑥 ≤ 5 𝑥 ≥ 6

𝑦 ≤ 4 𝑦 ≥ 5

𝑥 ≤ 6 𝑥 ≥ 7

𝑦 ≤ 3 𝑦 ≥ 4

𝑥 ≤ 7 𝑥 ≥ 8

Gambar 2.7

Skema pencabangan dan pembatasan Contoh 2.5


32

BAB III

MASALAH PEMOTONGAN GUILLOTINE

A. Masalah Pemotongan Guillotine

Pada produksi kertas dengan skala besar, kertas yang telah berbentuk rol

besar kemudian dipotong menjadi rol kecil sesuai dengan kebutuhan pesanan. Rol

kecil tersebut selanjutnya dipotong lagi menjadi lembaran berbentuk segi empat,

dan lembaran tersebut kemudian dipotong lagi menjadi kertas segi empat yang lebih

kecil.

Di dalam proses pemotongan lembaran segi empat besar ke segi empat yang

lebih kecil, kemungkinan besar terdapat sisa dari pemotongan yang tidak dapat

digunakan lagi selain kembali diolah menjadi bubur kertas. Hal ini tentunya cukup

merugikan produsen kertas apabila sisa pemotongan terlalu banyak. Oleh karena

itu, diperlukan pola pemotongan yang tepat sehingga sisa pemotongan dapat

diminimalisir. Pengaruh pola pemotongan terhadap sisa pemotongan dapat dilihat

dengan jelas pada Gambar 1.10 dan Gambar 1.11. Pola pada Gambar 1.10

membutuhkan dua lembar kertas awal untuk memenuhi pesanan sedangkan pola

pada Gambar 1.11 hanya membutuhkan satu lembar kertas awal.

Pada masalah nyata, beberapa pabrik kertas masih menggunakan cara

manual untuk menentukan pola pemotongan yang akan digunakan. Hal ini tentu

kurang efisien karena cara manual tidak selalu memberikan hasil yang optimal.

Misalkan 𝐻 × 𝑊 adalah segi empat awal dengan tinggi H dan lebar W, dan

R adalah himpunan dari segi empat kecil R1,R2, …, Rn yang berturut-turut berukuran


33

h1 × w1, h2 × w2, … , hn × wn. Akan ditentukan pola pemotongan Guillotine yang

sisa potongannya minimum dan jumlah segi empat kecil Ri yang ada pada pola tidak

lebih dari bi untuk i = 1, 2, … , n.

Dengan ai,j adalah banyaknya Ri pada pola pemotongan ke-j, xj adalah

banyaknya pola pemotongan ke-j, tj adalah sisa pada pola pemotongan ke-j (j = 1,

2, …, m) dan T adalah total sisa pemotongan, masalah tersebut dapat dirumuskan

sebagai berikut:

Meminimumkan

𝑇 = ∑ (𝐻𝑊 − ∑ ℎ𝑖𝑤𝑖𝑎𝑖,𝑗

𝑛

𝑖=1

)

𝑚

𝑗=1

𝑥𝑗

atau


𝑚

𝑗=1

𝑡𝑗 = 𝐻𝑊 − ∑ ℎ𝑖𝑤𝑖𝑎𝑖,𝑗

𝑛

𝑖=1

(3.1)

dengan kendala

0 ≤ ∑ 𝑥𝑗𝑎𝑖,𝑗

𝑚

𝑗=1

≤ 𝑏𝑖 , (𝑖 = 1, 2, … , 𝑛).


34

B. Metode Kombinasi

Menentukan bentuk pola pemotongan ke-j dan jumlah segi empat Ri yang

muncul pada pola pemotongan ke-j atau ai,j (j = 1, 2, …, m; i = 1, 2, …, n) merupakan

dua masalah penting dalam masalah pemotongan Guillotine. Namun dengan

metode kombinasi, kedua masalah tersebut dapat terselesaikan dengan sederhana.

Metode kombinasi adalah metode yang menghasilkan pola pemotongan

berkendala dengan cara terus menerus menyusun secara horisontal dan vertikal dari

segi empat yang telah ditentukan. Sebagai contoh, misalkan terdapat tiga macam

segi empat R1 = p1 × q1, R2 = p2 × q2, dan R3 = p3 × q3. Susunan horisontal dari dua

segi empat R1 dan R2 adalah sebuah segi empat Sh yang berdimensi maks{ p1, p2 }

× ( q1 + q2 ) sedangkan susunan vertikal dari R1 dan R2 adalah sebuah segi empat

Sv yang berdimensi ( p1 + p2 ) × maks{ q1, q2 }. Baik susunan horisontal Sh maupun

susunan vertikal Sv memuat segi empat R1 dan R2. Gambar 3.1 merupakan ilustrasi

dari susunan horisontal dan susunan vertikal dengan daerah yang berwarna abu-abu

menunjukkan sisa pemotongannya.

Gambar 3.1

(a) Susunan horisontal (Sh) dan (b) susunan vertikal (Sv)

(a) (b)


35

Perlu diperhatikan bahwa untuk susunan horisontal maupun vertikal dari

dua segi empat awal (Ri) yang sama akan menghasilkan suatu segi empat tanpa sisa

potongan.

Susunan horisontal tersebut selanjutnya dianggap sebagai segi empat yang

baru. Segi empat tersebut nantinya akan disusun lagi dengan segi empat awal (Ri)

(lihat Gambar 3.2) dan segi empat hasil susunan horisontal (Sh) maupun vertikal

(Sv) (lihat Gambar 3.3).

Gambar 3.2

Susunan vertikal Sh yang dibentuk dari R1 dan R2 dengan R3

Gambar 3.3

Susunan horisontal Sv dari R2 dan R3 dengan Sh dari R1 dan R2


36

Gambar 3.2 merupakan pola yang dibentuk dengan cara menyusun segi

empat R1 dan R2 (lihat Gambar 3.1(b)) secara horisontal kemudian menyusunnya

kembali secara vertikal dengan R3. Gambar 3.3 merupakan pola yang dibentuk

dengan cara menyusun segi empat R2 dan R3 secara vertikal (lihat Gambar 3.1(a))

dan menyusun segi empat R1 dan R2 secara horisontal (lihat Gambar 3.1(b))

kemudian menyusun kembali kedua susunan tersebut secara horisontal. Daerah

yang berwarna abu-abu merupakan daerah sisa pemotongan dalam (inner trim loss).

Daerah inilah yang harus diminimumkan untuk mendapatkan pola yang optimal.

Gambar 3.4 merupakan contoh dari pola pemotongan pada Gambar 3.3 yang

telah diterapkan pada kertas awal. Jika daerah abu-abu pada Gambar 3.1, 3.2 dan

3.3 merupakan sisa potongan dalam, daerah abu-abu pada Gambar 3.4 merupakan

gabungan dari sisa potongan dalam dan sisa potongan luar (outer trim loss) yang

merupakan sisa potongan pada pola tersebut.

Gambar 3.4

Pola pada Gambar 3.3 yang telah diterapkan di kertas awal


37

C. Algoritma P.Y. Wang

Metode kombinasi pada sub-bab sebelumnya memang sudah dapat

membentuk pola pemotongan Guillotine. Namun jika kita perhatikan, pola

pemotongan yang dibentuk belum tentu memenuhi kendala-kendala ada dalam

masalah. Oleh karena itu, dibutuhkan Algoritma P.Y. Wang untuk melengkapi

metode kombinasi. Di dalam tugas akhir ini, Algoritma P.Y. Wang hanya

digunakan untuk menghasilkan pola pemotongan yang mungkin dilakukan pada

segi empat awal.

Algoritma dari metode ini menggunakan parameter untuk membatasi

maksimum prosentase dari sisa pemotongan yang dihasilkan. Batas eror digunakan

untuk mengukur seberapa dekat sisa pola pemotongan dengan sisa dari solusi pola

pemotongan optimal. Algoritma ini mengeliminasi segi empat yang telah disusun

baik secara horisontal maupun vertikal, yang memiliki sisa pemotongan lebih dari

batas error. Pola pemotongan yang memiliki jumlah segi empat kecil awal (Ri) lebih

dari yang telah ditentukan (𝑏𝑖) juga akan dieliminasi dari iterasi selanjutnya.

Algoritma ini menghasilkan semua kemungkinan segi empat yang

memenuhi kendala dan parameter yang telah ditentukan.

Step 1.a. Tentukan nilai 𝛽, 0 ≤ 𝛽 ≤ 1.

𝛽 diperlukan untuk membatasi sisa pemotongan yang masih bisa

ditoleransi. 𝛽 memiliki nilai di antara 0 dan 1 sebab 𝛽

merupakan bentuk desimal dari prosentase sisa pemotongan

kertas.

b. Definisikan F0 = {R1, R2, …, Rn} dan k = 1.


38

F0 merupakan himpunan segi empat kecil awal untuk memulai

metode kombinasi. Segi empat-segi empat kecil Ri pada F0

kemudian satu persatu disusun secara horisontal maupun

vertikal pada langkah selanjutnya.

Step 2. Hitung Fk yang merupakan himpunan dari semua segi empat L

yang memenuhi:

a. L dibentuk dari susunan horisontal atau vertikal dari dua segi

empat pada Fk-1.

Seperti yang telah dijelaskan pada Step 1.b, pada F1 L dibentuk

dari Ri yang ada di F0.

b. Seleksi ukuran: ukuran 𝐿 = ℎ × 𝑤 tidak melebihi 𝐻𝑊.

Seleksi ini sangat diperlukan mengingat ukuran L yang melebihi

HW tidak akan muat untuk diterapkan pada kertas awal.

c. Seleksi sisa: sisa pemotongan dalam pada setiap L tidak boleh

melebihi 𝛽𝐻𝑊.

Seleksi ini bertujuan untuk mengeliminasi pola yang sisa

potongan dalamnya melebihi 𝛽𝐻𝑊

d. Seleksi batas: banyaknya segi empat Ri di L tidak melebihi

kendala batas bi.

Misal banyaknya segi empat R3 di L melebihi kendala batas b3,

maka pola yang mengandung L ini tidak akan memenuhi syarat

sebagai pola sehingga harus dihapus.


39

e. Seleksi kembar: dua L yang dibentuk dari susunan horisontal

atau vertikal yang sama (susunan horisontal R1 dan R2 sama

dengan susunan horisontal R2 dan R1) akan dibuang salah

satunya agar tidak membebani iterasi selanjutnya.

Step 3. Jika Fk = Fk+1, iterasi akan dihentikan dan dari Fk didapatkan

pola-pola pemotongan yang mungkin dilakukan. Selain itu nilai

k akan diperbaharui menjadi k = k + 1 kemudian dikembalikan

ke Step 2.

Fk = Fk+1 menandakan bahwa iterasi hanya diulang-ulang tanpa

ada perubahan elemen pada Fk yang artinya iterasi selanjutnya

tidak diperlukan lagi sehingga harus dihentikan. Namun jika Fk

≠ Fk+1 maka masih ada pola pemotongan yang belum terdaftar

sehingga diperlukan iterasi selanjutnya atau dengan kata lain

mencari Fk+1.

Setelah semua kemungkinan pola pemotongan didapatkan, masalah

selanjutnya yang muncul adalah: pola mana sajakah yang harus dipilih agar

mendapatkan sisa yang minimum? Masalah memilih pola tersebut kemudian

dimodelkan menjadi suatu masalah program linear bulat sehingga dapat dicari

penyelesaiannya. Namun hal tersebut tentu tidak mudah jika jumlah pola yang

didapat cukup banyak sehingga perhitungan manual tidak mungkin dilakukan. Oleh

karena itu, akan digunakan salah satu fungsi dari MATLAB optimization toolbox.


40

D. Intlinprog MATLAB

Pada dasarnya, intlinprog merupakan fungsi yang tersedia di MATLAB

optimization toolbox untuk menyelesaikan masalah Mixed-Integer Linear

Programming. Namun pada tugas akhir ini, intlinprog akan digunakan untuk

menyelesaikan masalah program linear bulat saja. Sebagai pembanding, pada tugas

akhir ini akan digunakan juga aplikasi LiPS 1.9.4 (Linear Program Solver). LiPS

adalah suatu aplikasi untuk menyelesaikan masalah program linear, program linear

bulat, maupun program linear campuran.

Menggunakan Algoritma Intlinprog

Masalah mixed-integer linear program pada intlinprog akan dijelaskan

sebagai berikut:

Min f dengan kendala:

𝑥(intcon) adalah bilangan bulat

𝑨 ∙ 𝒙 ≤ 𝒃

𝑨𝑒𝑞 ∙ 𝒙 = 𝒃𝑒𝑞

𝒍𝒃 ≤ 𝒙 ≤ 𝒖𝒃

Keterangan:

1. x adalah vektor yang elemennya adalah variabel keputusan xj.

2. f merupakan vektor koefisien dari fungsi objektif.

Fungsi objektif 𝑧 = 2𝑥1 + 4𝑥2 + 9𝑥3 memiliki vektor koefisien f = [2, 4,

9]


41

3. Intcon merupakan vektor yang menunjukkan variabel keputusan elemen x

mana saja yang harus bernilai bulat.

intcon = [1, 2, 7] berarti x1, x2, x7 harus bernilai bulat.

4. 𝑨 adalah matriks yang berisi koefisien dari x (ai,j) yang kendalanya berupa

pertidaksamaan linear.

5. 𝒃 merupakan vektor yang berisi bi yang kendalanya berupa pertidaksamaan

linear.

6. 𝑨𝑒𝑞 adalah matriks yang berisi koefisien dari x (ai,j) yang kendalanya

berupa persamaan linear.

7. 𝒃𝑒𝑞 merupakan vektor yang berisi bi yang kendalanya berupa

pertidaksamaan linear.

8. 𝒍𝒃 merupakan vektor yang berisi batas bawah dari x.

9. 𝒖𝒃 merupakan vektor yang berisi batas atas dari x.

Berikut adalah sintaks dari intlinprog yang akan digunakan dalam tugas

akhir ini:

[x, fval] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub)

Sintaks ini menghasilkan x atau x pada sintaks dan nilai dari fungsi objektif

atau fval pada sintaks) dengan memasukkan 𝒇 (f pada sintaks), intcon, 𝑨 (A pada

sintaks), 𝒃𝑒𝑞 (b pada sintaks), 𝑨𝑒𝑞 (Aeq pada sintaks), 𝒃𝑒𝑞 (beq pada sintaks), 𝒍𝒃

(lb pada sintaks) dan 𝒖𝒃 (ub pada sintaks).


42

Contoh 3.1

Diberikan masalah program linear bulat sebagai berikut:

Memaksimumkan

𝑧 = 35𝑥1 + 45𝑥2 + 65𝑥3 (3.2)

dengan kendala

3𝑥1 + 6𝑥2 + 8𝑥3 ≤ 120 (3.3)

4𝑥1 + 5𝑥2 + 6𝑥3 = 100 (3.4)

11𝑥1 + 15𝑥2 + 20𝑥3 ≤ 120 (3.5)

𝑥1, 𝑥2, 𝑥3 ≥ 0, 𝑥1, 𝑥2, 𝑥3 ∈ ℤ (3.6)

Masalah tersebut akan memiliki input pada intlinprog sebagai berikut:

Karena default dari intlinprog adalah meminimumkan sedangkan masalah

yang diberikan (3.2) adalah memaksimumkan, maka pada f harus dikali dengan

tanda negatif (2.1) sebagai berikut:

f = -[35, 45, 65].

Kendala (3.6) mengharuskan semua variabel keputusan bernilai bulat

sehingga

intcon = [1, 2, 3].

Kendala (3.3) dan (3.5) merupakan pertidaksamaan sedangkan Kendala

(3.4) merupakan persamaan sehingga 𝑨, 𝒃, 𝑨𝑒𝑞 dan 𝒃𝑒𝑞 berturut-turut adalah

sebagai berikut:

A = [3, 6, 8; 11, 15, 20],

b = [120, 280],

Aeq = [4, 5, 6] dan


43

beq = [100].

Variabel keputusan pada masalah ini memiliki batas bawah yaitu 𝒙 ≥ 0

namun tidak memiliki batas atas atau 𝒙 < ∞ . Simbol ∞ tidak ada pada input

MATLAB, namun MATLAB mengenali inf dengan artian yang sama (tak hingga)

sehingga inputnya pada intlintprog adalah sebagai berikut:

lb = [0, 0, 0] dan

ub = [inf, inf, inf].

Jika [x, fval] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub) dijalankan, maka

akan memberikan hasil sebagai berikut:

x =

20.0000

4.0000

0

fval =

-880

yang artinya penyelesaian optimal dari masalah program linear bulat ini adalah

(𝑥1, 𝑥2, 𝑥3) = (20, 4, 0) dengan nilai optimal 𝑧 = 880.

Contoh 3.2

Setelah mengetahui tentang metode kombinasi, algoritma P.Y Wang dan

fungsi intlinprog MATLAB, penulis akan menunjukkan aplikasi metode-metode

tersebut dengan contoh sederhana.


44

Misalkan potongan kertas besar dengan lebar 8,27 m dan panjang 11,69 m

dengan pesanan: 1 lembar kertas ukuran 4 m x 6,5 m, 1 lembar ukuran 4 m x 6 m,

1 lembar ukuran 5 m x 5 m, dan 1 lembar ukuran 3 m x 5 m (lihat Contoh 1.1). Sisa

potongan diharapkan tidak melebihi 10% dari total luas kertas awal. Tentukan pola

pemotongan Guillotine yang optimal!

Masalah di atas dapat dimodelkan sebagai berikut:

Step 1.a. Didapat ukuran segi empat awal yaitu H x W = 8,27 x 11,69,

ukuran segi empat kecil R1 = 4 x 6,5, R2 = 4 x 6, R3 = 5 x 5, R4 = 3 x 5, dan batas

sisa 𝛽 = 0,1.

Step 1.b. Didefinisikan F0 = {R1, R2, R3, R4} dan k = 1.

Step 2.a. Dengan metode kombinasi, didapatkan hasil susunan horisontal

maupun vertikal dari semua segi empat kecil. Tanda negatif pada komposisi hanya

untuk menunjukkan bahwa susunan yang dilakukan adalah susunan vertikal. Tabel

berikut adalah semua segi empat L yang dibentuk dari susunan horisontal atau

vertikal dari dua segi empat pada F0.

Tabel 3.1: Hasil susunan horisontal dan vertikal dari F0.

Segi empat L

ke-

Komposisi

Ukuran Sisa potongan

dalam Panjang Lebar

1 1 0 4 6,5 0

2 2 0 4 6 0

3 3 0 5 5 0

4 4 0 3 5 0

5 1 1 4 13 0


45

6 2 1 4 12,5 0

7 3 1 5 11,5 6,5

8 4 1 4 11,5 5

9 -1 -1 8 6,5 0

10 -2 -1 8 6,5 2

11 -3 -1 9 6,5 7,5

12 -4 -1 7 6,5 4,5

13 1 2 4 12,5 0

14 2 2 4 12 0

15 3 2 5 11 6

16 4 2 4 11 5

17 -1 -2 8 6,5 2

18 -2 -2 8 6 0

19 -3 -2 9 6 5

20 -4 -2 7 6 3

21 1 3 5 11,5 6,5

22 2 3 5 11 6

23 3 3 5 10 0

24 4 3 5 10 10

25 -1 -3 9 6,5 7,5

26 -2 -3 9 6 5

27 -3 -3 10 5 0


46

28 -4 -3 8 5 0

29 1 4 4 11.5 5

30 2 4 4 11 5

31 3 4 5 10 10

32 4 4 3 10 0

33 -1 -4 7 6.5 4,5

34 -2 -4 7 6 3

35 -3 -4 8 5 0

36 -4 -4 6 5 0

Segi empat L yang pertama hingga keempat sama dengan R1, R2, R3, R4

sedangkan segi empat L yang kelima merupakan susunan horisontal dari dua segi

empat R1 sehingga tidak memiliki sisa potongan dalam. Kemudian untuk segi empat

L yang kesepuluh merupakan susunan vertikal dari R2 dan R1 dan memiliki sisa

potongan dalam ( 8 x 6,5 ) – [( 4 x 6 ) + (4 x 6,5)] = 52 – ( 24 + 26 ) = 2 m2.

Untuk Step 2.b, 2.c, 2.d dan 2.e akan dijelaskan secara singkat dalam tabel

3.2. Tanda silang ( X ) pada kolom seleksi menunjukkan bahwa L tersebut dihapus

dari iterasi karna tidak memenuhi syarat pada proses seleksi yang ada. Perhatikan

bahwa apabila suatu L dihapus pada Step 2.b, maka L tersebut tidak akan

diperhitungkan pada step berikutnya, demikian pula step-step yang lain. Tanda strip

( – ) menunjukkan bahwa L lolos dari proses seleksi.


47

Tabel 3.2: Proses seleksi pada Step 2.

L

ke-

Komposisi

Ukuran

Sisa

Seleksi

Panjang Lebar

Ukuran

(2.b)

Sisa

(2.c)

Batas

(2.d)

Kembar

(2.e)

1 1 0 4 6,5 0 – – – –

2 2 0 4 6 0 – – – –

3 3 0 5 5 0 – – – –

4 4 0 3 5 0 – – – –

5 1 1 4 13 0 X X X X

6 2 1 4 12,5 0 X X X X

7 3 1 5 11,5 6,5 – – – –

8 4 1 4 11,5 5 – – – –

9 -1 -1 8 6,5 0 – – X X

10 -2 -1 8 6,5 2 – – – –

11 -3 -1 9 6,5 7,5 X X X X

12 -4 -1 7 6,5 4,5 – – – –

13 1 2 4 12,5 0 X X X X

14 2 2 4 12 0 X X X X

15 3 2 5 11 6 – – – –

16 4 2 4 11 5 – – – –

17 -1 -2 8 6,5 2 – – – X

18 -2 -2 8 6 0 – – X X


48

19 -3 -2 9 6 5 X X X X

20 -4 -2 7 6 3 – – – –

21 1 3 5 11,5 6,5 – – – X

22 2 3 5 11 6 – – – X

23 3 3 5 10 0 – – X X

24 4 3 5 10 10 – X X X

25 -1 -3 9 6,5 7,5 X X X X

26 -2 -3 9 6 5 X X X X

27 -3 -3 10 5 0 X X X X

28 -4 -3 8 5 0 – – – –

29 1 4 4 11.5 5 – – – X

30 2 4 4 11 5 – – – X

31 3 4 5 10 10 – X X X

32 4 4 3 10 0 – – X X

33 -1 -4 7 6.5 4,5 – – – X

34 -2 -4 7 6 3 – – – X

35 -3 -4 8 5 0 – – – X

36 -4 -4 6 5 0 – – X X

Pada seleksi ukuran, segi empat L ke-5 dihapus dari iterasi karena lebarnya

13 m atau melebihi W = 11,69 m, demikian pula L ke-6, ke-11, ke-13, ke-14, ke-

19, ke-25, ke-26 dan ke-27.


49

Seleksi selanjutnya yaitu seleksi sisa, menghapus L ke-24 dan ke-31 karena

memiliki sisa potongan dalam 10 m2 atau melebihi toleransi 𝛽𝐻𝑊 = 9,6676 m2

yang ditentukan.

Pada seleksi batas, L ke-9, 18, 23, 32 dan 36 dihapus karena jumlah masing-

masing Ri di L melebihi bi. Contohnya pada L ke-9 yang terdiri dari 2 R1 padahal

hanya dibutuhkan 1 R1. Kemudian pada seleksi kembar, segi empat L ke-17 dihapus

dari iterasi karena kembar dengan L ke-10 yaitu sama-sama merupakan susunan

vertikal dari R2 dan R1. L ke-21, 22, 29, 30, 33, 34 dan 35 juga dihapus dari iterasi

karena alasan serupa.

Dari step 2, didapat F1 seperti pada Tabel 3.3.

Tabel 3.3: Hasil proses seleksi dari Step 2.

Elemen 𝐹1ke- Komposisi

Ukuran Sisa potongan

dalam Panjang Lebar

1 1 0 4 6,5 0

2 2 0 4 6 0

3 3 0 5 5 0

4 4 0 3 5 0

5 3 1 5 11,5 6,5

6 4 1 4 11,5 5

7 -2 -1 8 6,5 2

8 -4 -1 7 6,5 4,5

9 3 2 5 11 6

10 4 2 4 11 5


50

11 -4 -2 7 6 3

12 -4 -3 8 5 0

Step 3. Karena 𝐹0 ≠ 𝐹1 maka k = 1 diperbaharui menjadi k = k + 1 = 2

kemudian kembali ke Step 2.

Iterasi tersebut terus-menerus diulangi sampai didapatkan 𝐹𝑘 = 𝐹𝑘+1

sehingga didapat pola-pola pemotongan yang mungkin dilakukan seperti pada

Tabel 3.4.

Tabel 3.4: Hasil dari algoritma P.Y Wang untuk Contoh 3.2.

Susunan (S)

ke-

Komposisi

susunan

1 1 0

2 2 0

3 3 0

4 4 0

5 3 1

6 4 1

7 -2 -1

8 -4 -1

9 3 2

10 4 2

11 -4 -2


51

Susunan pertama (S1) hingga keempat (S4) hanya memiliki 1 komposisi

susunan (0 tidak diperhitungkan) karena keempat susunan tersebut sama dengan

segi empat kecil Ri (i = 1, 2, 3, 4). Kemudian untuk S7 memiliki komposisi susunan

-2 dan -1 yang berarti susunan tersebut merupakan susunan vertikal dari S2 dan S1

(gambar 3.5(a)) sedangkan S12 memiliki komposisi susunan -4 dan -3 yang berarti

susunan tersebut merupakan susunan vertikal dari S4 dan S3 (Gambar 3.5(b)).

12 -4 -3

13 12 7

(a)

Gambar 3.5

(a) Ilustrasi S7 dan (b) ilustrasi S12

(b)


52

Jika kita perhatikan, S13 memiliki komposisi susunn 12 dan 7 yang berarti

susunan ini merupakan susunan horisontal dari S12 dan S7 yang juga merupakan

hasil susunan sebelumnya (susunan ganda).

Langkah selanjutnya, semua susunan (Sj) yang ada kemudian diproses

menjadi pola pemotongan (xj). Pada langkah ini, yang diperhatikan bukan lagi

bentuk susunan melainkan banyaknya masing-masing Ri pada tiap susunan.

Tabel 3.5: Kemungkinan pola pemotongan untuk Contoh 3.2.

Pola

pemotongan

ke- (𝑆𝑗)

Komposisi pola pemotongan Total sisa

pemotongan

(𝑡𝑗) R1 R2 R3 R4

1 1 0 0 0 70,6763

2 0 1 0 0 72,6763

3 0 0 1 0 71,6763

4 0 0 0 1 81,6763

Gambar 3.6

Ilustrasi S13


53

5 1 0 1 0 45,6763

6 1 0 0 1 55,6763

7 1 1 0 0 46,6763

8 1 0 0 1 55,6763

9 0 1 1 0 47,6763

10 0 1 0 1 57,6763

11 0 1 0 1 57,6763

12 0 0 1 1 56,6763

13 1 1 1 1 6,6763

Pada Tabel 3.4, susunan ke-7 memiliki komposisi -2 dan -1 sehingga pada

Tabel 3.5 pola pemotongan ke-7 memiliki 1 R2 dan 1 R1. Total sisa pemotongan

pola ini (t7) didapat dari persamaan (3.1) dengan ai,j adalah banyaknya Ri pada pola

pemotongan ke-j dan j = 7.

𝑡7 = 𝐻𝑊 − ∑ ℎ𝑖𝑤𝑖𝑎𝑖,7

𝑛

𝑖=1

𝑡7 = 𝐻𝑊 − [ℎ2𝑤2 ∙ 1 + ℎ1𝑤1 ∙ 1]

𝑡7 = (8,27 × 11,69) − [(4 × 6) + (4 × 6,5)]

𝑡7 = 96,6763 − (24 + 26) = 46,6763.

Dari Tabel 3.5 juga dapat dilihat dengan mudah bahwa pola pemotongan

ke-13 merupakan pola pemotongan yang optimal karena pola pemotongan tersebut

telah mencakup semua Ri yang dibutuhkan dan memiliki sisa pemotongan terkecil


54

yang kurang dari 10% kertas awal (9,66763 m2) sehingga penyelesaian untuk

Contoh 3.2 adalah pola pemotongan ke-13 dengan sisa pemotongan 6,6763 m2.

Contoh 3.3

Misalkan potongan kertas besar dengan panjang 8,27 m dan lebar 11,69 m

dengan pesanan: 12 lembar kertas ukuran 4 m x 6,5 m, 30 lembar ukuran 4 m x 6

m, 21 lembar ukuran 5 m x 5 m, dan 24 lembar ukuran 3 m x 5 m. Sisa potongan

per kertas diharapkan tidak melebihi 10% dari luas kertas awal. Masalah ini serupa

dengan Contoh 3.2, namun dengan jumlah bi masing-masing yang lebih dari satu

sehingga akan memiliki pola pemotongan optimal yang berbeda.

Tabel 3.6 : Pesanan kertas untuk Contoh 3.3

Ri

bi (lembar)

hi (meter) wi (meter)

4 6,5 12

4 6 30

5 5 21

3 5 24

Dengan metode kombinasi dan algoritma P.Y. Wang seperti pada Contoh

3.2, didapatkan komposisi susunan seperti pada Tabel 3.7 berikut:

Tabel 3.7 : Komposisi susunan untuk Contoh 3.3.

Susunan ke- Komposisi susunan

1 1 0

2 2 0


55

3 3 0

4 4 0

5 3 1

6 4 1

7 -1 -1

8 -2 -1

9 -4 -1

10 3 2

11 4 2

12 -2 -2

13 -4 -2

14 3 3

15 -4 -3

16 4 4

17 -4 -4

18 17 3

19 -16 -5

20 -6 -6

21 -11 -6

22 -16 -6

23 15 7

24 15 8


56

25 15 9

26 17 9

27 -16 -10

28 -11 -11

29 -16 -11

30 15 12

31 15 13

32 17 13

33 -16 -14

34 15 15

35 -16 -16

36 17 17

Sama seperti contoh sebelumnya, susunan pertama (S1) hingga keempat (S4)

hanya memiliki 1 komposisi susunan (0 tidak diperhitungkan) karena keempat

susunan tersebut sama dengan segi empat kecil Ri (i = 1, 2, 3, 4). Komposisi yang

bertanda positif menunjukkan bahwa susunan yang dilakukan adalah susunan

horisontal sedangkan komposisi yang bertanda negatif menunjukkan bahwa

susunan yang dilakukan adalah susunan vertikal.

Selanjutnya akan diperhatikan jumlah Ri tiap pola seperti pada Tabel 3.8.


57

Tabel 3.8: Komposisi pola dan total sisa pemotongan tiap pola.

Pola

pemotongan

ke- (𝑆𝑗)

Komposisi pola pemotongan Total sisa

pemotongan

(𝑡𝑗) R1 R2 R3 R4

1 1 0 0 0 70,6763

2 0 1 0 0 72,6763

3 0 0 1 0 71,6763

4 0 0 0 1 81,6763

5 1 0 1 0 45,6763

6 1 0 0 1 55,6763

7 2 0 0 0 44,6763

8 1 1 0 0 46,6763

9 1 0 0 1 55,6763

10 0 1 1 0 47,6763

11 0 1 0 1 57,6763

12 0 2 0 0 48,6763

13 0 1 0 1 57,6763

14 0 0 2 0 46,6763

15 0 0 1 1 56,6763

16 0 0 0 2 66,6763

17 0 0 0 2 66,6763

18 0 0 1 2 41,6763


58

19 1 0 1 2 15,6763

20 2 0 0 2 14,6763

21 1 1 0 2 16,6763

22 1 0 0 3 25,6763

23 2 0 1 1 4,6763

24 1 1 1 1 6,6763

25 1 0 1 2 15,6763

26 1 0 0 3 25,6763

27 0 1 1 2 17,6763

28 0 2 0 2 18,6763

29 0 1 0 3 27,6763

30 0 2 1 1 8,6763

31 0 1 1 2 17,6763

32 0 1 0 3 27,6763

33 0 0 2 2 16,6763

34 0 0 2 2 16,6763

35 0 0 0 4 36,6763

36 0 0 0 4 36,6763

Pada Tabel 3.8, susunan ke-23 memiliki komposisi 15 dan 7. Susunan ke 15

memiliki komposisi -4 dan -3 sedangkan susunan ke-7 memiliki komposisi -1 dan

-1 sehingga pada Tabel 3.8 pola pemotongan ke-23 memiliki 2 R1, 1 R3 dan 1 R4.


59

Total sisa pemotongan pola ini (t23) dapat dicari dengan persamaan (3.1) dengan ai,j

adalah banyaknya Ri pada pola pemotongan ke-j dan j = 23.

𝑡23 = 𝐻𝑊 − ∑ ℎ𝑖𝑤𝑖𝑎𝑖,23

𝑛

𝑖=1

𝑡23 = 𝐻𝑊 − [ℎ1𝑤1 ∙ 2 + ℎ3𝑤3 ∙ 1 + ℎ4𝑤4 ∙ 1 ]

𝑡23 = (8,27 × 11,69) − [(4 × 6,5) ∙ 2 + (5 × 5) + (3 × 5)]

𝑡23 = 96,6763 − (52 + 25 + 15) = 4,6763.

Pada Contoh 3.2, pola pemotongan optimal dapat langsung didapatkan

hanya dengan metode kombinasi dan algoritma P.Y. Wang saja karena hanya

diperlukan satu lembar untuk masing-masing potongan kertas kecil, namun pada

Contoh 3.3, harus dilakukan perhitungan lebih lanjut karena diperlukan lebih dari

satu lembar potongan kertas awal.

Masalah pemilihan pola optimal tersebut akan diselesaikan menggunakan

program linear dengan n menotasikan banyak pola pemotongan yang ada, m

menotasikan banyak jenis segi empat kecil, xj menotasikan pola pemotongan ke-j,

tj menotasikan total sisa potongan dari xj, ai,j menotasikan banyaknya segi empat

kecil Ri pada xj dan bi menotasikan banyaknya Ri yang dibutuhkan untuk memenuhi

pesanan.

Meminimumkan


𝑚

𝑗=1

dengan kendala


60


𝑛

𝑗=1

= 𝑏𝑖, 𝑖 = 1, … , 𝑚, 𝑥𝑗 ≥ 0, 𝑗 = 1, … , 𝑛

atau

𝑇 = 70,6763𝑥1 + 72,6763𝑥2 + 71,6763𝑥3 + 81,6763𝑥4

+ 39,1763𝑥5 + 50,6763𝑥6 + 44,6763𝑥7 + 44,6763𝑥8

+ 51,1763𝑥9 + 41,6763𝑥10 + 52,6763𝑥11

+ 48,6763𝑥12 + 54,6763𝑥13 + 46,6763𝑥14

+ 56,6763𝑥15 + 66,6763𝑥16 + 66,6763𝑥17

+ 36,6763𝑥18 + 4,6763𝑥19 + 4, ,6763𝑥20 + 4,6763𝑥21

+ 16,1763𝑥22 + 4,6763𝑥23 + 4,6763𝑥24 + 4,6763𝑥25

+ 16,1763𝑥26 + 8,6763𝑥27 + 8,6763𝑥28 + 19,6763𝑥29

+ 8,6763𝑥30 + 8,6763𝑥31 + 19,6763𝑥32

+ 16,6763𝑥33 + 16,6763𝑥34 + 16,6763𝑥35

+ 36,6763𝑥36

(3.7)

dengan kendala

𝑥1 + 𝑥5 + 𝑥6 + 2𝑥7 + 𝑥8 + 𝑥9 + 𝑥19 + 2𝑥20 + 𝑥21 + 𝑥22 + 2𝑥23 + 𝑥24

+ 𝑥25 + 𝑥26 = 12

(3.8)

𝑥2 + 𝑥8 + 𝑥10 + 𝑥11 + 2𝑥12 + 𝑥13 + 𝑥21 + 𝑥24 + 𝑥27 + 2𝑥28 + 𝑥29

+ 2𝑥30 + 𝑥31 + 𝑥32 = 30

𝑥3 + 𝑥5 + 𝑥10 + 2𝑥14 + 𝑥15 + 𝑥18 + 𝑥19 + 𝑥23 + 𝑥24 + 𝑥25 + 𝑥27

+ 𝑥30 + 𝑥31 + 2𝑥33 + 2𝑥34 = 21


61

𝑥4 + 𝑥6 + 𝑥9 + 𝑥11 + 𝑥13 + 𝑥15 + 2𝑥16 + 2𝑥17 + 2𝑥18 + 2𝑥19 + 2𝑥20

+ 2𝑥21 + 3𝑥22 + 𝑥23 + 𝑥24 + 2𝑥25 + 3𝑥26 + 2𝑥27

+ 2𝑥28 + 3𝑥29 + 3𝑥30 + 2𝑥31 + 3𝑥32 + 2𝑥33 + 2𝑥34

+ 4𝑥35 + 4𝑥36 = 24

Koefisien 𝑥1 pada fungsi objektif (3.7) berasal dari total sisa pemotongan

pola pertama (t1), demikian pula 𝑥2, 𝑥3, … , 𝑥36 sehingga fungsi objektif T berusaha

meminimumkan jumlah total sisa pemotongan dari 𝑥𝑗.

Kemudian untuk fungsi kendala (3.8) baris pertama, koefisien 𝑥1 berasal

dari jumlah R1 pada pola pertama sedangkan koefisien 𝑥2 berasa dari jumlah R1

pada pola kedua demikian pula 𝑥3, 𝑥4, … , 𝑥36 . Pada baris kedua, koefisien 𝑥1

berasal dari jumlah R2 pada pola pertama sedangkan koefisien 𝑥2 berasa dari jumlah

R2 pada pola kedua demikian pula 𝑥3, 𝑥4, … , 𝑥36.

Perhitungan manual akan sangat rumit mengingat terdapat 36 variabel

keputusan sehingga akan digunakan Optimization Toolbox dari MATLAB untuk

menyelesaikannya dan aplikasi LiPS 1.9.4 sebagai pembanding.

Dengan Optimization Toolbox dari MATLAB, didapatkan solusi optimal

yaitu x18 = 1, x21 = 1, x23 = 5, x24 = 1, x30 = 14 dan T = 209,8786. Artinya diperlukan

1 lembar pola pemotongan ke-18, 1 lembar pola pemotongan ke-21, 5 lembar pola

pemotongan ke-23, 1 lembar pola pemotongan ke 24, dan 14 lembar pola

pemotongan ke-30. Jadi, dibutuhkan 22 lembar kertas awal dengan total sisa

pemotongan 209,8786 m2 untuk memenuhi pesanan. Mengingat toleransi 10% dari

total 22 lembar kertas adalah 10% x 22 x 8,27 m x 11,69 m = 212,688 m2, maka

total sisa pemotongan masih masuk dalam toleransi.


62

Kemudian dengan menggunakan aplikasi LiPS 1.9.4 (Linear Program

Solver) sebagai pembanding, didapatkan solusi optimal yaitu x18 = 1, x20 = 1, x23 =

4, x24 = 2, x30 = 14, T = 209,8786. Artinya, dibutuhkan 1 lembar pola pemotongan

ke-18, 1 lembar pola pemotongan ke-20, 4 lembar pola pemotongan ke-23, 2 lembar

pola pemotongan ke-24 dan 14 lembar pola pemotongan ke-30 untuk memenuhi

pesanan dengan total sisa pemotongan 209,8786 m2.

MATLAB dan LiPS memberikan hasil yang berbeda meskipun terdapat

pilihan pola pemotongan yang mirip, yaitu sama-sama menggunakan pola

pemotongan ke-18, 23, 24 dan 30. Total sisa pemotongan kedua solusi juga

menunjukkan hasil yang sama yaitu 209,8786 m2. Ini menunjukkan bahwa masalah

ini mempunyai lebih dari satu solusi pola pemotongan optimal.


63

BAB IV

SIMULASI PEMOTONGAN GUILLOTINE

Pada bab ini akan dijelaskan bagaimana cara menggunakan aplikasi yang

telah dibuat oleh penulis berdasarkan metode kombinasi. Aplikasi ini dibuat dengan

Graphical User Interface (GUI) MATLAB. Berikut adalah penjelasan dan cara

menggunakan aplikasi ini.

Dengan membuka aplikasi MATLAB dan menjalankan program optgui,

maka akan terbuka jendela aplikasi seperti pada Gambar 4.1. Aplikasi ini hanya

terdiri dari satu jendela sehingga baik input data maupun output data dapat dilihat

sekaligus.

Gambar 4.1:

Tampilan program pemotongan Guillotine kertas segi empat


64

Masukkan data kertas awal yaitu panjang dan lebar, serta toleransi sisa yang

dikehendaki. Pastikan semua data memiliki satuan yang sama karena program tidak

mengkonversi semua masukan data, demikian pula toleransi sisa. Pastikan juga

kolom kertas kecil terisi dengan lengkap sesuai dengan banyaknya kertas kecil yang

dibutuhkan.

Gambar 4.2

Tampilan untuk input data


65

Pada bagian output data terdapat tabel pola, tabel indeks, total sisa

pemotongan dan prosentasenya, toleransi total luas kertas awal dan prosentasenya,

serta jumlah kertas awal. Jumlah kertas awal menunjukkan banyaknya kertas awal

yang dibutuhkan untuk memenuhi pesanan. Total sisa menunjukkan total sisa

pemotongan yang dihasilkan dari pola-pola tersebut sedangkan toleransi digunakan

untuk membandingkan total sisa pemotongan dengan toleransi yang diberikan.

Gambar 4.3

Tampilan untuk output data


66

Sebagai simulasi, akan diselesaikan Contoh 3.3 dengan aplikasi ini.

Misalkan potongan kertas besar dengan lebar 8,27 m dan panjang 11,69 m

dengan pesanan: 12 lembar kertas ukuran 4 m x 6,5 m, 30 lembar ukuran 4 m x 6

m, 21 lembar ukuran 5 m x 5 m, dan 24 lembar ukuran 3 m x 5 m. Sisa potongan

per kertas diharapkan tidak melebihi 10% dari luas kertas awal. Tentukan pola

pemotongan Guillotine yang optimal!

Berikut merupakan tampilan program untuk Contoh 3.3:

Gambar 4.4

Tampilan input dan output untuk Contoh 3.3


67

Untuk memperjelas, berikut adalah tampilan output untuk Contoh 3.3:

Pada tabel pola, ditunjukkan bahwa pilihan pola yang optimal yaitu satu

lembar pola ke-18, satu lembar pola ke-21, lima lembar pola ke 23, satu lembar pola

ke 24 dan 14 pola ke-30 dengan komposisi seperti yang ada pada indeks. Cara

membaca indeks telah dijelaskan di bab sebelumnya. Banyaknya kertas yang

dibutuhkan untuk melengkapi pesanan adalah 22 lembar dengan total sisa 209,8786

m2 atau 9,878692% dari total kertas dengan toleransi awal 212.688 m2 atau 10%

dari total kertas.

Perlu kita perhatikan bahwa tidak setiap data yang diberikan dapat

menghasilkan sisa pemotongan yang kurang dari toleransi yang kita harapkan

karena bisa saja terdapat sisa yang cukup banyak pada beberapa kertas yang tidak

mungkin dihindari.

Gambar 4.5

Tampilan output untuk Contoh 3.3


68

BAB V

KESIMPULAN DAN SARAN

A. Kesimpulan

Masalah pemotongan kertas merupakan hal yang penting bagi industri

kertas. Apabila kertas yang terbuang akibat pola pemotongan dan jumlah kertas

yang dibutuhkan untuk memenuhi pesanan dapat diminimumkan, maka biaya

produksi juga menjadi minimum dengan harapan keuntungan yang didapat akan

lebih tinggi. Masalah ini juga memiliki berbagai kendala yang harus

dipertimbangkan, salah satunya adalah pemotongan yang digunakan adalah

pemotongan Guillotine. Oleh karena itu penulis menggunakan gabungan dari

algoritma P.Y. Wang dan program linear untuk menyelesaikan masalah ini.

Pertama, algoritma P.Y. Wang digunakan untuk membuat pola-pola pemotongan

Guillotine yang mungkin untuk dilakukan. Kemudian pola-pola pemotongan

tersebut dimodelkan dengan program linear untuk memilih pola mana saja yang

akan menghasilkan sisa potongan paling sedikit dan tetap dapat memenuhi jumlah

pesanan.

Perlu kita perhatikan juga bahwa tidak setiap data yang diberikan dapat

menghasilkan sisa pemotongan yang kurang dari toleransi yang kita harapkan

karena bisa saja terdapat sisa yang cukup banyak pada beberapa kertas yang tidak

mungkin dihindari. Penentuan prosentase toleransi juga sangat penting mengingat

dengan diberikan prosentase yang kecil, diharapkan sisa pemotongannya juga


69

menjadi lebih sedikit. Namun prosentase yang terlalu kecil dapat mengakibatkan

hilangnya beberapa pola dan tidak didapat hasil pola pemotongan sama sekali.

Pada tugas akhir ini, penulis juga telah membuat aplikasi GUI MATLAB

berdasarkan algoritma P.Y. Wang dan program linear untuk menyelesaikan

masalah pemotongan Guillotine ini. Aplikasi ini juga diharapkan dapat dengan

mudah dimengerti oleh pengguna awam.

B. Saran

Penulis menyadari tugas akhir ini masih memiliki banyak kekurangan. Oleh

karena itu, penulis mengharapkan nantinya ada yang melanjutkan penelitian ini.

Pada tugas akhir ini hanya dibahas pemotongan Guillotine kertas segi empat.

Penulis berharap nantinya pemotongan tidak terbatas pada segi empat saja namun

bidang dua dimensi lain misalnya lingkaran. Aplikasi yang dibuat oleh penulis juga

masih mengharuskan pengguna untuk memasukkan batas toleransi. Hasil dari

aplikasi untuk mengoptimalkan pemotongan Guillotine di tugas akhir ini juga

masih berbentuk indeks. Akan lebih baik apabila hasil aplikasi dapat berupa

gambar sehingga pengguna akan lebih mudah membayangkan pemotongan yang

dilakukan.


70

DAFTAR PUSTAKA

Christofides, Nicos & Whitlock, Charles. An Algorithm for Two-Dimensional

Cutting Problems. Operations Research. 25(1): 30-44.

Dantzig, George B. & Thapa, Mukund N (1997). Linear Programming, 1:

Introduction. New York: Springer-Verlag.

http://www.mathworks.com/help/optim/ug/intlinprog.html (diakses 5 Juni 2017

pukul 11:10).

http://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-

algorithms.html (diakses 8 Mei 2017 pukul 09:59).

http://www.youtube.com/user/SappiTube.

Ignizo, James P. & Cavalier, Tom M. (1994). Linear Programming. New Jersey:

Prentice-Hall, Inc.

Jr., David J. Rader. (2010). Deterministic Operations Research, Models and

Methods in Linear Optimization. New Jersey: John Wiley & Sons, Inc.

Kolman, Bernard & Beck, Robert E. (1995). Elementary Linear Programming with

Applications. Amsterdam: Elsevier Science & Technology Books.

P.Y. Wang. (1983). Two Algorithm for Constrained Two-Dimensional Cutting

Stock Problems. Operations Research. 31(3): 573-586.


71

LAMPIRAN

Berikut ini adalah code program untuk aplikasi GUI MATLAB yang telah

dibuat beserta fungsi-fungsi di dalam aplikasi.

A. Code untuk susunan horisontal dan vertikal

function T = susun(A) T = A(:,[2:6]); %Mengambil data yang diperlukan

k=length(A(:,1)); kode1= A(:,1); tinggi= A(:,2); lebar= A(:,3); trim= A(1:k,6);

for i=1:k %Susunan horisontal h_hor = max(tinggi(i),tinggi); w_hor = lebar(i)+lebar; %menyimpan komposisi susunan horisontal in_hor = [[kode1(1):kode1(k)]' [kode1(i)*ones(k,1)]]; %menghitung sisa potongan trim_hor=h_hor.*w_hor-tinggi.*lebar-

tinggi(i)*lebar(i)+trim;

%Susunan vertikal h_ver=tinggi(i)+tinggi; w_ver=max(lebar(i),lebar); %menyimpan komposisi susunan vertikal in_ver=[-1*[kode1(1):kode1(k)]' -1*[kode1(i)*ones(k,1)]]; %menghitung sisa potongan trim_ver=h_ver.*w_ver-tinggi.*lebar-

tinggi(i)*lebar(i)+trim;

%Menggabungkan hasil susunan vertikal dan horisontal T=[T; h_hor w_hor in_hor trim_hor; h_ver w_ver in_ver

trim_ver]; end

B. Code fungsi untuk seleksi ukuran

function F = seleksi_ukuran(A,H,W) hapus_h = find(A(:,1)>H); %list untuk dihapus berdasarkan h hapus_w = find(A(:,2)>W); %list untuk dihapus berdasarkan w hapus = union(hapus_h,hapus_w); %list final untuk dihapus A(hapus,:) = []; %menghapus elemen F yang tidak lolos seleksi F = A; end


72

C. Code fungsi seleksi sisa

function T=seleksi_trim(A,was) trim = A(:,length(A(1,:))); %Mengambil hanya data sisa

pemotongan hapus = trim>was; %Mencari elemen yang tidak memenuhi syarat A(hapus,:) = []; %Menghapus elemen yang tidak lolos seleksi T = A; end

D. Code fungsi seleksi batas 1

function T=seleksi_bound(A,b) p = length(b); hapus = [0]; for i=1:length(A(:,1)) hitung = histc(abs(A(i,3:5)),1:p); %menghitung Ri tiap

baris c = hitung'<=b; %Mencari baris dimana Ri<=bi d = sum(c); if d < p hapus = [hapus; i]; %Membuat list baris yang tidak

lolos seleksi end end hapus(1) = []; A(hapus,:) = []; %Menghapus baris yang tidak lolos seleksi T = A; end

E. Code fungsi seleksi batas 2

function F = seleksi_bound2(A1,b,indeks) p = length(b); hapus = [0]; A = abs(indeks); A(:,1) = []; for i = 1:length(A(:,1)) hitung = histc(A(i,:),1:p); %menghitung jumlah Ri tiap

baris c = hitung'<=b; %Mencari baris dimana Ri <= bi d = sum(c);

%Membuat list baris yang tidak lolos seleksi if d < p hapus = [hapus; i]; end end hapus(1) = []; A1(hapus,:) = []; %Menghapus baris yang tidak lolos seleksi F = A1;


73

F. Code fungsi untuk membuat indeks

function ind=kompo(b,indeks)

p=length(b); A=abs(indeks); A1 = A(:,1); A(:,1) = []; %Menghapus bagian yang tidak masuk hitungan [bar, kol] = size(A); A = [A zeros(bar,16-kol)];

for i = 1:bar k = find(A(i,:)>p); if sum(k)==0 A(i,:)=A(i,:); else k1 = A(i,1); k2 = A(i,2); if k1<=p k1=[k1]; else g1 = find(A(k1,:)>0, 1, 'last' );

%==max(find(A(k1,:)>0)) k1=[A(k1,[1:g1])]; end if k2<p k2=[k2]; else g2=find(A(k2,:)>0, 1, 'last' );

%==max(find(A(k1,:)>0)) k2=[A(k2,1:g2)]; end ganti=[k1 k2]; A(i,:)=[ganti zeros(1,16-length(ganti))]; end end ind=[A1 A];

G. Code untuk mencari ukuran maksimum dari indeks

%Fungsi ini digunakan untuk menentukan pola dengan kotak penyusun

terbanyak function longest=cari(indeks1) jumlah=length(indeks1(:,1)); %Menentukan banyaknya pola for i=1:jumlah maxperbaris(i)=find(indeks1(i,:)>0, 1, 'last'); %Dicari elemen

tidak nol perbaris end longest=max(maxperbaris);


74

H. Code GUI dari aplikasi

% --- Menjalankan aplikasi untuk tombol RUN function RUN_Callback(hObject, eventdata, handles)

%Mengambil data input dari GUI H1 = get(handles.H,'string'); H = str2double(H1);

W1 = get(handles.W,'string'); W = str2double(W1);

beta1 = get(handles.beta,'string'); beta = str2double(beta1)/100;

%Mengambil data kertas kecil dari input GUI tab1 = get(handles.tabel,'Data'); for i1=1:6 h(i1) = str2double(tab1(1,i1)); %data h w(i1) = str2double(tab1(2,i1)); %data w b(i1) = str2double(tab1 (3,i1)); %data b end p=find(h>0, 1, 'last' ); %mencari jumlah elemen h yg tak nol

%mendefinisikan data-data yang telah diinput (step 1) h=h(1:p)'; w=w(1:p)'; b=b(1:p)'; hxw=h.*w; was=beta*H*W; n=10;

hw=[h w [1:p]' zeros(p,1) zeros(p,1)];

%Metode kombinasi pertama untuk memulai iterasi (step 2.a) for i=1:length(h) %Susunan horisontal h_hor=max(h(i),h); w_hor=w(i)+w; in_hor=[(1:length(h))' i*ones(length(h),1)]; %save komposisi

rect trim_hor=h_hor.*w_hor-h.*w-h(i)*w(i); %Susunan vertikal h_ver=h(i)+h; w_ver=max(w(i),w); in_ver=[-1*(1:length(h))' -1*[i*ones(length(h),1)]]; trim_ver=h_ver.*w_ver-h.*w-h(i)*w(i);

hw=[hw; h_hor w_hor in_hor trim_hor; h_ver w_ver in_ver

trim_ver];

end


75

%Seleksi-seleksi pada step 2 F=seleksi_ukuran(hw,H,W); %seleksi ukuran F=seleksi_trim(F,was); %seleksi sisa F=seleksi_bound(F,b); %seleksi batas F=seleksi_twin(F,b); %seleksi kembar

F1=[(1:(length(F(:,1))))' F]; Fj=F1; %menyimpan data T1 sebagai pembanding untuk penghentian

iterasi

%Iterasi algoritma for j=1:n

Fbuild=susun(Fj); F=seleksi_ukuran(Fbuild,H,W); F=seleksi_trim(F,was); inde=[[1:(length(F(:,1)))]' F(:,[3 4])]; inde1=kompo(b,inde); F=seleksi_bound2(F,b,inde1); F=seleksi_twin(F,b); Fj2=[[1:(length(F(:,1)))]' F];

indeks=Fj2(:,[1 4 5]); indeks1=kompo(b,indeks);

%Menghentikan iterasi berlebih F_uji=Fj; Fj=Fj2; [pj1, lb1]=size(F_uji); [pj2, lb2]=size(Fj); if pj1==pj2 jumlah=pj1*lb2; sama=sum(sum(F_uji==Fj)); if jumlah==sama break end end end

%Pembuatan komposisi pola for i=1:length(Fj(:,1)) elmax=cari(indeks1); daftar=abs(indeks1(i,2:elmax)); pola(i,:)=histc(daftar,1:p); end

%Hasil dari pembuatan pola luas = pola*hxw; total_trim = H*W - luas; hasil_akhir = [Fj(:,1:3) luas total_trim pola];

%Menggunakan intlinprog untuk memilih pola f = total_trim; A = pola';


76

[x, fval] =

intlinprog(f,[1:length(f)],[],[],A,b,zeros(1,length(f)),Inf*ones(1

,length(f)));

%Mencari variabel keputusan yang tak nol untuk dijadikan indeks j1 = find(x>0); j2 = hasil_akhir(j1,:); j3 = round(x(j1)); akhir = [j2(:,1) j3 j2(:,5)];

total_kertas = sum(akhir(:,2)); %menghitung jumlah kertas yang

digunakan toler = was*total_kertas; %luas total toleransi kertas persen_sisa = fval/(total_kertas*H*W)*100; %prosentasi total sisa

kertas persen_toler = beta*100; %prosentase toleransi

%indeks yang masuk dalam hasil akhir k1 = akhir(:,1); kk = abs([indeks(k1,2) ; indeks(k1,3)]); c = [k1 ; kk]; c = union(c,c);%menghilangkan elemen yang double c(find(c==0))=[]; k2 = find(kk > p); k3 = sum(k2); while k3 > 0 kk = abs([indeks(kk(k2),2) ; indeks(kk(k2),3)]); k2 = find(kk>p); k3 = sum(k2); c = [c; kk]; c = union(c,c); end

indekss=indeks(c,:);

%Menampilkan hasil pada GUI oops=num2str(fval); set(handles.text7,'string',oops) set(handles.kertasawal,'string',total_kertas); set(handles.toleransi,'string',toler); set(handles.tspersen,'string',persen_sisa); set(handles.bta,'string',persen_toler);

set(handles.hasil1,'data',akhir) set(handles.hasil2,'data',indekss)

% --- Fungsi reset untuk menghapus data pada GUI function pushbutton2_Callback(hObject, eventdata, handles) set(handles.H,'String','') set(handles.W,'String','') set(handles.beta,'String','') set(handles.text7,'String','') set(handles.kertasawal,'String','') set(handles.toleransi,'String','')


77

set(handles.tspersen,'String','') set(handles.bta,'String','') set(handles.tabel,'Data',cell(size(get(handles.tabel,'Data')))) set(handles.hasil1,'Data',cell(size(get(handles.hasil1,'Data')))) set(handles.hasil2,'Data',cell(size(get(handles.hasil2,'Data'))))


mengoptimalkan pemotongan guillotine kertas segi … · pola pemotongan pada gambar 1.8 tidak dapat...

Documents