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 :
- Mulai
- Tentukan penyelesaian fisibel awal berupa matriks C (n x n)
- Dalam setiap baris, tentukan sel yang memiliki nilai terkecil.
Kurangkan seluruh sel pada baris tersebut dengan sel yang memiliki
nilai terkecil.
- Dalam setiap kolom, tentukan sel yang memiliki nilai terkecil.
Kurangkan seluruh sel pada kolom tersebut dengan sel yang memiliki nilai
terkecil.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Dari sel-sel yang tidak tertutup garis, tentukan sel yang memiliki nilai terkecil. Bobotnya adalah k.
- Kurangkan setiap sel yang tidak tertutup garis dengan k.
- Tambahkan setiap sel yang tertutup 2 garis dengan k. Kembali ke langkah 5.
- 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.
Ada anak bertanya pada Bapaknya Saya; "Mas, komputernya kok bisa dipake main God of War 2 (PS 2 Emulator)? kalo komputer ayah saya kok cuma bisa main solitaire doang ya?". Saya pun menjawab dengan penuh ketelatenan (tapi tetap fokus pada monitor pc biar g mati kratosnya..hehe), " Dhek bukannya tidak bisa, kemungkinan besar komputer kamu tuh spesifikasinya nggak mencukupi atau dengan kata lain komputer kamu perlu di upgrade lagi tapi kalo,,....dhek...,adhek"( ternyata anak itu sudah pergi dan bermain dengan ponakan saya ). OMG!! Jadi guwa tadi nyerocos sendiri dong? aaargh...!!
> 
Standar
xHTML adalah sebuah standar baru yang dicetuskan oleh W3C untuk
menggantikan standar lama yaitu HTML. Standar xHTML hampir sama dengan
HTML yang sudah ada tetapi memiliki aturan-aturan penulisan yang lebih
ketat daripada HTML, keduanya merupakan bahasa markup untuk dokumen teks
yang berfungsi untuk menentukan struktur dokumen serta mengatur fungsi
dan bagaimana dokumen tersebut ditampilkan di browser. Secara garis
besar tujuan utama standar XHTML adalah agar semua halaman web memiliki
struktur yang benar dan tata-cara penulisan tag yang konsisten sehingga
dapat dibaca dengan baik untuk semua perangkat yang mampu membaca
halaman web. Selain itu standar XHTML bertujuan menegaskan fungsinya
sebagai pembentuk struktur dokumen sedangkan untuk pengaturan tampilan
dokumen di browser (warna, jenis huruf, ukuran dll) diatur dengan
menggunakan CSS.
