Мађарска метода је алгоритам који омогућава минимизирање трошкова у оптимизацијском проблему заснованом на линеарном програмирању.
Циљ мађарске методе је да пронађе минималне трошкове скупа задатака које морају извршити најпогоднији људи.
Користи линеарно програмирање (ПЛ) за извођење низа корака који се могу аутоматизовати. Дакле, алати попут статистичког софтвера Р (између осталих) имају неколико врло корисних пакета за ове проблеме оптимизације.
Порекло мађарске методе
Његов творац је био мађарски математичар (отуда и име) Харолд В. Кухн 1955. Други математичар, Јамес Мункрес, ревидирао га је 1957. Овом еволуцијом добио је и друга имена попут Мункрес-овог или Кухн-Мункрес-овог алгоритма за алокацију.
С друге стране, ова метода има преседан код два аутора, Денеса Конига и Јено Егервари, и Јевреја и Мађара. Први је развио теорију графова на којој се заснива овај алгоритам. Друга је генерализовала Конигову теорему и омогућила Куну да развије метод.
Кораци мађарске методе
Кораци које треба следити омогућавају извођење мађарске методе на једноставан начин помоћу табеле. Поред тога, ова шема коју приказујемо омогућиће нам да на глобални начин сагледамо процес који ћемо детаљно развити у последњем примеру.
- Као прелиминарне кораке, морате доделити људе (редове) низу пројеката (колоне). Поред тога, потребно је израчунати различите трошкове сваког пројекта у зависности од тога ко га изводи и са тим информацијама направити матрицу (Ц).
- У матрици (Ц) тражимо минималну вредност сваког реда. Ово одузимамо од свих елемената у реду и изводимо исту операцију са колонама. Појавиће се нова матрица (Ц`) са резултатима претходних операција.
- Даље, креирамо «графикон једнакости», који нам омогућава да одаберемо задатке и пројекте са најнижим трошковима. Оптимум би били они елементи чији је резултат био нула. Ако је тачно да не постоји елемент са нултом вредношћу додељеном више од једног реда, алгоритам се завршава.
- У супротном, мора се извршити нови задатак. Израђује се нова матрица на коју се примењује низ модификација, као што ћемо видети у примеру. Поново стварамо графикон и настављамо док не добијемо матрицу која има најмање једну нулу у сваком реду и на позицијама које се не понављају.
- Са овим информацијама већ имамо додељене људе и пројекте (нуле) који оптимизују проблем. Ако је задатак већ додељен у претходном реду, он се одбацује у следећем. Да бисмо израчунали минимални трошак збрајамо трошкове почетне матрице који се појављују на положају ових нула.
Пример мађарске методе
Погледајмо једноставан пример мађарске методе. Замислимо да имамо троје радника и они морају бити распоређени у три пројекта. У свакој ћелији креирамо почетну матрицу (Ц) и вредности трошкова. За то морате користити информације доступне у компанији. Једном када имамо све ово започињемо процес. Табела вам може помоћи.
Израчунавамо минимуме сваког реда и одузимамо их од елемената тог реда и чинимо исто са колонама (кораци 1 и 2). У резултујућој матрици (Ц`) цртамо линије на такав начин да покривају све нуле и заузврат се секу (корак 3). Видимо да постоје две линије, али највећа вредност броја редова или колона је три. Морамо наставити.
Сада бирамо најмањи од непокривених бројева, у овом примеру је два (тамноплава). Одузимамо га од претходних и додајемо онима који се налазе на месту где се линије пресецају. У нашем случају то су још две (Е3, Т1). Преостала нам је нова матрица (корак 4). Прецртамо линије и бројамо. Постоје три линије, исто као и број редова или колона. Алгоритам је завршен.
Почињемо са редом или колоном са најмање нула (Е1, Т1). Ако је задатак већ додељен, не може се поново доделити, на пример, са Е2 не можете користити прву нулу Т1, јер је овај задатак додељен Е1. Укупни трошак, по мађарској методи, биће збир трошкова оригиналне матрице (корак 1) која се налази у истом положају као и изабране нуле (корак 5).