Contoh Kasus Algoritma Hungaria

Algoritma Hungaria dibuat oleh seorang ahli matematika yang berasal dari Hungaria bernama D. Konig, algoritma ini digunakan untuk menyelesaikan masalah penugasan, yaitu kasus khusus dari model transportasi dimana sejumlah A sumber ditugaskan atau dialokasikan kepada sejumlah T tujuan dengan nilai efektifitas atau nilai biaya C.
Pada dasarnya algoritma ini memodifikasi baris dan kolom dalam matriks efektifitas sampai muncul sebuah komponen nol tunggal dalam setiap baris atau kolom sehingga komponen tersebut dapat dipilih sebagai alokasi penugasan baris dan kolom yang sesuai dengan komponen tersebut. Semua alokasi penugasan yang dibuat adalah alokasi yang optimal, dan saat diterapkan pada matriks efektifitas awal, maka akan memberikan hasil biaya alokasi penugasan yang paling minimum.

Dalam kalimat sederhana algoritma hungaria adalah algoritma untuk menyelesaikan masalah alokasi penugasan satu sumber (pekerja) tepat ke satu tujuan (pekerjaan) sehingga waktu kerja menjadi minimal. Penggambaran masalah penugasan dalam bentuk jaringan ditunjukan pada gambar berikut :

Langkah-langkah algoritma Hungaria
Algoritma Hungaria akan mencari alokasi pasangan untuk setiap node sumber (A) masing-masing tepat ke satu node tujuan (T) dengan biaya (C) seminimal mungkin. Langkah langkah algoritma Hungaria adalah sebagai berikut :

1. Mulai
2. Tentukan penyelesaian fisibel awal berupa matriks C (n x n)
3. Dalam setiap baris, tentukan sel yang memiliki nilai terkecil. Kurangkan seluruh sel pada baris tersebut dengan sel  yang memiliki nilai terkecil.
4. Dalam setiap kolom, tentukan sel yang memiliki nilai terkecil. Kurangkan seluruh sel pada kolom tersebut dengan sel yang memiliki nilai terkecil.
5. Periksa setiap baris yang hanya memiliki 1 buah nol yang belum ditandai. Jika ada, maka tandai sel ini dengan simbol (∆) dan tandai sel nol lainnya yang terletak pada kolom yang sama dengan simbol (×). Ulangi sampai setiap baris tidak punya nol yang belum ditandai atau paling sedikit 2 buah nol yang belum ditandai.
6. Periksa setiap kolom yang hanya memiliki 1 buah nol yang belum ditandai. Jika ada maka tandai sel ini dengan simbol (∆) dan tandai sel nol lainnya yang terletak pada baris yang sama dengan simbol (×). Ulangi sampai setiap kolom tidak punya nol yang belum ditandai atau paling sedikit 2 buah nol yang belum ditandai.
7. Ulangi langkah 5 dan 6 sampai salah satu kemungkinan berikut terjadi : a. Semua baris sudah mempunyai alokasi penugasan (∆), b. Ada paling sedikit 2 buah nol yang belum ditandai pada setiap baris atau kolom, c. Tidak ada nol yang belum ditandai dan alokasi penugasan yang lengkap belum tercapai.
8. Jika (a) maka alokasi penugasan lengkap sudah tercapai lanjutkan ke langkah 14, Jika (b) maka pilih salah satu sel nol yang belum ditandai dan berikan tanda (∆) sebagai alokasi penugasan, dan tandai semua sel nol lain pada baris dan kolom yang bersesuaian lalu kembali ke langkah 5. Jika (c) maka Lanjutkan ke langkah 9.
9. Lakukan langkah berikut : 1. Tandai baris (check) yang belum punya alokasi penugasan, 2. Tandai kolom (check) yang belum ditandai yang mempunyai nol di baris yang sudah ditandai, 3. Tandai baris (check) yang belum ditandai yang punya penugasan di kolom yang sudah ditandai. Lakukan langkah 2 dan 3 sampai terbentuk perulangan tertutup.
10. Gambar garis melewati semua baris yang belum diberi tanda (check) dan gambar garis melewati semua kolom yang sudah diberi tanda (check). Garis-garis ini akan menutupi semua elemen nol dalam matriks penugasan.
11. Dari sel-sel yang tidak tertutup garis, tentukan sel yang memiliki nilai terkecil. Bobotnya adalah k.
12. Kurangkan setiap sel yang tidak tertutup garis dengan k.
13. Tambahkan setiap sel yang tertutup 2 garis dengan k. Kembali ke langkah 5.
14. Selesai.

Contoh Kasus :
Seorang pelatih renang memiliki 4 orang perenang yang akan diterjunkan dalam lomba 400 meter gaya ganti perseorangan. Semua perenang dapat berenang dalam setiap gaya. Akan tetapi karena spesialisasi yang berbeda-beda, maka waktu yang dibutuhkan juga berbeda-beda. Waktu (dalam detik) yang dibutuhkan perenang dengan gaya yang ditentukan adalah sbb :

Langkah 1 dan 2 :
Tentukan matriks penyelesaian awal

Langkah 3 :
Cari nilai terkecil di tiap baris, lalu kurangkan semua elemen dengan nilai terkecil tersebut.


Langkah 4 :
Cari nilai terkecil di tiap kolom, lalu kurangkan semua elemen dengan nilai terkecil tersebut.

Langkah 5 dan 6 :
Cari baris yang mempunyai nol tunggal, tandai sebagai alokasi penugasan. dan hapus nol lain yang terletak di kolom yang sama. Jika sudah tidak ada lagi, cari kolom yang mempunyai nol tunggal, tandai sebagai alokasi penugasan. dan hapus nol lain yang terletak di baris yang sama. Pada contoh ini : sel yang ditandai sebagai sel alokasi, ditandai dengan sel berwarna biru, sedangkan sel bernilai nol yang dihapus ditandai dengan sel berwarna merah.

Pada contoh ini, urutan alokasinya adalah :
sel (3,4) lalu menghapus nol di sel (1,4),(2,4) dan (4,4)
sel (4,2) lalu menghapus nol di sel (2,2)
sel (1,1) lalu menghapus nol di sel (1,3)
Langkah 7 :
Pada tabel alokasi dari langkah 6 diatas, tidak ada lagi elemen nol lagi yang belum ditandai, tetapi alokasi penugasan belum lengkap karena hanya berjumlah 3 alokasi. Terdapat baris yang belum memiliki alokasi penugasan yaitu baris 2. Kemungkinan yang muncul adalah kemungkinan (c).

Langkah 9 :

9.1. Tandai baris (P) yang belum punya alokasi penugasan : (Baris 2)
9.2. Tandai kolom (check) yang belum ditandai yang mempunyai nol di baris yang sudah ditandai (Kolom 2 dan 4)
9.3. Tandai baris (check) yang belum ditandai yang punya penugasan di kolom yang sudah ditandai. (Kolom 3 dan 4)
Ulangi lagi langkah 9.2 dan 9.3 sampai terbentuk closed loops
9.2 Tandai kolom (check) yang belum ditandai yang mempunyai nol di baris yang sudah ditandai (Tidak ada)
9.3 Tandai baris (check) yang belum ditandai yang punya penugasan di kolom yang sudah ditandai. (Tidak Ada)
Karena sudah tidak ada baris/kolom yang dapat ditandai lagi, maka lanjutkan ke langkah 10
Langkah 10 :
Gambar garis melewati semua baris yang belum diberi tanda (check) dan gambar garis melewati semua kolom yang sudah diberi tanda (check). Garis-garis ini akan menutupi semua elemen nol dalam matriks penugasan

Elemen yang tertutup 2 garis di tandai dengan sel yang berwarna hijau tua
Elemen yang tertutup 1 garis di tandai dengan sel yang berwarna hijau muda
Elemen terkecil yang tidak tertutup garis terdapat pada sel (2,1) bernilai 1. k=1.
Langkah 11,12 dan 13 :

Selanjutnya kembali lakukan langkah 5 dan 6.

Langkah 5 dan 6 :

Pada contoh ini, urutan alokasinya adalah :
sel (3,4) lalu menghapus nol di sel (2,4) dan (4,4)
sel (4,2) lalu menghapus nol di sel (2,2)
sel (2,1) lalu menghapus nol di sel (1,1)
sel (1,3) lalu menghapus nol di sel (1,1)
Pada matriks ini sudah terbentuk matriks dengan alokasi penugasan lengkap (terdapat 4 alokasi penugasan), sehingga artinya alokasi penugasan optimal sudah tercapai, yaitu sel (3,4),(4,2),(2,1) dan (1,3). Hasil akhirnya adalah :

Total Waktu yang ditempuh : 62 + 67 + 55 + 69 = 253 detik, merupakan total waktu paling optimal. Artinya sebaiknya Perenang-1 melakukan gaya kupu-kupu, Perenang-2(Punggung), Perenang-3(Bebas), Perenang-4(Dada).
Referensi :
Gillett, Billy E. (1982). Introduction to Operations Research. New Delhi – India : TATA McGraw-Hill Publishing Company ltd.
Siang, Jong Jek. (2007) , Metode Penugasan, Kuliah Riset Operasi, Yogyakarta – Indonesia : Universitas Kristen Duta Wacana.