PENENTUAN BATAS BAWAH PADA METODE BRANCH AND PRICE
SKRIPSI
MEILIANA 080803036
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
PENENTUAN BATAS BAWAH PADA METODE BRANCH AND PRICE
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat untuk mencapai gelar sarjana sains
MEILIANA 080803036
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
PERSETUJUAN
Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PENENTUAN BATAS BAWAH PADA METODE BRANCH AND PRICE : SKRIPSI : MEILIANA : 080803036 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Medan, April 2012 Pembimbing 2
Pembimbing 1
Prof. Dr. Herman Mawengkang NIP 19461128 1974031 001
Prof. Dr. Drs. Iryanto, M.Si NIP. 19460404 1971071 001
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua.
Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D. NIP. 196209011988031002
PERNYATAAN
PENENTUAN BATAS BAWAH PADA METODE BRANCH AND PRICE
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Juli 2012
Meiliana 080803036
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Tuhan yang Maha Penyayang, atas kemurahan dan berkat yang telah diberikan sehingga penulis dapat menyelesaikan skripsi dengan judul ”Penentuan Batas Bawah pada Metode Branch and Price” guna melengkapi syarat memperoleh gelar sarjana Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam di Universitas Sumatera Utara. Dalam kesempatan ini, penulis ingin mengucapkan terima kasih yang sebesarbesarnya kepada semua pihak yang telah membantu dan membimbing penulis dalam penyusunan skripsi ini, ucapan terima kasih saya sampaikan kepada : 1. Bapak Prof. Dr. Drs. Iryanto, M.Si selaku pembimbing I dan Bapak Prof. Dr. Herman Mawengkang selaku pembimbing II yang telah memberikan bimbingan dan pengarahan kepada saya sehingga skripsi ini dapat saya selesaikan.
2. Bapak Drs. Sawaluddin, M.IT dan Bapak Syahril Efendi, S.Si, MIT selaku dosen penguji saya. 3. Bapak Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D. dan Ibu Dra.Mardiningsih, M.Si selaku Ketua dan Sekretaris Departemen Matematika. 4. Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 5. Semua Dosen pada Departemen Matematika FMIPA USU dan pegawai di FMIPA USU. 6. Seluruh teman di jurusan Matematika khususnya stambuk 2008, serta sahabat– sahabat penulis: Windy, Romi, Isnaini, Ningrum, Evi, Riyandi, Sherly, Alan, Lindo, Wilya, dan Indra serta teman-teman lainnya yang tidak bisa penulis sebutkan satu persatu. 7. Seluruh adik-adik junior stambuk 2009, stambuk 2010, stambuk 2011 serta Abang dan Kakak alumni. 8. Paman penulis Lim Chai Kiat yang berkontribusi banyak dalam pendidikan yang saya jalani. 9. Ayahanda LIM CHAI HIE, Ibunda ANG KIM TJUH serta adik-adik penulis FERRY dan MEIRIATI yang selama ini memberikan bantuan dan dorongan yang diperlukan.
Penulis menyadari masih banyak kekurangan dan kelemahan dalam penulisan skripsi ini. Untuk itu penulis minta maaf kepada seluruh pembaca bila ada kesalahan serta penulis mengharapkan saran dan kritikan demi kesempurnaan skripsi ini. Akhir kata, semoga skripsi ini dapat bermanfaat bagi kita semua.
Medan, Juli 2012 Penulis,
Meiliana
ABSTRAK
Program bilangan bulat (Integer Programming) merupakan sutau program linear khusus dimana variabel-variabel keputusannya harus merupakan bilangan bulat. Ada banyak cara untuk menyelesaikan program bilangan bulat ini, diantaranya metode branch and price. Seperti halnya metode branch and bound, dalam penyelesaianya menggunakan metode branch and price akan memerlukan iterasi-iterasi yang panjang. Untuk memperpendek iterasi itu maka ditentukan batas bawahnya. Kata Kunci: Program bilangan bulat, metode branch and price.
DETERMINE THE LOWER BOUND OF BRANCH AND PRICE METHOD
ABSTRACT
Integer Programming is a specific linear programming where the variables of decision are integer. There are so many kind of way to finish this integer programming; one of them is Branch and Price method. Like Branch and Bound method, in the step to finish the integer programming in Branch and Price method need the iterations that are too long. To make the iteration to be short then should be given the lower bound. Keywords: Integer Programming, branch and price method.
DAFTAR ISI
Halaman Judul Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Tinjauan Pustaka 1.4 Tujuan Penelitian 1.5 Kontribusi Penelitian 1.6 Metode Penelitian Bab 2 Landasan Teori 2.1 Program Linear 2.2 Program Bilangan Bulat (Integer Programming) 2.2.1 Beberapa Model Integer Programming 2.2.2 Metode Penyelesaian Integer Programming 2.3 Metode Simpleks 2.4 Metode Branch and Bound 2.5 Metode Branch and Price Bab 3 Pembahasan 3.1 Penentuan Batas Bawah pada Metode Branch and Bound 3.2 Penentuan Batas Bawah pada Metode Branch and Price Bab 4 Kesimpulan dan Saran 4.1 Kesimpulan 4.2 Saran Daftar Pustaka Lampiran
Halaman i ii iii iv vi vii viii ix x 1 2 2 3 4 4
5 9 11 12 13 17 19
21 32 44 44
DAFTAR TABEL
Halaman Tabel 2.1 Tabel Simpleks Tabel 3.1 Tabel Simpleks awal Tabel 3.2 Tabel Simpleks untuk bagian 1 Tabel 3.3 Tabel Simpleks untuk bagian 2 Tabel 3.4 Tabel Simpleks untuk bagian 3 Tabel 3.5 Tabel Simpleks untuk bagian 5 Tabel 3.6 Tabel Simpleks untuk bagian 6 Tabel 3.7 Tabel Simpleks awal Tabel 3.8 Tabel Simpleks untuk bagian 1 Tabel 3.9 Tabel Simpleks untuk bagian 2 Tabel 3.10 Tabel Simpleks untuk bagian 3 Tabel 3.11 Tabel Simpleks untuk bagian 4 Tabel 3.12 Tabel Simpleks awal Tabel 3.13 Tabel Simpleks untuk bagian 1 Tabel 3.14 Tabel Simpleks untuk bagian 2 Tabel 3.15 Tabel Simpleks untuk bagian 4 Tabel 3.16 Tabel Simpleks awal Tabel 3.17 Tabel Simpleks untuk bagian 1 Tabel 3.18 Tabel Simpleks untuk bagian 3 Tabel 3.19 Tabel Simpleks untuk bagian 4
16 22 23 23 25 26 27 28 29 29 31 31 34 35 36 37 39 40 42 43
DAFTAR GAMBAR
Halaman Gambar 3.1 Percabangan untuk iterasi awal Gambar 3.2 Percabangan untuk iterasi 1 Gambar 3.3 Percabangan untuk iterasi 2 Gambar 3.4 Percabangan untuk iterasi 3 Gambar 3.5 Percabangan untuk iterasi awal Gambar 3.6 Percabangan untuk iterasi 1 Gambar 3.7 Percabangan untuk iterasi 2 Gambar 3.8 Percabangan awal Gambar 3.9 Percabangan untuk iterasi 1 Gambar 3.10 Percabangan untuk iterasi 2 Gambar 3.11 Percabangan awal Gambar 3.12 Percabangan untuk iterasi 1 Gambar 3.13 Percabangan untuk iterasi 2
22 24 25 27 28 30 32 34 36 38 39 42 43
