APLIKASI ALGORITMA BRANCH AND BOUND UNTUK MENGOPTIMALKAN PERMASALAHAN PENUGASAN DENGAN ADANYA KENDALA TAMBAHAN
SKRIPSI
PAULINUS SITANGGANG 050803060
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
APLIKASI ALGORITMA BRANCH AND BOUND UNTUK MENGOPTIMALKAN PERMASALAHAN PENUGASAN DENGAN ADANYA KENDALA TAMBAHAN
SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
PAULINUS SITANGGANG 050803060
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2010
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: APLIKASI ALGORITMA BRANCH AND BOUND UNTUK MENGOPTIMALKAN PERMASALAHAN PENUGASAN DENGAN ADANYA KENDALA TAMBAHAN : SKRIPSI : PAULINUS SITANGGANG : 050803060 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, Maret 2010
Komisi Pembimbing
:
Pembimbing II
Pembimbing I
Drs. Henry Rani Sitepu, M.Si NIP 19530303 198303 1 002
Prof. Dr. Herman Mawengkang NIP 19461128 197403 1 001
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,
Dr. Saib Suwilo, M.Sc NIP. 19640109 198803 1 004
Universitas Sumatera Utara
iii
PERNYATAAN
APLIKASI ALGORITMA BRANCH AND BOUND UNTUK MENGOPTIMALKAN PERMASALAHAN PENUGASAN DENGAN ADANYA KENDALA TAMBAHAN
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Maret 2010
PAULINUS SITANGGANG 050803060
Universitas Sumatera Utara
iv
PENGHARGAAN
Puji
Universitas Sumatera Utara
v
ABSTRAK
Masalah penugasan adalah merupakan suatu masalah yang sangat nyata dalam kehidupan keprofesian. Secara umum masalah ini berkisar tentang bagaimana memasangkan orang atau karyawan dengan job yang ada secara tepat. Sehingga biaya atau waktu yang diperlukan adalah minimum. Karena dalam kehidupan nyata setiap pekerjaan itu berbedabeda dan setiap orang memiliki keahlian yang berbeda pula, maka biaya yang dibutuhkan untuk setiap pemilihan pekerjaan tentunya berbeda pula. Fungsi objektif dari masalah ini adalah bagaimana meminimumkan biaya yang terjadi selama penugasan, sehingga kita sebagai pihak yang melakukan penugasan mengeluarkan biaya seminimum mungkin. Algoritma Branch and Bound merupakan pendekatan yang baik dalam mencari solusi ini. Dengan metode Breadht First Search dan menggunakan metode pencarian solusi dalam ruang solusi yang sistematis, algoritma ini sangat tepat untuk masalah ini.
Universitas Sumatera Utara
vi
APPLICATIONS ALGORITHM BRANCH AND BOUND FOR OPTIMIZING ASSIGNMENT PROBLEM WITH ADDITIONAL CONSTRAINTS
ABSTRACT
Assignment problem is a very real problem in life professions. In general, this issue revolves on how to pair the person or employee with an existing job properly. So that the cost or time required is minimum. Because in real life every job is different and everyone has different skills, the cost needed for every vote certainly different jobs. Objective function of this problem is how to minimize costs incurred during the assignment, so that we as a part an assignment spend a minimum cost. Branch and Bound algorithm is a good approach in finding solutions. Breadht First Search method and search using the solution in a systematic solution space, this algorithm is very appropriate for this problem.
Universitas Sumatera Utara
vii
DAFTAR ISI
Halaman ii iii iv v vi vii viii ix
PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR BAB 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Pembatasan Masalah 1.4 Tujuan penelitian 1.5 Manfaat penelitian 1.6 Metode penelitian 1.7 Tinjauan Pustaka
1 1 2 2 2 3 3 3
BAB 2 LANDASAN TEORI 2.1 Matriks 2.1.1 Pengertian Matriks 2.1.2 Penjumlahan Matriks 2.1.3 Perkalian Matriks 2.1.4 Perkalian Matriks Dengan Bilangan 2.2 Masalah Transportasi
6 6 6 7 7 8 8
BAB 3 PEMBAHASAN 3.1 Algoritma Branch and Bound 3.1.1 Pembangkit Status Secara Breadht First Search 3.1.2 Pembangkit Status Secara Depth First Search 3.2 Contoh Kasus dan Penyelesaiannya 3.3 Pembahasan Dengan Adanya Kendala Tambahan 3.3.1 Untuk Job Lebih Banyak Dari Pekerja 3.3.2 Untuk Pekerja Lebih Banyak Dari Job
13 13 13 14 15 26 26 34
BAB 4 KESIMPULAN DAN SARAN 4.1 Kesimpulan 4.2 Saran
40 40 40
DAFTAR PUSTAKA
Universitas Sumatera Utara
viii
DAFTAR TABEL
Halaman Tabel 2.1
Model transportasi
12
Universitas Sumatera Utara
ix
DAFTAR GAMBAR
Halaman Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 3.7 Gambar 3.8 Gambar 3.9 Gambar 3.10 Gambar 3.11 Gambar 3.12 Gambar 3.13 Gambar 3.14 Gambar 3.15 Gambar 3.16 Gambar 3.17 Gambar 3.18 Gambar 3.19 Gambar 3.20 Gambar 3.21
Diagram pohon untuk metoda Branch and Bound Akar pohon assignment problem untuk Pohon ruang status untuk simpul 2 Pohon ruang status untuk simpul 3 Pohon ruang status untuk simpul 4 Pohon ruang status untuk simpul 5 Pohon ruang status untuk simpul 6 Pohon ruang status untuk simpul 7 Pohon ruang status untuk simpul 8 Pohon ruang status untuk simpul 9 Pohon ruang status untuk simpul 10 Pohon ruang solusi Assignment Problem Pohon ruang status simpul 5 untuk job lebih banyak dari pekerja Pohon ruang status simpul 8 untuk job lebih banyak dari pekerja Pohon status simpul 10 untuk job lebih banyak dari pekerja Pohon solusi pertama untuk job lebih banyak dari pekerja Pohon solusi kedua untuk job lebih banyak dari pekerja Pohon simpul 5 untuk pekerja lebih banyak dari job Pohon simpul 8 untuk pekerja lebih banyak dari job Pohon simpul 10 untuk pekerja lebih banyak dari job Pohon solusi untuk pekerja lebih banyak dari job
14 16 17 17 18 19 20 21 22 23 24 25 28 29 30 31 33 35 37 38 39
Universitas Sumatera Utara
