APLIKASI METODE BRANCH AND CUT DALAM OPTIMASI PRODUKSI POT BUNGA (Studi Kasus: UD. Pot Bunga Mukhlis Rangkuti, Gelugur)
SKRIPSI
NUSAIBAH KHOLILAH 100803035
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2015
APLIKASI METODE BRANCH AND CUT DALAM OPTIMASI PRODUKSI POT BUNGA (Studi Kasus: UD. Pot Bunga Mukhlis Rangkuti, Gelugur)
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat untuk mencapai gelar Sarjana Sains
NUSAIBAH KHOLLAH 100803035
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2015
PERSETUJUAN
Judul
: Aplikasi Metode Branch and Cut Dalam Optimasi Produksi Pot Bunga (Studi Kasus: UD. Pot Bunga Mukhlis Rangkuti, Gelugur)
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: : : : : :
Skripsi Nusaibah Kholilah 100803035 Sarjana (S1) Matematika Matematika Matematika Dan Ilmu Pengetahuan Universitas Sumatera Utara
Alam
Disetujui di Medan, April 2015
Komisi Pembimbing: Pembimbing 2,
Pembimbing 1,
Dr. Elly Rosmaini, M.Si.
Dr. Faigiziduhu Bu’ulolo, M.Si. NIP. 195312181980031003
NIP. 196005201985032002
Disetujui oleh: Departemen Matematika FMIPA USU Ketua,
Prof. Dr. Tulus, M.Si. NIP. 196209011988031002 i
PERNYATAAN
APLIKASI METODE BRANCH AND CUT DALAM OPTIMASI PRODUKSI POT BUNGA (Studi Kasus: UD. Pot Bunga Mukhlis Rangkuti, Gelugur)
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri. Kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, April 2015
NUSAIBAH KHOLILAH 100803035
ii
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Allah SWT Yang Maha Pemurah dan Maha Penyayang, dengan limpahan karunia-Nya penulis dapat menyelesaikan penyusunan skripsi ini dengan judul Aplikasi Metode Branch and Cut dalam Optimasi Produksi Pot Bunga (Studi Kasus: UD. Pot Bunga Mukhlis Rangkuti, Gelugur). Terimakasih penulis sampaikan kepada Bapak Dr. Faigiziduhu Bu’ulolo, M.Si selaku pembimbing 1 dan Ibu Dr. Elly Rosmaini, M.Si selaku pembimbing 2 yang telah meluangkan waktunya selama penulisan skripsi ini. Terimakasih kepada dosen pembanding, Bapak Dr. Syahriol Sitorus, S.Si, M.IT dan Ibu Dra. Asima Manurung, M.Si atas saran yang membangun dalam penulisan skripsi ini. Terimakasih kepada Bapak Prof. Dr. Tulus, M.Si dan Ibu Dr. Mardiningsih, M.Si selaku Ketua dan Sekretaris Departemen Matematika FMIPA USU. Terimakasih kepada Bapak Dr. Sutarman, M.Sc selaku Dekan FMIPA USU, Pembantu Dekan FMIPA USU, seluruh Staff dan Dosen Matematika serta rekan-rekan kuliah. Akhirnya tidak terlupakan kepada Ayahanda Muhammad Dongan dan Ibunda Hamidah serta saudara-saudari yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Allah SWT akan membalasnya.
iii
APLIKASI METODE BRANCH AND CUT DALAM OPTIMASI PRODUKSI POT BUNGA (Studi Kasus: UD. Pot Bunga Mukhlis Rangkuti, Gelugur)
ABSTRAK
UD. Pot Bunga Mukhlis Rangkuti merupakan usaha kecil dan menengah yang memproduksi pot bunga dengan berbagai bentuk dan ukuran. Perusahaan ini melakukan produksi berdasarkan persediaan bahan baku dan jumlah permintaan yang ada. Oleh karena itu, perusahaan perlu melakukan perencanaan produksi agar dapat memproduksi pot bunga secara optimal. Metode yang digunakan untuk menentukan jumlah produksi optimal adalah metode branch and cut. Metode branch and cut merupakan gabungan dari metode branch and bound dan metode cutting plane. Metode ini mampu menyelesaikan permasalahan integer programming dengan lebih baik dibandingkan dengan metode branch and bound murni. Hasil penelitian diperoleh bahwa terdapat 2 alternatif jumlah produksi optimal dari masing-masing pot bunga, yaitu 70 buah pot segi minimalis, 90 buah pot sampan minimalis, 117 buah pot petak segi besar bonsai, 99 buah pot bulat besar ukir bonsai, 77 buah pot segi ukir bonsai, 68 buah pot guci sedang dan 58 buah pot guci kecil, atau 70 buah pot segi minimalis, 92 buah pot sampan minimalis, 115 buah pot petak segi besar bonsai, 98 buah pot bulat besar ukir bonsai, 81 buah pot segi ukir bonsai, 68 buah pot guci sedang dan 58 buah pot guci kecil dengan kentungan sebesar Rp 11.554.000.
Kata kunci: Integer programming, branch and cut, optimasi, perencanaan produksi.
iv
APLICATION OF BRANCH AND CUT METHOD IN OPTIMIZATION OF FLOWER POT PRODUCTION (Case Study: UD. Pot Bunga Mukhlis Rangkuti, Gelugur)
ABSTRACT
UD. Pot Bunga Mukhlis Rangkuti are small and medium enterprises which produce the flower pot with a various of shapes and sizes. This company production based on inventory of raw materials and the amount of the demand. Therefore, companies need to make production planning in order to produce an optimal flower pots. The method used to determine the optimal production is the branch and cut method. Branch and cut method is a combination of branch and bound method and cutting plane method. This method is able to solve the integer programming problems better than pure branch and bound method. The results obtained that there are 2 alternative optimal production of each flowerpot, namely 70 pieces square minimalist pots, 90 pieces canoe minimalist pots, 117 pieces large square bonsai pots, 99 large round carved bonsai pots, 77 pieces square carved bonsai pots, 68 medium jar pots and 58 pieces small jar pots, or 70 pieces square minimalist pots, 92 pieces canoe minimalist pots, 115 pieces large square bonsai pots, 98 large round carved bonsai pots, 81 square carved bonsai pots, 68 pieces medium jar pots and 58 pieces small jar pots with profits at Rp 11.554.000.
Keywords: Integer programming, branch and cut, optimization, production planning.
v
DAFTAR ISI
Halaman PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR LAMPIRAN
i ii iii iv v vi viii ix
Bab 1. PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tinjauan Pustaka 1.5 Tujuan Penelitian 1.6 Manfaat Penelitian 1.7 Metodologi Penelitian 1.6.1 Studi Pendahuluan 1.6.2 Pengumpulan Data 1.6.3 Pengolahan Data
1 1 2 2 3 5 5 5 5 5 6
Bab 2. LANDASAN TEORI 2.1 Perencanaan Produksi 2.2 Program Linier 2.2.1 Unsur – Unsur Program Linier 2.2.2 Asumsi Dasar Program Linier 2.3 Program Bilangan Bulat Linier 2.4 Metode Simpleks 2.4.1 Langkah – Langkah Metode Simpleks 2.5 Metode Dual Simpleks 2.6 Metode Branch And Bound 2.7 Metode Cutting Plane 2.8 Metode Branch And Cut
7 7 9 10 10 11 13 15 16 17 19 23
Bab 3. HASIL DAN PEMBAHASAN 3.1 Pengumpulan Data 3.2 Pengolahan Data 3.2.1 Perumusan Fungsi Tujuan 3.2.2 Perumusan Fungsi Kendala 3.2.3 Analisis Metode Branch And Cut
26 26 29 29 30 31
vi
Bab 4. KESIMPULAN DAN SARAN 4.1 Kesimpulan 4.2 Saran
67 67 68
DAFTAR PUSTAKA
69
LAMPIRAN
70
vii
DAFTAR TABEL
Nomor Tabel 2.1 2.2 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20
Judul
Tabel Optimum Program Masalah Linier Setelah Penambahan Pemotongan Fraksional Data Volume Penjualan Pot Bunga Bulan Januari – Juni 2014 Komposisi Bahan Baku Produk Persediaan Bahan Baku Selama Satu Bulan Biaya Produksi Setiap Produk Harga Jual Produk Keuntungan Tiap Satu Unit Produk Jumlah Produksi Pot Bunga Bulan Maret 2015 Iterasi Awal Metode Dual Simpleks Iterasi 1 Metode Dual Simpleks Iterasi 2 Metode Dual Simpleks Iterasi 3 Metode Dual Simpleks Iterasi 4 Metode Dual Simpleks Iterasi 5 Metode Dual Simpleks Iterasi 6 Metode Dual Simpleks Iterasi 7 Metode Dual Simpleks Iterasi 8 Metode Dual Simpleks Iterasi 9 Metode Dual Simpleks Tabel Simpleks Optimal Sub-Masalah 2 Tabel Simpleks Optimal Sub-Masalah 5 Solusi Optimal
viii
Halaman
20 22 26 27 27 28 28 29 29 34 36 38 40 42 44 46 48 50 52 57 62 65
DAFTAR LAMPIRAN
Nomor Lamp 1 2 3 4 5 6 7 8 9
Judul
Halaman
Hasil Perhitungan Sub-Masalah 1 dengan Bantuan Software POM-QM for Windows Hasil Perhitungan Sub-Masalah 2 dengan Bantuan Software POM-QM for Windows Hasil Perhitungan Sub-Masalah 3 dengan Bantuan Software POM-QM for Windows Hasil Perhitungan Sub-Masalah 4 dengan Bantuan Software POM-QM for Windows Hasil Perhitungan Sub-Masalah 5 dengan Bantuan Software POM-QM for Windows Hasil Perhitungan Sub-Masalah 6 dengan Bantuan Software POM-QM for Windows Diagram Penyelesaian dengan Menggunakan Metode Branch and Cut Hasil Perhitungan dengan Metode Branch and Bound Menggunakan Software POM-QM for Windows Gambar Produk
ix
70 71 72 73 74 75 76 77 81
