Penerapan Algoritme Hungaria Berdasarkan Teorema König dan Egerváry dalam Masalah Penugasan
Abstract
Masalah penugasan dapat dimodelkan dalam suatu bentuk integer programming. Masalah penugasan timbul akibat masing-masing sumber daya memiliki tingkatan efisiensi yang berbeda dalam menjalankan tugas yang berbeda. Karena itu pengalokasian sumber daya untuk mengerjakan tugas secara efisien merupakan keputusan yang penting. Secara umum, masalah penugasan dapat dituliskan sebagai pengalokasian sejumlah sumber daya ke sejumlah tugas agar mengoptimumkan suatu fungsi objektif tertentu. Salah satu metode yang dapat digunakan dalam masalah penugasan adalah metode Hungaria. Metode Hungaria merupakan algoritme yang diperkenalkan oleh Harold W. Kuhn, algoritme ini dikembangkan berdasarkan hasil kerja Denes König dan Jeno Egerváry. Tujuan dari penulisan karya ilmiah ini adalah mengkaji secara teoretis Teorema König dan Egerváry dan menerapkan algoritme Hungaria pada suatu kasus masalah penugasan. Teorema akan dikaji dengan pembuktian beberapa teorema teori graf terkait dan dengan teorema dualitas. Dalam karya ilmiah ini diterapkan algoritme Hungaria dengan kompleksitas O(n^4). The assignment problem can be modeled as an integer programming. Assignment problems arise because each resource has different level of efficiency to perform different tasks. Therefore, allocating resources to perform tasks efficiently is an important decision. In general, assignment problem can be described as allocating a number of resources to a number of tasks in order to optimize a certain objective function. One method that can be used to solve assignment problems is the Hungarian method. Hungarian method is an algorithm introduced by Harold W. Kuhn, this algorithm was developed based on the work of Denes König and Jeno Egerváry. The purpose of writing this paper is to theoretically examine the König and Egerváry Theorem and apply the Hungarian algorithm to one case of the assignment problems. The theorem will be examined by proving several related graph theory theorems and the duality theorems. In this paper, the Hungarian algorithm with O(n^4) complexity is applied.
Collections
- UT - Mathematics [1365]