Hanifah Putri Wijaya , 4150405518 (2009) Penyelesaian Matching Bobot Maksimun Masalah Penugasan dengan Metode Hungarian. Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF (Penyelesaian Matching Bobot Maksimun Masalah Penugasan dengan Metode Hungarian) - Published Version Download (951kB) | Preview

Abstract

Salah satu topik yang menarik dalam graf adalah masalah penugasan pekerjaan yang dapat dimodelkan dalam graf bipartit G (S, T, E) yang himpunan partisinya cocok dengan pekerja dan tempat/ kedudukan. Masalah penugasan optimal yang merupakan matching bobot maksimal dalam graf bipartit ini dapat menggunakan algoritma Hungarian. Metode yang digunakan dalam algoritma Hungarian dapat memecahkan masalah sangat sederhana dan mudah dipahami. Solusi yang diperoleh bila kita menggunakan algoritma Hungarian akan selalu optimum. Berdasarkan penjelasan di atas, penulis ini mengkaji bagaimana menyelesaikan matching bobot maksimum masalah penugasan dengan metode Hungarian. Penelitian ini merupakan penelitian studi pustaka yang dilakukan dalam dua tahap, yaitu (1) mempelajari dan mengkaji matching bobot maksimum masalah penugasan dalam graf bipartit dengan menggunakan referensi yang ada serta bagaimana membuktikan teorema yang mendukung keberadaannya (2) menggunakan metode Hungarian untuk menyelesaikan matching bobot maksimum masalah penugasan dalam graf bipartit. Untuk menyelesaikan matching bobot maksimum masalah penugasan dalam graf bipartit dapat digunakan algoritma Hungarian. Sebelum membahas algoritma Hungarian terlebih dahulu dibahas teorema: suatu matching M dalam graf G adalah matching maksimum jika dan hanya jika tidak ada path perluasan yang memuat M dalam G. Langkah‐langkah yang digunakan untuk menyelesaikan matching bobot maksimum masalah penugasan sebagai berikut. Memodelkan permasalahan tersebut dengan program linier, menyelesaikan bentuk dual dari program linier pada langkah sebelumnya, menyelesaikan model dual tersebut dengan algoritma Hungarian. Solusi yang diperoleh bila kita menggunakan algoritma hungarian akan selalu optimum. Berdasarkan hasil penelitian tersebut, penulis menyarankan kepada peneliti lain untuk mengkaji penyelesaian matching bobot maksimum masalah penugasan dalam graf bipartitel lengkap dengan algorit lain

Actions (login required)

View Item