PARAAN NG HUNGARIAN: KUNG ANO ANG BINUBUO NITO, HALIMBAWA - DUDAS - 2025

Ang pamamaraan ng Hungarian ay isang algorithm na ginagamit sa mga problema sa paglalaan kung nais mong mabawasan ang gastos. Iyon ay, ginagamit upang mahanap ang pinakamababang gastos sa pamamagitan ng pagtatalaga ng maraming tao sa iba't ibang mga aktibidad batay sa hindi bababa sa gastos. Ang bawat aktibidad ay dapat italaga sa ibang tao.

Ang isang problema sa paglalaan ay isang espesyal na uri ng problema sa linear programming, kung saan ang layunin ay upang mabawasan ang gastos o oras sa pagkumpleto ng isang bilang ng mga trabaho sa pamamagitan ng maraming tao.

Pinagmulan: pixabay.com

Isa sa mga mahahalagang katangian ng problema sa paglalaan ay ang isang trabaho (o manggagawa) lamang ang itinalaga sa isang makina (o proyekto).

Ang pamamaraang ito ay binuo ng Hungarian matematika D. Konig. Para sa kadahilanang ito, kilala ito bilang pamamaraan ng Hungarian para sa mga problema sa pagtatalaga. Kilala rin ito bilang algorithm ng alokasyon ng Kuhn-Munkres.

Ang anumang problema sa paglalaan ay madaling malulutas sa pamamaraang ito na binubuo ng dalawang phase:

- Sa pamamagitan ng unang yugto ng pagbawas ng hilera at pagbawas ng haligi ay isinasagawa.

- Sa ikalawang yugto ang solusyon ay na-optimize sa isang matibay na batayan.

Ano ang paraan ng Hungarian?

Ang pamamaraan ng Hungarian ay binubuo ng apat na mga hakbang. Ang unang dalawang hakbang ay isinasagawa nang isang beses lamang, habang ang mga hakbang 3 at 4 ay paulit-ulit hanggang sa natagpuan ang isang pinakamainam na alokasyon.

Ang isang parisukat na matrix ng order n by n ay isinasaalang-alang bilang data ng pag-input, na dapat maglaman lamang ng mga hindi negatibong elemento.

Para sa isang naibigay na problema, kung ang bilang ng mga hilera sa matrix ay hindi katumbas ng bilang ng mga haligi, dapat na maidagdag ang isang dummy row o isang haligi ng dummy, depende sa kaso. Ang mga gastos sa paglalaan para sa mga dummy cells ay palaging inilalaan bilang zero.

Hakbang 1: ibawas ang minima ng bawat hilera

Para sa bawat hilera sa hanay, ang elemento na may pinakamababang halaga ay pinili at ibawas mula sa bawat elemento sa hilera na iyon.

Hakbang 2: ibawas ang mga minimum mula sa bawat haligi

Katulad nito, ang item na may pinakamababang halaga ay pinili para sa bawat haligi at ibabawas mula sa bawat item sa haligi na iyon.

Hakbang 3: takpan ang lahat ng mga zero na may isang minimum na bilang ng mga linya

Ang lahat ng mga zero sa matrix na nagreresulta mula sa hakbang 2 ay dapat na sakop gamit ang isang minimum na bilang ng mga pahalang at patayong linya, alinman sa pamamagitan ng mga hilera o mga haligi.

Kung ang isang kabuuan ng n mga linya ay kinakailangan upang masakop ang lahat ng mga zero, kung saan n ay katumbas ng laki n beses n ng matrix, isang optimal na paglalaan sa pagitan ng mga zero ay makuha at samakatuwid ay tumitigil ang algorithm.

Kung hindi man, kung mas mababa sa n mga linya ay kinakailangan upang masakop ang lahat ng mga zero sa array, magpatuloy sa hakbang 4.

Hakbang 4: lumikha ng mga sobrang zero

Ang pinakamaliit na elemento ng matrix (tinatawag na k) na hindi sakop ng isa sa mga linya na ginawa sa hakbang 3 ay napili.

Ang halaga ng k ay ibinabawas mula sa lahat ng mga elemento na hindi sakop ng mga linya. Kasunod nito, ang halaga ng ka ay idinagdag sa lahat ng mga elemento na sakop ng interseksyon ng dalawang linya.

Ang mga item na sakop ng isang solong linya ay naiwan. Matapos maisagawa ang hakbang na ito, bumalik ka sa hakbang 3.

Optimum na paglalaan

Matapos ang algorithm ay tumigil sa hakbang 3, isang hanay ng mga zero ang napili tulad ng bawat hilera at ang bawat haligi ay may isang napiling zero.

Kung sa proseso ng pagpili na ito ay walang solong zero sa isang hilera o haligi, kung gayon ang isa sa mga zero ay pipiliin. Ang natitirang mga zero sa haligi o hilera na iyon ay tinanggal, na ulitin ang parehong para sa iba pang mga atas.

Kung walang isang solong pagtatalaga sa zero, maraming mga solusyon. Gayunpaman, ang gastos ay mananatiling pareho para sa iba't ibang mga hanay ng mga takdang-aralin.

Ang anumang dummy row o haligi na idinagdag ay tinanggal. Ang mga zero na napili sa panghuling matris na ito ay tumutugma sa perpektong takdang kinakailangan sa orihinal na matris.

Halimbawa

Isaalang-alang natin ang isang kumpanya kung saan mayroong apat na aktibidad (A1, A2, A3, A4) na dapat gawin ng apat na manggagawa (T1, T2, T3, T4). Ang isang aktibidad ay dapat italaga sa bawat manggagawa.

Ang sumusunod na matris ay nagpapakita ng halaga ng pagtatalaga ng isang tiyak na manggagawa sa isang tiyak na aktibidad. Ang layunin ay upang mabawasan ang kabuuang gastos ng gawain na binubuo ng apat na aktibidad na ito.

Hakbang 1: ibawas ang minima ng bawat hilera

Magsisimula ka sa pamamagitan ng pagbabawas ng elemento na may minimum na halaga sa bawat hilera mula sa iba pang mga elemento sa hilera. Halimbawa, ang pinakamaliit na elemento sa unang hilera ay 69. Samakatuwid, ang 69 ay binawi mula sa bawat elemento sa unang hilera. Ang nagresultang matris ay:

Hakbang 2: ibawas ang mga minimum mula sa bawat haligi

Sa parehong paraan, ang elemento na may pinakamababang halaga ng bawat haligi ay binawi mula sa iba pang mga elemento ng haligi na iyon, na nakukuha ang sumusunod na matris:

Hakbang 3: takpan ang lahat ng mga zero na may isang minimum na bilang ng mga linya

Ngayon ay matutukoy namin ang pinakamababang bilang ng mga linya (pahalang o patayo) na kinakailangan upang masakop ang lahat ng mga zero sa matrix. Ang lahat ng mga zero ay maaaring masakop gamit ang 3 linya:

Dahil ang bilang ng mga linya na kinakailangan ay tatlo at mas mababa ito sa laki ng matrix (n = 4), nagpapatuloy kami sa hakbang 4.

Hakbang 4: lumikha ng mga sobrang zero

Ang pinakamaliit na elemento na hindi saklaw ng mga linya ay napili, na ang halaga ay 6. Ang halagang ito ay ibinabawas mula sa lahat ng mga elemento na hindi sakop at ang parehong halaga na ito ay idinagdag sa lahat ng mga elemento na sakop ng interseksyon ng dalawang linya. Nagreresulta ito sa sumusunod na matris:

Tulad ng ipinahiwatig sa pamamaraan ng Hungarian, ang hakbang na tatlo ay dapat gampanan muli.

Hakbang 3 (ulitin)

Muli ang pinakamababang bilang ng mga linya na kinakailangan upang masakop ang lahat ng mga zero sa matrix ay natutukoy. Sa oras na ito apat na linya ay kinakailangan:

Dahil ang bilang ng mga linya na kinakailangan ay 4, katumbas ng laki ng matrix (n = 4), mayroon kaming isang pinakamainam na paglalaan sa pagitan ng mga zero sa matrix. Samakatuwid, huminto ang algorithm.

Optimum na paglalaan

Tulad ng ipinapahiwatig ng pamamaraan, ang pagpili na ginawa ng mga sumusunod na zero ay tumutugma sa isang pinakamainam na takdang-aralin:

Ang pagpili ng mga zero ay tumutugma sa sumusunod na pinakamainam na paglalaan sa orihinal na gastos matrix:

Samakatuwid, ang manggagawa 1 ay dapat magsagawa ng aktibidad 3, manggagawa 2, aktibidad 2, manggagawa 3, aktibidad 1, at manggagawa 4 ay dapat magsagawa ng aktibidad 4. Ang kabuuang gastos ng pinakamainam na takdang ito ay 69 + 37 + 11 + 23 = 140.

Mga Sanggunian

1. Algorithm ng Hungarian (2019). Ang algorithm ng Hungarian. Kinuha mula sa: hungarianalgorithm.com.
2. Pag-aaral (2019). Gamit ang Hungarian Algorithm upang Malutas ang mga problema sa Takdang-aralin. Kinuha mula sa: study.com.
3. Mga Trabaho ng Karunungan (2018). Paraan ng Hungarian para sa Paglutas ng Suliranin sa Takdang Aralin - Mga Teknikong Dami para sa Pamamahala. Kinuha mula sa: wisdomjobs.com.
4. Mga Geeks para sa Geeks (2019). Algorithm ng Hungarian para sa Suliranin sa Assignment. Kinuha mula sa: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Hungarian Maximum Matching Algorithm. Napakatalino. Kinuha mula sa: brilliant.org.