Ungārijas metode ir algoritms, kas ļauj samazināt izmaksas optimizācijas problēmā, kuras pamatā ir lineāra programmēšana.
Ungārijas metodes mērķis ir atrast minimālās izmaksas par uzdevumu kopumu, kas jāveic vispiemērotākajiem cilvēkiem.
Tas izmanto lineāro programmēšanu (PL), lai veiktu virkni darbību, kuras var automatizēt. Tādējādi tādiem rīkiem kā statistikas programmatūra R (cita starpā) šīm optimizācijas problēmām ir vairākas ļoti noderīgas paketes.
Ungārijas metodes izcelsme
Tās radītājs bija ungāru matemātiķis (līdz ar to arī nosaukums) Harolds V. Kūns 1955. gadā. Cits matemātiķis Džeimss Munkress to pārskatīja 1957. gadā. Ar šo evolūciju tas ir saņēmis citus nosaukumus, piemēram, Munkres vai Kuhn-Munkres piešķiršanas algoritmu.
No otras puses, šai metodei ir divi autori - gan ebreji, gan ungāri - Dénes Königs un Jenő Egerváry. Pirmais izstrādāja grafu teoriju, uz kuras balstās šis algoritms. Otrais vispārināja Kēniga teorēmu un ļāva Kūnam izstrādāt metodi.
Ungārijas metodes soļi
Veicamās darbības ļauj Ungārijas metodi veikt vienkāršā veidā, izmantojot izklājlapu. Turklāt šī shēma, kuru mēs parādīsim, ļaus mums globāli redzēt procesu, kuru mēs detalizēti izstrādāsim pēdējā piemērā.
- Kā sākotnējas darbības jums jāpiešķir cilvēki (rindas) projektu virknei (kolonnas). Turklāt ir jāaprēķina katra projekta dažādās izmaksas atkarībā no tā, kas to veic, un jāveido matrica (C) ar šo informāciju.
- Matricā (C) mēs meklējam katras rindas minimālo vērtību. Mēs to atņemam no visiem rindas elementiem un veicam to pašu darbību ar kolonnām. Parādīsies jauna matrica (C`) ar iepriekšējo darbību rezultātiem.
- Tālāk mēs izveidojam «vienādojumu grafiku», kas ļauj mums izvēlēties uzdevumus un projektus ar viszemākajām izmaksām. Optimālākais būtu tie elementi, kuru rezultāts būtu nulle. Ja ir taisnība, ka nav elementa ar nulles vērtību, kas piešķirta vairāk nekā vienai rindai, algoritms beidzas.
- Pretējā gadījumā ir jāveic jauns uzdevums. Tiek izgatavota jauna matrica, kurai tiek piemērota virkne modifikāciju, kā redzēsim piemērā. Mēs atjaunojam diagrammu un turpinām, līdz mums ir matrica, kurai katrā rindā ir vismaz viena nulle un pozīcijās, kas neatkārtojas.
- Izmantojot šo informāciju, mums jau ir piešķirti cilvēki un projekti (nulles), kas optimizē problēmu. Ja uzdevums jau ir piešķirts iepriekšējā rindā, tas tiek izmests nākamajā. Lai aprēķinātu minimālās izmaksas, mēs pievienojam sākotnējās matricas izmaksas, kas parādās šo nulļu pozīcijā.
Ungārijas metodes piemērs
Apskatīsim vienkāršu ungāru metodes piemēru. Iedomāsimies, ka mums ir trīs darbinieki, un viņi ir jāpiešķir trim projektiem. Katrā šūnā mēs izveidojam sākotnējo matricu (C) un izmaksu vērtības. Tam jums jāizmanto uzņēmumā pieejamā informācija. Kad mums tas viss ir, mēs sākam procesu. Var palīdzēt izklājlapa.
Mēs aprēķinām katras rindas minimumus un atņemam tos no šīs rindas elementiem un darām to pašu ar kolonnām (1. un 2. darbība). Iegūtā matricā (C`) mēs zīmējam līnijas tā, lai tās aptvertu visas nulles un, savukārt, savstarpēji krustotos (3. solis). Mēs redzam, ka ir divas līnijas, bet rindu vai kolonnu skaita lielākā vērtība ir trīs. Mums jāturpina iet.
Tagad mēs izvēlamies mazāko no nesegtajiem skaitļiem, šajā piemērā tie ir divi (tumši zili). Mēs to atņemam no iepriekšējiem un pievienojam tiem, kas atrodas vietās, kur krustojas līnijas. Mūsu gadījumā tie ir vēl divi (E3, T1). Mums paliek jauna matrica (4. solis). Pārzīmējam līnijas un skaitām. Ir trīs rindas, tāpat kā rindu vai kolonnu skaits. Algoritms ir pabeigts.
Mēs sākam ar rindu vai kolonnu ar vismazākajām nullēm (E1, T1). Ja uzdevums jau ir piešķirts, to nevar atkārtoti piešķirt, piemēram, ar E2 nevar izmantot T1 pirmo nulli, jo šis uzdevums tika piešķirts E1. Kopējās izmaksas pēc ungāru metodes būs sākotnējās matricas (1. solis) izmaksu summa, kas atrodas tajā pašā pozīcijā kā izvēlētās nulles (5. darbība).