Top Qs
Timeline
Obrolan
Perspektif

Algoritma Hungaria

Dari Wikipedia, ensiklopedia bebas

Remove ads

Metode Hungaria adalah algoritme optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial.[1] Algoritme ini mudah dimengerti dan diterapkan untuk menyelesaikan soal yang berupa penugasan dengan cara menemukan pemasangan sempurna.[2]

Pada dasarnya, proses algorima ini melibatkan perubahan biaya di dalam array sampai beberapa menjadi nol. Meski begitu, hal ini tidak mempengaruhi hasil optimasi dengan metode ini.

Remove ads

Penjelasan yang mudah

Ringkasan
Perspektif

Dalam contoh ini, ada empat pekerja: Andre, Budi, Corry, dan Durian. Setiap pekerja bisa melakukan empat tugas yang berbeda: menggosok kamar mandi, menanam bunga, membersihkan lantai, dan melap jendela. Tetapi, setiap pekerja meminta bayaran yang berbeda-beda untuk tugas yang sama. Diilustrasikan dalam tabel di bawah ini:

Informasi lebih lanjut Menggosok kamar mandi, Menanam bunga ...

Tujuan atas menyelesaikan soal ini adalah untuk menugaskan pekerjaan untuk setiap individu yang terlibat dan mendapatkan hasil optimal dengan biaya yang paling minim.

Untuk memodifikasi beberapa angka (yang dalam hal ini adalah biaya) menjadi nol, kurangi angka minimal dari setiap kolom dan barisan sampai salah satunya menjadi nol.

Langkah 1

Soal pembagian kerja di atas dapat diubah dalam bentuk matriks, akan tetapi, tabel akan tetap digunakan untuk penjelasan yang lebih jelas, seperti di bawah ini:

Informasi lebih lanjut A, B ...
  • Unit angka dalam tabel = 1000 Rupiah

Dalam matriks di atas, kurangi angka minimal dari setiap barisan

Informasi lebih lanjut (-), A ...

Ulangi langkah 1 untuk setiap baris:

Informasi lebih lanjut (-), A ...

Jumlah total angka minus adalah -90, yang menyatakan bahwa biaya lebih dari Rp. 90,000 ekstra (atau penalti) yang akan dibayar. Jika angka 0 telah diperoleh untuk setiap baris dan kolom, Rp. 90,000 telah menjadi biaya minimum yang tetap. Namun, dalam hal ini belum diperoleh. Maka, langkah-langkah selanjutnya diperlukan.

Langkah 2

Seperti di langkah 1, kurangi angka minimal dari setiap kolom tanpa memperhatikan kolom yang telah mempunyai nilai nol.

Informasi lebih lanjut (-), 1 (-15) ...

Untuk memperoleh biaya minimal, tambahkan Rp. 15,000 dan Rp. 5,000 yang telah dikurangi dalam kolom 1 dan 4 ke dalam biaya total Rp. 90,000, sehingga biaya total sekarang menjadi Rp. 110,000.

Walaupun sekarang bilangan 0 bisa terlihat di setiap baris dan kolom, pembagian tugas belum bisa dilakukan dengan memilih tugas dengan memilih setiap angka nol untuk setiap orang.

Melihat angka dalam anti-diagonal bernilai 0 kecuali nilai 1 di kolom keempat, pembagian tugas dapat dilakukan dengan syarat biaya total menjadi 111, atau tepatnya Rp. 111,000. Untuk mencari total biaya minimum yang kurang dari itu, penugasan yang sempurna bisa didapat dengan menyusun kembali untuk mendapatkan pemasangan sempurna (perfect matching).

Langkah 3

Cobalah untuk membagi tugas supaya biaya penalti menjadi nol. Kalau angka 0 telah diperoleh di dalam setiap baris dan kolom setelah penugasan, algoritme bisa diberhentikan karena penugasan optimal telah diperoleh. Jika tidak, lanjutkan dengan mengambil hanya angka 0 dalam tabel sebelumnya.

Informasi lebih lanjut A, B ...

Langkah 4

Dengan menggunakan metode di atas, temukan angka minimal dalam setiap garis horizonal dan vertikal yang memiliki nilai nol paling banyak. Dalam soal ini, coret barisan B dan D secara horizontal dan kolom 2 secara vertikal. Setiap barisan atau kolom itu dicoret saat mereka telah dinilai minimal.

Informasi lebih lanjut A, B ...

Langkah 5

Modifikasi semua entri di dalam matrix dengan cara mengurangi angka minimum yang didapat dari entri yang tidak termodifikasi. Dalam soal ini, kurangi nilai 1 untuk memperoleh nilai nol dalam anti-diagonal dan tambahkan nilai 1 untuk entri yang tidak tersentuh.

Informasi lebih lanjut A, B ...

Langkah 6

Tetapkan pekerjaan berdasarkan angka minimal dari setiap baris.

Informasi lebih lanjut A, B ...

Dalam soal ini, total biaya minimal adalah Rp. 111,000 dengan penugasan:

Andre = melap jendela
Budi = membersihkan lantai
Corry = menanam bunga
Durian = menggosok kamar mandi

Dengan penugasan seperti di atas, biaya minimal dengan melibatkan seluruh individual dengan satu pekerjaan dapat diperoleh.

Remove ads

Referensi

Bacaan lanjutan

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads