KAEDAH HUNGARY: CONTOHNYA - DUDAS - 2026

The Cara Hungary adalah satu algoritma yang digunakan dalam masalah peruntukan apabila anda mahu untuk mengurangkan kos. Iaitu, ia digunakan untuk mencari kos minimum dengan menugaskan beberapa orang untuk pelbagai aktiviti berdasarkan kos yang paling rendah. Setiap aktiviti mesti diberikan kepada orang lain.

Masalah peruntukan adalah jenis masalah pengaturcaraan linear khas, di mana tujuannya adalah untuk meminimumkan kos atau masa menyelesaikan sejumlah pekerjaan oleh beberapa orang.

Sumber: pixabay.com

Salah satu ciri penting dari masalah peruntukan adalah hanya satu pekerjaan (atau pekerja) yang ditugaskan untuk mesin (atau projek).

Kaedah ini dikembangkan oleh ahli matematik Hungary D. Konig. Atas sebab ini, ia dikenali sebagai kaedah Hungary untuk masalah penugasan. Ia juga dikenali sebagai algoritma peruntukan Kuhn-Munkres.

Segala masalah peruntukan dapat diselesaikan dengan mudah dengan menggunakan kaedah ini yang terdiri daripada dua fasa:

- Dengan pengurangan baris fasa pertama dan pengurangan lajur dilakukan.

- Pada fasa kedua penyelesaian dioptimumkan secara berulang.

Apakah kaedah Hungary?

Kaedah Hungary terdiri daripada empat langkah. Dua langkah pertama dilaksanakan hanya sekali, sementara langkah 3 dan 4 diulang sehingga peruntukan optimum dijumpai.

Matriks segiempat dari urutan n oleh n dianggap sebagai input data, yang mesti mengandungi unsur bukan negatif sahaja.

Untuk masalah tertentu, jika bilangan baris dalam matriks tidak sama dengan bilangan lajur, baris dummy atau kolum dummy mesti ditambahkan, bergantung pada kasusnya. Kos peruntukan untuk sel-sel dummy selalu diperuntukkan sebagai sifar.

Langkah 1: tolak minimum setiap baris

Untuk setiap baris dalam array, elemen dengan nilai terendah dipilih dan dikurangkan dari setiap elemen dalam baris tersebut.

Langkah 2: tolak minimum dari setiap lajur

Begitu juga, item dengan nilai terendah dipilih untuk setiap lajur dan dikurangkan dari setiap item di lajur itu.

Langkah 3: tutup semua angka sifar dengan bilangan garis minimum

Semua angka sifar dalam matriks yang dihasilkan dari langkah 2 mesti ditutup dengan menggunakan bilangan minimum garis mendatar dan menegak, sama ada dengan baris atau lajur.

Sekiranya sejumlah garis n diperlukan untuk merangkumi semua angka nol, di mana n sama dengan ukuran n kali n dari matriks, peruntukan optimum antara nol akan diperoleh dan oleh itu algoritma berhenti.

Jika tidak, jika diperlukan garis kurang dari n untuk menutup semua nol dalam larik, teruskan ke langkah 4.

Langkah 4: buat sifar tambahan

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

Nilai k ditolak dari semua elemen yang tidak diliputi oleh garis. Selepas itu, nilai ka ditambahkan ke semua elemen yang diliputi oleh persilangan dua garis.

Item yang dilindungi oleh satu baris dibiarkan seperti sedia ada. Setelah melakukan langkah ini, anda kembali ke langkah 3.

Peruntukan yang optimum

Setelah algoritma dihentikan pada langkah 3, satu set sifar dipilih sedemikian rupa sehingga setiap baris dan setiap lajur hanya dipilih satu sifar.

Sekiranya dalam proses pemilihan ini tidak ada satu sifar dalam satu baris atau lajur, maka salah satu nol tersebut akan dipilih. Sifar yang tinggal di lajur atau baris itu dikeluarkan, mengulangi perkara yang sama untuk tugasan lain juga.

Sekiranya tidak ada penugasan sifar tunggal, terdapat banyak penyelesaian. Walau bagaimanapun, kos akan tetap sama untuk pelbagai jenis tugasan.

Segala baris atau lajur dummy yang telah ditambahkan akan dikeluarkan. Nol yang dipilih dalam matriks akhir ini sesuai dengan tugasan ideal yang diperlukan dalam matriks asal.

Contohnya

Mari kita pertimbangkan syarikat di mana terdapat empat aktiviti (A1, A2, A3, A4) yang mesti dijalankan oleh empat pekerja (T1, T2, T3, T4). Satu aktiviti mesti diberikan setiap pekerja.

Matriks berikut menunjukkan kos penugasan pekerja tertentu untuk aktiviti tertentu. Objektifnya adalah untuk meminimumkan jumlah kos tugas yang dibuat dari keempat aktiviti ini.

Langkah 1: tolak minimum setiap baris

Anda mulakan dengan mengurangkan elemen dengan nilai minimum di setiap baris dari elemen lain dalam baris itu. Sebagai contoh, elemen terkecil pada baris pertama ialah 69. Oleh itu, 69 dikurangkan dari setiap elemen pada baris pertama. Matriks yang dihasilkan adalah:

Langkah 2: tolak minimum dari setiap lajur

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

Langkah 3: tutup semua angka sifar dengan bilangan garis minimum

Sekarang kita akan menentukan bilangan garis minimum (mendatar atau menegak) yang diperlukan untuk merangkumi semua angka nol dalam matriks. Semua sifar dapat ditutup dengan menggunakan 3 baris:

Oleh kerana bilangan garis yang diperlukan adalah tiga dan lebih kecil daripada ukuran matriks (n = 4), kita teruskan dengan langkah 4.

Langkah 4: buat sifar tambahan

Elemen terkecil yang tidak diliputi oleh garis dipilih, yang nilainya adalah 6. Nilai ini dikurangkan dari semua elemen yang tidak diliputi dan nilai yang sama ini ditambahkan ke semua elemen yang diliputi oleh persilangan dua garis. Ini menghasilkan matriks berikut:

Seperti yang ditunjukkan dalam kaedah Hungarian, langkah ketiga mesti dilakukan lagi.

Langkah 3 (ulangi)

Sekali lagi bilangan garis minimum yang diperlukan untuk menutup semua sifar dalam matriks ditentukan. Kali ini diperlukan empat baris:

Oleh kerana bilangan garis yang diperlukan adalah 4, sama dengan ukuran matriks (n = 4), kita mempunyai peruntukan yang optimum antara nol di dalam matriks. Oleh itu, algoritma berhenti.

Peruntukan yang optimum

Seperti yang ditunjukkan oleh kaedah, pilihan yang dibuat dari angka nol berikut sesuai dengan tugas yang optimum:

Pilihan sifar ini sesuai dengan peruntukan optimum berikut dalam matriks kos asal:

Oleh itu, pekerja 1 mesti melakukan aktiviti 3, pekerja 2, aktiviti 2, pekerja 3, aktiviti 1, dan pekerja 4 mesti melakukan aktiviti 4. Jumlah kos tugas optimum ini ialah 69 + 37 + 11 + 23 = 140.

Rujukan

1. Algoritma Hungary (2019). Algoritma Hungary. Diambil dari: hungarianalgorithm.com.
2. Kajian (2019). Menggunakan Algoritma Hungary untuk Menyelesaikan Masalah Tugasan. Diambil dari: study.com.
3. Pekerjaan Bijak (2018). Kaedah Hungarian untuk Menyelesaikan Masalah Tugasan - Teknik Kuantitatif untuk Pengurusan. Diambil dari: atamaijobs.com.
4. Geeks untuk Geeks (2019). Algoritma Hungary untuk Masalah Tugasan. Diambil dari: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Algoritma Pemadanan Maksimum Hungarian. Cemerlang. Diambil dari: brilliant.org.