LEMBAR PERSEMBAHAN
“Victoria Concordia Crescit” “Victory Comes Through Harmony” - Arsenal FC
Tugas akhir ini saya persembahkan untuk: Ida Sang Hyang Widhi Wasa yang memberikan kelancaran dan berkah dalam penyusunan skripsi ini Keluarga yang selalu memberi doa serta support kepadaku Kawan-kawan yang sering membantuku Bapak dan Ibu Dosen yang ada di lingkungan Jurusan Matematika Fakultas MIPA Universitas Udayana selama ini membimbingku
ii
PENERAPAN BRANCH AND BOUND ALGORITHM DALAM OPTIMALISASI PRODUKSI ROTI
KOMPETENSI FINANSIAL [SKRIPSI]
Sebagai syarat untuk memperoleh gelar Sarjana Sains bidang Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana
Tulisan ini merupakan hasil penelitian yang belum pernah dipublikasikan
GEDE SURYAWAN 1008405056
Pembimbing II
Pembimbing I
Kartika Sari, S.Si., M.Sc.
Ni Ketut Tari Tastrawati, S.Si., M.Si.
NIP. 197007112003122001
NIP. 197405282002122002
iii
LEMBAR PENGESAHAN TUGAS AKHIR Judul Nama Nim Fakultas/Jurusan Kompetensi Tanggal Seminar
: Penerapan Branch and Bound Algorithm dalam Optimalisasi Produksi Roti : Gede Suryawan : 1008405056 : Matematika dan Ilmu Pengetahuan Alam/Matematika : Finansial : 7 Oktober 2016 Disetujui oleh:
Pembimbing II
Pembimbing I
Kartika Sari, S.Si., M.Sc. NIP. 197007112003122001
Ni Ketut Tari Tastrawati, S.Si., M.Si. NIP. 197405282002122002 Penguji I
Drs. I Nyoman Widana, M.Si. NIP. 196408081991031004
Penguji III
Penguji II
Ni Made Asih, S.Pd., M.Si. NIP. 197405282002122002
Ir. Tjokorda Bagus Oka, Ph.D. NIP. 195411261986031001
Mengetahui, Jurusan Matematika FMIPA Unud Ketua
Desak Putu Eka Nilakusmawati, S.Si., M.Si. NIP. 197106111997022001
iv
Judul
:
Penerapan Branch and Bound Algorithm dalam Optimalisasi Produksi Roti
Nama
: Gede Suryawan (NIM: 1008405056)
Pembimbing : 1. Ni Ketut Tari Tastrawati, S.Si., M.Si. 2. Kartika Sari, S.Si., M.Sc.
ABSTRAK Perusahaan yang bergerak di bidang produksi seperti Ramadhan Bakery pasti menginginkan keuntungan yang optimal di setiap produksinya. Untuk memperoleh keuntungan yang optimal, Ramadhan Bakery yang memproduksi roti mempertimbangkan kombinasi penjualan produk per harinya. Penelitian ini bertujuan untuk mencari keuntungan optimal yang diperoleh perusahaan per harinya dengan menentukan kombinasi jumlah produksi masing-masing roti. Metode Branch and Bound digunakan di dalam penelitian ini dengan bantuan software QSB 2.0. Berdasarkan hasil penerapan metode ini, perusahaan mendapatkan keuntungan sebesar Rp. 1.195.624 dengan memproduksi 360 pcs roti coklat biasa, 300 pcs roti coklat ekstra, 306 pcs roti bulat rasa coklat dan 129 pcs roti kasur rasa coklat. Keuntungan yang diperoleh akan meningkat sebanyak 25,2 % dari sebelumnya. Kata Kunci: Optimalisasi, Branch and Bound, Keuntungan Optimal
v
Title
: Branch and Bound Algorithm Implementation for Optimizing Bread Production
Name
: Gede Suryawan (NIM: 1008405056)
Supervisor
: 1. Ni Ketut Tari Tastrawati, S.Si., M.Si. 2. Kartika Sari, S.Si., M.Sc.
ABSTRACT Companies which engaged in production activities such as Ramadhan Bakery absolutely want optimum profit in their every production. To obtain optimum benefit, Ramadhan Bakery who producing bread conside a combination of product sales per day. This study aims to find the optimal gains obtained by the company per day by determining the combination of production quantities of each bread. Branch and Bound method applied for this study and helped by QSB 2.0 software. Based on the result of applying this method, it made profit Rp. 1.195.624 by producing 360 pcs of original chocolate bread, 300 pcs of extra chocolate bread, 306 pcs of rounding chocolate-flavored bread and 129 pcs of mattress chocolate-flavored bread. The profit will increase amount 25,2 % than before. Keywords: Optimize, Branch and Bound, Optimum Profit
vi
KATA PENGANTAR Puji syukur penulis panjatkan kehadirat Tuhan Yang Maha Esa karena atas rahmat-Nya penulis dapat menyelesaikan tugas akhir dengan judul “Penerapan Branch and Bound Algorithm dalam Optimalisasi Produksi Roti”. Sehubungan dengan telah terselesaikannya tugas akhir ini, maka penulis mengucapkan terima kasih kepada berbagai pihak yang telah membantu penulis, antara lain: 1.
Ibu Desak Putu Eka Nilakusmawati, S.Si, M.Si. selaku Ketua Jurusan Matematika FMIPA Universitas Udayana.
2.
Bapak I Wayan Sumarjaya, S.Si., M.Stats., selaku Ketua Komisi Tugas Akhir di Jurusan Matematika Universitas Udayana.
3.
Ibu Ni Ketut Tari Tastrawati, S.Si., M.Si. selaku Dosen Pembimbing I yang telah banyak membantu, membimbing, serta memberikan semangat selama penyusunan tugas akhir ini.
4.
Ibu Kartika Sari, S.Si., M.Sc. selaku Dosen Pembimbing II yang telah banyak memberikan bimbingan, dukungan serta arahan, sehingga tugas akhir ini dapat terselesaikan.
5.
Ibu Ni Made Asih, S.Pd., M.Si. selaku Dosen Pembimbing Akademik yang telah banyak membantu memberikan nasehat serta semangat kepada Saya.
6.
Seluruh dosen di lingkungan Jurusan Matematika FMIPA Universitas Udayana yang telah memberikan banyak ilmu dan motivasi dari awal masa perkuliahan hingga sekarang.
7.
Teman-teman di Jurusan Matematika yang telah memberikan dukungan moral dalam penyelesaian tugas akhir ini.
8.
Seluruh keluarga yang telah memberikan semangat untuk menyelesaikan tugas akhir ini.
vii
Penulis menyadari bahwa apa yang telah dipaparkan pada tugas akhir ini masih jauh dari sempurna. Oleh karena itu kritik dan saran yang membangun sangat penulis harapkan.
Bukit Jimbaran,
Penulis
viii
BIODATA ALUMNI
Nama Lengkap
: Gede Suryawan
NIM
: 1008405056
Jenis Kelamin
: Laki-laki
Tempat, Tanggal Lahir
: Denpasar, 19 September 1992
Alamat
: Jalan Pertulaka No. 14 Denpasar Utara
Agama
: Hindu
Tanggal Lulus
: 7 Oktober 2016
Kompetensi
: Finansial
IP Kumulatif
: 2,86
Predikat Kelulusan
: Memuaskan
Nilai TOEFL Lokal
: 463
Email
:
[email protected]
Nomor Handphone
: 08983193026
Nama Ayah
: I Nyoman Sukarya
Nama Ibu
: Ni Nyoman Rintin
Alamat Ayah/Ibu
: Jalan Pertulaka No. 14 Denpasar Utara
ix
DAFTAR ISI
Hal PROPOSAL TUGAS AKHIR.................................................................................... i LEMBAR PENGESAHAN TUGAS AKHIR .......................................................... iv ABSTRAK..................................................................................................................v KATA PENGANTAR............................................................................................ viii BIODATA ALUMNI ............................................................................................... ix DAFTAR ISI ..............................................................................................................x DAFTAR TABEL ................................................................................................... xii DAFTAR LAMPIRAN .......................................................................................... xiii BAB I PENDAHULUAN ..........................................................................................1 1.1
Latar Belakang ..............................................................................................1
1.2
Rumusan Masalah .........................................................................................3
1.3
Tujuan Penelitian ..........................................................................................3
1.4
Batasan Masalah............................................................................................3
1.5
Manfaat Penelitian .......................................................................................4
BAB II TINJAUAN PUSTAKA ................................................................................5 2.1
Optimalisasi ..................................................................................................5
2.2
Pemrograman Integer (PI).............................................................................8
2.3
Branch and Bound Algorithm (B&B) .........................................................13
BAB III METODE PENELITIAN ...........................................................................22 3.1
Sumber Data................................................................................................22
3.2
Variabel Penelitian ......................................................................................22
3.3
Data Penelitian ............................................................................................22
vx
3.4
Metode Analisis Branch and Bound Algorithm ..........................................23
BAB IV HASIL DAN PEMBAHASAN..................................................................25 4.1
Memodelkan Masalah Optimalisasi ke dalam Bentuk Persamaan Linear ..25
4.1.1
Variabel Keputusan.................................................................................25
4.1.2
Batasan Penggunaan Bahan Terigu.........................................................26
4.1.3
Batasan Penggunaan Bahan Ragi............................................................27
4.1.4
Batasan Penggunaan Bahan Susu Bubuk................................................28
4.1.5
Batasan Penggunaan Bahan Gula Pasir...................................................28
4.1.6
Batasan Penggunaan Bahan Margarin ....................................................29
4.1.7
Batasan Penggunaan Bahan Coklat.........................................................30
4.1.8
Batasan Penggunaan Bahan Garam ........................................................31
4.1.9
Batasan Penggunaan Bahan Kuning Telur..............................................32
4.1.10 Batasan Target Produksi ..........................................................................32 4.1.11 Batasan Produksi Maksimal....................................................................34 4.1.12 Biaya Pembuatan Roti.............................................................................35 4.1.13 Fungsi Tujuan .........................................................................................37 4.1.14 Model Pemrograman Linear dalam Optimalisasi Produksi Roti ............39 4.2 Menghitung Nilai Optimum dari Model .....................................................40 BAB V KESIMPULAN DAN SARAN ...................................................................47 5.1
Kesimpulan .................................................................................................47
5.2
Saran............................................................................................................47
DAFTAR PUSTAKA LAMPIRAN
xi viii
DAFTAR TABEL
Tabel
Halaman
2.1
Tabel Simpleks............................................................................................11
4.1
Data Penelitian Bahan (dalam gr per pcs roti) ............................................25
4.2
Target Produksi Masing-masing Jenis Roti ................................................33
4.3
Batasan Produksi Maksimal........................................................................34
4.4
Harga Beli Bahan ........................................................................................35
4.5
Harga Bahan Pembuatan Roti (dalam gr per satu pcs roti) .........................35
4.6
Biaya Pembuatan Tiap Jenis Roti (per pcs) ................................................36
4.7
Harga Jual Tiap Jenis Roti ..........................................................................37
4.8
Keuntungan Roti per pcs.............................................................................38
ixii viii x
DAFTAR LAMPIRAN
Lampiran 1.1
Lampiran Perhitungan Awal
1.2
Lampiran Perhitungan Bagian A
1.3
Lampiran Perhitungan Bagian B
1.4
Lempiran Perhitungan Bagian A1
xiii viii
