Metode Hungaria untuk Masalah Penugasan

Halo Sixtyfourians!

Melanjutkan pembahasan kita tentang teori dasar Masalah Penugasan (Assignment Problem), kali ini kita akan masuk ke "menu utama": Teknik Perhitungan Metode Hungaria.

Jika kalian memiliki matriks biaya dan bingung bagaimana mencari kombinasi termurah tanpa harus menghitung satu per satu secara manual, metode inilah jawabannya. Mari kita bedah langkah-langkahnya!

Misal diberikan permasalahan:

Seorang pelatih renang ingin membentuk tim renang yang tangguh untuk terjun di 400m estafet gaya ganti pada suatu pertandingan tingkat nasional. Ada empat perenang dibawah asuhannya merupakan perenang terbaiknya. Perenang tersebut menguasai dengan baik keempat gaya yang dipertandingkan. Pelatih ingin melakukan penugasan satu perenang pada satu gaya berdasarkan data waktu terbaik mereka untuk tiap gaya nomor 100 meter. Waktu (dalam detik) masing-masing perenang pada masing-masing gaya disajikan pada table berikut ini.

	Budi	Giri	Koko	Fajar
Kupu-Kupu	52,4	48,3	55,6	49,5
Dada	55,4	58,2	59,1	57,3
Punggung	62,7	62,5	60,9	63,2
Bebas	47,7	49,1	53,5	52,1

Bagaimana cara pelatih itu menugaskan perenangnya agar diperoleh waktu tercepat!.

1. Penyusutan Baris dan Kolom (Reduksi Matriks)

Langkah pertama adalah membuat setiap baris dan kolom memiliki setidaknya satu angka nol (unsur nol). Ini didasarkan pada Dalil Penyusutan.

Caranya:

Susutkan Baris: Cari angka terkecil di setiap baris, lalu kurangi semua angka di baris tersebut dengan angka terkecil itu.

Tabel yang diberikan diatas setelah disusutkan setiap barisnya menjadi:

	P1	P2	P3	P4
G1	4,1	0	7,3	1,2
G2	0	2,8	3,7	1,9
G3	1,8	1,6	0	2,3
G4	0	1,4	5,8	4,4

Susutkan Kolom: Periksa apakah setiap kolom sudah punya angka 0?

Ternyata kolom P4 belum ada angka 0, karena yang terkecil adalah 1,2; susutkan masing-masing sel di kolom P4 dengan 1,2; tabelnya menjadi:

	P1	P2	P3	P4
G1	4,1	0	7,3	0
G2	0	2,8	3,7	0,7
G3	1,8	1,6	0	1,1
G4	0	1,4	5,8	3,2

2. Uji Keoptimuman (Garis Penutup Nol)

Apakah tabel di atas sudah optimal? Kita harus mengujinya dengan menarik garis penutup nol.

Aturannya:"Buat garis tegak atau mendatar untuk menutup semua angka nol dengan jumlah garis yang seminimal mungkin."

Analisis:

Jika jumlah garis < jumlah baris/kolom (n), maka tabel belum optimal.

Jika jumlah garis = jumlah baris/kolom (n), maka tabel sudah optimal.

Pada kasus ini (n = 4), kita bisa menutup semua angka nol hanya dengan 3 garis. Karena 3 garis < 4 dimensi matriks, maka tabel belum optimal. Kita harus lanjut ke Langkah 3.

3. Revisi Tabel

Karena belum optimal, kita perlu memodifikasi tabel dengan aturan berikut:

• Cari Unsur Terkecil: Lihat angka-angka yang tidak tertutup garis. Cari yang paling kecil. (Di kasus ini, angka terkecil yang terbuka adalah 0,7; yaitu pada posisi K24).

• Kurangi: Kurangi semua angka yang tidak tertutup garis dengan angka terkecil tersebut (dikurangi 0,7).

• Tambah: Tambahkan angka yang terletak di persimpangan garis (terkena dua garis) dengan angka terkecil tersebut (ditambah 1).

• Tetap: Angka yang hanya terkena satu garis tidak berubah.

Hasil Revisi: Tabel baru terbentuk. Sekarang kita lakukan Uji Garis Ulang.

Sekarang, untuk menutup semua nol, kita membutuhkan minimal 4 garis. Karena jumlah garis (4) sama dengan jumlah baris/kolom (4), maka tabel ini sudah memuat pola optimum.

4. Alokasi Penugasan (Eksekusi)

Langkah terakhir adalah menentukan siapa mengerjakan apa. Gunakan strategi "Scanning" untuk memilih kotak nol.

• Pilih Nol Tunggal: Cari baris/kolom yang hanya punya satu angka nol.

Kolom P2 dan P3 memiliki nol tunggal. Baris G3 dan G4 memiliki nol tunggal. Akan tetapi satu-satunya nol yang tunggal di baris dan kolomnya adalah sel K33. Pilih sel K33, sehingga baris G3 dan kolom P3 jenuh.

• Ulangi:

Dari baris dan kolom yang tersisa, baris G4 memiliki nol tunggal di K41 dan kolom P2 memiliki nol tunggal di K12, kita dapat memilih antara K41 atau K12, misal dipilih K41, sehingga baris G4 dan kolom P1 jenuh.

Dari baris dan kolom yang tersisa, kolom P2 memiliki nol tunggal di K12, pilih K12, sehingga baris G1 dan kolom P2 jenuh.

Terakhir secara otomatis P4 tertugaskan untuk G2.

Jadi, penyelesaian optimal dari permasalahan tersebut tercapai jika pelatih tersebut membuat schedule penugasan sebagai berikut: 

Budi berenang gaya bebas dengan waktu 47,7 detik

Giri berenang gaya kupu-kupu dengan waktu 48,3 detik

Koko berenang gaya punggung dengan waktu 60,9 detik

Fajar berenang gaya dada dengan waktu 57,3 detik

Jadi, total waktu minimum adalah 47,7 + 48,3 + 60,9 + 57,3 = 214,2 detik.