plagiat merupakan tindakan tidak terpuji · pdf filedapat dipindahkan ke file excel. contoh...

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

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

i

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


ii

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


v

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


vii

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


viii

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


x

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.


xi

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


xii

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


xiii

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


1

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).


2

Proses pemotongan rol kertas pada mesin penggulung yang menghasilkan rol-

rol 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.

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

(a) (b)

(c)


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.

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.

2 Cutter Knives

Reel Produce by

Paper Machine

(Input)

Large Sheet

(Output)

5 Slitter Knives


4

Berikut skema proses produksi kertas.

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

Mesin kertas

Mesin penggulung Pisau pemotong

Rol kertas

Mesin pemotong

ukuran kertas kecil

Kertas ukuran kecil

Penyortiran

Mesin

pemotong

Pengemasan

Manual

Pengemasan

Kertas ukuran besar


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 (lebar) dan fokus pada (optimalisasi)

meminimumkan jumlah rol.


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


13

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:


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 = + + + 2.1

Dengan kendala

{ + + + =+ + + =+ + + =, , … ,

2.2

Perumusan di atas dapat ditulis secara ringkas menjadi


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 harus

bernilai tak negatif. Fungsi linear (2.3) disebut fungsi tujuan. Dengan disebut

koefisien teknis, disebut koefisien ongkos, dan disebut suku tetap di ruas kanan

disingkat “suku tetap” atau “ruas kanan”. Jika , = , … , 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 dikembang-

kan dan diterapkannya ke persoalan bisnis. Metode simpleks adalah metode siste-

matis 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

∑= , = , … , 2.6

, = , … ,

Maka dapat didefinisikan variabel pengetat + , + , … , + dan fungsi tujuan

sebagai berikut.

+ = −∑= , = , … , 2.7

=∑= 2.8

Dengan notasi ini, masalah ini dapat diuraikan kembali menjadi

Memaksimumkan dengan kendala , , … , + 2.9

Setiap solusi layak , , … , dari (2.6) ditunjukkan oleh + bilangan

bulat tak negatif , , … , + dengan + , + , … , + 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 , , … , dari (2.6) dapat diperluas, dengan cara yang

ditunjukkan oleh (2.7), menjadi , , … , + dari (2.9).

2. Setiap solusi layak , , … , + dari (2.9) dapat dipersempit dengan

menghapus variabel pengetat, menjadi solusi layak , , … , dari (2.6).

3. 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 , , … , + dan .

Pertama definisikan + , + , … , + dan , serta + + 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 variabel dari , , … , +

dan fungsi tujuan dalam variabel tersisa.

3. 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 , , merupakan variabel

tidak dasar (diberi nilai nol) dan variabel pengetat , , , merupakan variabel

dasar. Jadi solusi layak yang bersesuaian adalah = , = , = , =, = , = , = , dan = . Sehingga memenuhi syarat kedua dan ketiga

dalam kamus.

Pada iterasi pertama, kita mencoba meningkatkan nilai dengan membuat

salah satu variabel sisi kanan positif. Terdapat tiga variabel , , yang akan

dipilih. Biasanya akan dipilih variabel pada 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 =. Sehingga kendala adalah batas atas terketat dan mengimplikasikan

. Dalam meningkatkan solusi layak diperoleh = dan = . Variabel

masuk menjadi basis 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 = . Sehingga memenuhi syarat kedua

dan ketiga dalam kamus.

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 meningkat, maka begitu juga nilai = / . Namun,

nilai , , dan menurun, dan tidak satu pun diizinkan menjadi negatif. Ketiga

kendala , , memberikan batas atas pada kenaikan , diberikan

batas tiap variabel yaitu = , = / , = sehingga kendala adalah

batas atas terketat dan mengimplikasikan / . Dalam meningkatkan solusi

layak diperoleh = / dan = . Variabel masuk menjadi basis dan

variabel 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 = / . Sehingga memenuhi syarat

kedua dan ketiga dalam kamus.

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 menurun, dan

tidak satu pun diizinkan menjadi negatif. Keempat kendala , ,, memberikan batas atas pada kenaikan , diberikan batas tiap variabel

yaitu = / , = / , = / , = sehingga kendala

adalah batas atas terketat dan mengimplikasikan / . Dalam meningkatkan

solusi layak diperoleh = / dan = . Variabel masuk menjadi basis dan

variabel 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 , , (diberi nilai nol) dan

variabel dasar , , , . Jadi solusi layak yang bersesuaian adalah =/ , = / , = / , = / , = , = , = , dan = .

Sehingga memenuhi syarat kedua dan ketiga dalam kamus.

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 = . Hal ini memenuhi syarat kedua dan

ketiga dalam kamus.

Untuk setiap pilihan bilangan , , , , , , dan , berikut pernyataan

ekuivalen yang memenuhi syarat pertama dalam kamus:

1. , , , , , , dan merupakan solusi (2.10)




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 + , + , … , + maka masalah

ini menjadi sebagai berikut.

Maksimumkan

= (2.15)

Dengan kendala

=

(2.16)

Dimana = , , … , + �, = , , … , + , =[ , +⋱ , + ], dan = [ ].


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 variabel-

variabel dasar dan tidak dasar diketahui.

Untuk setiap solusi layak ∗ yaitu , , … , + dibagi ke dalam variabel

dasar dan variabel tidak dasar. Contohnya, membagi vektor menjadi dan �

sehingga matriks terbagi menjadi dan �, dan menjadi dan �. Dengan

demikian kita dapat menuliskan = menjadi

[ �] [ �] = = − � �

(2.17)

Dengan = = [ �] [ �] = + � �

Dimana matriks adalah nonsingular.

Teorema 2.1

Matriks adalah nonsingular.

Bukti:

Kita tunjukkan bahwa matriks adalah nonsingular dengan menunjukkan = tepat memiliki satu solusi. Karena solusi layak ∗ memenuhi persamaan

∗ = dan �∗ = , maka persamaan tersebut memenuhi persamaan ∗ =


27

∗ − � �∗ = . Untuk memeriksa bahwa tidak ada solusi lain, dimisalkan

terdapat sebarang solusi layak ̃ sedemikian hingga ̃ = dan ̃� = .

Dengan demikian vektor ̃ memenuhi ̃ = ̃ + �̃� = , itu harus

memenuhi persamaan di kamus yang bersesuaian dengan ∗. Tetapi karena ̃ � = maka ̃ = ∗ . Jadi, terbukti matriks adalah nonsingular.█

Matriks disebut juga matriks basis atau basis. Matriks basis dapat kita

notasikan menjadi matriks . Karena adalah matriks nonsingular maka − akan

selalu ada. Sehingga kita dapat menuliskan persamaan dan menjadi =− − − � � dan = − + � − − � �. Tentunya − tak

lain adalah vektor ∗ 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 = − dengan menyelesaikan

sistem = . Kedua, menghitung � − � kemudian dipilih elemen dari

vektor � − � 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

turun ke nol meninggalkan basis. Pada persamaan = ∗ − − � �,

berubah dari ∗ menjadi ∗ − � dengan merupakan kolom − � yang

bersesuaian dengan variabel masuk atau dapat dituliskan = − . Jika terdapat

elemen yang memenuhi ∗ − � = maka variabel tersebut menjadi variabel

keluar.

Berikut iterasi dari metode simpleks direvisi yaitu sebagai berikut.

1. Selesaikan sistem = dimana adalah matriks basis awal, sehingga

ditemukan vektor .

2. Tentukan kolom yang masuk, yaitu jika variabel tidak dasar berhubungan

dengan elemen dari � dan kolom dari �, maka � − � = − .

Untuk masalah maksimum (minimum), kolom 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.

3. Selesaikan sistem = , sehingga didapat vektor .

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 ∗ − � = maka kolom tersebut menjadi kolom keluar.

5. 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

Akhir

Tidak

Tidak terdapat

penyelesaian

Tidak

Menyelesaikan sistem = − .

Menyelesaikan sistem = −

Apakah terdapat

kenaikan nilai t terbesar

sedemikian hingga ∗ − � 0?

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

Didapat nilai B dan ∗ dengan

menggantikan kolom keluar

dengan kolom masuk.

Solusi optimal dan

didapat nilai B dan ∗

yang baru

Ya

Ya

Menentukan nilai awal B dan ∗

Tidak terdapat

kolom masuk

Terdapat kolom

masuk

Mencari vektor a

(kolom masuk) yaitu elemen

paling positif dari � − �. Apakah

semua elemen � − �<0?

Gambar 2.1 : Diagram alir metode simpleks direvisi


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. Menyelesaikan sistem = 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.

3. Selesaikan sistem = , sehingga didapat vektor = [ ,,, ]. 4. Didapatkan nilai � = sedemikian hingga ∗ − � dan terdapat 1

komponen dari ∗ − � = yaitu variabel yang menjadi variabel keluar.

5. Didapat matriks awal yang baru dengan menukar kolom masuk dengan

kolom keluar yaitu

= [ ] dan vektor ∗ = [ ]. Iterasi 2:

1. Menyelesaikan sistem = sehingga diperoleh vektor = [ ]. 2. Tentukan kolom yang masuk dengan menyelesaikan � − � = −

yaitu sebagai berikut


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, sub-

masalah 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 adalah pembulatan ke bawah dari

solusi program linear berbentuk pecahan.

b. � = � + , dimana 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 sub-

masalah 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 � sebagai berikut.

Minimumkan = +

Dengan kendala

{ ++, dan bilan�an bulat Jawab:

1. 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 = , . Solusi tidak

berbentuk bilangan bulat maka kembali ke langkah 2.




sebagai berikut.

Sub-masalah 5: � = � + , ,

Minimumkan = +

Dengan kendala

{ ++

,

dan

Sub-masalah 6: � = � + , ,


41

Minimumkan = +

Dengan kendala

{ ++

,



Langkah 5: Dari sub-masalah 5 diperoleh = , = , , dan = , .

Solusi yang diperoleh tidak berbentuk bilangan bulat maka kembali ke langkah

2.




sebagai berikut.

Sub-masalah 7: � = � + , ,

Minimumkan = +

Dengan kendala

{ ++

,


42

dan

Sub-masalah 8: � = � + , ,

Minimumkan = +

Dengan kendala

{ ++

,



Langkah 5: Dari sub-masalah 7 cabang dihentikan karena sub-masalah tidak

memiliki daerah layak.

Dari sub-masalah 8 diperoleh = , = , dan = . Solusi berbentuk

bilangan bulat maka = dijadikan sebagai batas atas.


bilangan bulat dan = lebih kecil dari batas atas sebelumnya maka =

dijadikan sebagai batas atas yang baru.


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.

�0

1 = 2,5

2 = 0

= 2,5

�1

1 = 2

2 = 1,2

= 3,2

�2

1 = 3

2 = 0

= 3

�3

Tidak

memiliki

daerak

layak

�4

1 = 1,67

2 = 2

= 3,67

�5

1 = 1

2 = 3,6

= 4,6

�6

1 = 2

2 = 2

= 4

�8

1 = 2

2 = 4

= 6

�7

Tidak

memiliki

daerah

layak

1 2

2 1

1 1

2 3

1 3

2 2

1 2

2 4

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

∑= � (2.18)

Dimana adalah bilangan bulat tak negatif = , , . . . , dan merupakan

banyaknya barang ke- yang dimasukan ke dalam karung, adalah ukuran barang

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

Kita asumsikan adalah nilai barang ke-i yang bernilai positif (variabel

dengan dapat segera dihapus). Perbandingan ⁄ merupakan nilai per

satuan ukuran dari barang ke- atau sebagai efisiensi variabel . Kita asumsikan

lagi efisiensi variabel 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 cabang-

cabang yang merupakan solusi-solusi layak itu sendiri.

Untuk membuat suatu cabang, pada setiap cabang dibuat nilai sebesar

mungkin lalu dilanjutkan pada cabang berikutnya dengan nilai + sebesar

mungkin begitu seterusnya. Secara resmi, adalah bilangan bulat yang diperoleh

dengan membulatkan nilai ke bawah, solusi ini didefinisikan dengan rekursi

(perulangan)

= � −∑−= ⁄

(2.21)

Dengan = , , . . . , 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 ∗, ∗ , … , ∗ menghasilkan

∑ ∗= =

Jika ∑ = > , maka mengganti dengan ∑ = dan mengganti ∗ , ∗ , … , ∗ dengan , , … , .

Selanjutnya menemukan cabang yang baru dari solusi layak ( , , … , )

dengan = − dan tetap mereduksi sampai > ditemukan. Jika

didapatkan terbesar sedemikian hingga − dan > maka dapat

ditunjukkan bahwa ̅ = untuk = , , . . . , − dan ̅ = − .


46

Berdasarkan (2.19), setiap variabel + , + , … , + memiliki efisiensi

paling besar + +⁄ maka

∑ ̅= + ++ ∑ ̅= +

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 ̅ , ̅ , … , ̅ tidak layak untuk

dibuatkan cabang lagi (atau cabang dipotong) dimana koefisien adalah bilangan

bulat positif. Sehingga harus dibuatkan cabang lagi yaitu dengan menemukan

terbesar sedemikian hingga − dan > dan ditunjukkan bahwa ̅ =

untuk = , , . . . , − dan ̅ = − .

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

ketika koefisien bukan bilangan bulat positif menjadi

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

Metode ini disebut dengan metode cabang dan batas yang akan ditunjukkan

dengan ringkas pada langkah-langkah di bawah.

1. Menentukan nilai awal yaitu = dan = .

2. Menemukan perpanjangan cabang. Untuk = + , + , . . . , maka =⌊(� − ∑ −= )⁄ ⌋. Biasanya untuk = �⁄ . Maka didapat solusi

terbaik ∗ , ∗ , … , ∗ .

3. Memperbaiki solusi. Jika ∑ = > , maka mengganti dengan ∑ =

dan mengganti ∗ , ∗ , … , ∗ dengan , , … , .

4. Menemukan cabang selanjutnya.

Menemukan terbesar sedemikian hingga − dimana > . Kita

dapat tuliskan ̅ = untuk = , , . . . , − .

a. Jika = maka berhenti; selain itu ganti dengan − .

b. Jika = , maka kembali ke 4a, selain itu ganti dengan = − .

5. Pencarian cabang yang lebih baik.

Jika ∑ ̅= + ��+1��+1 (� − ∑ ̅= ) (untuk koefisien bukan

bilangan bulat positif) atau ∑ ̅= + ��+1��+1 (� − ∑ ̅= ) + (untuk

koefisien 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

Akhir

Ya

Mengganti solusi sebelumnya

( 1∗, 2

∗ ,… , ∗ ) dengan

1, 2 ,… , .

TidakM Tidak

berubah

Apakah terdapat

= 0 dan = 1?

Mereduksi k sampai diperoleh

> 0 lalu mengganti

dengan ̅ = − 1, dimana ̅ = untuk =

1, 2, . . . , − 1.

Tidak

Apakah koefisien

bilangan bulat

positif?

Menentukan perpanjangan cabang.

Untuk = + 1, + 2, . . . , maka

= ⌊(� − ∑ −1

=1 )⁄ ⌋ dan

didapat solusi terbaik 1∗ , 2

∗ ,… , ∗ .

Apakah ∑ ̅=1 ++1

+1(� − ∑ ̅=1 ) ?

Apakah ∑ ̅=1 ++1

+1(� − ∑ ̅=1 )

+ 1 ?

Ya

Menentukan nilai

awal yaitu = 0

dan = 0.

Vektor a

Tidak

Tidak

Mengganti M

dengan ∑ =1

Ya

Ya

Tidak

Apakah ∑ =1 > ?

Ya

Gambar 2.2: Diagram alir masalah Knapsack

Contoh 2.4


50

Maksimumkan

+ + +

Dengan kendala , + , + +

Jawab:


2. Menemukan cabang. Untuk = + , + , . . . , maka = ,⁄ =

= ⌊( −∑−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑−= )⁄ ⌋ = − , . + , . + . ⁄ =

Maka didapat solusi terbaik ∗ = , ∗ = ∗ = ∗ = .

3. Menentukan apakah solusi yang diperoleh meningkat?

Karena ∑ = = > = , maka = dan ∗ = , ∗ = ∗ = ∗ =

diganti menjadi = , = = = .

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=1 dimana >, 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 ̅ = .


51

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

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

. + /, − , .

+ = , >

Karena pertidaksamaan tersebut tidak terpenuhi maka cabang layak untuk

dibuatkan cabang lagi. Kembali ke langkah 2

2. Diketahui k=1 dan = ̅ = , maka diperoleh

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − , . + , . + . )⁄ ⌋

=

3. Karena ∑ = = , > = , maka = , dan ∗ = , ∗ =∗ = ∗ = diganti menjadi = , = , = , = .

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=2 dimana > diperoleh. Maka kita ganti = dengan ̅ = .



52


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

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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . + . ) + / ( − , . + , . ) ,

+ = ,

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak untuk


4. Didapatkan k=2 = lalu dikurangkan sampai diperoleh k=1 dengan

diperoleh > . Maka kita ganti = dengan ̅ = .




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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . ) + /, ( − , . ) ,

+ , = , ,


53


dibuatkan cabang lagi. Kembali ke langkah 4.

4. Kita peroleh k=1 dimana > , maka kita ganti = dengan ̅ = .




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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . ) + /, ( − , . ) ,

= , ,


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

Gambar 2.4: Pohon enumerasi yang dihasilkan dari contoh 2.4

Contoh 2.5

Maksimumkan

= + + +


Jawab:



= ⌊( −∑−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑−= )⁄ ⌋ = − , . + , . ⁄ =

= = = == = = =

= dipotong

= dipotong

= dipotong


55

= ⌊( −∑−= )⁄ ⌋ = − , . + , . + . ⁄ =



Karena ∑ = = > = , maka = dan ∗ = , ∗ = ∗ = ∗ =

diganti menjadi = , = = = .

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=1 dimana >, maka kita ganti = menjadi = .




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

∑ ̅= + ++ ( −∑ ̅= )

. + /, − , .

+ = , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − , . ,⁄ =


56

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . + . ⁄ =

3. Karena ∑ = = , > = , maka = , dan ∗ = , ∗ =∗ = ∗ = dengan = , = , = , = .

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=2 dimana >. Maka kita ganti = dengan ̅ = .




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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . + . ) + / ( − , . + , . ) ,

+ = , > ,



2. Diketahui k=2, = ̅ = dan = ̅ = , maka diperoleh

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . ⁄ =


57

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . + . ⁄ =

3. Karena ∑ = = , > = , , maka = , dan ∗ = , ∗ =, ∗ = , ∗ = dengan ∗ = , ∗ = , ∗ = , ∗ = .

4. Didapatkan k=3 dan > , maka kita ganti = menjadi ̅ = .



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

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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . + . + . ) + / ( − , . + , . + . ) ,

+ = , ,



4. Didapatkan k=3 dan > , maka kita ganti = menjadi ̅ = .




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


58

∑ ̅= + ++ (� −∑= ) ,

( . + . + . ) + / ( − , . + , . + . ) ,

+ = , ,



4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=1 dimana > dan kita ganti = dengan ̅ = .




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

∑ ̅= + ++ (� −∑= ) ,

( . ) + /, ( − , . ) ,

+ , = , ,



4. Kita peroleh k=1 dengan < dan kita ganti = dengan ̅ = .



59



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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . ) + /, ( − , . ) ,

= , ,



4. Kita peroleh k=1 dengan = maka iterasi berhenti.

Jadi didapatkan solusi optimal yaitu ∗ = , ∗ = , ∗ = , ∗ = dan =, .


60



Contoh 2.6

Maksimumkan

+ + +


Jawab:

Dengan langkah-langkah seperti contoh sebelumnya didapatkan solusi yaitu ∗ = , ∗ = , ∗ = , ∗ = dengan = , ∗ = , ∗ = , ∗ = , ∗ =

dengan = , dan ∗ = , ∗ = , ∗ = , ∗ = dengan = .

= = = ==

= = ==

= == dipotong

= dipotong= dipotong

= dipotong


61



= = = == = = =

= dipotong

== = =

= == dipotong

= dipotong

=

= = == dipotong

= dipotong

= dipotong

= dipotong

= dipotong


61

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 = ,… , , 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 � yang bukan bagian dari

model bagian pemotongan persediaan. Misalkan komponen dari vektor �. Setiap komponen berkorespondensi dengan banyaknya rol ukuran yang digunakan

pada pola pemotongan. Misalkan adalah koefisien pada fungsi tujuan yang

berhubungan dengan setiap keperluan permintaan pada model bagian pemotongan

persediaan. Maka pola pemotongan � yang harus ditambahkan ke model bagian

sewaktu-waktu adalah

−∑�= <

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 , , … , dan adalah

vektor baris dengan komponen , , . . . , . Setiap kolom � = [ , , … , ]� dari

menunjukkan pola pemotongan rol jumbo menjadi rol kecil dengan lebar = , , … , . Jadi � adalah kolom dari jika hanya jika , , … ,

adalah bilangan bulat tak negatif sedemikian hingga ∑ �. Dengan metode


66

simpleks yang direvisi ditunjukkan adanya kolom tidak dasar dari di langkah 2

dari setiap iterasi, yaitu ketika kolom baru � (kolom masuk) ditemukan. Setelah

menghitung vektor baris (harus berupa bilangan bulat tak negatif), kita mencari , , … , bilangan bulat tak negatif sedemikian hingga

, untuk setiap bilangan bulat

∑�= �

−∑�= <

(3.3)

(3.4)

(3.5)

Ketika ∑�= > , 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

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

lebar adalah . Diasumsikan lebar rol kecil diurutkan dari terbesar sampai

terkecil: > > >

Akan dibentuk nilai awal dan ∗ dengan iterasi. Dimulai iterasi ,

diketahui � terdiri − + dari subscript , , . . . , . Untuk setiap subscript di �, terdapat ′ yang menunjukkan sisa permintaan rol kecil dengan lebar (untuk

nilai awal kita tentukan ′ = untuk setiap i). Pada iterasi ke-j, kita definisikan

kolom ke-j dengan = [ , , … , ]� yang akan membentuk .

= { , jika �� −∑−= ⁄ , jika �

Solusi awal ∗ akan menggunakan pola ini sampai sisa permintaan ′ terpenuhi. Nilai berkorespondensi dengan kolom ke-j dari dan merupakan nilai

terkecil dari ′⁄ dengan � dan > . Sehingga ′ untuk setiap


68

� dan = ′ untuk paling tidak suatu �. Kemudian hapus subscript dari �, mengganti ′ dengan ′ − , 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 = , = dan R terdiri dari 4 subscript (i=1,2,3,4).

Karena �, maka kita peroleh

= ,⁄ =

= ⌊( −∑= )⁄ ⌋ = − , . ,⁄ =


69

= ⌊( −∑= )⁄ ⌋ = − , . + ⁄ =

= ⌊( −∑= )⁄ ⌋ = − , . + + ⁄ =

Karena > maka = ′⁄ = / = . Sehingga ′ untuk

setiap � dan = ′ . Jadi kita hapus subscript k=1 dari R dan diperoleh ′ =− . = , ′ = − . = , ′ = − . = .

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

Karena � dan � maka diperoleh

=

= ,⁄ =

= ⌊( −∑= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑= )⁄ ⌋ = − , . + , . + . ⁄ =

Karena > maka = ′⁄ = / = . Sehingga ′ untuk

setiap � dan = ′ . Jadi kita hapus subscript k=2 dari R dan diperoleh ′ =− . = , ′ = − . = .


70

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

Karena , � dan � maka diperoleh

=

=

= / =

= ⌊( −∑= )⁄ ⌋ = − , . + , . + . ⁄ =

Karena > maka = ′⁄ = / = , . Sehingga ′ untuk

setiap � dan = ′ . Jadi kita hapus subscript k=3 dari R dan diperoleh ′ =− , . = .

Iterasi 4. Diketahui = , = dan R terdiri dari 1 subscript (i=4). Karena , , � dan � maka diperoleh =

=

=

= ⌊( −∑= )⁄ ⌋ = − , . + , . + . ⁄ =

Karena > maka = ′⁄ = / = .

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.

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

1. Menyelesaikan masalah dengan

metode simpleks direvisi.

2. Pada langkah 2 metode simpleks

direvisi menggunakan metode

cabang dan batas masalah

knapsack.


72

= [ ] dan ∗ = [ , ] Kemudian kita memulai iterasi pertama yang dilakukan melalui langkah-

langkah berikut.

1. Menyelesaikan sistem = [ , , , ], sehingga diperoleh nilai =[ , , , ]. 2. Mencari bilangan bulat tak negatif , , , sedemikian hingga , + , + +

+ + + >

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

dan diperoleh = , = , = , = atau dapat ditulis =[ , , , ]�. Karena ∑�= > maka = [ , , , ]� menjadi kolom masuk.

3. Menyelesaikan sistem = , sehingga didapat vektor = [ , , , ]�.

4. Mencari kenaikan nilai � terbesar sedemikian hingga ∗ − � . Didapatkan � = dari perbandingan ⁄ dan , ⁄ . Kolom ketiga adalah kolom keluar

karena ∗ − = [ , , , ]�.

5. Sehingga kita mendapatkan

= [ ] dan ∗ = [ − �/� ] = [ ] Kemudian dapat dimulai iterasi kedua yaitu sebagai berikut


73


+ + + >


dan diperoleh = , = , = , = atau dapat ditulis =[ , , , ]�. Karena ∑�= > maka = [ , , , ]� menjadi kolom masuk.


4. Mencari kenaikan nilai � terbesar sedemikian hingga ∗ − � . Didapatkan � = dari perbandingan ⁄ , ⁄ dan ⁄ . Kolom pertama adalah kolom

keluar karena ∗ − = [ , , , ]�.

5. Sehingga kita mendapatkan

= [ ] dan ∗ = [ �− �/− �/ ] = [ ] Kemudian dilanjutkan iterasi ketiga yaitu sebagai berikut.



74

+ + + >


dan diperoleh = , = , = , = atau dapat ditulis = [ , , , ]�.

Karena ∑�= = maka = [ , , , ]� 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

Pola

pemotongan ke-

Lebar rol

Banyak rol

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

Pola Lebar rol Sisa

(inchi)

A

(roll)

B

(roll)

C

(roll)

D

(roll) 25.5 22.5 20 15

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 6 1 1 1 1 1

Jumlah rol 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

Kolom

Pesanan untuk lebar rol 25,5

inchi terpenuhi yaitu 78 rol,

pesanan rol 22,5 inchi terpenuhi

yaitu 40 rol, pesanan rol 20


pesanan rol 42 inchi terpenuhi

yaitu 30 rol.

1. Semua pesanan dapat

terpenuhi.

2. Sisa yang dihasilkan

kurang dari sama dengan

lebar minimum pesanan

rol.

Program QM Pesanan untuk lebar rol 25,5






yaitu 30 rol.


terpenuhi.




rol.

Toolbox

Optimization

pada

MATLAB






terpe-nuhi.




76



yaitu 30 rol.


rol.

Toolbox

Solver pada

Excel







yaitu 30 rol.


terpenuhi.




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

Pola

pemotongan ke-

Lebar rol Banyak

rol 135 108 93 42

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

Pola Lebar rol Sisa

(cm)

A

(roll)

B

(roll)

C

(roll)

D

(roll) 135 108 93 42

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

Kolom

Pesanan untuk lebar rol 135 cm

terpenuhi yaitu 97 rol, pesanan

rol 108 cm terpenuhi yaitu 610

rol, pesanan rol 93 cm terpenuhi

yaitu 395 rol, pesanan rol 42 cm

terpenuhi yaitu 211 rol.

1. Semua pesanan dapat terpe-

nuhi dengan jumlah yang

tepat/tidak berlebih.

2. Namun terdapat pola (pola

4) yang menghasilkan sisa

dengan lebar melebih dari

lebar minimum pesanan rol.

Program QM Pesanan untuk lebar rol 135 cm


rol 108 cm terpenuhi yaitu


nuhi. Namun pada pesanan

rol 42 cm dan 120 cm


78

610,5 rol, pesanan rol 93 cm



rol.

menghasilkan rol yang

melebihi pesanan.



lebar mi-nimum pesanan

rol.

Toolbox

Optimization

pada

MATLAB







rol.





melebihi pesanan.




rol.

Toolbox

Solver pada

Excel







rol.





melebihi pesanan.




79


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

terpe-nuhi dengan jumlah

yang tepat/tidak berlebih.

2. Tidak perlu membentuk

semua pola kemungkinan.

1. Terdapat sisa yang

melebihi dari lebar

minimum pesanan rol.

2. Solusi belum tentu berupa

bilangan bulat.

Program QM,

toolbox

Optimization

pada MATLAB,

dan toolbox

Solver pada

Excel




rol.

1. Jumlah rol yang dihasil-

kan dapat melebihi jumlah

rol yang diminta/dipesan.

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 ′ − dan lanjutkan

proses iterasi ke-j+1.

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

Rol ( )

Permintaan

( )

Produksi (setelah

dibulatkan ke bawah)

Sisa ( ′) 135 cm 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 { − . ⁄ = min { =

= min{ ′⌊(� −∑= )⁄ ⌋ = min { − . + . ⁄

= min { =

= min{ ′⌊(� −∑= )⁄ ⌋

= min { − . + . + . ⁄ = min { =

Sehingga didapatkan ′ = , ′ = , ′ = , ′ = .

Iterasi 2

= min { ′�⁄ = min { ⁄ = min { =


82

= min{ ′⌊(� −∑= )⁄ ⌋ = min { − . ⁄ = min { =

= min{ ′⌊(� −∑= )⁄ ⌋ = min { − . + . ⁄

= min { =

= min{ ′⌊(� −∑= )⁄ ⌋

= min { − . + . + . ⁄ = min { =

Sehingga didapatkan ′ = , ′ = , ′ = , ′ = .

Iterasi 3

= min { ′�⁄ = min { ⁄ = min { =

= min{ ′⌊(� −∑= )⁄ ⌋ = min { − . ⁄ = min { =

= min{ ′⌊(� −∑= )⁄ ⌋ = min { − . + . ⁄

= min { =


83

= { ′⌊(� −∑= )⁄ ⌋

= min { − . + . + . ⁄ = min { =

Sehingga didapatkan ′ = , ′ = , ′ = , ′ = . 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

Pola

Lebar rol pesanan

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


84

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


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.


91

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


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.


93

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.


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.


95

LAMPIRAN A

Berikut ini adalah langkah-langkah penyelesaian dari contoh soal.

1. Jawaban dari contoh soal 2.6

Maksimumkan

+ + +


Jawab:



= ⌊( −∑−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑−= )⁄ ⌋ = − , . + , . + . ⁄ =



Karena ∑ = = , > = , maka = , dan ∗ = , ∗ =∗ = ∗ = diganti menjadi = , = = = .


96

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=1 dimana >. Maka kita ganti = menjadi ̅ = .




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

∑ ̅= + ++ (� −∑ ̅= ) ,

. + /, − , . ,

+ = , > ,




= ⌊( −∑ ̅−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − , . + , . + . )⁄ ⌋

=


97

3. Karena ∑ = = > = , , maka = dan ∗ = , ∗ = ∗ =∗ = diganti menjadi = , = , = , = .

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=2 dimana >. Maka kita ganti = dengan ̅ = ..




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

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

( . + . ) + / ( − , . + , . )

+ =



4. Didapatkan k=2 = lalu dikurangkan sampai diperoleh k=1 dimana > dan kita ganti = dengan ̅ = .




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


98

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

( . ) + /, ( − , . )

+ , = , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − , . + , . + . )⁄ ⌋

= 3. Karena ∑ = = = = , maka = dan ∗ = , ∗ = diganti

menjadi = , = , = , = .

4. Didapatkan k=3 dimana < , maka kita ganti = dengan ̅ = .




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


99

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

( . + . + ) + / ( − , . + , . + )

+ , = , >



2. Diketahui k=3, = ̅ = , = ̅ = , dan = ̅ = , maka diperoleh

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − , . + , . + . )⁄ ⌋

= 3. Karena ∑ = = , = , maka = dan ∗ = , ∗ =

diganti menjadi = , = , = , = .

4. Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=2 dimana <, maka kita ganti = dengan ̅ = .




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

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

( . + . ) + / ( − , . + , . )


100

+ = ,



4. Kita peroleh k=2 dimana < , maka kita ganti = dengan ̅ = .




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

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

( . + . ) + / ( − , . + , . )

+ . = ,







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


101

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

( . ) + /, ( − , . )

= , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − , . ,⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = − , . + , . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − , . + , . + . )⁄ ⌋

= 3. Karena ∑ = = = , maka = dan ∗ = , ∗ = diganti

menjadi = , = , = , = .






102

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

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

( . + . ) + / ( − , . + , . )

+ , = ,







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

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

( . + . ) + / ( − , . + , . )

+ = ,





103




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

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

( . + . ) + / ( − , . + , . )

+ , = ,







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

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

( . + . ) + / ( − , . + , . )

= ,


104



4. Kita peroleh k=1 dimana = , maka iterasi berhenti.

Jadi didapatkan solusi yaitu ∗ = , ∗ = , ∗ = , ∗ = dengan = , ∗ = , ∗ = , ∗ = , ∗ = dengan = , dan ∗ = , ∗ = , ∗ = , ∗ =

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

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

Karena �, maka kita peroleh

= ⁄ =

= ⌊( −∑= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑= )⁄ ⌋ = − . + ⁄ =

= ⌊( −∑= )⁄ ⌋ = − . + + ⁄ =


106

Karena > maka = ′⁄ = / = , . Sehingga ′ untuk

setiap � dan = ′ . Jadi kita hapus subscript k=1 dari R dan diperoleh ′ =− , . = , ′ = − , . = , ′ = − , . = .

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

Karena � dan � maka diperoleh

=

= ⁄ =

= ⌊( −∑= )⁄ ⌋ = − . + . ⁄ =

= ⌊( −∑= )⁄ ⌋ = − . + . + . ⁄ =

Karena , > maka = ′⁄ , ′⁄ = ⁄ , ⁄ = , . Sehingga ′ untuk setiap � dan = ′ . Jadi kita hapus

subscript k=4 dari R dan diperoleh ′ = − , . = , ′ = −, . = .

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

Karena , � dan � maka diperoleh

=

= ⁄ =


107

= ⌊( −∑= )⁄ ⌋ = − . + . ⁄ =

=

Karena > maka = ′⁄ = / = , . Sehingga ′ untuk setiap � dan = ′ . Jadi kita hapus subscript k=2 dari R dan

diperoleh ′ = − , . = .

Iterasi 4. Diketahui = , = dan R terdiri dari 1 subscript (i=3). Karena , , � dan � maka diperoleh

=

=

= ⁄ =

=

Karena > maka = ′⁄ = / = , .

Jadi diperoleh solusi layak sebagai berikut.

= [ ] dan ∗ = [ ,,,, ] Kemudian, kita menggunakan metode simpleks direvisi dengan nilai awal di

atas.


108

1. Menyelesaikan sistem = [ , , , ], sehingga diperoleh nilai =[ , , , ]. 2. Mencari bilangan bulat tak negatif , , , sedemikian hingga + + +

+ + >

Masalah di atas dikenal dengan masalah Knapsack. Berikut langkah-langkah

metode cabang dan batas Knapsack.

1) Menentukan nilai awal yaitu = dan = .

2) Menemukan cabang. Untuk = + , + , . . . , maka = ⁄ =

= ⌊( −∑−= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑−= )⁄ ⌋ = ⌊( − . + . )⁄ ⌋ =

= ⌊( −∑−= )⁄ ⌋ = − . + . + . ⁄ =


3) Menentukan apakah solusi yang diperoleh meningkat?

Karena ∑ = = > = , maka = dan ∗ = , ∗ = ∗ =∗ = diganti menjadi = , = = = .


109

4) Didapatkan k=3 = lalu dikurangkan sampai diperoleh k=1

dimana > , 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 = ̅ = , maka diperoleh

= ⌊( −∑ ̅−= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − . + . )⁄ ⌋

=

= ⌊( −∑ ̅−= )⁄ ⌋

= ⌊( − . + . + . )⁄ ⌋ =


110

3) Karena ∑ = = = , maka = dan ∗ = , ∗ = ∗ =∗ = diganti menjadi = , = , = , = .


dimana > . Maka kita ganti = menjadi ̅ = .



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

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

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

( . + . ) + / ( − . + . )

+ = , >

Karena pertidaksamaan tersebut tidak terpenuhi makacabang layak


2) Diketahui k=2 dan = ̅ = , = ̅ = , maka diperoleh

= ⌊( −∑ ̅−= )⁄ ⌋ = − . + . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋

= ⌊( − . + . + . )⁄ ⌋ =


111

3) Karena ∑ = = , < = maka = dan ∗ = , ∗ =, ∗ = , ∗ = diganti menjadi = , = , = , =

4) Didapatkan k=3 dimana < , maka kita ganti = dengan ̅ =.



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

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

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

( . + . + . ) + ( − . + . + . )

+ = , <

Karena pertidaksamaan tersebut terpenuhi maka cabang tidak layak



dimana < , maka kita ganti = dengan ̅ = .



pertidaksamaan berikut dengan k=1 dan ̅ =

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


112

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

( . ) + / ( − . )

= , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = − . + . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋

= − . + . + . ⁄ =

3) Karena ∑ = = = , maka = dan ∗ = , ∗ = ∗ = diganti menjadi = , = , = , = .

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





113

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

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

( . + . ) + / ( − . + . )

+ = , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − . + . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋

= − . + . + . ⁄ =

3) Karena ∑ = = , > = , maka = , dan ∗ =, ∗ = , ∗ = , ∗ = diganti menjadi = , = , =, = .

4) Kita peroleh k=3 dimana > . Maka kita ganti = menjadi ̅ =.





114

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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . + . ) + ( − . + . + . ) ,

+ = , < ,







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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . ) + ( − . + . + . ) ,

+ = , < ,

Karena pertidaksamaan tersebut terpenuhi makacabang tidak layak



115





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

∑ ̅= + ++ (� −∑ ̅= ) ,

( . + . ) + ( − . + . )

+ = <



4) Kita peroleh k=1 dimana = , maka iterasi berhenti.

Jadi didapatkan solusi optimal yaitu ∗ = , ∗ = , ∗ = , ∗ = dengan = , . Karena ∑�= < maka = [ , , , ]�menjadi kolom masuk.


4. Mencari nilai t terkecil sedemikian sedemikian hingga ∗ − � .

Didapatkan � = , dari perbandingan rasio , ⁄ dan , ⁄ . Kolom

keempat adalah kolom keluar karena ∗ − , = [ , , , ]. 5. Sehingga kita mendapatkan


116

= [ ] dan ∗ = [ ,,, − �/� ] = [ ,,,, ] Kemudian dapat dimulai iterasi kedua yaitu sebagai berikut

1. Menyelesaikan sistem = [ , , , ], sehingga diperoleh nilai =[ , , , ]. 2. Mencari bilangan bulat tak negatif , , , sedemikian hingga + + +

+ + >

Masalah di atas dikenal dengan masalah Knapsack. Berikut langkah-langkah

metode cabang dan batas Knapsack.

1) Menentukan nilai awal yaitu = dan = .

2) Menemukan cabang. Untuk = + , + , . . . , maka = ⁄ =

= ⌊( −∑−= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑−= )⁄ ⌋ = ⌊( − . + . )⁄ ⌋ =

= ⌊( −∑−= )⁄ ⌋ = − . + . + . ⁄ =



117

3) Menentukan apakah solusi yang diperoleh meningkat?

Karena ∑ ∗= = > = , maka = dan ∗ = , ∗ = ∗ =∗ = diganti menjadi = , = = = .


dimana > , maka kita ganti = menjadi ̅ = .




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

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

. + / − .

+ = , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − . + . )⁄ ⌋

=


118

= ⌊( −∑ ̅−= )⁄ ⌋

= ⌊( − . + . + . )⁄ ⌋ =

3) Karena ∑ = = = , maka = dan ∗ = , ∗ = ∗ =∗ = diganti menjadi = , = , = , = .


dimana > . Maka kita ganti = menjadi ̅ = .




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

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

( . + . ) + / ( − . + . )

+ = , <




dengan diperoleh > . Maka kita ganti = dengan ̅ = .



119



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

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

( . ) + / ( − . )

= , >




= ⌊( −∑ ̅−= )⁄ ⌋ = − . ⁄ =

= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − . + . )⁄ ⌋

=

= ⌊( −∑ ̅−= )⁄ ⌋

= ⌊( − . + . + . )⁄ ⌋ =

3) Karena ∑ = = = , maka = dan ∗ = , ∗ =

diganti menjadi = , = , = , = .


120


dimana < , maka kita ganti = dengan ̅ = .




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

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

( . + . ) + / ( − . + . )

+ = , >




= ⌊( −∑ ̅−= )⁄ ⌋ = ⌊( − . + . )⁄ ⌋

=

= ⌊( −∑ ̅−= )⁄ ⌋

= ⌊( − . + . + . )⁄ ⌋ =

3) Karena ∑ = = = , maka = dan ∗ = , ∗ =, ∗ = , ∗ = diganti menjadi = , = , = , = .


121





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

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

( . + . + . ) + ( − . + . + . )

+ =







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

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


122

( . + . + . ) + ( − . + . + . )

+ = ,







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

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

( . + . ) + / ( − . + . )

= ,



4) Kita peroleh k=1 dimana = , maka iterasi berhenti.

Jadi didapatkan solusi optimal yaitu ∗ = , ∗ = , ∗ = , ∗ = dengan = . Karena ∑�= maka = [ , , , ]� 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.

Pola

pemotongan ke-

Lebar rol Banyak

rol 135 108 93 42

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


plagiat merupakan tindakan tidak terpuji · pdf filedapat dipindahkan ke file excel. contoh...

Documents