Skripsi

Penerapan algoritma branch and bound dalam memecahkan assignment problem / Rifka Amelia Ismawati

Abstrak
Kata kunci graph masalah penugasan algoritma branch and bound Salah satu cabang matematika yang banyak berhubungan dengan masalah kehidupan sehari-hari adalah graph. Teori graph merupakan cabang matematika yang aplikasinya banyak dijumpai misalnya pada masalah penugasan. Contoh dari masalah penugasan adalah penugasan karyawan pada suatu perusahaan. Seorang pekerja akan ditugaskan ke tepat satu pekerjaan dan satu pekerjaan hanya boleh dilakukan oleh seorang pekerja saja. Permasalahannya adalah bagaimana meminimumkan total jumlah gaji yang harus dikeluarkan oleh perusahaan. Pada skripsi ini dipelajari tentang bagaimana cara menyelesaikan masalah penugasan dengan menggunakan algoritma branch and bound. Algoritma branch and bound merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status atau proses pencarian pada algoritma ini menggunakan skema algoritma Breadth-First Search (BFS). Pada skema BFS simpul yang dibangkitkan terlebih dahulu adalah simpul yang bertetanggaan dengan simpul akar. Sedangkan pada algoritma branch and bound prinsip pencarian solusinya tidak seperti pada algoritma BFS murni akan tetapi berdasarkan nilai ongkos simpul yang memiliki nilai paling ekstrem (maksimum atau minimum). Selanjutnya untuk mempermudah proses perhitungan maka dalam skripsi ini algoritma branch and bound diimplementasikan ke dalam program komputer dengan bahasa Delphi. Selain dengan menggunakan bahasa Delphi penyelesaian masalah penugasan juga menggunakan program WINQSB dan POM for WINDOWS sebagai pembanding. Dari hasil penyelesaian masalah penugasan dengan menggunakan program Borland Delphi 7.0 yang menvisualisasikan algoritma branch and bound diperoleh hasil penugasan yang sama seperti pada program bantu WINQSB dan POM for WINDOWS.

Informasi Detail

DDC

Rs 518.1 ISM p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2010.

Deskripsi Fisik

x, 90 lembar : il., tab. ; 30 cm.

Bahasa

Indonesia

No Reg

03854/KI/10

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang, 2010

Subjek

1. ALGORITMA BRANCH - PENERAPAN

Pembimbing

1. SUBANJI ; 2. DARMAWAN SATYANANDA

Lampiran Berkas