Algoritma Hungaria

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.

Penjelasan yang mudah

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:

Soal pembagian kerja

	Menggosok kamar mandi	Menanam bunga	Membersihkan lantai	Melap jendela
Andre	Rp. 80,000	Rp. 40,000	Rp. 50,000	Rp. 46,000
Budi	Rp. 40,000	Rp. 70,000	Rp. 20,000	Rp. 25,000
Corry	Rp. 30,000	Rp. 10,000	Rp. 20,000	Rp. 30,000
Durian	Rp. 35,000	Rp. 20,000	Rp. 25,000	Rp. 30,000

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:

Soal pembagian kerja

	1	2	3	4
A	80	40	50	46
B	40	70	20	25
C	30	10	20	30
D	35	20	25	30

• Unit angka dalam tabel = 1000 Rupiah

Dalam matriks di atas, kurangi angka minimal dari setiap barisan

	(-)	1	2	3	4
A	(-40)	40	0	10	6
B		40	70	20	25
C		30	10	20	30
D		35	20	25	30

Ulangi langkah 1 untuk setiap baris:

Setelah pengurangan minimal

	(-)	1	2	3	4
A	(-40)	40	0	10	6
B	(-20)	20	50	0	5
C	(-10)	20	0	10	20
D	(-20)	15	0	5	10

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.

Pengurangan minimal (lanjutan)

	(-)	1 (-15)	2	3	4 (-5)
A	(-40)	25	0	10	1
B	(-20)	5	50	0	0
C	(-10)	5	0	10	15
D	(-20)	0	0	5	5

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.

Hanya angka nol

	1	2	3	4
A		0
B			0	0
C		0
D	0	0

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.

	1	2	3	4
A	25	0	10	1
B	5	50	0	0
C	5	0	10	15
D	0	0	5	5

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.

	1	2	3	4
A	24	0	9	0
B	5	51	0	0
C	4	0	9	14
D	0	1	5	5

Langkah 6

Tetapkan pekerjaan berdasarkan angka minimal dari setiap baris.

	1	2	3	4
A	24	0	9	0
B	5	51	0	0
C	4	0	9	14
D	0	1	5	5

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.