Lompat ke isi

Algoritma Hungaria: Perbedaan antara revisi

Ensiklopedia Pengetahuan Universitas Islam Sultan Agung

Maintenance script (bicara | kontrib)

37.956 suntingan
Maintenance script (bicara | kontrib)
37.956 suntingan
Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187961; atribusi sumber disertakan.
 
Maintenance script (bicara | kontrib)
37.956 suntingan
Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi
 
Baris 1: Baris 1:
'''Metode [[Hungaria]]''' adalah algoritma optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial. Algoritma ini mudah dimengerti dan diterapkan untuk menyelesaikan soal yang berupa penugasan dengan cara menemukan pemasangan sempurna.
'''Metode [[Hungaria]]''' adalah algoritma optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial.<ref>Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.</ref> Algoritma ini mudah dimengerti dan diterapkan untuk menyelesaikan soal yang berupa penugasan dengan cara menemukan pemasangan sempurna.<ref>http://www.hungarianalgorithm.com/</ref>


Pada dasarnya, proses algorima ini melibatkan perubahan biaya di dalam array sampai beberapa menjadi nol. Meski begitu, hal ini tidak memengaruhi hasil optimasi dengan metode ini.
Pada dasarnya, proses algorima ini melibatkan perubahan biaya di dalam array sampai beberapa menjadi nol. Meski begitu, hal ini tidak memengaruhi hasil optimasi dengan metode ini.
Baris 5: Baris 5:
== Penjelasan yang mudah ==
== 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:
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:
 
{| class="wikitable"
|+ 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.
Tujuan atas menyelesaikan soal ini adalah untuk menugaskan pekerjaan untuk setiap individu yang terlibat dan mendapatkan hasil optimal dengan biaya yang paling minim.
Baris 14: Baris 33:
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 di atas dapat diubah dalam bentuk matriks, akan tetapi, tabel akan tetap digunakan untuk penjelasan yang lebih jelas, seperti di bawah ini:


{| class="wikitable"
|+ 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
* Unit angka dalam tabel = 1000 Rupiah
Baris 19: Baris 58:
Dalam matriks di atas, kurangi angka minimal dari setiap barisan
Dalam matriks di atas, kurangi angka minimal dari setiap barisan


{| class="wikitable"
|+
!
! (-)
! 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:
Ulangi '''langkah 1''' untuk setiap baris:


{| class="wikitable"
|+ 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.
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.
Baris 28: Baris 109:
Seperti di '''langkah 1''', kurangi angka minimal dari setiap kolom tanpa memperhatikan kolom yang telah mempunyai nilai nol.
Seperti di '''langkah 1''', kurangi angka minimal dari setiap kolom tanpa memperhatikan kolom yang telah mempunyai nilai nol.


{| class="wikitable"
|+ 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.
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.
Baris 38: Baris 140:
Cobalah untuk membagi tugas supaya biaya penalti menjadi nol. Kalau angka 0 telah diperoleh di dalam setiap baris dan kolom setelah penugasan, algoritma bisa diberhentikan karena penugasan optimal telah diperoleh. Jika tidak, lanjutkan dengan mengambil hanya angka 0 dalam tabel sebelumnya.
Cobalah untuk membagi tugas supaya biaya penalti menjadi nol. Kalau angka 0 telah diperoleh di dalam setiap baris dan kolom setelah penugasan, algoritma bisa diberhentikan karena penugasan optimal telah diperoleh. Jika tidak, lanjutkan dengan mengambil hanya angka 0 dalam tabel sebelumnya.


{| class="wikitable"
|+ Hanya angka nol
!
! 1
! 2
! 3
! 4
|-
! A
|  || 0 || ||
|-
! B
| || || 0 || 0
|-
! C
| || 0 ||  ||
|-
! D
| 0 || 0 ||  ||
|}


=== Langkah 4 ===
=== 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.
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.


{| class="wikitable"
|+
!
! 1
! style="background: red;"|2
! 3
! 4
|-
! A
| 25 || style="background: red;"|0 || 10 || 1
|-
! style="background: red;"| B
| style="background: red;"|5 || style="background: red;"|50 || style="background: red;"|0 || style="background: red;"|0
|-
! C
| 5 || style="background: red;"|0 || 10 || 15
|-
! style="background: red;"| D
| style="background: red;"|0 || style="background: red;"|0 || style="background: red;"|5 || style="background: red;"|5
|}


=== Langkah 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.
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.


{| class="wikitable"
|+
!
! 1
! style="background: red;"|2
! 3
! 4
|-
! A
| style="background: yellow;"|24 || style="background: red;"|0 || style="background: yellow;"|9 || style="background: yellow;"|0
|-
! style="background: red;"| B
| style="background: red;"|5 || style="background: blue;"|51 || style="background: red;"|0 || style="background: red;"|0
|-
! C
| style="background: yellow;"|4 || style="background: red;"|0 || style="background: yellow;"|9 || style="background: yellow;"|14
|-
! style="background: red;"| D
| style="background: red;"|0 || style="background: blue;"|1 || style="background: red;"|5 || style="background: red;"|5
|}


=== Langkah 6 ===
=== Langkah 6 ===
Tetapkan pekerjaan berdasarkan angka minimal dari setiap baris.
Tetapkan pekerjaan berdasarkan angka minimal dari setiap baris.


{| class="wikitable"
|+
!
! 1
! 2
! 3
! 4
|-
! A
| 24 || 0 || 9 || style="background: green;"|0
|-
! B
| 5 || 51 || style="background: green;"|0 || 0
|-
! C
| 4 || style="background: green;"|0 || 9 || 14
|-
! D
| style="background: green;"|0 || 1 || 5 || 5
|}


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


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


== Bacaan lanjutan ==
== Bacaan lanjutan ==
* Van Meter, Rodney. "Optimization Theory (DS2) Lecture #9 Minimum Cost Perfect Matching in Bipartite Graphs and the Hungarian Algorithm." Optimization Theory (DS2) Lecture #9Minimum Cost Perfect Matching in Bipartite Graphs and the Hungarian Algorithm. Shonan Fujisawa Campus, Keio University, 6 Dec. 2016. Web. 24 Jan. 2017.<http://web.sfc.keio.ac.jp/~rdv/keio/sfc/teaching/optimization-theory/optimization-theory-2016/Opt-Lec09-notes-bipartite.html>.
* Van Meter, Rodney. "Optimization Theory (DS2) Lecture #9 Minimum Cost Perfect Matching in Bipartite Graphs and the Hungarian Algorithm." Optimization Theory (DS2) Lecture #9Minimum Cost Perfect Matching in Bipartite Graphs and the Hungarian Algorithm. Shonan Fujisawa Campus, Keio University, 6 Dec. 2016. Web. 24 Jan. 2017.<http://web.sfc.keio.ac.jp/~rdv/keio/sfc/teaching/optimization-theory/optimization-theory-2016/Opt-Lec09-notes-bipartite.html>.
== Referensi ==
<references />


== Sumber dan atribusi ==
== Sumber dan atribusi ==


Artikel ini diadaptasi dalam mode teks dari
Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+Hungaria&oldid=29187961 Wikipedia bahasa Indonesia], revisi 29187961 (2026-05-02T15:36:02Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.
[https://id.wikipedia.org/w/index.php?title=Algoritma_Hungaria&oldid=29187961 Wikipedia bahasa Indonesia],
 
revisi 29187961 (2026-05-02T15:36:02Z).
<!-- WIKI_UNISSULA_PRESENTATION_V4 -->
Gambar, media, infobox, templat navigasi, dan kategori sumber
tidak diimpor ke Wiki Unissula.
Atribusi dan lisensi mengikuti ketentuan Creative Commons
Atribusi-BerbagiSerupa (CC BY-SA) pada sumber Wikipedia.

Revisi terkini sejak 23 Agustus 2026 03.10

Metode Hungaria adalah algoritma optimasi kombinatorial yang menyelesaikan masalah berdasarkan pembagian kerja dalam waktu polinomial.[1] Algoritma 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 memengaruhi 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, algoritma 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.

Bacaan lanjutan

Referensi

  1. ↑ Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
  2. ↑ http://www.hungarianalgorithm.com/

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29187961 (2026-05-02T15:36:02Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.


Diperoleh dari "https://wiki.unissula.ac.id/index.php?title=Algoritma_Hungaria&oldid=420"