UNGĀRU METODE: NO KĀ TĀ SASTĀV, PIEMĒRS - DUDAS - 2025

Ungārijas metode ir algoritms, kas izmanto sadales problēmas, ja jūs vēlaties, lai samazinātu izmaksas. Tas ir, to izmanto, lai atrastu minimālās izmaksas, norīkojot vairākus cilvēkus dažādām darbībām, pamatojoties uz viszemākajām izmaksām. Katra darbība jāpiešķir citai personai.

Piešķiršanas problēma ir īpaša veida lineārā programmēšanas problēma, kuras mērķis ir samazināt izmaksas vai laiku vairāku darbu pabeigšanai, ko veic vairāki cilvēki.

Avots: pixabay.com

Viens no svarīgiem piešķiršanas problēmas raksturojumiem ir tas, ka mašīnai (vai projektam) tiek piešķirts tikai viens darbs (vai darbinieks).

Šo metodi izstrādāja ungāru matemātiķis D. Konigs. Šī iemesla dēļ to sauc par ungāru metodi uzdevumu piešķiršanai. Tas ir arī pazīstams kā Kuhn-Munkres piešķiršanas algoritms.

Jebkuru sadales problēmu var viegli atrisināt, izmantojot šo metodi, kas sastāv no diviem posmiem:

- Ar pirmo fāzi tiek samazināti rindas un kolonnas.

- Otrajā fāzē risinājums tiek optimizēts iteratīvi.

Kāda ir ungāru metode?

Ungārijas metode sastāv no četriem posmiem. Pirmie divi soļi tiek izpildīti tikai vienu reizi, savukārt 3. un 4. darbība tiek atkārtota, līdz tiek atrasts optimālais piešķīrums.

Kvadrātveida matricu ar secību n ar n uzskata par ievades datiem, kuriem jāsatur tikai nenegatīvi elementi.

Konkrētās problēmas gadījumā, ja matricā esošo rindu skaits nav vienāds ar kolonnu skaitu, atkarībā no gadījuma jāpievieno fiktīvā rinda vai fiktīvā kolonna. Piešķiršanas izmaksas šīm fiktīvajām kamerām vienmēr tiek sadalītas kā nulle.

1. solis: atņemiet katras rindas minimumu

Katrā masīva rindā tiek izvēlēts elements ar zemāko vērtību un atņemts no katra elementa šajā rindā.

2. solis: atņemiet minimumus no katras kolonnas

Līdzīgi katrai kolonnai tiek atlasīts vienums ar viszemāko vērtību un atņemts no katras šīs kolonnas vienības.

3. solis: pārklājiet visas nulles ar minimālo līniju skaitu

Visas nulles matricā, kas izriet no 2. posma, jāaptver, izmantojot minimālo horizontālo un vertikālo līniju skaitu, vai nu ar rindām, vai kolonnām.

Ja, lai aptvertu visas nulles, ir vajadzīgas n līnijas, kur n ir vienāds ar matricas n lielumu n un n, tad nullēm tiek noteikts optimālais sadalījums, un tāpēc algoritms apstājas.

Pretējā gadījumā, ja ir vajadzīgas mazāk nekā n līnijas, lai aptvertu visas nulles masīvā, pārejiet pie 4. darbības.

4. solis: izveidojiet papildu nulles

Tiek izvēlēts mazākais matricas elements (saukts k), kuru neaptver viena no 3. solī izveidotajām līnijām.

K vērtību atņem no visiem elementiem, uz kuriem līnijas neattiecas. Pēc tam ka vērtība tiek pievienota visiem elementiem, uz kuriem attiecas divu līniju krustošanās.

Vienumi, kurus sedz viena rinda, tiek atstāti tādi, kādi ir. Pēc šīs darbības veikšanas jūs atgriezīsities 3. darbībā.

Optimāls sadalījums

Pēc algoritma apturēšanas 3. darbībā tiek izvēlēta nulles kopa, lai katrā rindā un katrā kolonnā būtu atlasīta tikai viena nulle.

Ja šajā atlases procesā rindā vai kolonnā nav vienas nulles, tiks izvēlēta viena no šīm nullēm. Atlikušās nulles tajā kolonnā vai rindā tiek noņemtas, atkārtojot to pašu arī citiem uzdevumiem.

Ja nav vienas nulles piešķiršanas, ir vairāki risinājumi. Tomēr dažādu uzdevumu komplektu izmaksas nemainīsies.

Visas pievienotās fiktīvās rindas vai kolonnas tiek noņemtas. Tādējādi šajā galīgajā matricā izvēlētās nulles atbilst ideālajam piešķīrumam, kas nepieciešams sākotnējā matricā.

Piemērs

Apsvērsim uzņēmumu, kurā ir četras darbības (A1, A2, A3, A4), kuras jāveic četriem darbiniekiem (T1, T2, T3, T4). Vienam darbiniekam jāpiešķir viena darbība.

Šī matrica parāda izmaksas, kas saistītas ar noteikta darbinieka noteiktām darbībām. Mērķis ir līdz minimumam samazināt uzdevuma kopējās izmaksas, kas sastāv no šīm četrām darbībām.

1. solis: atņemiet katras rindas minimumu

Sākumā atņemiet elementu ar minimālo vērtību katrā rindā no citiem šīs rindas elementiem. Piemēram, mazākais pirmās rindas elements ir 69. Tāpēc no katra pirmās rindas elementa tiek atņemts 69. Iegūtā matrica ir:

2. solis: atņemiet minimumus no katras kolonnas

Tādā pašā veidā no pārējiem šīs kolonnas elementiem tiek atņemts elements ar katras kolonnas minimālo vērtību, iegūstot šādu matricu:

3. solis: pārklājiet visas nulles ar minimālo līniju skaitu

Tagad mēs noteiksim minimālo līniju skaitu (horizontālu vai vertikālu), kas nepieciešams, lai aptvertu visas nulles matricā. Visas nulles var aptvert, izmantojot 3 līnijas:

Tā kā nepieciešamais līniju skaits ir trīs un tas ir mazāks par matricas lielumu (n = 4), mēs turpinām ar 4. darbību.

4. solis: izveidojiet papildu nulles

Tiek izvēlēts mazākais elements, kuru līnijas neaptver, kura vērtība ir 6. Šī vērtība tiek atņemta no visiem elementiem, uz kuriem neattiecas, un šī pati vērtība tiek pievienota visiem elementiem, uz kuriem attiecas divu līniju krustošanās. Rezultātā tiek iegūta šāda matrica:

Kā norādīts Ungārijas metodē, atkal jāveic trešais solis.

3. darbība (atkārtot)

Atkal tiek noteikts minimālais līniju skaits, kas vajadzīgs, lai visas matricas nullītes būtu pārklātas. Šoreiz ir vajadzīgas četras līnijas:

Tā kā nepieciešamais līniju skaits ir 4, kas vienāds ar matricas lielumu (n = 4), mums ir optimāls sadalījums starp nullēm matricā. Tāpēc algoritms apstājas.

Optimāls sadalījums

Kā norāda metode, no šīm nullēm izdarītā atlase atbilst optimālajam piešķīrumam:

Šī nulles izvēle atbilst šādam optimālam sadalījumam sākotnējā izmaksu matricā:

Tāpēc 1. darbiniekam jāveic 3. darbība, 2. darbinieka, 2. darbība, 3. darbinieka, 1. darbība un 4. darbiniekam jāveic 4. darbība. Šīs optimālās darba kopējās izmaksas ir 69 + 37 +. 11 + 23 = 140.

Atsauces

1. Ungārijas algoritms (2019). Ungāru algoritms. Iegūts no: hungarianalgorithm.com.
2. Pētījums (2019. gads). Ungāru algoritma izmantošana uzdevuma problēmu risināšanai. Paņemts no: study.com.
3. Gudrības darbi (2018). Ungāru metode uzdevuma problēmas risināšanai - vadības kvantitatīvās metodes. Paņemts no: wisdomjobs.com.
4. Geeks Geeksam (2019). Ungārijas uzdevuma problēmas algoritms. Iegūts no: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Ungārijas maksimālais atbilstības algoritms. Lieliski. Iegūts no: brilliant.org.