METODE HONGARIA: TERDIRI DARI APA, CONTOH - DUDAS - 2025

The metode Hungarian adalah sebuah algoritma yang digunakan dalam masalah alokasi bila Anda ingin meminimalkan biaya. Artinya, digunakan untuk mencari biaya minimum dengan menugaskan banyak orang untuk berbagai aktivitas berdasarkan biaya yang paling rendah. Setiap aktivitas harus ditetapkan ke orang yang berbeda.

Masalah alokasi adalah jenis khusus dari masalah pemrograman linier, yang tujuannya adalah meminimalkan biaya atau waktu penyelesaian sejumlah pekerjaan oleh banyak orang.

Sumber: pixabay.com

Salah satu karakteristik penting dari masalah alokasi adalah bahwa hanya satu pekerjaan (atau pekerja) yang ditugaskan ke sebuah mesin (atau proyek).

Metode ini dikembangkan oleh matematikawan Hungaria D. Konig. Untuk alasan ini, metode ini dikenal sebagai metode Hongaria untuk masalah penugasan. Ini juga dikenal sebagai algoritma alokasi Kuhn-Munkres.

Setiap masalah alokasi dapat dengan mudah diselesaikan dengan menerapkan metode ini yang terdiri dari dua tahap:

- Dengan pengurangan baris fase pertama dan pengurangan kolom dilakukan.

- Pada tahap kedua, solusi dioptimalkan secara iteratif.

Apa metode Hongaria?

Metode Hongaria terdiri dari empat langkah. Dua langkah pertama hanya dijalankan sekali, sedangkan langkah 3 dan 4 diulangi hingga alokasi optimal ditemukan.

Matriks persegi berorde n kali n dianggap sebagai data masukan, yang harus berisi hanya elemen non-negatif.

Untuk masalah tertentu, jika jumlah baris dalam matriks tidak sama dengan jumlah kolom, baris dummy atau kolom dummy harus ditambahkan, tergantung pada kasusnya. Biaya alokasi untuk sel dummy tersebut selalu dialokasikan sebagai nol.

Langkah 1: kurangi minimum setiap baris

Untuk setiap baris dalam larik, elemen dengan nilai terendah dipilih dan dikurangi dari setiap elemen di baris itu.

Langkah 2: kurangi nilai minimum dari setiap kolom

Demikian pula, item dengan nilai terendah dipilih untuk setiap kolom dan dikurangi dari setiap item di kolom itu.

Langkah 3: tutupi semua nol dengan jumlah baris minimum

Semua angka nol dalam matriks yang dihasilkan dari langkah 2 harus ditutup dengan menggunakan jumlah minimum garis horizontal dan vertikal, baik per baris atau kolom.

Jika total n baris diperlukan untuk mencakup semua nol, di mana n sama dengan ukuran n kali n matriks, alokasi optimal antara nol akan diperoleh dan oleh karena itu algoritme berhenti.

Jika tidak, jika diperlukan kurang dari n baris untuk mencakup semua angka nol dalam larik, lanjutkan ke langkah 4.

Langkah 4: buat nol ekstra

Elemen terkecil dari matriks (disebut k) yang tidak tercakup oleh salah satu garis yang dibuat pada langkah 3 dipilih.

Nilai k dikurangi dari semua elemen yang tidak tercakup oleh garis. Selanjutnya, nilai ka ditambahkan ke semua elemen yang tercakup oleh perpotongan dua garis.

Item yang dicakup oleh satu baris dibiarkan apa adanya. Setelah melakukan langkah ini, Anda kembali ke langkah 3.

Alokasi optimal

Setelah algoritma dihentikan pada langkah 3, satu set angka nol dipilih sehingga setiap baris dan setiap kolom hanya memiliki satu nol yang dipilih.

Jika dalam proses pemilihan ini tidak ada satu nol pun dalam satu baris atau kolom, maka salah satu dari nol tersebut akan dipilih. Angka nol yang tersisa di kolom atau baris itu dihapus, mengulangi hal yang sama untuk tugas lainnya juga.

Jika tidak ada satu penugasan nol, ada beberapa solusi. Namun, biayanya akan tetap sama untuk set penugasan yang berbeda.

Setiap baris atau kolom tiruan yang telah ditambahkan akan dihapus. Angka nol yang dipilih dalam matriks akhir ini dengan demikian sesuai dengan penetapan ideal yang diperlukan dalam matriks asli.

Contoh

Mari kita pertimbangkan sebuah perusahaan dimana ada empat kegiatan (A1, A2, A3, A4) yang harus dilakukan oleh empat pekerja (T1, T2, T3, T4). Satu aktivitas harus ditetapkan per pekerja.

Matriks berikut menunjukkan biaya penugasan pekerja tertentu ke aktivitas tertentu. Tujuannya adalah untuk meminimalkan total biaya tugas yang terdiri dari empat aktivitas ini.

Langkah 1: kurangi minimum setiap baris

Anda mulai dengan mengurangi elemen dengan nilai minimum di setiap baris dari elemen lain di baris itu. Misalnya, elemen terkecil di baris pertama adalah 69. Oleh karena itu, 69 dikurangi dari setiap elemen di baris pertama. Matriks yang dihasilkan adalah:

Langkah 2: kurangi nilai minimum dari setiap kolom

Dengan cara yang sama, elemen dengan nilai minimum setiap kolom dikurangkan dari elemen lain di kolom tersebut, memperoleh matriks berikut:

Langkah 3: tutupi semua nol dengan jumlah baris minimum

Sekarang kita akan menentukan jumlah garis minimum (horizontal atau vertikal) yang diperlukan untuk menutupi semua angka nol dalam matriks. Semua angka nol dapat ditutup dengan menggunakan 3 baris:

Karena jumlah garis yang dibutuhkan adalah tiga dan lebih kecil dari ukuran matriks (n = 4), kita lanjutkan ke langkah 4.

Langkah 4: buat nol ekstra

Elemen terkecil yang tidak tercakup oleh garis dipilih, yang nilainya 6. Nilai ini dikurangi dari semua elemen yang tidak tercakup dan nilai yang sama ini ditambahkan ke semua elemen yang tercakup oleh perpotongan dua garis. Ini menghasilkan matriks berikut:

Seperti yang ditunjukkan dalam metode Hongaria, langkah ketiga harus dilakukan lagi.

Langkah 3 (ulangi)

Sekali lagi, jumlah garis minimum yang diperlukan untuk mencakup semua angka nol dalam matriks ditentukan. Kali ini dibutuhkan empat baris:

Karena jumlah garis yang dibutuhkan adalah 4, sama dengan ukuran matriks (n = 4), kita memiliki alokasi optimal antara angka nol dalam matriks. Oleh karena itu, algoritme berhenti.

Alokasi optimal

Seperti yang ditunjukkan metode, pemilihan yang dibuat dari angka nol berikut ini sesuai dengan penetapan optimal:

Pilihan angka nol ini sesuai dengan alokasi optimal berikut ini dalam matriks biaya asli:

Oleh karena itu, pekerja 1 harus melakukan aktivitas 3, pekerja 2, aktivitas 2, pekerja 3, aktivitas 1, dan pekerja 4 harus melakukan aktivitas 4. Total biaya penugasan optimal ini adalah 69 + 37 + 11 + 23 = 140.

Referensi

1. Algoritma Hongaria (2019). Algoritme Hungaria. Diambil dari: hungarianalgorithm.com.
2. Study (2019). Menggunakan Algoritma Hungaria untuk Memecahkan Masalah Penugasan. Diambil dari: study.com.
3. Wisdom Jobs (2018). Metode Hongaria untuk Memecahkan Masalah Penugasan - Teknik Kuantitatif untuk Manajemen. Diambil dari: wisdomjobs.com.
4. Geeks for Geeks (2019). Algoritma Hungaria untuk Masalah Penugasan. Diambil dari: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Algoritma Pencocokan Maksimum Hongaria. Cemerlang. Diambil dari: brilian.org.