OPTIMASI PEMOTONGAN BALOK KAYU DENGAN POLA PEMOTONGAN SATU DIMENSI MENGGUNAKAN TEKNIK PEMBANGKIT KOLOM (COLUMN GENERATION TECHNIQUE)
SKRIPSI
Diajukan kepada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Yogyakarta untuk Memenuhi sebagian Persyaratan guna Memperoleh Gelar Sarjana Sains
Disusun oleh: Jariyanto 013114738
PROGRAM STUDI MATEMATIKA JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI YOGYAKARTA 2008
OPTIMASI PEMOTONGAN BALOK KAYU DENGAN POLA PEMOTONGAN SATU DIMENSI MENGGUNAKAN TEKNIK PEMBANGKIT KOLOM (COLUMN GENERATION TECHNIQUE) Oleh Jariyanto NIM: 013114738 ABSTRAK Perusahaan pengolahan kayu biasanya mengkonversikan kayu-kayu bulat menjadi kayu berbentuk balok, papan atau bentuk-bentuk lain yang sesuai dengan tujuan penggunaannya. Selanjutnya kayu-kayu yang telah berbentuk balok, maupun papan diolah kembali menjadi ukuran-ukuran tertentu sesuai dengan pesanan dari para pemilik usaha dagang (UD) kayu. Penelitian ini bertujuan untuk mengoptimalkan penggunaan balok kayu dengan cara meminimumkan sisa pemotongan dan mengurangi produksi surplus. Dengan demikian, optimasi ini dapat membantu perusahaan kayu agar tidak menderita kerugian serta mengurangi pemborosan dalam penggunaan kayu. Persoalan yang kemudian muncul adalah jika perusahaan kayu tersebut menerima pesanan dalam jumlah besar, misal sebanyak m, akibatnya pola-pola yang digunakan juga semakin banyak, misal n pola. Untuk memenuhi pesanan, perusahaan kayu harus memotong balok kayu panjang (L) meter berdasarkan pola j , j 1, 2, ..., n . Hasil pemotongannya sejumlah aij batang dengan panjang K i ,
i 1, 2, ..., m ; j 1, 2, ..., n. Persoalan ini dapat disusun ke dalam persoalan program linear dan dapat dicari solusinya menggunakan teknik-teknik penyelesaian dalam program linear. Salah satu teknik yang digunakan dalam optimasi pemotongan balok kayu adalah teknik pembangkit kolom (column generation technique). Dengan teknik ini akan diperoleh pola-pola yang paling layak, yaitu pola yang menghasilkan sisa pemotongan paling minimum. Penyelesaian dengan teknik ini, iterasinya akan menghasilkan suatu subpersoalan yang dinamakan persoalan knapsack dan digunakan metode cabang dan batas untuk menyelesaikannya. Perhitungan menggunakan teknik pembangkit kolom dapat diselesaikan dengan bantuan software aplikasi LINDO. Dari ouput LINDO, persoalan knapsack dapat dirumuskan dari dual prices. Selanjutnya persoalan knapsack diselesaikan dengan metode cabang dan batas secara manual. Harga akhir ( z j c j ), j 1, 2, ..., n, menggunakan teknik pembangkit kolom akan optimal jika fungsi tujuan dari persoalan knapsack bernilai nol. Jika belum nol maka solusi yang diperoleh merupakan suatu pola baru yang berkorespondensi dengan pola-pola pemotongan yang sudah ada. Iterasi selanjutnya digunakan metode simpleks direvisi. Dari tabel bersangkutan teknik ini akan menghasilkan persoalan knapsack kembali. Iterasi berulang sampai diperoleh solusi optimal. Solusi yang diperoleh merupakan suatu pola-pola pemotongan yang akan menghasilkan sisa pemotongan dan produksi surplus yang minimum.
DAFTAR ISI Halaman HALAMAN JUDUL ...............................................................................
i
HALAMAN PERSETUJUAN ................................................................
ii
HALAMAN PENGESAHAN .................................................................
iii
HALAMAN PERNYATAAN ................................................................
iv
HALAMAN MOTTO DAN PERSEMBAHAN .....................................
v
ABSTRAK ..............................................................................................
vi
KATA PENGANTAR .............................................................................
vii
DAFTAR ISI ...........................................................................................
ix
DAFTAR GAMBAR ..............................................................................
xi
DAFTAR TABEL ...................................................................................
xii
BAB I
BAB II
PENDAHULUAN A. Latar Belakang Persoalan ...........................................
1
B. Pembatasan Persoalan ...............................................
5
C. Rumusan Persoalan ...................................................
5
D. Tujuan Penulisan ......................................................
6
E. Manfaat Penulisan ....................................................
6
LANDASAN TEORI A. Program Linear .........................................................
7
B. Sistem Persamaan .....................................................
14
C. Matriks ......................................................................
17
D. Persoalan Knapsack ..................................................
29
E. Metode Simpleks ......................................................
30
F. Metode Simpleks Direvisi ........................................
39
G. Program Linear Bilangan Bulat ................................
50
H. Metode Cabang dan Batas (Branch and Bound Method) ..................................................................... BAB III
53
PEMBAHASAN A. Pola Awal dan Kombinasi Pola yang paling layak dalam Pemotongan Balok Kayu ...............................
63
B. Implementasi Teknik Pembangkit Kolom dalam Optimasi Pemotongan Balok Kayu .......................... C. Implementasi
Sofware Aplikasi dalam Mencari
Solusi Optimal Pemotongan Balok Kayu ................. BAB IV
72
98
PENUTUP A. Kesimpulan ...............................................................
120
B. Saran .........................................................................
123z
DAFTAR PUSTAKA ............................................................................
124
DAFTAR GAMBAR Halaman Gambar 2.1
Tiga kemungkinan solusi persamaan linear ......................
16
Gambar 2.2
Diagram alir metode simpleks .........................................
31
Gambar 2.3
Diagram alir metode cabang dan batas .............................
56
Gambar 2.4
Pohon cabang dan batas persoalan knapsack 0-1 ............
62
Gambar 3.1
Pola pemotongan ..............................................................
63
Gambar 3.2
Pohon cabang dan batas persoalan awal ..........................
89
Gambar 3.3
Pohon cabang dan batas persoalan kedua .........................
96
DAFTAR TABEL Halaman Tabel 2.1
Tabel umum metode simpleks ..........................................
34
Tabel 2.2
Tabel awal metode simpleks ..............................................
36
Tabel 2.3
Tabel simpleks antara awal ...............................................
37
Tabel 2.4
Tabel kedua metode simpleks ............................................
37
Tabel 2.5
Tabel simpleks antara kedua .............................................
38
Tabel 2.6
Tabel ketiga metode simpleks ............................................
39
Tabel 3.1
Tabel hasil pesanan kombinasi I, II dan III ........................
67
Tabel 3.2
Tabel jumlah pesanan ........................................................
68
Tabel 3.3
Tabel pola pemotongan balok kayu panjang 7 meter .........
80
Tabel 3.4
Tabel pola pemotongan balok kayu panjang 5 meter .........
104
Tabel 3.5
Tabel pola pemotongan balok kayu panjang 8 meter .........
112
